Checker Bitboards Tutorial

Contents

• Introduction
• Padded Array
• Bitboards
• Generating Moves
• Evaluation with bitboards
• Appendix : Alternative bitboard layouts

Links on this site

Introduction

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 )

Bitboards:

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  

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 MASK_L3, MASK_L5, MASK_R3, MASK_R5;
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:

• Counting the number of bits set in a bitboard can be done very quickly. (I just use a lookup table twice, for the low and high 16-bits of a 32-bit bitboard.)
• You can compute mobility with bitboards quickly, so you can add naive mobility to your evaluation without worrying about slowdown. Although I am still confused about what's needed to evaluate mobility effectively in checkers. I know identifying trapped pieces is good, but bitboards aren't as helpful there.
• You can create special evaluation masks, like (BP & ~BK & MASK_ROW7) to do a quick test to see if there are any black checkers one move from promoting. Then if there are you can test to make sure they aren't blocked. Or you can check if a side has a king in a double corner with a line like this (BK & MASK_DCORNER).
• You can compute a bitboard for each square, of locations where an enemy piece could stop a checker on that square from promotion, then if the checker is unstoppable, adjust the evaluation accordingly.

Appendix : Alternative bitboard layouts

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

   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