Monday, July 19, 2010

One Deeper Perft for Checkers

I optimized the distributed implementation for 8x8 checkers with a transposition table (but one that stores full board positions to avoid the risk of "hard collisions"). The speed improvement enabled me to compute perft(23) on a cluster of machines in a relatively short time.

As before, the table below shows the perft breakdown per move (called "divide") from the start position, but now for depths 21 to 23.

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

See my checkers page for more details.