Introduction to Chess Board Representation
(Up to Chess AI)
Get Printable Version

One of the deciding factors in the structure of a board game program is the representation of the board. In Chess AI, the representation of the board has differed quite a lot from program to program, and over time new systems have been invented.

The first system, and the one that may be thought of as the simplest in concept, is just an 8 x 8 matrix that can hold one value per square: 0 if there the square is empty, 1 if there is a white pawn, 2 if there is a white knight, -1 if there is a black pawn, etc.

This concept is really quite easy, because it just requires a matrix and some constants. However, it can become difficult to compute the possible moves on the board, because the computer must check the bounds and the locations of the pieces over and over. So, the program will cycle through the board perhaps 20-30 times per turn.

Another representation method tries to help the computation of moves by combining the normal move generator and the bounds checking mechanism. The hardest moves to compute are those of the knight, for it can leap over and around other pieces, and the moves are not in a straight line or diagonal like all of the other pieces. Also, the knight can jump far outside the board, and it is difficult to compute an illegal move for the knight.

So, this new system proposes to have the board represented not on an 8 x 8 matrix as previously done, but in a 12 x 12 matrix. The 8 x 8 matrix of the board is then centered with a 2 row border around it. This ensures that all knight moves lie within the matrix, no matter where the knight starts from. Next, the program treats the 2 row border as "filled" (that is, occupied by unmoveable, undesignated pieces) and thus, the moves into the border by any piece would be illegal. This method tries to integrate the move generator and the bounds checker by creating a raised "rim" around the board, ensuring that any move trying to get out will be blocked by the "rim."

By far one of the most innovative representations is the bitboard. Say you have a 64-bit integer. Now, that's interesting...there are also 64 squares on a chess board...quite a coincidence. Some programmers also recognized this coincidence, and they quickly caught on to how valuable this relationship might be.

A 64-bit integer can be processed by a 64-bit CPU quite easily and quickly, so programmers reasoned that if the chess board could be represented on a 64-bit integer, the CPU would process the application faster and more easily.

Thus, the bitboard -- as it is known -- was born. Each bitboard can only have values of true and false (1's and 0's), so you would have multiple bitboards, and each bitboard would keep track of one aspect of the board position. For instance, one bitboard could keep track of all empty squares, another could keep track of all White rooks, another for all White pawns, another for all Black bishops, and so on. To access one square of a bitboard required only a few bit-operations, which languages like C handled well. The C++ code for accessing a square of the bitboard would look like this:

bool getSquare(bitBoard bb, int squareNum)
{
  // Checks to see if the bitboard "bb" has a value of
  // true at the bit "squareNum" bits from the right.
  return (bb & (1 << squareNum));
}

This representation was overwhelmingly successful, and many of the top chess computers of today use this representation scheme because it optimizes the advantage of the 64-bit processor.

Bitboards are also quite handy for move generation. For instance, let's say you have all of the possible moves for Black's knights computed and recorded on a bitboard. Then, to decide which moves are blocked by Black's own pieces, you take a bitboard of all of Black's pieces, take the complement (the NOT operator) and then AND it to your knights' moves bitboard. The resulting bitboard contains all of the possible moves of Black's knights. Although it takes a bit of work, this method can be applied in similar ways to generate the moves of other pieces as well.

The main reason to use the bitboard over other representations is speed, but there are tradeoffs. Using the bitboard in an quick manner is complicated, and it can take up a lot of space (you have to have many different bitboards to store all the information you need, and it is often quite useful to have many extra kinds of bitboards to speed up certain operations, such as bitboards to record all of the different places the black king could move). So, many programs use one of the previously described representation methods, which are simpler to describe and implement. In the same way as other algorithms, the use of efficient board representations is a tradeoff between complexity, speed, and space requirements.