Archive‎ > ‎Fall 2009‎ > ‎Course Project‎ > ‎Buddy Suite‎ > ‎Milestone 3: Chess Game Logic‎ > ‎

BitBoards

This is an alternative chess board representation. The information contained in this page has been copied from here. Be careful, the information might not be correct or complete. This page only gives you an overview of this type of chess board representation.

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 1st bit of the bitboard will refer to the first square of the board.
  • the 2nd bit of the bitboard will refer to the B1 square.
  • the 64th 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:

In Binary
(base 2)

00000000 00000000 00000000 00000000 00000000 00000000 11111111 11111111
The first sixteen bits (the squares from A1 to H2) are set to 1.

In Hexadecimal
(base 16)

00 00 00 00 00 00 FF FF

In decimal
(base 10)

65,535

In Pseudo-code

 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
The squares B1, G1, B8, G8 are set to 1.

In Hexadecimal
(base 16)

42 00 00 00 00 00 00 42

In decimal
(base 10)

4,755,801,206,503,243,842

In Pseudo-code

 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 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:

Bitwise-AND

0

1

0

0

0

1

0

1

 

MyFirstBitBoard 00000000 00000000 00000000 00000000 00000000 00000000 11111111 11111111

Bitwise-AND

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:

Bitwise-OR

0

1

0

0

1

1

1

1

 

    

Bitwise-XOR

0

1

0

0

1

1

1

0

 

Bitwise-Complement

This operator receives one BITBOARD as INPUT and will change:
  • all its bit set to 1 to 0
  • all its bit set to 0 to 1.

So if it receives MyFirstBitBoard as INPUT:
00000000 00000000 00000000 00000000 00000000 00000000 11111111 11111111

it will return the following Bitboard:
11111111 11111111 11111111 11111111 11111111 11111111 00000000 00000000



 

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

    1st Step

    Compute all the white pieces attacked by Black:

                                        BitBoardStep1 := WhitePieces Bitwise-AND AttackedByBlack ;

    2nd Step

    Compute all squares that are not attacked by white:

                                        BitBoardStep2 := Bitwise-Complement (AttackedByWhite) ;

    3rd 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!

    Comments