Wednesday, September 12, 2012

Perft for Checkers for Depth 25

Continuing my quest for deeper and deeper perft numbers for 8x8 checkers, I now computed depth 25 with the same distributed implementation I used earlier for depths up to 24. Below you see the perft breakdown per move (called "divide") from the initial position for depths 23, 24 and 25 (my depth 23 and 24 numbers were recently kindly confirmed by Murray Cash at the World Draughts Forum).

move          divide(23)        divide(24)          divide(25)
--------------------------------------------------------------
12-16:  1123463594881857  5192042148594780   24019313789608561
11-16:  1131373985922218  5248615918291379   24153215782987793
11-15:   984253557821317  4602138522979438   21659601983574539
10-15:  1000606302770349  4643700995955222   21609957136212495
10-14:   856779998157523  3988937724259353   18496978526984076
 9-14:  1003310451936358  4712325943133747   22101040287502927
 9-13:  1337748969176591  6263620622082081   29027372375205409
--------------------------------------------------------------
        7437536860666213 34651381875296000  161067479882075800


The numbers were computed on on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as bulk counting. Please note that the move generator does not eliminate duplicate captures (viz. the situation where a king can capture the same pieces in different directions; a situation that starts to occur at depth 12 and up).