Writing a chess program in 99 steps

Our move generator is going to generate pseudo-legal moves, this means that there will be no test against leaving our own king in check.  This test will be carried out when we actually make the move.  Most generated moves will never made (due to cut-offs), so it's faster to do legality testing when we actually make the move, rather than doing these tests in the move generator. 

Move generation for Knights

Bitboard move generation for knights is the easiest to explain, so we'll start with that.

The basic idea for bitboard move generation is that all moves are pre-computed and stored in a lookup table, and the move generator simply looks up the moves in this table. I'll explain the code for white knights step by step, it's only 17 lines (complete code will follow):

01 targetBitmap = ~board.whitePieces;
02 move.setPiec(WHITE_KNIGHT);

03 tempPiece = board.whiteKnights;

04 while (tempPiece)

05 {

06   from = firstOne(tempPiece);

07   tempMove = KNIGHT_ATTACKS[from] & targetBitmap;

08   while (tempMove)

09   {

10     to = firstOne(tempMove);

11     move.setTosq(to);

12     move.setCapt(board.square[to]);

13     moveBuffer[moveBufLen++].moveInt = move.moveInt;

14     tempMove ^= BITSET[to];

15   }

16   tempPiece ^= BITSET[from];

17 }

line 01: targetBitmap is a bitboard with all possible target fields, basically all fields except the ones that are occupied by white pieces (because we cannot capture our own piece).
line 02: we already know what piece is going to move, so store the Piec bitfield in the move (it is a white knight).
line 03: tempPiece is a local bitboard, it holds all white knights. We're going to loop over all white knights and generate all white knight moves.
line 04: start of the loop over all white knights (see also line 16). If there is no white knight left, then we're ready.
line 06: here we detect the from bitfield of the current white knight (using firstOne).
line 07: this is the essence of bitboard move generation: we do a bitwise AND of the target bitboard with the attack bitboard that belongs to the piece/from-field. This attack bitboard is a pre-computed lookup table.

An example of a 'piece/from attack bitboard': for a white knight (piece) on e4 (from), the attack bitboard KNIGHT_ATTACKS[E4] looks like this:

KNIGHT_ATTACKS[E4] bitboard ('x' and '.' are zeroes):

. . . . . . . .
. . . . . . . .
. . . 1 . 1 . .
. . 1 . . . 1 .
. . . . x . . .
. . 1 . . . 1 .
. . . 1 . 1 . .
. . . . . . . .
 

There are 64 KNIGHT_ATTACKS bitboards, one for each from-field. These are just 64 pre-computed lookup bitboards for knight moves. After AND-ing the attack bitboard with our targetBitmap, we end up with all target squares for a white knight on e4.  So all the moves for a knight on e4 are generated in one go ('bit-parallel', if you like). We don't need a loop to calculate the target squares, because they are already pre-computed and stored in the attack bitboards. This technique of move generation is one of the main advantages of using bitboards.

line 08: this is a loop over all the target fields that we found, every target field represents a different knight move. See also line 14.
              If there is no target field left (tempMove = 0), then we're ready.
line 10: detect the current target field (again using firstOne).
lines 11 and line 12: store the tosq and capt bitfields of the move.
           Now you'll understand why we introduced the square array in the Board struct.
           This is a very convenient way of looking up if we captured an opponent's piece, or moved the knight to an empty field.
           If we only had bitboards to represent the position, this detection would be much more expensive (requiring a loop over all 6 bitboards of black pieces).
line 13: copy the move into the moveBuffer, and increment moveBuflen.
line 14: remove the current target square from tempMove, and go back to line 08 for the next move.
line 16: remove the current white knight from tempPiece, and go back to line 04 for the next white knight.
 

In summary, this position shows the move generation for the white knight on c3, with the 3 relevant bitboards:

Relevant move generation bitboards for the white knight on c3:

targetBitmap = ~whitePieces	KNIGHT_ATTACKS[c3] (simple table lookup)	knight moves: KNIGHT_ATTACKS[c3] & targetBitmap
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . 1 1 1 1 1 1 1 1 1 1 1 1 1 . 1 1 1 1 1 . . 1 1 . 1 . 1 . 1 1 1 . . 1 . 1 . . . 1 . 1	. . . . . . . . . . . . . . . . . . . . . . . . . 1 . 1 . . . . 1 . . . 1 . . . . . . . . . . . 1 . . . 1 . . . . 1 . 1 . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . 1 . 1 . . . . 1 . . . 1 . . . . . . . . . . . 1 . . . 1 . . . . 1 . . . . . .

Move generation for the kings is very similar to this, we first generate the target bitboard, then 'AND' this with the king attack bitboard, which simply has all 8 bits around the king square set. Castling is dealt with separately, because we have to check if the side to move still has the appropriate castling rights (as stored in the board structure), and also if the fields between king and rook are empty.  For instance, for white's king-side castling, we test if squares f1 and g1 are free. This is easy using bitboards, and the test looks as follows: 

if (!(maskF1G1 & ~occupiedSquares))

Pawn moves are also generated this way, but need more work. Normal moves (non-captures) and captures have separate attack bitboards and need different conditions regarding occupancy of the target fields. En-passant captures also need to be dealt with separately, because these are captures with an empty target field. The target field for en-passant moves is stored in the board structure. If a pawn reaches the 8th or 1st rank, we have to store the 4 possible pawn promotions (to knight, bishop, rook and queen) as separate moves. Finally, white and black pawns cannot share the same attack bitboards, because they move in different directions. Many differences if compared with knight moves, but the basic ideas are the same.

last update: Thursday 23 June 2011