Perft(12) count confirmed

[Rein Halbersma]

The only change I made was to increase the hash signature length from (about) 56 bits to (about) 120 bits due to a couple of false positive matches in the early test runs.

How did you detect false positive matches on the signature? If you are trailblazing new ply depths no-one has done before, can you know for sure you have avoided all false positive matches?

PS Not calling into question your results but I am doing something similar in checkers. There is always a small chance false positive signatures can happen and wreck the exactness of the results. I'm concluding the entire board position must be stored in the hash table to avoid this (96 bits in checkers).

At the Draughts Forum, Aart Bik has published the perft(23) results for checkers. See http://laatste.info/bb3/viewtopic.php?f=53&t=2889 The result is 7437536860666213 (about 7.4e+15, an order of magnitude smaller than perft(12) for chess). Aart used a cluster of computers and didn't give a time to depth for his result. I computed perft(22) on an old P4 machine and that took 3 days, so I believe perft(23) to take about 10 days and perft(24) about 3 weeks. The perft method was of course accelerated by bulk-counting and hashing. If you can run on an i7 or better, and do some parallel stuff, you might pull off perft(24) in a few days.

I don't quite understand how you can store the entire checkers position in 96-bits (16-bytes). Do you leave out the kings bitboard? I suppose that would not make 100% that your hash signature is unique.

My hash entries are 32 bytes: 24 bytes of position info (3 bitboards storing white and black pieces, and kings) plus 8 bytes of perft info (59 bits for the count and 5 bits for the depth). Furthermore, I split my hash table into a wtm and a btm table, so that I don't need to store the side to move. This format will scale to perft(25), for which the estimated count is 1.6e+17, and this fits within 59 bits =5.6e+17. An alternative that scales to perft(28) is to use 64 bits for the count and to let the hash table be an array of mini tables (one per depth) so that you can then drop the color altogether (because side to move is completely determined by the depth).

[Rémi Coulom]

I don't quite understand how you can store the entire checkers position in 96-bits (16-bytes). Do you leave out the kings bitboard? I suppose that would not make 100% that your hash signature is unique.

I guess: 32 bits for white + 32 bits for black + 32 bits for king status = 96 bits (only half of the board is used in checkers). That's 12 bytes, BTW. You may have to encode side to move, too. That may be done by king status of empty squares.

Rémi

[Rein Halbersma]

I don't quite understand how you can store the entire checkers position in 96-bits (16-bytes). Do you leave out the kings bitboard? I suppose that would not make 100% that your hash signature is unique.

I guess: 32 bits for white + 32 bits for black + 32 bits for king status = 96 bits (only half of the board is used in checkers). That's 12 bytes, BTW. You may have to encode side to move, too. That may be done by king status of empty squares.

Rémi

OK, thanks, 96-bits is 12 bytes (not 16 as I mistakenly wrote) which is indeed 3 x 32-bit integers, containing all data. I am using 64-bit integers for my checkers program as that allows some easier shifting (no need to do edge detection and no odd/even row distinction). My bit-layout is incidentally the same as in Samuel's checkers program (it needs at least 36-bit integers). Your side to move solution is also nice!

[sje]

Also in the calculation, a pair of separate transposition tables indexed by color are maintained. This effectively adds an extra bit of hash code length.

[jwes]

I don't quite understand how you can store the entire checkers position in 96-bits (16-bytes). Do you leave out the kings bitboard? I suppose that would not make 100% that your hash signature is unique.

I guess: 32 bits for white + 32 bits for black + 32 bits for king status = 96 bits (only half of the board is used in checkers). That's 12 bytes, BTW. You may have to encode side to move, too. That may be done by king status of empty squares.

Rémi

Since there are five possibilites for each square, you could back 3 squares in 7 bits, which would give 76 bits for any position (30 squares in 70 bits, 2 squares in 5 bits, and 1 bit for side to move).

[Rein Halbersma]

I don't quite understand how you can store the entire checkers position in 96-bits (16-bytes). Do you leave out the kings bitboard? I suppose that would not make 100% that your hash signature is unique.

I guess: 32 bits for white + 32 bits for black + 32 bits for king status = 96 bits (only half of the board is used in checkers). That's 12 bytes, BTW. You may have to encode side to move, too. That may be done by king status of empty squares.

Rémi

Since there are five possibilites for each square, you could back 3 squares in 7 bits, which would give 76 bits for any position (30 squares in 70 bits, 2 squares in 5 bits, and 1 bit for side to move).

That would be quite slow of course, since the position struct itself is 96-bits and storing it in the hashtable is a simple memcpy, whereas your solution would entail a costly code/decode step when reading/writing to the hash table.

[Sven]

I don't quite understand how you can store the entire checkers position in 96-bits (16-bytes). Do you leave out the kings bitboard? I suppose that would not make 100% that your hash signature is unique.

I guess: 32 bits for white + 32 bits for black + 32 bits for king status = 96 bits (only half of the board is used in checkers). That's 12 bytes, BTW. You may have to encode side to move, too. That may be done by king status of empty squares.

Rémi

Since there are five possibilites for each square, you could back 3 squares in 7 bits, which would give 76 bits for any position (30 squares in 70 bits, 2 squares in 5 bits, and 1 bit for side to move).

The first and last rank have only 4 states due to promotion so you need only 4x2 + (24/3)x7 + 4x2 + 1 = 73 bits.

EDIT: To avoid slow decoding operations it would be possible to encode the 8 squares on first and last rank with 2 bits each and the other 24 squares with 3 bits each, plus side to move bit. That is 16+72+1=89 which needs the same number of bytes (12) as 96 but comes without decoding of the side to move status. The only drawback is to have three piece mapping tables (first rank, last rank, all other ranks) and therefore one additional level of indirection.

Sven

[murraycash]

Yes I saw Aart's perft(23) result, mine matched his that is 7437536860666213 positions in 4d 19:28:34 on an AMD X2-3800 single threaded with 1GB hash table. At that rate it should take about 13 days to do perft(24).

I think perft is a really worthwhile exercise and kudos to those that lead the way and put the computer hours in to benefit everyone else.

[Rein Halbersma]

Yes I saw Aart's perft(23) result, mine matched his that is 7437536860666213 positions in 4d 19:28:34 on an AMD X2-3800 single threaded with 1GB hash table. At that rate it should take about 13 days to do perft(24).

I think perft is a really worthwhile exercise and kudos to those that lead the way and put the computer hours in to benefit everyone else.

Great to see the confirmation. Please keep us informed at the draughts forum as well.

[abik]

Yes I saw Aart's perft(23) result, mine matched his that is 7437536860666213 positions in 4d 19:28:34 on an AMD X2-3800 single threaded with 1GB hash table. At that rate it should take about 13 days to do perft(24).

Thanks for verifying my previous perft results and ........ challenge accepted
Below my new results for perft(24) for 8x8 checkers from the initial position, broken down per move.

Code: Select all

 0 : 12-16   = 5192042148594780
 1 : 11-16   = 5248615918291379
 2 : 11-15   = 4602138522979438
 3 : 10-15   = 4643700995955222
 4 : 10-14   = 3988937724259353
 5 :  9-14   = 4712325943133747
 6 :  9-13   = 6263620622082081
    ------------------------------------------
perft(24)   = 34651381875296000