Chess - Programming - BitBoards

A BitBoard is comprised of a 64-bit word, which is used to store the positions of different Chess Pieces.

8 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 0 0 
6 0 0 0 0 0 0 0 0 
5 0 0 0 0 0 0 0 0 
4 0 0 0 0 0 0 0 0 
3 0 0 0 0 0 0 0 0 
2 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 
  a b c d e f g h

Every square on a Chess Board is represented by one bit in the 64-bit word.

Since there are 12 different pieces in chess, 12 BitBoards are needed to store a chess position:

whiteKing - bitboard with the position bit of the white king set to 1 (and other bits set to 0).
whiteQueens - bitboard with the position bits of all white queens set to 1 (and other bits set to 0), etc
whiteRooks
whiteBishops
whiteKnights
whitePawns
blackKing
blackQueens
blackRooks
blackBishops
blackKnights
blackPawns

Benefits of BitBoards

Bitboards offer speed advantages in two parts of the program.

First (and this is the main reason for using them) the move generator is going to be very fast.
- There are no loops to slide a piece down a diagonal, or rank/file as you will see later in the section on the move generator.
Second, bitboards offer speed improvements in the evaluation function.
- For example, we can check if the white pawn on square e4 is passed with a single bitboard operation, there is no need to loop over the squares d5, d6, d7, e5, e6, e7, f5, f6 and f7 to see if any square is occupied by black pawns.
- The Board structure will contain the 12 bitboards, together with additional variables for e.g. castling rights.

The bit-numbering convention for BitBoards

bit #0 will be the rightmost bit in the 64-bit word (least significant bit, or LSB), and
bit #63 will be the leftmost bit in the 64-bit word (most significant bit, or MSB).
Furthermore, square a1 = bit #0, h1 = bit #7, a8 = bit #56 and h8 = bit #63.

 RANKS:
   8 |       56   57   58   59   60   61   62   63  (MSB,
   7 |       48   49   50   51   52   53   54   55  left)  
   6 |       40   41   42   43   44   45   46   47  
   5 |       32   33   34   35   36   37   38   39 
   4 |       24   25   26   27   28   29   30   31  
   3 |       16   17   18   19   20   21   22   23  
   2 |        8    9   10   11   12   13   14   15
   1 | (LSB,  0    1    2    3    4    5    6    7
       right)
           -------------------------------------------
 FILES:      a     b    c    d    e    f    g    h

NOTE: If FILE and RANK are numbered from 1..8, then SQUARE (0..63) can be calculated as follows: SQUARE = 8 * RANK + FILE - 9;

Fast bitwise Operations

There are some fast bit-wise operations that we can perform on bitboards.

For instance, if we want to have a bitboard of all white pieces, then we can get this by using the bit-wise OR operator:

whitePieces = whiteKing | whiteQueens | whiteRooks | whiteBishops | whiteKnights | whitePawns;

Or all occupied squares:

occupiedSquares = whitePieces | blackPieces;

Determine what pieces are on the board

The union of two sets is superset of both.

For instance the union of all white and black pieces are the set of all occupied squares:

white pieces     |  black pieces     =  occupied squares
. . . . . . . .     1 . 1 1 1 1 1 1     1 . 1 1 1 1 1 1
. . . . . . . .     1 1 1 1 . 1 1 1     1 1 1 1 . 1 1 1
. . . . . . . .     . . 1 . . . . .     . . 1 . . . . .
. . . . . . . .     . . . . 1 . . .     . . . . 1 . . .
. . . . 1 . . .  |  . . . . . . . .  =  . . . . 1 . . .
. . . . . 1 . .     . . . . . . . .     . . . . . 1 . .
1 1 1 1 . 1 1 1     . . . . . . . .     1 1 1 1 . 1 1 1
1 1 1 1 1 1 . 1     . . . . . . . .     1 1 1 1 1 1 . 1

NOTE: Since white and black pieces are always disjoint, one may use addition here as well.

But this fails for unions of attack sets, since squares may be attacked or defended by multiple pieces of course.

Attacks

To determine opponent pieces a queen may capture:

'and' the queen-attacks bitboard with the set of opponent pieces:

queen attacks    &  opponent pieces  =  attacked pieces
. . . . . . . .     1 . . 1 1 . . 1     . . . . . . . .
. . . 1 . . 1 .     1 . 1 1 1 1 1 .     . . . 1 . . 1 .
. 1 . 1 . 1 . .     . 1 . . . . . 1     . 1 . . . . . .
. . 1 1 1 . . .     . . . . . . . .     . . . . . . . .
1 1 1 * 1 1 1 .  &  . . . * . . 1 .  =  . . . * . . 1 .
. . 1 1 1 . . .     . . . . . . . .     . . . . . . . .
. . . 1 . 1 . .     . . . . . . . .     . . . . . . . .
. . . 1 . . . .     . . . . . . . .     . . . . . . . .

Determine Empty Squares

The set of empty squares for instance is the complement-set of all occupied squares and vice versa:

~occupied squares  =   empty squares
  1 . 1 1 1 1 1 1      . 1 . . . . . .
  1 1 1 1 . 1 1 1      . . . . 1 . . .
  . . 1 . . . . .      1 1 . 1 1 1 1 1
  . . . . 1 . . .      1 1 1 1 . 1 1 1
~ . . . . 1 . . .  =   1 1 1 1 . 1 1 1
  . . . . . 1 . .      1 1 1 1 1 . 1 1
  1 1 1 1 . 1 1 1      . . . . 1 . . .
  1 1 1 1 1 1 . 1      . . . . . . 1 .

Determine Squares which are exclusively set in one of the two sets

Use XOR (Exclusive or).

1 . . . . . . 1     . . . . . . . .     1 . . . . . . 1
. 1 . . . . 1 .     . . . . . . . .     . 1 . . . . 1 .
. . 1 . . 1 . .     . . 1 1 1 1 . .     . . . 1 1 . . .
. . . 1 1 . . .     . . 1 1 1 1 . .     . . 1 . . 1 . .
. . . 1 1 . . .  ^  . . 1 1 1 1 . .  =  . . 1 . . 1 . .
. . 1 . . 1 . .     . . 1 1 1 1 . .     . . . 1 1 . . .
. 1 . . . . 1 .     . . . . . . . .     . 1 . . . . 1 .
1 . . . . . . 1     . . . . . . . .     1 . . . . . . 1

Determine Squares which are set in both BitBoards

Determine if one Bitboard is a subset of the other.

Use xor (or subtraction).

super               sub                 super &~ sub
. . . . . . . .     . . . . . . . .     . . . . . . . .
. 1 1 1 1 1 1 .     . . . . . . . .     . 1 1 1 1 1 1 .
. 1 1 1 1 1 1 .     . . 1 1 1 1 . .     . 1 . . . . 1 .
. 1 1 1 1 1 1 .  ^  . . 1 1 1 1 . .     . 1 . . . . 1 .
. 1 1 1 1 1 1 .     . . 1 1 1 1 . .  =  . 1 . . . . 1 .
. 1 1 1 1 1 1 .  -  . . 1 1 1 1 . .     . 1 . . . . 1 .
. 1 1 1 1 1 1 .     . . . . . . . .     . 1 1 1 1 1 1 .
. . . . . . . .     . . . . . . . .     . . . . . . . .

C++ Bitwise Operators

There are six bitwise operators in C++, that are used in combination with bitboards:

&	The AND operator, compares two values, and returns a value that has its bits set if, and only if, the two values being compared both have their bits set.
\|	The OR operator, compares two values, and returns a value that has its bits set if one or the other value, or both, have their bits set.
^	The XOR operator, compares two values, and returns a value that has its bits set if one or the other value has its corresponding bits set, but not both.
~	The Ones Complement, or Inversion, operator acts only on one value and inverts it, turning all ones into zeros, and all zeros into ones.
>>	The Right Shift operator, shifts the bits from the high bit (MSB) to the low bit (LSB), the number of bit positions specified.
<<	The Left Shift operator, shifts the bits from the low bit (LSB) to the high bit (MSB), the number of bit positions specified.

Frequently used bitwise operations

Bitwise set bits

Mask has all bits set that need to be set:

Result |= Mask;

Bitwise set bits

Mask has all bits cleared that need to be set:

Result |= ~Mask;

Bitwise clear bits

Mask has all bits set that need to be cleared:

Result &= ~Mask;

Bitwise clear bits

Mask has all bits cleared that need to be cleared:

Result &= Mask;

Logical test for bits set

Mask has bits set that need to be tested for all 1:

if (Test & Mask) == Mask)

NOTE:

1 = all Test bits are 1.
0 = not all Test bits are 1.

Logical test for bits set

Mask has bits cleared that need to be tested for all 1:

if ((Test & ~Mask) == ~Mask)

NOTE:

1 = all Test bits are 1.
0 = not all Test bits are 1.

Logical test for bits cleared

Mask has bits set that need to be tested for all 0:

if ((~Test & Mask) == Mask)

NOTE:

1 = all Test bits are 0.
0 = not all Test bits are 0.

Logical test for bits cleared

Mask has bits cleared that need to be tested for all 0:

if ((~Test & ~Mask) == ~Mask)

NOTE:

1 = all Test bits are 0.
0 = not all Test bits are 0.

References

http://graphics.stanford.edu/~seander/bithacks.html

Table of Contents

Chess - Programming - BitBoards

Benefits of BitBoards

The bit-numbering convention for BitBoards

Fast bitwise Operations

Determine what pieces are on the board

Attacks

Determine Empty Squares

Determine Squares which are exclusively set in one of the two sets

Determine Squares which are set in both BitBoards

C++ Bitwise Operators

Frequently used bitwise operations

Bitwise set bits

Bitwise set bits

Bitwise clear bits

Bitwise clear bits

Logical test for bits set

Logical test for bits set

Logical test for bits cleared

Logical test for bits cleared

References