perft for 8x8 checkers (depth 23)

[AartBik]

Today I felt the "itch" Rein was alluding to in his previous posting, and computed perft(23) for 8x8 checkers. This time the distributed implementation has been further optimized with a transposition table, but because I store full board positions I don't have the risk of "hard collisions". The table below shows the perft breakdown per move from the start position for depths 21 to 23.

Code: Select all

move        divide(21)       divide(22)        divide(23)
---------------------------------------------------------
12-16:  52945190026737  243598269855110  1123463594881857
11-16:  53527954221225  246743868125768  1131373985922218
11-15:  44775005468548  209016678583301   984253557821317
10-15:  46574865098865  215412869777867  1000606302770349
10-14:  39822944739732  184865466345796   856779998157523
09-14:  45530585259776  213736468971938  1003310451936358
09-13:  61923979665936  288999100078322  1337748969176591
---------------------------------------------------------
       345100524480819 1602372721738102  7437536860666213

[Rein Halbersma]

Today I felt the "itch" Rein was alluding to in his previous posting, and computed perft(23) for 8x8 checkers. This time the distributed implementation has been further optimized with a transposition table, but because I store full board positions I don't have the risk of "hard collisions". The table below shows the perft breakdown per move from the start position for depths 21 to 23.

Code: Select all

move        divide(21)       divide(22)        divide(23)
---------------------------------------------------------
12-16:  52945190026737  243598269855110  1123463594881857
11-16:  53527954221225  246743868125768  1131373985922218
11-15:  44775005468548  209016678583301   984253557821317
10-15:  46574865098865  215412869777867  1000606302770349
10-14:  39822944739732  184865466345796   856779998157523
09-14:  45530585259776  213736468971938  1003310451936358
09-13:  61923979665936  288999100078322  1337748969176591
---------------------------------------------------------
       345100524480819 1602372721738102  7437536860666213

Hi Aart,

Another one bites the dust...

Good idea to hash the full position, although that reduces the number of hash entries. For me it would be a factor of 2: my current 8 byte hash keys + 8 bytes counts, compared to 24 byte positions + 8 byte counts, and I would have to have 2 tables: one for wtm and one for btm (to eliminate storing the side to move). I won't be trying to verify this number for a while at least.

Rein

[Rein Halbersma]

Today I felt the "itch" Rein was alluding to in his previous posting, and computed perft(23) for 8x8 checkers. This time the distributed implementation has been further optimized with a transposition table, but because I store full board positions I don't have the risk of "hard collisions". The table below shows the perft breakdown per move from the start position for depths 21 to 23.

Code: Select all

move        divide(21)       divide(22)        divide(23)
---------------------------------------------------------
12-16:  52945190026737  243598269855110  1123463594881857
11-16:  53527954221225  246743868125768  1131373985922218
11-15:  44775005468548  209016678583301   984253557821317
10-15:  46574865098865  215412869777867  1000606302770349
10-14:  39822944739732  184865466345796   856779998157523
09-14:  45530585259776  213736468971938  1003310451936358
09-13:  61923979665936  288999100078322  1337748969176591
---------------------------------------------------------
       345100524480819 1602372721738102  7437536860666213

Today I tried your scheme with hashing the full position. I now use 2 hash tables of 512M each, one for wtm and one for btm positions. This allows me to save a position as only the 3 bitboards (24 bytes) + the count & depth (another 8 bytes, of which 5 bits for depth counting), so in total 32 bytes per hash entry (which allows 2 entries per cache line!). In all I have now 2 * 16 M hash entries.

The overall speed for up to d=15 is about a factor of 2 slower! I haven't analyzed it in depth, but first of all the lookup/storage of hash entries is more expensive (32 bytes vs 16 bytes per entry during storage, and 24 bytes vs 8 bytes in the equality comparison during lookup).

For my particular implementation I have another slow down because do not use incremental Zobrist hashing for this type of lock (it would take a few inelegant modifications to my carefully crafted generic hash_map, so I'm a bit lazy here), and ab initio Zobrist hashing is quite a bit more expensive.

The d=22 computation took 3 days, and to confirm the d=23 will take about 10 days with only a 64-bit signature and probably 3 weeks when storing the whole position (or I have to do some recoding of my hash table). d=24 will be at least 3 weeks and probably 6 weeks. Not for the time being, so you can rest a bit, Aart

[Rein Halbersma]

For my particular implementation I have another slow down because do not use incremental Zobrist hashing for this type of lock (it would take a few inelegant modifications to my carefully crafted generic hash_map, so I'm a bit lazy here), and ab initio Zobrist hashing is quite a bit more expensive.

Not wanting to add stuff to supposedly generic code because it would break stuff is of course an oxymoron. Truly generic code should not break. According to the Open/Closed principle: adding new features only requires adding new code, not changing old code. I've now decoupled the hash indexing from the hash signature into an orthogonal design. Incremental Zobrist hashing now also works seamlessly with storing the full piece lists as a hash signature. Even better, the speed is now within 10% than the old perft() code that stored a 64-bit integer signature. I can post some code for those that are interested in generic programming.