Bitboard
|
|
A bitboard is a data structure commonly used in computer systems that play chess.
The bitboard appears to have been originally developed by the Kaissa team in the Soviet Union in the late 1960s. A bitboard is a 64-bit sequence of bits (0 or 1), which indicates the absence or presence (false or true) of some state about each place on the board.
A board position can then be represented using a series of bitboards. For example, a series of bitboards for each piece type or pawn, for each side, can represent the board position. Typically, to speed certain tasks, additional bitboards are also used to identify where any piece is, to identify blocking pieces.
Query results can also be represented using bitboards. For example, the query "what are the squares between X and Y?" can be represented as a bitboard. These query results are generally precalculated, so that a program can simply retrieve a query result with one memory load.
The advantage of the bitboard representation is that it takes advantage of the bit operations available on nearly all computer systems. Nearly all computer systems have bitwise and, bitwise or, bitwise not, and bitwise exclusive or operations that operate rapidly. On 64-bit or more computers, 64-bit operations can occur in one instruction. 32-bit computers generally require more, and thus are not quite as efficient in implementing bitboards as 64-bit processors. Some computers have additional instructions, such as finding the "first" bit, that make bitboard operations even more efficient.
"Rotated" bitboards are usually used in programs that use bitboards. These bitboards rotate the bitboard positions by 90 degrees, 45 degrees, and/or 315 degrees. These rotated bitboards make certain operations more efficient. A typical bitboard will have one byte per rank of the chess board. With this bitboard it's easy to determine rook attacks across a rank, using a table indexed by the occupied square and the occupied positions in the rank (because rook attacks stop at the first occupied square). By rotating the bitboard 90 degrees, rook attacks across a file can be examined the same way. Adding bitboards roated 45 degrees and 315 degrees produces bitboards where the diagonals are easy to examine. The queen can be examined by combining rook and bishop attacks. Rotated bitboards appear to have been developed separately and (essentially) simultaneously by the developers of the DarkThought and Crafty programs.
Bitboard representations can take more space than some other representions, and thus are not as effective for systems with small amounts of memory (e.g., 64K or less).
Many other games besides chess benefit from bitboards. In Connect Four, they allow for very efficient testing for 4 consecutive discs, by just two shift+and operations per direction.
External links
- Heinz, Ernst A. How DarkThought plays chess. ICCA Journal, Vol. 20(3), pp. 166-176, Sept. 1997) (http://supertech.lcs.mit.edu/~heinz/dt/node2.html)
- Laramee, Francois-Dominic. Chess Programming Part 2: Data Structures. (http://www.gamedev.net/reference/programming/features/chess2/page3.asp)
- Verhelst, Paul. Chess Board Representations. (http://www.xs4all.nl/~verhelst/chess/representations.html)