This is an old revision of the document!
Table of Contents
Chess - Programming - BitBoards
A BitBoard is comprised of a 64-bit word, which is used to store the positions of different Chess Pieces.
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
The bit-numbering convention for the 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;
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;
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.