An Introduction to BITBOARDS
by Franck ZIBI
When designing a chess playing program, the author has to find a way to store the position of the pieces on the board.
The most natural approach is to use a 64length vector. Therefore:
 MyBoardVector[ 1] will return the piece located in A1
 MyBoardVector[ 2] will return the piece located in A2
 …
 MyBoardVector[64] will return the piece located in H8
The bitboard architecture is another way to achieve the same objective.
A bitboard is a 64 bit length variable, and as you know 64 is a ‘magic number’ both in chess and in computer science.
What about using some bitboards (64 bits/bitboard) to map a
chess board (64 squares/board)?
For instance:
 the 1^{st} bit of the bitboard will refer to the first square of the board.
 the 2^{nd} bit of the bitboard will refer to the B1 square.
 …
 the 64^{th} bit (and last bit) of the bitboard will refer to the H8 square.
Now we can try to build our first bitboard: a bitboard that will represent all the white pieces in the initial position of the chessboard.
 All the bits of our bitboard associated with a square containing a white piece will be set to 1
 All the other bits will be set to 0.
0
A80
B80
C80
D80
E80
F80
G80
H80
A70
B70
C70
D70
E70
F70
G70
H70
A60
B60
C60
D60
E60
F60
G60
H60
A50
B50
C50
D50
E50
F50
G50
H50
A40
B40
C40
D40
E40
F40
G40
H40
A30
B30
C30
D30
E30
F30
G30
H31
A21
B21
C21
D21
E21
F21
G21
H21
A11
B11
C11
D11
E11
F11
G11
H1
So our bitboard will look like:
In
Binary (base 2) 
00000000 00000000 00000000 00000000 00000000 00000000 11111111 11111111 
In Hexadecimal 
00 00 00 00 00 00 FF FF 
In decimal 
65,535 
In Pseudocode 
BITBOARD MyFirstBitBoard := 65535; 
A bitboard that will be associated with all the knights (both white and black) in the initial position of the chess board will be:
In
Binary (base 2) 
01000010 00000000 00000000 00000000 00000000 00000000 00000000 01000010 
In Hexadecimal 
42 00 00 00 00 00 00 42 
In decimal 
4,755,801,206,503,243,842 
In Pseudocode 
BITBOARD MySecondBitBoard := 4755801206503243842; 
II  Bitwise operators  the magical part of Bitboards
Now comes the real advantage of bitboards.
How if you are
looking to built a third bitboard with all the *white* knights in the initial
position ?
The answer is :
MyThirdBitBoard := MyFirstBitBoard BitwiseAND MySecondBitBoard;
A BitwiseAND (logical AND) between our first
two bitboards (the one with all the white pieces and the one with all the
knights) is enough!
The bitwiseAND operator compares each bit of
MyFirstBitBoard to the corresponding bit of MySecondBitBoard.
If both bits
are 1, the corresponding result bit in MyThirdBitBoard is set to
1.
Otherwise, the corresponding result bit is set to 0.
So it uses the
following rule:
BitwiseAND 
0 
1 
0 
0 
0 
1 
0 
1 
MyFirstBitBoard  00000000 00000000 00000000 00000000 00000000 00000000 11111111 11111111 
BitwiseAND  
MySecondBitBoard  01000010 00000000 00000000 00000000 00000000 00000000 00000000 01000010 
Equals  
MyThirdBitBoard  00000000 00000000 00000000 00000000 00000000 00000000 00000000 01000010 
The three other useful bitwise operators are:


 

III  An example from ''real life''
ZChess 1.2 needs to compute a bitboard called 'WhitePiecesEnPrise' for all white pieces that are attacked but not defended. It can use the following 3 bitboards:
WhitePieces: all the white pieces on the board AttackedByWhite: all the squares attacked by the white side AttackedByBlack: all the squares attacked by the black side
1^{st} Step
Compute all the white pieces attacked by Black:
BitBoardStep1 := WhitePieces BitwiseAND AttackedByBlack ;
2^{nd} Step
Compute all squares that are not attacked by white:
BitBoardStep2 := BitwiseComplement (AttackedByWhite) ;
3^{rd} Step
Compute the Bitboard of white pieces that are both (BitwiseAND) attacked by black (BitBoardStep1) and not attacked by white (BitBoardStep2)
WhitePiecesEnPrise := BitBoardStep1 BitwiseAND BitBoardStep2 ;
So only three (2 AND and one Complement) bitwise operations are needed!
IV  32bit processors: the dark side of Bitboards
Most of today's computers use a 32bit architecture (Pentium,
Athlon,Cyrix...).
That means that they cannot efficiently manage 64bit
instructions.
Even if the latest compilers support 64bit variables, (Delphi >= 4, Visual C++, gcc , Watcom, etc...), they will have to split the variable into two 32bit instructions before sending them to the processor, and to rearrange them later: that's a major drawback in performance.
The 64bit computers that we can find on the market today are not too expensive (especially the Dec Alpha 21164: <= 3000 USD), but they are not nearly as common as the 32bit computers. We have to wait at least 2 more years to see the 64bit architecture as a standard.
V  ComputerChess Related Links
How DarkThought Plays Chess :  http://wwwipd.ira.uka.de/Tichy/DarkThought/node6.html 
The source code of Crafty:  ftp://ftp.cis.uab.edu/pub/hyatt/v16/crafty16.15.zip 
Pharaon Home Page:  http://www.fzibi.com/pharaon.htm 