Checkers Bitboard representation

[universecoder]

I have been writing a checkers program for a few days( without reviewing any literature) and used 3 uint64_t data types ( light, dark and king) for representing the board. Upon reviewing literature( http://www.3dkingdoms.com/checkers/bitboards.htm) I realized that I should have used 32 bit bitboards instead.

However, wouldn't bit operations on 64 bit integers be faster?

Also, does the 64 bit data type give me a serious handicap here? I would have to change my entire codebase to incorporate the change.

[Sven]

I have been writing a checkers program for a few days( without reviewing any literature) and used 3 uint64_t data types ( light, dark and king) for representing the board. Upon reviewing literature( http://www.3dkingdoms.com/checkers/bitboards.htm) I realized that I should have used 32 bit bitboards instead.

However, wouldn't bit operations on 64 bit integers be faster?

Also, does the 64 bit data type give me a serious handicap here? I would have to change my entire codebase to incorporate the change.

I am not convinced at all that the bitboard encoding of squares shown under the link above is really clever. It saves a small amount of memory by storing the whole board in three 32-bit integers but it requires quite some additional calculations since the required shifts depend on the current rank. For instance, on odd ranks you need to shift by 3 or 4 to go "left up" or "right up" while on even ranks you need to shift by 4 or 5 for the same purpose. That makes the whole implementation a bit clumsy. Therefore, when implementing checkers with bitboards I could imagine to use the same encoding of squares shown for the "Padded Array" representation under the link above. This uses 45 bits in total per bitboard which fits into a 64-bit integer:

Code: Select all

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

This would result in fixed shift widths of +4/+5 and -4/-5 so I'd imagine it should help to keep the code simple.

As to your original question, I don't think that using 64 bit instead of 32 bit would make a substantial difference for the overall performance in this case. In my opinion the most important point will be to find a clever evaluation and search strategy; due to the rules being quite simple (with the only exception of multiple jumps for kings), generating and making/unmaking moves will be so fast for checkers that you probably won't even notice it is happening at all.

How did you define the square encoding in your engine?

[AlvaroBegue]

I have been writing a checkers program for a few days( without reviewing any literature) and used 3 uint64_t data types ( light, dark and king) for representing the board. Upon reviewing literature( http://www.3dkingdoms.com/checkers/bitboards.htm) I realized that I should have used 32 bit bitboards instead.

However, wouldn't bit operations on 64 bit integers be faster?

Also, does the 64 bit data type give me a serious handicap here? I would have to change my entire codebase to incorporate the change.

I am not convinced at all that the bitboard encoding of squares shown under the link above is really clever. It saves a small amount of memory by storing the whole board in three 32-bit integers but it requires quite some additional calculations since the required shifts depend on the current rank. For instance, on odd ranks you need to shift by 3 or 4 to go "left up" or "right up" while on even ranks you need to shift by 4 or 5 for the same purpose. That makes the whole implementation a bit clumsy.

In my checkers engine I have these functions to deal with the "clumsiness". Everywhere else the code looks clean:

Code: Select all

  u32 NW(u32 p) {
    return (&#40;p & 0x0f0f0f0fu&#41; << 4&#41; | (&#40;p & 0x00707070u&#41; << 5&#41;;
  &#125;

  u32 NE&#40;u32 p&#41; &#123;
    return (&#40;p & 0x00f0f0f0u&#41; << 4&#41; | (&#40;p & 0x0e0e0e0eu&#41; << 3&#41;;
  &#125;

  u32 SE&#40;u32 p&#41; &#123;
    return (&#40;p & 0xf0f0f0f0u&#41; >> 4&#41; | (&#40;p & 0x0e0e0e00u&#41; >> 5&#41;;
  &#125;

  u32 SW&#40;u32 p&#41; &#123;
    return (&#40;p & 0x0f0f0f00u&#41; >> 4&#41; | (&#40;p & 0x70707070u&#41; >> 3&#41;;
  &#125;

[phhnguyen]

I did not work with checker but Xiangqi (the board size is 90). From my recent experience:
- uint64_t usually is the best for speed. But the gain depends much on the way you optimise the code, and just about 2-5% faster, compared with uint32_t
- if you organise bitboard well, you can easily convert (cast) data structure from uint64_t to uint32_t and vice versa whenever you want. That make the difference between representations become so little

IMO, if your data with uint32_t-representation is significantly smaller than one with uint64_t, go with uint32_t. Otherwise go with uint64_t for having easier life

[Rein Halbersma]

For instance, on odd ranks you need to shift by 3 or 4 to go "left up" or "right up" while on even ranks you need to shift by 4 or 5 for the same purpose. That makes the whole implementation a bit clumsy. Therefore, when implementing checkers with bitboards I could imagine to use the same encoding of squares shown for the "Padded Array" representation under the link above. This uses 45 bits in total per bitboard which fits into a 64-bit integer:

Code: Select all

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

This would result in fixed shift widths of +4/+5 and -4/-5 so I'd imagine it should help to keep the code simple.

Computer checkers pioneer Arthur Samuel used the following 35-bit representation

Code: Select all

  35  34  33  32
31  30  29  28
  26  25  24  23
22  21  20  19
  17  16  15  14
13  12  11  10
  08  07  06  05
04  03  02  01

This representation was already invented in 1959, taking advantage of a very peculiar 36-bit IBM computer at the time (Samuel was an IBM employee).

[Sven]

I have been writing a checkers program for a few days( without reviewing any literature) and used 3 uint64_t data types ( light, dark and king) for representing the board. Upon reviewing literature( http://www.3dkingdoms.com/checkers/bitboards.htm) I realized that I should have used 32 bit bitboards instead.

However, wouldn't bit operations on 64 bit integers be faster?

Also, does the 64 bit data type give me a serious handicap here? I would have to change my entire codebase to incorporate the change.

I am not convinced at all that the bitboard encoding of squares shown under the link above is really clever. It saves a small amount of memory by storing the whole board in three 32-bit integers but it requires quite some additional calculations since the required shifts depend on the current rank. For instance, on odd ranks you need to shift by 3 or 4 to go "left up" or "right up" while on even ranks you need to shift by 4 or 5 for the same purpose. That makes the whole implementation a bit clumsy.

In my checkers engine I have these functions to deal with the "clumsiness". Everywhere else the code looks clean:

Code: Select all

  u32 NW(u32 p) {
    return (&#40;p & 0x0f0f0f0fu&#41; << 4&#41; | (&#40;p & 0x00707070u&#41; << 5&#41;;
  &#125;

  u32 NE&#40;u32 p&#41; &#123;
    return (&#40;p & 0x00f0f0f0u&#41; << 4&#41; | (&#40;p & 0x0e0e0e0eu&#41; << 3&#41;;
  &#125;

  u32 SE&#40;u32 p&#41; &#123;
    return (&#40;p & 0xf0f0f0f0u&#41; >> 4&#41; | (&#40;p & 0x0e0e0e00u&#41; >> 5&#41;;
  &#125;

  u32 SW&#40;u32 p&#41; &#123;
    return (&#40;p & 0x0f0f0f00u&#41; >> 4&#41; | (&#40;p & 0x70707070u&#41; >> 3&#41;;
  &#125;

In my case this would look like:

Code: Select all

static u64 const BORDER = 0x1e100804021fULL;

u64 NW(u64 p) {
    return &#40;p << 4&#41; & ~BORDER;
&#125;

u64 NE&#40;u64 p&#41; &#123;
    return &#40;p << 5&#41; & ~BORDER;
&#125;

u64 SE&#40;u64 p&#41; &#123;
    return &#40;p >> 4&#41; & ~BORDER;
&#125;

u64 SW&#40;u64 p&#41; &#123;
    return &#40;p >> 5&#41; & ~BORDER;
&#125;

and for the 36-bit representation (including bit 0) of Arthur Samuel, as mentioned by Rein, in a 64-bit world it could be like this (note the right-to-left orientation):

Code: Select all

static u64 const BORDER = 0x8040201ULL;

u64 NW(u64 p) {
    return &#40;p << 5&#41; & ~BORDER;
&#125;

u64 NE&#40;u64 p&#41; &#123;
    return &#40;p << 4&#41; & ~BORDER;
&#125;

u64 SE&#40;u64 p&#41; &#123;
    return &#40;p >> 5&#41; & ~BORDER;
&#125;

u64 SW&#40;u64 p&#41; &#123;
    return &#40;p >> 4&#41; & ~BORDER;
&#125;

Not sure who will win, "less instructions" or "less bytes per position".

[Rein Halbersma]

for the 36-bit representation (including bit 0) of Arthur Samuel, as mentioned by Rein, in a 64-bit world it could be like this (note the right-to-left orientation):

Code: Select all

static u64 const BORDER = 0x8040201ULL;

u64 NW(u64 p) {
    return &#40;p << 5&#41; & ~BORDER;
&#125;

u64 NE&#40;u64 p&#41; &#123;
    return &#40;p << 4&#41; & ~BORDER;
&#125;

u64 SE&#40;u64 p&#41; &#123;
    return &#40;p >> 5&#41; & ~BORDER;
&#125;

u64 SW&#40;u64 p&#41; &#123;
    return &#40;p >> 4&#41; & ~BORDER;
&#125;

Not sure who will win, "less instructions" or "less bytes per position".

You can drop the "& ~BORDER" in each of these expressions! Why? Look carefully: the board has a hidden column at both sides of the board that automatically prevents moving pieces from sliding to the other side.

If you start from a valid position, and if there is no overlap between BORDER and any of the piece bitboards, then move detection can never set a bit within that BORDER bitboard. The only thing to take care of is computing the empty squares from an "occupied" bitboard:

Code: Select all

empty_squares = ~BORDER ^ occupied;

In my draughts program, this is the only place where I need the BORDERS bitboard. Never for shifting. If your position struct contains an EMPTY bitboard, then you only have to do this once per position (after make_move). But each subsequent shift you can safely do without the border masking.

In checkers, this BORDER mask is also called "GHOST" mask, because the corresponding bits are neither empty nor occupied. You have

Code: Select all

BORDER ^ occupied ^ empty == -1u

[Rein Halbersma]

Code: Select all

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

See above for the illustration: the squares 9, 18, 27 are part of the BORDER bitboard (or 8, 17, 26 if you use 0-counting). They appear on both sides of the board (in effect, with this numbering the board is cylindrical, but if the BORDER bitboard is neither empty nor occupied, it's not detectable).

You can't move e.g. 05-09 because square 09 never has a 1-bit in the empty bitboard, and you also can't jump 05 x 13 (via 09) because 09 cannot have a 1-bit on the occupied bitboard either!

[Sven]

Code: Select all

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

See above for the illustration: the squares 9, 18, 27 are part of the BORDER bitboard (or 8, 17, 26 if you use 0-counting). They appear on both sides of the board (in effect, with this numbering the board is cylindrical, but if the BORDER bitboard is neither empty nor occupied, it's not detectable).

You can't move e.g. 05-09 because square 09 never has a 1-bit in the empty bitboard, and you also can't jump 05 x 13 (via 09) because 09 cannot have a 1-bit on the occupied bitboard either!

I understand your trick: you want to postpone applying the "& ~BORDER" operation as much as possible. That will work, of course, although I'm not sure whether it saves a lot with today's optimizing compilers.

[Rein Halbersma]

Code: Select all

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

See above for the illustration: the squares 9, 18, 27 are part of the BORDER bitboard (or 8, 17, 26 if you use 0-counting). They appear on both sides of the board (in effect, with this numbering the board is cylindrical, but if the BORDER bitboard is neither empty nor occupied, it's not detectable).

You can't move e.g. 05-09 because square 09 never has a 1-bit in the empty bitboard, and you also can't jump 05 x 13 (via 09) because 09 cannot have a 1-bit on the occupied bitboard either!

I understand your trick: you want to postpone applying the "& ~BORDER" operation as much as possible. That will work, of course, although I'm not sure whether it saves a lot with today's optimizing compilers.

It's not postponing, but avoiding them altogether. For every position, I only need a single access to BORDER, namely to recompute the empty_squares bitboard after make_move(). After that, every shift of a pieces/occupied/empty bitboard for move generation, evaluation etc., are all free of the & ~BORDERS masking. Even with perfect caching of this constant, it still saves a single instruction per shift operation. The compiler cannot optimize this away because the board contents are runtime dependent data.

AFAIK, all the top draughts programs use this BORDERS layout. It's a double bonus of cleaner code and shaving a few instructions. Added ELO is tiny of course.