Perft for 8x8 checkers (depth 21)

[AartBik]

Today I was prototyping a distributed worker pool at work which needed some test input, and this, together with Rein's recent excellent work on providing perft for all variants of checkers gave me a good excuse to compute perft for checkers for depth 21 (one deeper than results I posted a while back). The perft breakdown per move for depths 18 up to 21 is shown below.

Code: Select all

move      divide(18)    divide(19)     divide(20)      divide(21)
----------------------------------------------------------------------
12-16 :   550829166472  2517202147314  11531470109861   52945190026737
11-16 :   566149929068  2564849953998  11736729175821   53527954221225
11-15 :   435063007630  2041959240377   9515983205474   44775005468548
10-15 :   472279451484  2180656975018  10055597639275   46574865098865
10-14 :   402570639569  1859042884028   8600202424158   39822944739732
09-14 :   441590753001  2068865301476   9698986164172   45530585259776
09-13 :   625398758917  2881467090588  13406062152792   61923979665936
----------------------------------------------------------------------
         3493881706141 16114043592799  74545030871553  345100524480819

For completeness, here is the full perft list.

Code: Select all

perft(1)  =               7  in         0 ms.
perft(2)  =              49  in         0 ms.
perft(3)  =             302  in         0 ms.
perft(4)  =            1469  in         0 ms.
perft(5)  =            7361  in         0 ms.
perft(6)  =           36768  in         1 ms.     36,768.0 KN/s
perft(7)  =          179740  in         5 ms.     35,948.0 KN/s
perft(8)  =          845931  in        23 ms.     36,779.6 KN/s
perft(9)  =         3963680  in        86 ms.     46,089.3 KN/s
perft(10) =        18391564  in       398 ms.     46,210.0 KN/s
perft(11) =        85242128  in      1821 ms.     46,810.6 KN/s
perft(12) =       388623673  in      8395 ms.     46,292.3 KN/s
perft(13) =      1766623630  in     37182 ms.     47,512.9 KN/s
perft(14) =      7978439499  in    174947 ms.     45,604.9 KN/s
perft(15) =     36263167175  in    808155 ms.     44,871.5 KN/s
perft(16) =    165629569428  in   3767118 ms.     43,967.2 KN/s
perft(17) =    758818810990  in  17317695 ms.     43,817.5 KN/s
perft(18) =   3493881706141
perft(19) =  16114043592799
perft(20) =  74545030871553
perft(21) = 345100524480819

[Rein Halbersma]

Today I was prototyping a distributed worker pool at work which needed some test input, and this, together with Rein's recent excellent work on providing perft for all variants of checkers gave me a good excuse to compute perft for checkers for depth 21 (one deeper than results I posted a while back). The perft breakdown per move for depths 18 up to 21 is shown below.

Code: Select all

perft(17) =    758818810990  in  17317695 ms.     43,817.5 KN/s
perft(18) =   3493881706141
perft(19) =  16114043592799
perft(20) =  74545030871553
perft(21) = 345100524480819

Hi Aart,

Congratulations on your computation.

If d=17 takes about 4 hours on a single core, then with a branching factor of 4.7 or so, then on the same desktop machine you could already get to d=18 in a day, d=19 within a week, d=20 in a month and d=21 in half a year (ball park figures). I am just curious how much you speeded this up with your worker pool. How many workers and how many wall clock hours did the computation for d=21 take?

Furthermore, if your worker pool scales up to the equivalent of 55,000 single cores (including overhead), then half a year of crunching would get you to d=28. At that point you will go beyond the 1e19 threshold that still fits within 64-bit integers and you will need to do some extra bookkeeping. It sounds quite high-end to me, but you are at Google so...

Rein

[AartBik]

I am just curious how much you speeded this up with your worker pool. How many workers and how many wall clock hours did the computation for d=21 take?

I am afraid I must remain a little vague on details. Let's just say perft(21) ran quickly enough that it still more or less qualifies as test run .
In any case, thank you for providing perft for all the other variants of checkers. I believe information like that is very valuable to aspirant engine programmers!