Home Previous Bottom Next

Writing a chess program in 99 steps

07  Internal representation of the chess board - bitboards

My implementation of bitboards is based on articles from Robert Hyatt.   The concept is quite simple: a 64-bit word is used to store the positions of e.g. all black pawns, or all white rooks. Every square is represented by one bit in the 64-bit word. And since there are 12 different pieces in chess, we need 12 bitboards to store a chess position:

  1. whiteKing bitboard with the position bit of the white king set to 1 (and other bits set to 0).
  2. whiteQueens bitboard with the position bits of all white queens set to 1 (and other bits set to 0), etc
  3. whiteRooks
  4. whiteBishops
  5. whiteKnights
  6. whitePawns
  7. blackKing
  8. blackQueens
  9. blackRooks
  10. blackBishops
  11. blackKnights
  12. blackPawns

We will also need to introduce a bit-numbering convention for our 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, see figure below:    

 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   

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;

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.

Bitwise setting & testing operations

Following is an overview of frequently used bitwise setting & testing 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)
  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)
  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)
  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)
  1 = all Test bits are 0
  0 = not all Test bits are 0

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.

Some variables are going to be computed incrementally. "Incremental updating" means that a variable is updated during makeMove and unmakeMove.  For instance, int Material holds the total material balance on the board (pawn = 100, knight = 300, etc, using positive numbers for white and negative numbers for black).  If a piece is captured or promoted, Material will be updated accordingly. This information can be readily used in the evaluation function. Incrementally updating the material balance in makeMove may be advantageous in case we want to know the material balance while traversing down the search tree, it's always kept up to date without having to do a full evaluation of the position. Another convenient array to introduce is int square[64].  This array will keep track of the contents of each square, and is useful if we want to know e.g. what piece is on square e2.

Now we have a data structure that allows us to display the chess board, set up the board, and read a position from a FEN string, so this is all I am going to explain about bitboards; There will be more information on working with bitboards later.

step 8: board.h
#ifndef WINGLET_BOARD_H_
#define WINGLET_BOARD_H_
 
#include "defines.h"
 
struct Board
{
       BitMap whiteKing, whiteQueens, whiteRooks, whiteBishops, whiteKnights, whitePawns;
       BitMap blackKing, blackQueens, blackRooks, blackBishops, blackKnights, blackPawns;
       BitMap whitePieces, blackPieces, occupiedSquares;
 
       unsigned char nextMove;        // WHITE_MOVE or BLACK_MOVE
       unsigned char castleWhite;     // White's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2
       unsigned char castleBlack;     // Black's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2
       int epSquare;                  // En-passant target square after double pawn move
       int fiftyMove;                 // Moves since the last pawn move or capture
 
       // additional variables:
       int Material;                  // incrementally updated, total material on board,
                                      // in centipawns, from white’s side of view
       int square[64];                // incrementally updated, this array is usefull if we want to
                                      // probe what kind of piece is on a particular square.
       BOOLTYPE viewRotated;          // only used for displaying the board. TRUE or FALSE.
 
       void init();
       void initFromSquares(int input[64], unsigned char next, int fiftyM, int castleW, int castleB, int epSq);
       void initFromFen(char fen[], char fencolor[], char fencastling[], char fenenpassant[], int fenhalfmoveclock, int fenfullmovenumber);
       void display();
};
 
 
#endif

 

Home Previous Top Next

last update: Saturday 04 June 2011