Contents  Introduction  Basic Board  Representations  Bit Boards  Transposition  Tables  Generating Hash  Keys for Chess  Boards  History Tables  Pre-processing  move generation  Printable version     The Series  Getting Started  Data Structures  Move Generation  Basic Search  Advanced Search  Evaluation  Functions

Bit Boards

For many games, it is hard to imagine better representations than the simple one-square, one-slot array.  However, for chess, checkers and other games played on a 64-square board, a clever trick was developed (apparently by the KAISSA team in the Soviet Union) in the late 60's: the bit board.

KAISSA ran on a mainframe equipped with a 64-bit processor.  Now, 64 happens to be the number of squares on a chess board, so it was possible to use a single memory word to represent a yes-or-no or true-or-false predicate for the whole board.  For example, one bitboard might contain the answer to "Is there a white piece here?" for each square of the board.

Therefore, the state of a chess game could be completely represented by 12 bitboards: one each for the presence of white pawns, white rooks, black pawns, etc.  Adding two bitboards for "all white pieces" and "all black pieces" might accelerate further computations.  You might also want to hold a database of bitboards representing the squares attacked by a certain piece on a certain square, etc.; these constants come in handy at move generation time.

The main justification for bit boards is that a lot of useful operations can be performed using the processor's instruction set's 1-cycle logical operators.  For example, suppose you need to verify whether the white queen is checking the black king.  With a simple square-array representation, you would need to:

• Find the queen's position, which requires a linear search of the array and may take 64 load-test cycles.
• Examine the squares to which it is able to move, in all eight directions, until you either find the king or run out of possible moves.

This process is always time-consuming, more so when the queen happens to be located near the end of the array, and even more so when there is no check to be found, which is almost always the case!

With a bitboard representation, you would:

• Load the "white queen position" bitboard.
• Use it to index the database of bitboards representing squares attacked by queens.
• Logical-AND that bitboard with the one for "black king position".

If the result is non-zero, then the white queen is checking the black king.  Assuming that the attack bitboard database is in cache memory, the entire operation has consumed 3-4 clock cycles!

Another example: if you need to generate the moves of the white knights currently on the board, just find the attack bitboards associated with the positions occupied by the knights and AND them with the logical complement of the bitboard representing "all squares occupied by white pieces" (i.e, apply the logical NOT operator to the bitboard), because the only restriction on knights is that they can not capture their own pieces!

For a (slightly) more detailed discussion of bitboards, see the article describing the CHESS 4.5 program developed at Northwestern University, in Peter Frey's book Chess Skill in Man and Machine; there are at least two editions of this book, published in 1977 and 1981.

Note: To this day, few personal computers use true 64-bit processors, so at least some of the speed advantages associated with bitboards are lost.  Still, the technique is pervasive, and quite useful.

Next : Transposition Tables