to Chess Board Representation
(Up to Chess
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,
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)
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