Representing the Board State
Before commencing with an algorithm, we need to settle on our data structures - in particular, how do we represent the state of the chess board? An obvious method, particularly if you’re an OOP fiend, would be to use an array of Piece objects, with each piece type (knight, bishop, etc.) a class inheriting from Piece. If that’s what you thought of, discard it immediately! For extremely time-sensitive applications, you’ll find that these abstractions aren’t so zero-cost after all, and that working as close to the metal as possible is an advantage that you should seize with reckless abandon.
In particular, did you notice something familiar about the number of squares, 64? Yep, the largest integer type is stored in 64 bits, and can be efficiently manipulated by modern 64-bit processors. That’s why the fundamental object in fast chess engines is the bitboard. It’s a 64-bit integer with each set bit representing occupancy in the corresponding square. For instance, the integer 16 when written in binary representation is 1000, and 129 is 1000001. To see how this corresponds to a chess board, pad the number with 0s at the front, then put the 8 lowest bits from left to right in the lowermost row, the next 8 lowest bits in the row above it, and so on. Here’s what that looks like for the two examples I gave you:
0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 | 1 0 0 0 0 0 0 1
16 129
These bitboards respectively represent the starting position of the white queen, and the white rooks! So the state of a board can be represented by 12 bitboards (2 colors $\times$ 6 piece types), which we update as the players make moves.
The question is why does this provide a speedup? It’s because all the generation and verification of legal moves in a position, in accordance with the complex rules of chess, can be rapidly executed using the bitwise operators: AND, OR, XOR and bitshifts. OK, so how is that beneficial? The best way to find out is how it overcomes the downsides of our original idea: an array of Piece objects.
Suppose we want to measure the amount of area controlled by our pawns, as a rough measure of piece mobility during the evaluation stage. In the Piece-Array paradigm, this would involve looping over each square on the board, checking whether it’s a pawn, then finding the squares to the north-left and north-right (provided of course they don’t fall of the board). If this sounds tedious, that’s because it is.
Au contraire, the bitboard technique is incredibly fast. Using a dot for zero, suppose we have a white pawn bitboard like so:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . 1 1 . . .
. . 1 . . . . .
. . . . . 1 . 1
1 1 . . . . . .
. . . . . . . .
If we ignore the A-file and shift the bitboard 7 bits to the right, we get
. . . . . . . .
. . . . . . . .
. . 1 1 . . . .
. 1 . . . . . .
. . . . 1 . 1 .
1 . . . . . . .
. . . . . . . .
. . . . . . . .
These are the squares attacked by pawns in the north-west direction! Moreover, we can ignore the H-file and shift 9 bits to the right, to get
. . . . . . . .
. . . . . . . .
. . . . 1 1 . .
. . . 1 . . . .
. . . . . . 1 .
. 1 1 . . . . .
. . . . . . . .
. . . . . . . .
If we OR these together, we get the bitboard of all squares attacked by all our pawns. To find the area covered, we have to count the number of 1s, i.e. perform a popcount, for which extremely fast dark magic routines like “De Bruijn sequences” exist. And we’re done. Don’t lose sight of the fact that these bitboards are just numbers! So this entire function would be coded by something like:
// get the white pawn bitboard
Bitboard pb = board.bitboards[WHITE + PAWN]
// (no A-file for NW attacks ) (no H-file for NE attacks)
int area_attacked = popcount( ((pb & 18374403900871474942) << 7) | ((pb & 9187201950435737471) << 9) )
Of course, these numbers would be categorised into lookup tables rather than hardcoded. What’s more, each bitwise operation is even cheaper than an addition. This creates the speedup we were promised, especially since bitboard methods find use in all three stages of a chess engine.
Bitboards do have a major downside though. With our new data model, it becomes expensive to query which piece occupies a given square. To counter this we use the best of both worlds, by storing both an array of bitboards, and an 64-array of pieces, often called a mailbox. The bitboard array is indexed by piece type, while the mailbox is indexed by board square, and we have to update both while making a move (this duplication is practically trivial).
This forms the core of the board class, although as we will see later it will be useful to store additional data for
- complying with e.g. the 50-move rule or threefold repetition
- storing special bitboards computerd during the move generation phase for reuse in the later phases
Representing Chess Moves
Apart from the board, it is integral to have an efficient representation of chess moves - selecting the best move in a position is, after all, the objective of a chess engine. Fundamentally, a move is a pair of start and end squares: we don’t even need the piece being moved since this can be inferred form the board data. Let’s try and store this in 16 bits. A square is represented by 6 bits ($2^6=64$), so with uint16_t move = (from_square << 6) | to_square, we still have 4 bits left over, which we’ll call “flags”.
Flags contain the remaining info necessary to specify “special” moves. These include captures, pawn promotions, double pawn push, castling and en passant. As luck would have it, there are 16 possible combinations which fit snugly in the top 4 bits. While performing a move on a board, these flags need to be queried since they might make updates to the board state (e.g. you can only castle once).
Flags have a secondary purpose in the search phase. Certain types of moves, such as promotion captures, are likelier to be overwhelmingly better than other moves in the position. So before searching through the game tree, we can sort the moves heuristically so that if we chance upon a winning move earlier on, we save time by avoiding the rest of the branches.
And that’s all, on to move generation! The posts are probably going to get a lot longer from here.