Checkers Bitboard representation
Moderators: hgm, Rebel, chrisw
-
- Posts: 53
- Joined: Mon Sep 19, 2016 6:51 am
Checkers Bitboard representation
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.
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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Checkers Bitboard representation
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:universecoder wrote: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.
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
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?
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Checkers Bitboard representation
In my checkers engine I have these functions to deal with the "clumsiness". Everywhere else the code looks clean:Sven Schüle wrote: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.universecoder wrote: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.
Code: Select all
u32 NW(u32 p) {
return ((p & 0x0f0f0f0fu) << 4) | ((p & 0x00707070u) << 5);
}
u32 NE(u32 p) {
return ((p & 0x00f0f0f0u) << 4) | ((p & 0x0e0e0e0eu) << 3);
}
u32 SE(u32 p) {
return ((p & 0xf0f0f0f0u) >> 4) | ((p & 0x0e0e0e00u) >> 5);
}
u32 SW(u32 p) {
return ((p & 0x0f0f0f00u) >> 4) | ((p & 0x70707070u) >> 3);
}
-
- Posts: 1434
- Joined: Wed Apr 21, 2010 4:58 am
- Location: Australia
- Full name: Nguyen Hong Pham
Re: Checkers Bitboard representation
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
- 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
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: Checkers Bitboard representation
Computer checkers pioneer Arthur Samuel used the following 35-bit representationSven Schüle wrote: 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:
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.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
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
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Checkers Bitboard representation
In my case this would look like:AlvaroBegue wrote:In my checkers engine I have these functions to deal with the "clumsiness". Everywhere else the code looks clean:Sven Schüle wrote: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.universecoder wrote: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.
Code: Select all
u32 NW(u32 p) { return ((p & 0x0f0f0f0fu) << 4) | ((p & 0x00707070u) << 5); } u32 NE(u32 p) { return ((p & 0x00f0f0f0u) << 4) | ((p & 0x0e0e0e0eu) << 3); } u32 SE(u32 p) { return ((p & 0xf0f0f0f0u) >> 4) | ((p & 0x0e0e0e00u) >> 5); } u32 SW(u32 p) { return ((p & 0x0f0f0f00u) >> 4) | ((p & 0x70707070u) >> 3); }
Code: Select all
static u64 const BORDER = 0x1e100804021fULL;
u64 NW(u64 p) {
return (p << 4) & ~BORDER;
}
u64 NE(u64 p) {
return (p << 5) & ~BORDER;
}
u64 SE(u64 p) {
return (p >> 4) & ~BORDER;
}
u64 SW(u64 p) {
return (p >> 5) & ~BORDER;
}
Code: Select all
static u64 const BORDER = 0x8040201ULL;
u64 NW(u64 p) {
return (p << 5) & ~BORDER;
}
u64 NE(u64 p) {
return (p << 4) & ~BORDER;
}
u64 SE(u64 p) {
return (p >> 5) & ~BORDER;
}
u64 SW(u64 p) {
return (p >> 4) & ~BORDER;
}
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: Checkers Bitboard representation
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.Sven Schüle wrote: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):Not sure who will win, "less instructions" or "less bytes per position".Code: Select all
static u64 const BORDER = 0x8040201ULL; u64 NW(u64 p) { return (p << 5) & ~BORDER; } u64 NE(u64 p) { return (p << 4) & ~BORDER; } u64 SE(u64 p) { return (p >> 5) & ~BORDER; } u64 SW(u64 p) { return (p >> 4) & ~BORDER; }
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 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
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: Checkers Bitboard representation
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
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!
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Checkers Bitboard representation
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 wrote: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).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
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!
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: Checkers Bitboard representation
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.Sven Schüle wrote: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 wrote: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).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
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!
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.