Thursday, July 8, 2010

Perft for Checkers (yet again)

Rein Halbersma recently posted 8x8 checkers perft results for depth 22 with a request for confirmation (because he uses a hash table, he wanted to make sure no "hard collisions" occur). So I verified his results for depth 22 using a distributed, brute force implementation (no hash tables).

The table below shows the perft breakdown per move (called "divide") from the start position for depths 20 to 22.

move    divide(20)      divide(21)       divide(22)
-------------------------------------------------------
12-16:  11531470109861  52945190026737  243598269855110
11-16:  11736729175821  53527954221225  246743868125768
11-15:   9515983205474  44775005468548  209016678583301
10-15:  10055597639275  46574865098865  215412869777867
10-14:   8600202424158  39822944739732  184865466345796
 9-14:   9698986164172  45530585259776  213736468971938
 9-13:  13406062152792  61923979665936  288999100078322
-------------------------------------------------------
        74545030871553 345100524480819 1602372721738102

For more information, see my checkers page.