Bitboards,
also called bitsets or bitmaps, are among other things used to represent the board inside a chess program in a piece centric manner. Bitboards, are in essence, finite sets of up to 64elements - all the squares of a chessboard, one bit per square. Other board games with greater board sizes may be use set-wise representations as well [1], but classical chess has the advantage that one 64-bit word or register covers the whole board. Even more bitboard friendly is Checkers with 32-bit bitboards and less piece-types than chess [2][3] .
To represent the board we typically need one bitboard for each piece-type and color - likely encapsulated inside a class or structure, or as an array of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position.
Of course bitboards are not only about the existence of pieces - it is a general purpose, set-wise data-structure fitting in one 64-bit register. For example, a bitboard can represent things like attack- and defend sets, move-target sets and so on.
To be aware of their scalar 64-bit origin, we use so far a type defined unsigned integer U64 in our C or C++ source snippets, the scalar 64-bit long in Java. Feel free to define a distinct type or wrap U64 into classes for better abstraction and type-safety during compile time. The macro C64 will append a suffix to 64-bit constants as required by some compilers:
typedef unsigned __int64 U64; // for the old microsoft compilers
typedef unsigned long long U64; // supported by MSC 13.00+ and C99
#define C64(constantU64) constantU64##ULL
The use of bitboards has spawned numerous discussions about their costs and benefits. The major points to consider are:
Bitboards can have a high information density.
Single populated or even empty Bitboards have a low information density.
Bitboards are weak in answering questions like what piece if any resides on square x. One reason to keep a redundant mailbox board representation with some additional update costs during make/unmake.
Bitboards can operate on all squares in parallel using bitwise instructions. This is one of the main arguments used by proponents of bitboards, because it allows for a flexibility in evaluation.
Bitboards are rather handicapped on 32 bit processors, as each bitwise computation must be split into two or more instructions [13] . As most modern processors are now 64 bit, this point is somewhat diminished [14] .
Bitboards often rely on bit-twiddling and various optimization tricks and special instructions for certain hardware architectures, such as bitscan and population count. Optimal code requires machine dependent header-files in C/C++. Portable code is likely not optimal for all processors.
Some operations on bitboards are less general, f.i. shifts. This requires additional code overhead.
also called bitsets or bitmaps, are among other things used to represent the board inside a chess program in a piece centric manner. Bitboards, are in essence, finite sets of up to 64 elements - all the squares of a chessboard, one bit per square. Other board games with greater board sizes may be use set-wise representations as well [1], but classical chess has the advantage that one 64-bit word or register covers the whole board. Even more bitboard friendly is Checkers with 32-bit bitboards and less piece-types than chess [2] [3] .
Table of Contents
The Board of Sets
To represent the board we typically need one bitboard for each piece-type and color - likely encapsulated inside a class or structure, or as an array of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position.Bitboard Basics
Of course bitboards are not only about the existence of pieces - it is a general purpose, set-wise data-structure fitting in one 64-bit register. For example, a bitboard can represent things like attack- and defend sets, move-target sets and so on.General Bitboard Techniques
The fundamental bitboard basics.Pattern and Attacks
This is basically about chess, how to calculate attack-sets and various pattern for evaluation and move generation purposes.Move Generation Issues
Bitboard aspects on move generation and static exchange evaluation (SEE).Miscellaneous
Defining Bitboards
To be aware of their scalar 64-bit origin, we use so far a type defined unsigned integer U64 in our C or C++ source snippets, the scalar 64-bit long in Java. Feel free to define a distinct type or wrap U64 into classes for better abstraction and type-safety during compile time. The macro C64 will append a suffix to 64-bit constants as required by some compilers:Bitboard-History
The general approach of bitsets was proposed by Mikhail R. Shura-Bura in 1952 [5] [6]. The bitboard method for holding a board game appears to have been invented also in 1952 by Christopher Strachey using White, Black and King bitboards in his checkers program for the Ferranti Mark 1 [7], and in the mid 1950's by Arthur Samuel in his checkers program as well. In computer chess, bitboards were first described by Georgy Adelson-Velsky et al. in 1967 [8] , reprinted 1970 [9] . Bitboards were used in Kaissa and in Chess. The invention and publication of Rotated Bitboards by Robert Hyatt [10] and Peter Gillgasch with Ernst A. Heinz in the 90s was another milestone in the history of bitboards. Steffan Westcott's innovations, too expensive on 32-bit x86 processors, should be revisited with x86-64 and SIMD instructions in mind. With the advent of fast 64-bit multiplication along with faster memory, Magic Bitboards as proposed by Lasse Hansen [11] and refined by Pradu Kannan [12] have surpassed Rotated.Analysis
The use of bitboards has spawned numerous discussions about their costs and benefits. The major points to consider are:Publications
1970 ...
1980 ...
1990 ...
2000 ...
2010 ...
Forum Posts
1994
1995 ...
2000 ...
2005 ...
2010 ...
2015 ...
Viewer & Calculator
External Links
References
Up one level