Writing a bitboard chess engine
March 15, 2009
I've shifted my focus a little and am currently writing a bitboard based chess engine. Bitboard based engines aren't quite as straight forward as array based chess engines, but they offer benefits in both move generation and board evaluation. The idea is to represent the board in a series of 64 bit integers, as in the following sample board structure:
#define BITBOARD unsigned long long
typedef struct {
/* colours */
BITBOARD white_pieces;
BITBOARD black_pieces;
/* white pieces */
BITBOARD white_pawns;
BITBOARD white_knights;
BITBOARD white_bishops;
BITBOARD white_rooks;
BITBOARD white_queens;
BITBOARD white_kings;
/* black pieces */
BITBOARD black_pawns;
BITBOARD black_knights;
BITBOARD black_bishops;
BITBOARD black_rooks;
BITBOARD black_queens;
BITBOARD black_kings;
} BOARD;
The nice thing about bitboards is that one has access to a multitude of information through simple (and fast!) bitwise operations (AND, OR, NOT, XOR and shifts). Bitboards have a really high information density, and are easily manipulated on 64 bit machines. In fiasco, I'm using a little endian bitboard representation (that is, A1 is the 0th bit, or 2^0, A7 is the 7th bit or 2^7, B1 is the 8th bit or 2^8 and H8 is the 63rd bit or 2^63).
A sample default board representation might be:
/* colours */
BITBOARD white_pieces = 0xFFFFLLU;
BITBOARD black_pieces = 0xFFFF000000000000LLU;
/* white pieces */
BITBOARD white_pawns = 0xFF00LLU;
BITBOARD white_knights = 0x42LLU;
BITBOARD white_bishops = 0x24LLU;
BITBOARD white_rooks = 0x81LLU;
BITBOARD white_queens = 0x8LLU;
BITBOARD white_kings = 0x10LLU;
/* black pieces */
BITBOARD black_pawns = 0xFF000000000000LLU;
BITBOARD black_knights = 0x4200000000000000LLU;
BITBOARD black_bishops = 0x2400000000000000LLU;
BITBOARD black_rooks = 0x8100000000000000LLU;
BITBOARD black_queens = 0x800000000000000LLU;
BITBOARD black_kings = 0x1000000000000000LLU;
Move generation of knights and kings are trivial with bitboards (well they're simple with arrays too, but still faster here). One simply has to precompute an array of possible knight or king moves from each square, and do a simple array look up to find possible move locations. For example:
BITBOARD knight_moves[64] = {
0x20400LLU, 0x50800LLU, 0xA1100LLU, 0x142200LLU,
0x284400LLU, 0x508800LLU, 0xA01000LLU, 0x402000LLU,
... };
So for example, if I wanted to find the moves for a piece at A1 (which is the 0th bit if you recall), I would look up knight_moves[0], which is 0x20400LLU in base-16. Translated to binary, this is 10 00000100 00000000, meaning the knight at A1 can access the pieces at C2 and B3.
Right now I'm working on implementing rotated bitboard move generation, which allow me to generate moves of sliding pieces in a loop-less (bitwise) fashion. Dr. Robert Hyatt has a great paper on the subject, which is a must-read for any potential bitboard based chess engine author. Most of the top engines today are bitboard based, such as Rybka, Crafty and Glaurung, and I hope this approach proves beneficial in Fiasco ;).