Page 1 of 2
Checkers Bitboard representation
Posted: Sun Jul 02, 2017 4:55 pm
by 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.
Re: Checkers Bitboard representation
Posted: Sun Jul 02, 2017 9:48 pm
by Sven
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.
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?
Re: Checkers Bitboard representation
Posted: Mon Jul 03, 2017 2:27 am
by AlvaroBegue
Sven Schüle wrote: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.
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 ((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);
}
Re: Checkers Bitboard representation
Posted: Mon Jul 03, 2017 8:55 am
by 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
Re: Checkers Bitboard representation
Posted: Mon Jul 03, 2017 11:15 am
by Rein Halbersma
Sven 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:
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).
Re: Checkers Bitboard representation
Posted: Mon Jul 03, 2017 10:00 pm
by Sven
AlvaroBegue wrote:Sven Schüle wrote: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.
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 ((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);
}
In my case this would look like:
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;
}
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 (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;
}
Not sure who will win, "less instructions" or "less bytes per position".
Re: Checkers Bitboard representation
Posted: Mon Jul 03, 2017 11:09 pm
by Rein Halbersma
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):
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;
}
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
Re: Checkers Bitboard representation
Posted: Mon Jul 03, 2017 11:27 pm
by 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!
Re: Checkers Bitboard representation
Posted: Tue Jul 04, 2017 10:32 pm
by Sven
Rein Halbersma wrote: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.
Re: Checkers Bitboard representation
Posted: Tue Jul 04, 2017 11:06 pm
by Rein Halbersma
Sven Schüle wrote:Rein Halbersma wrote: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.