Checker Bitboards Tutorial

by Jonathan Kreuzer


Links on this site

Gui Checkers    (My Checkers program)
Board Game Page    (My other game-playing programs: Pointy Stone, Slow Chess)
Tutorials Page    (Unrelated 3D programming tutorials)


I believe bitboards are ideally suited to checkers. A bitboard represents a piece of information about each square on the board with a single bit. Bitboards are most mentioned in relation to chess, but they don't fit in with a chess program as elegantly. (Note: I don't mean to imply they can't be good for chess. ) The sliding moves in chess aren't easily generated with bitboards, and there are more piece types, so you need more bitboards. Bitboards have also been used in Othello, though my own Pointy Stone doesn't use them. I don't see any drawbacks to using bitboards with checkers besides the added complication.

I couldn't find any information about checker bitboards on the internet, but I believe their use is common in strong programs. I have no idea if the specifics of the representation and methods I describe here are common too. My primary reason for writing this is the chance that there's some originality to the contents, at least in the world of web tutorials. I've done more programming of chess than of checkers, but never wrote an article on chess because there's so much of chess programming information already on the net.

Padded Array:

The board representation my checkers program used initally was a padded array. Although only 46 squares are needed, I use char BoardArray[48]; (Actually, I just started with a 64 byte array of each square, but that isn't a particulary effective representation.) Simple Checkers by Martin Fierz is the first place I saw the padded array, I don't know if it was common before that or not. Here's the square numbers as they correspond to an actual checker board, you'll notice that certain numbers are skipped. These are given a value that says they're invalid to move to.

   37  38  39  40
 32  33  34  35
   28  29  30  31
 23  24  25  26
   19  20  21  22
 14  15  16  17
   10  11  12  13
 05  06  07  08    

Because of the padding you don't have to check if a destination square is off the edge of the board, and the +4,+5,-4,-5 deltas always move the same direction. To see if a checker can move Up-Right for example, you can use just one line: if ( BoardArray[ source_square + 5 ] == EMPTY )


Checkers only has 2 types of pieces, 2 colors, and 32 squares. That means all the information about piece types and locations for the entire board can be stored in three 32-bit integers, totalling only 12 bytes. These three bitboards are "White Pieces"(WP), "Black Pieces"(BP), and "Kings"(K).

To use bitboards, you should be familiar with bitwise operations, like OR |, AND &, XOR ^, NOT ~, and Shifting Left << or Right >>.
To get a bitboard of the white kings, you use the following line WK = WP & K; similarily to exclude kings use WP & ~K

Here's the numbering of the squares for the bitboard representation I use.

   28  29  30  31 
 24  25  26  27
   20  21  22  23
 16  17  18  19
   12  13  14  15
 08  09  10  11  
   04  05  06  07 
 00  01  02  03  
(I have white pieces starting on the top, black on the bottom.)

Now that we have the bitboards, the question is what good do they do? Technically it's possible to do the same things with absolutely any board representation. Bitboards however can speed up the move generation and the evaluation significantly. In checkers, since jumps are forced, perhaps the biggest gain is when generating moves we can quickly find out if any jumps are possible. One thing that needs to be considered is that with only 32 bits per square, a 4 bit shift for instance will move zig-zag since the direction on our board representation it shifts depends on the row.

Generating Moves:

Here's how you can compute a bitboard containing the white pieces that are able to move. I'm starting with this because it's simpler than jumps, though less useful. You should review the square numbers for the bitboard representation to understand the code. For example a left shift by 4 moves every bit to Sq+4, and this is always a legal move and will never wraparound horizontally. We start with a bitboard of unoccupied squares, then shift, then AND with the White Pieces. Sq+3 is only legal on some squares, so we first do the bitwise AND with a bitmask that contains the squares for which it is a legal move. (Note: UINT is defined as a 32-bit unsigned integer.)

UINT CBitBoard::GetMoversWhite( ) 
  const UINT nOcc = ~(WP | BP); // Not Occupied
  const UINT WK = WP&K;         // Kings
  UINT Movers = (nOcc << 4) & WP;
  Movers |= ((nOcc&MASK_L3) << 3) & WP;
  Movers |= ((nOcc&MASK_L5) << 5) & WP;
  if ( WK ) {
      Movers |= (nOcc >> 4) & WK;
      Movers |= ((nOcc&MASK_R3) >> 3) & WK;
      Movers |= ((nOcc&MASK_R5) >> 5) & WK;
  return Movers;

This is an example of code initializing the bit-tables. Other Masks can be initialized in a similar way.

UINT S[32];

S[0] = 1;
for (int i = 1; i < 32; i++) { S[i] = S[i-1] * 2; }

MASK_L3 = S[ 1] | S[ 2] | S[ 3] | S[ 9] | S[10] | S[11] | S[17] | S[18] | S[19] | S[25] | S[26] | S[27];
MASK_L5 = S[ 4] | S[ 5] | S[ 6] | S[12] | S[13] | S[14] | S[20] | S[21] | S[22];
MASK_R3 = S[28] | S[29] | S[30] | S[20] | S[21] | S[22] | S[12] | S[13] | S[14] | S[ 4] | S[ 5] | S[ 6];
MASK_R5 = S[25] | S[26] | S[27] | S[17] | S[18] | S[19] | S[ 9] | S[10] | S[11];

Jump moves are a little trickier, although they are where the biggest speed gain with bitboard move generation is to be had. The reason for this is all jumps are forced in checkers, so it's good to find the pieces that can jump, if any, as quickly as possible. Also doing a jumps-only quiescence search is common. Here's how you can compute a bitboard containing the white pieces that are able to jump. Since we are finding jumpers, we start with a bitboard of empty squares, move them diagonally, AND with enemy pieces, move them diagonally, then AND with friendly pieces that can move that direction. This could be done without any if statements at all, but I played around with adding a few for speed.

UINT CBitBoard::GetJumpersWhite( )
  const UINT nOcc = ~(WP | BP);
  const UINT WK = WP&K;
  UINT Movers = 0;
  UINT Temp = (nOcc << 4) & BP;
  if (Temp) Movers |= (((Temp&MASK_L3) << 3) | ((Temp&MASK_L5) << 5)) & WP;
  Temp = ( ((nOcc&MASK_L3) << 3) | ((nOcc&MASK_L5) << 5) ) & BP;
  Movers |= (Temp << 4) & WP;
  if (WK) {
      Temp = (nOcc>> 4) & BP;
      if (Temp) Movers |= (((Temp&MASK_R3) >> 3) | ((Temp&MASK_R5) >> 5)) & WK;
      Temp = ( ((nOcc&MASK_R3) >> 3) | ((nOcc&MASK_R5) >> 5) ) & BP;
      if (Temp) Movers |= (Temp >> 4) & WK;
  return Movers;

Now here is where perhaps I'll dissapoint readers a bit. I started with a working padded array representation program, then added bitboards on top of it. To actually generate the moves I still use the array, and both the array and bitboards are updated in the makemove function. For a complete example of move generation using only an array, you can download the source code to Gui Checkers.

Here's how to loop through each set bit of a bitboard. Single bits are anded to 0 until they are all 0. Since I use the 48 byte array, the square number is converted.

 while (Movers) 
    UINT sq = FindHighBit( Movers );
    Movers &= ~S[sq];
    int square = BoardLoc_32to48[ sq ];
    // Do stuff here
// Helper function
// HighBit is a 65536 element lookup table that stores the highest bit set for 16-bit data.
UINT inline FindHighBit( UINT Moves )
   if ( ((Moves>>16) & 65535) ) return HighBit[ ((Moves>>16) & 65535) ] + 16;
   if ( (Moves & 65535) ) return HighBit[ (Moves & 65535) ];
   return 0;

Evaluation with Bitboards:

With bitboards you have a lot more evaluation options available. Bitboards are very good for operating on the board as a whole instead of individual squares. This is an area where I would hope for big gains if I would was good enough at checkers to know what's effective for the evaluation. Actually I haven't done much with bitboard evaluation, maybe I'll expand this section in the future. Here are a few ideas:



Appendix : Alternative bitboard layouts

Ed Gilbert, author of the very strong Kingsrow, writes:

I certainly agree with you that checkers is ideally suited for this data format.  I noticed that you use the same bit definitions that Martin uses in cake, i.e. bit 0 for square 4, bit 1 for square 3, ...  I think Martin chose this representation because it is used in the Chinook endgame database, and back when that was the only db we had it was convenient to use this format to eliminate the necessity of a bitmap translation when doing db lookups.  A slight drawback to this format is that the conversion between square numbers and bits is not as straightforward and generally requires a table lookup. In kingsrow I use bit 0 for square 1, ..., bit 31 for square 32, which is a little simpler, and also makes it easier for me to decipher the bitmaps in my head when I'm looking at them with a debugger.

There is another representation for checkers bitboards which has some very nice properties for move generation.  One version of it goes like this (numbers representing bit positions in the bitmap):

   11  05  31  25 
 10  04  30  24 
   03  29  23  17 
 02  28  22  16 
   27  21  15  09 
 26  20  14  08 
   19  13  07  01 
 18  12  06  00 

A move forward to the left is always a rotate left 7 bits, regardless of which row you start on.  A move to the right is always a 1 bit rotate.  For the representations that we use our programs now, the even rows must be handled separately from the odd rows, which is a lot of duplication of effort.  This scheme was first shown to me by a Thai checkers programmer named Thotsaphon Thanatipanonda.  Of course there are some drawbacks to it. You need to use some machine language rotate instructions to do the rotates efficiently, as C does not have a rotate operator.  The main drawback is that it makes it difficult to do table lookups based on a few consecutive rows of checkers pieces.  For example, in kingsrow I use bits 0 through 7 as an index into a table to do backrank evaluations for the black pieces.  I have a similar table based lookup for runaway evaluations.  These operations become less efficient using this kind of bitboard format.  But even so, this looks very attractive for speeding up the move generator.  I think I might have given it a try if I had known about it when I was first writing a checkers program, but it was too much effort to change once a lot of code was written and tested.