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 64-length 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.

I - Our First Bitboard

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 A8	0 B8	0 C8	0 D8	0 E8	0 F8	0 G8	0 H8
0 A7	0 B7	0 C7	0 D7	0 E7	0 F7	0 G7	0 H7
0 A6	0 B6	0 C6	0 D6	0 E6	0 F6	0 G6	0 H6
0 A5	0 B5	0 C5	0 D5	0 E5	0 F5	0 G5	0 H5
0 A4	0 B4	0 C4	0 D4	0 E4	0 F4	0 G4	0 H4
0 A3	0 B3	0 C3	0 D3	0 E3	0 F3	0 G3	0 H3
1 A2	1 B2	1 C2	1 D2	1 E2	1 F2	1 G2	1 H2
1 A1	1 B1	1 C1	1 D1	1 E1	1 F1	1 G1	1 H1

So our bitboard will look like:

A bitboard that will be associated with all the knights (both white and black) in the initial position of the chess board will be:

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 Bitwise-AND MySecondBitBoard;

A Bitwise-AND (logical AND) between our first two bitboards (the one with all the white pieces and the one with all the knights) is enough!
The bitwise-AND 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:

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 Bitwise-AND AttackedByBlack ;

2^nd Step

Compute all squares that are not attacked by white:

                                    BitBoardStep2 := Bitwise-Complement (AttackedByWhite) ;

3^rd Step

Compute the Bitboard of white pieces that are both (Bitwise-AND) attacked by black (BitBoardStep1) and not attacked by white (BitBoardStep2)

                                    WhitePiecesEnPrise := BitBoardStep1 Bitwise-AND BitBoardStep2 ;

So only three (2 AND and one Complement) bitwise operations are needed!

IV - 32-bit processors: the dark side of Bitboards

Most of today's computers use a 32-bit architecture (Pentium, Athlon,Cyrix...).
That means that they cannot efficiently manage 64-bit instructions.

Even if the latest compilers support 64-bit variables, (Delphi >= 4, Visual C++, gcc , Watcom, etc...), they will have to split the variable into two 32-bit instructions before sending them to the processor, and to rearrange them later: that's a major drawback in performance.

The 64-bit 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 32-bit computers. We have to wait at least 2 more years to see the 64-bit architecture as a standard.

V - Computer-Chess Related Links