perft for 8x8 checkers

[abik]

With the new improvements in place, it would almost be a waste not to go deeper with my perft for checkers computation. Therefore, I computed perft(27) from the initial position of 8x8 checkers. Below you see the perft breakdown per move, called "divide". As stated before, these numbers were computed on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures.

Code: Select all

 move                divide(27)
-------------------------------
 12-16    =  516399283859880203
 11-16    =  519502096014967805
 11-15    =  476666239516455180
 10-15    =  468705060101275533
 10-14    =  400425747281243848
  9-14    =  486493422418651579
  9-13    =  631652334435528457 
-------------------------------
perft(27) = 3499844183628002605

The implementation is "fault tolerant" against machine failures. Nevertheless, since I saw a few of these recoveries in this particular run, I may rerun this depth soon to verify the results pedantically.

[Ajedrecista]

Hello Aart:

With the new improvements in place, it would almost be a waste not to go deeper with my perft for checkers computation. Therefore, I computed perft(27) from the initial position of 8x8 checkers. Below you see the perft breakdown per move, called "divide". As stated before, these numbers were computed on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures.

Code: Select all

 move                divide(27)
-------------------------------
 12-16    =  516399283859880203
 11-16    =  519502096014967805
 11-15    =  476666239516455180
 10-15    =  468705060101275533
 10-14    =  400425747281243848
  9-14    =  486493422418651579
  9-13    =  631652334435528457 
-------------------------------
perft(27) = 3499844183628002605

The implementation is "fault tolerant" against machine failures. Nevertheless, since I saw a few of these recoveries in this particular run, I may rerun this depth soon to verify the results pedantically.

Congratulations again... no words. It is also good that Paul Byrne is confirming high perft numbers. Your improvements must be dazzling in order to get such advances.

I wrote a source code in my previous post but I made a mistake in the size of some real variables: the maximum size of 'perft' and 'bound' are switched between them; the rest is OK.

It is definitively very difficult to estimate what I call 'factor': factor(27) ~ 0.999678 while I said that it should be around 1.001 although I thought that it would be a little less, but not below 1! So, my bound(28) ~ 16,230,572,258,251,894,082 ~ 1.6231e+19, while factor(28) could be around 1.008 or 1.01, but it is the most difficult step of the estimate; perft(n) = factor(n)*bound(n), so Perft(28) can be around 1.636e+19 or 1.6393e+19.

If I said that Perft(27) was directly bound(27) ~ 3.501e+18, my relative error will be ~ 0.0322% (very low), but I said that my estimate for Perft(27) would be around 3.5045e+19, then the relative error is 0.133% more less. So, I do not know if Perft(28) will be nearer to 1.636e+19 (or 1.6393e+19) or to 1.6231e+19.

Regards from Spain.

Ajedrecista.

[ibid]

24 and 25 (re)confirmed. Or more precisely, the final perft
totals are confirmed; my program doesn't produce the divide
so I cannot comment there.

-paul

[abik]

24 and 25 (re)confirmed. Or more precisely, the final perft
totals are confirmed.-paul

Nice! Thanks for confirming my numbers. Any plans (and possibly ETA) for the confirming the higher depths? Should I fire up perft(28) already?

[abik]

My quest for deeper perft numbers for 8x8 checkers using has reached depth 28. Below you see the perft(28) breakdown per move, called "divide". As stated before, the numbers were computed on a cluster of machines, optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures. At this point, the limits of 64-bit unsigned integers have been reached. Although there are obvious ways around these restrictions, this seems a very good time to give this (by now probably insane) project a rest (although I may do some re-computations to get more confidence in the higher depth numbers; third party confirmation always welcome!).

Code: Select all

divide(28)
12-16 = 2400708339858199191
11-16 = 2431386196712611878
11-15 = 2231787529331259810
10-15 = 2186446356811761737
10-14 = 1872427919495823777
 9-14 = 2285893686261887442
 9-13 = 2969067990365356900
--------------------------- +
       16377718018836900735   = perft(28)

[ibid]

28. Yikes. I clearly need a cluster of machines to keep up. :)

I can however confirm your perft 26 (not the divide, as before).

27 is running now and 28 should be doable (couple of weeks?);
I don't see going any higher than that either, run times are
getting a bit much.

-paul

[abik]

28. Yikes. I clearly need a cluster of machines to keep up.

I can however confirm your perft 26 (not the divide, as before).

27 is running now and 28 should be doable (couple of weeks?);
I don't see going any higher than that either, run times are
getting a bit much.

-paul

Thanks again Paul. I highly appreciate your time confirming all these numbers! I have updated the acknowledgments on my page accordingly.

[Ajedrecista]

Hello again:

My quest for deeper perft numbers for 8x8 checkers using has reached depth 28. Below you see the perft(28) breakdown per move, called "divide". As stated before, the numbers were computed on a cluster of machines, optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures. At this point, the limits of 64-bit unsigned integers have been reached. Although there are obvious ways around these restrictions, this seems a very good time to give this (by now probably insane) project a rest (although I may do some re-computations to get more confidence in the higher depth numbers; third party confirmation always welcome!).

Code: Select all

divide(28)
12-16 = 2400708339858199191
11-16 = 2431386196712611878
11-15 = 2231787529331259810
10-15 = 2186446356811761737
10-14 = 1872427919495823777
 9-14 = 2285893686261887442
 9-13 = 2969067990365356900
--------------------------- +
       16377718018836900735   = perft(28)

Great achievement! Congratulations. Paul is also doing a great job. Perft(28) ~ 1.6378e+19, which is fairly close to my estimates including factors (1.636e+19 to 1.6393e+19). I thought that factor(28) should be between 1.008 and 1.01 (the average value is 1.009) and finally factor(28) ~ 1.0090659625701241... I was almost right (and too much lucky)!

I read that your perft project is going to take a rest, so Perft(29) is not expected soon. Writing about perft estimates, I get bound(29) ~ 76,433,960,643,219,238,224 ~ 7.6434e+19; factor(29) is very tricky to estimate IMHO. I have some 'almost random' candidates for factor(29):

Code: Select all

Perft(29) = bound(29) * factor(29)
BF(29) = Perft(29)/Perft(28)

Factor(29) ~ 0.9958; Perft(29) ~ 7.6113e+19 ---> BF(29) ~ 4.6473
Factor(29) ~ 0.9967; Perft(29) ~ 7.6182e+19 ---> BF(29) ~ 4.6515
Factor(29) = 1     ; Perft(29) ~ 7.6434e+19 ---> BF(29) ~ 4.6669

I know that estimates are so different between them. The only thing I am more less sure about is that the first two numbers of Perft(29) will be 76.

Regards from Spain.

Ajedrecista.

[abik]

Great achievement! Congratulations. Paul is also doing a great job. Perft(28) ~ 1.6378e+19, which is fairly close to my estimates including factors (1.636e+19 to 1.6393e+19). I thought that factor(28) should be between 1.008 and 1.01 (the average value is 1.009) and finally factor(28) ~ 1.0090659625701241... I was almost right (and too much lucky)!

Thanks again for the interesting background. It is good to see that the actual and expected ballpark numbers match although, of course, in the distributed execution a single lost number would go unnoticed that way but have a disastrous impact on the final result And who knows, someone else may want to pick up perft(29).....

[Ajedrecista]

Hello:

Going a little off-topic about chess and even perft of checkers, I would like to compare an upper bound of the search space complexity of the game of checkers. Taking the formula given by Schaeffer and Lake at page 6:

Solving the Game of Checkers

I re-did the calculations for 8x8 checkers and tried boards of other sizes as well: 4x4, 6x6, 10x10, 12x12 and 14x14. Why up to 14x14, which is too large? The answer is here:

Checkers Variants

I only counted the positions with the formula of the paper (adapting it to each board size, of course), not caring about specific rules of each variant: short kings, long kings, flying kings, pieces (not kings) capturing backwards... only an upper bound of positions. Can it be compared with the Shannon number?

Here are my results, which have rounding problems in big numbers:

Code: Select all

Search space complexity of 4x4 checkers:
 
Pieces                                 Positions
 
   1                                          28
   2                                         342
   3                                        1796
   4                                        3921
 
TOTAL:                                      6087

Code: Select all

Search space complexity of 6x6 checkers:
 
Pieces                                 Positions
 
   1                                          66
   2                                        2055
   3                                       40108
   4                                      549855
   5                                     5622786
   6                                    44447001
   7                                   273507984
   8                                  1294977024
   9                                  4627352224
  10                                 12134317536
  11                                 22071836160
  12                                 23385567744
 
TOTAL:                               63838220543

Code: Select all

Search space complexity of 8x8 checkers:
 
Pieces                                 Positions
 
   1                                         120
   2                                        6972
   3                                      261224
   4                                     7092774
   5                                   148688232
   6                                  2503611964
   7                                 34779531480
   8                                406309208481
   9                               4048627642976
  10                              34778882769216
  11                             259669578902016
  12                            1695618078654976
  13                            9726900031328256
  14                           49134911067979776
  15                          218511510918189056
  16                          852888183557922816
  17                         2905162728973680640
  18                         8568043414939516928
  19                        21661954506100113408
  20                        46352957062510379008
  21                        82459728874435248132
  22                       118435747136817856510
  23                       129406908049181900800
  24                        90072726844888186888
 
TOTAL:                     500995484682338672640

Code: Select all

Search space complexity of 10x10 checkers:
 
Pieces                                 Positions
 
   1                                         190
   2                                       17685
   3                                     1074760
   4                                    47955250
   5                                  1674983028
   6                                 47682277890
   7                               1137352566120
   8                              23192869318605
   9                             410524268090110
  10                            6382578818402089
  11                           87989763464416800
  12                         1083873425359341760
  13                        12005368645341329920
  14                       120198412703760821170
  15                      1092575843151836391300
  16                      9049666309745673032000
  17                     68515048604937281781000
  18                    475379572518154534810000
  19                   3029276415195634417600000
  20                  17760725575656125192000000
  21                  95948824611933020825000000
  22                 478161650645720819200000000
  23                2200046522344775945700000000
  24                9350432472816025261600000000
  25               36713074006549923917000000000
  26              133115326397483132130000000000
  27              445262840883963658540000000000
  28             1371642574772212368200000000000
  29             3881724488615763743800000000000
  30            10058981371592363051000000000000
  31            23772943355051015221000000000000
  32            50995058612905238248000000000000
  33            98724680895317275652000000000000
  34           171322901232003475730000000000000
  35           264234542214143615330000000000000
  36           358083405295857670100000000000000
  37           419266403291399983380000000000000
  38           412290102722075092800000000000000
  39           321162036032103771910000000000000
  40           166194017427075056870000000000000
 
TOTAL:        2301985676687843186100000000000000

Code: Select all

Search space complexity of 12x12 checkers:
 
Pieces                                           Positions
 
   1                                                   276
   2                                                 37554
   3                                               3358100
   4                                             221965215
   5                                           11565576024
   6                                          494737906204
   7                                        17866770453576
   8                                       555948664334415
   9                                     15138309678595620
  10                                    365142853574969778
  11                                   7878544541223823908
  12                                 153291387230276539140
  13                                2707618534799148813000
  14                               43662801981688688494000
  15                              645931511691892260850000
  16                             8802724917410556485700000
  17                           110909649438387386970000000
  18                          1296013672573706314400000000
  19                         14084337869231138030000000000
  20                        142693858756390721420000000000
  21                       1350666841700006762100000000000
  22                      11967135929240394607000000000000
  23                      99417334369031838387000000000000
  24                     775553125415954084980000000000000
  25                    5688685206156550498400000000000000
  26                   39279838694669275467000000000000000
  27                  255582344206340977730000000000000000
  28                 1568504818050325187700000000000000000
  29                 9086029355705177329200000000000000000
  30                49715022896568321309000000000000000000
  31               257083311352963984050000000000000000000
  32              1257008948607189878900000000000000000000
  33              5813619163416315720500000000000000000000
  34             25440487757700828592000000000000000000000
  35            105357183416258919400000000000000000000000
  36            412965952658829798710000000000000000000000
  37           1532103928105984316100000000000000000000000
  38           5379679211368140872400000000000000000000000
  39          17874793699412320016000000000000000000000000
  40          56183375135571075438000000000000000000000000
  41         166975941167484231770000000000000000000000000
  42         468914661255220899850000000000000000000000000
  43        1243209303449877642000000000000000000000000000
  44        3108203187846125212100000000000000000000000000
  45        7317597469409017769900000000000000000000000000
  46       16194468520263063611000000000000000000000000000
  47       33620848239656796749000000000000000000000000000
  48       65321141672118069939000000000000000000000000000
  49      118442904457559671140000000000000000000000000000
  50      199809257054351952610000000000000000000000000000
  51      312479646553190280410000000000000000000000000000
  52      451163220329919574750000000000000000000000000000
  53      598451915018177118190000000000000000000000000000
  54      724949033047696003910000000000000000000000000000
  55      795828911931557019870000000000000000000000000000
  56      783353690761126660310000000000000000000000000000
  57      680421707323268491230000000000000000000000000000
  58      507429862402632346710000000000000000000000000000
  59      306778202437354964490000000000000000000000000000
  60      126263942198161224990000000000000000000000000000
 
TOTAL:   5732895173614141674400000000000000000000000000000

Code: Select all

Search space complexity of 14x14 checkers:
 
Pieces                                                               Positions
 
   1                                                                       378
   2                                                                     70707
   3                                                                   8725780
   4                                                                 799139481
   5                                                               57929241510
   6                                                             3461859862083
   7                                                           175404849597864
   8                                                          7691261100679611
   9                                                        296458685575522470
  10                                                      10169104794502355793
  11                                                     313518377536489416280
  12                                                    8758967191789816846100
  13                                                  223265349271869315040000
  14                                                 5222600670210970329900000
  15                                               112670589594425226260000000
  16                                              2251465777178171552600000000
  17                                             41829988468555362268000000000
  18                                            724967185449953311750000000000
  19                                          11755288396043370881000000000000
  20                                         178800707753129052860000000000000
  21                                        2557075325937801437800000000000000
  22                                       34456448306752769309000000000000000
  23                                      438303566168658646900000000000000000
  24                                     5272339779764893814800000000000000000
  25                                    60066582532096819296000000000000000000
  26                                   649052076094110772510000000000000000000
  27                                  6660464193057871273500000000000000000000
  28                                 64986025936901763214000000000000000000000
  29                                603523179758669909070000000000000000000000
  30                               5340160608158823802100000000000000000000000
  31                              45060134677769713162000000000000000000000000
  32                             362882898105578873880000000000000000000000000
  33                            2791282260278363493700000000000000000000000000
  34                           20521227869427585325000000000000000000000000000
  35                          144290630421056727510000000000000000000000000000
  36                          970859912492248060710000000000000000000000000000
  37                         6254380150603841700100000000000000000000000000000
  38                        38594500337265519340000000000000000000000000000000
  39                       228225392513224362540000000000000000000000000000000
  40                      1293792661417993282200000000000000000000000000000000
  41                      7033542895568931544500000000000000000000000000000000
  42                     36679335615326097577000000000000000000000000000000000
  43                    183535058889649655040000000000000000000000000000000000
  44                    881379842450605645830000000000000000000000000000000000
  45                   4062882840651015762900000000000000000000000000000000000
  46                  17980342533445419587000000000000000000000000000000000000
  47                  76401971489122099753000000000000000000000000000000000000
  48                 311738128557488492760000000000000000000000000000000000000
  49                1221449083348785567600000000000000000000000000000000000000
  50                4595871103266384962700000000000000000000000000000000000000
  51               16605803452847073550000000000000000000000000000000000000000
  52               57614205525715048581000000000000000000000000000000000000000
  53              191928808054016336820000000000000000000000000000000000000000
  54              613818061433174277300000000000000000000000000000000000000000
  55             1884343151294882188800000000000000000000000000000000000000000
  56             5551569172133999194500000000000000000000000000000000000000000
  57            15692870772011663565000000000000000000000000000000000000000000
  58            42549424154314459916000000000000000000000000000000000000000000
  59           110621194928256941590000000000000000000000000000000000000000000
  60           275648632712866860930000000000000000000000000000000000000000000
  61           658008296331689767130000000000000000000000000000000000000000000
  62          1503869593713418651600000000000000000000000000000000000000000000
  63          3288452431609774703900000000000000000000000000000000000000000000
  64          6874210491237278764200000000000000000000000000000000000000000000
  65         13724406718552010012000000000000000000000000000000000000000000000
  66         26141510361125267267000000000000000000000000000000000000000000000
  67         47445370660288095834000000000000000000000000000000000000000000000
  68         81935460842444892497000000000000000000000000000000000000000000000
  69        134424701381415344440000000000000000000000000000000000000000000000
  70        209146544786479710500000000000000000000000000000000000000000000000
  71        307990258387688672000000000000000000000000000000000000000000000000
  72        428344881710970713500000000000000000000000000000000000000000000000
  73        561263161128863153220000000000000000000000000000000000000000000000
  74        690985230303674372540000000000000000000000000000000000000000000000
  75        796789162434472264360000000000000000000000000000000000000000000000
  76        857445467740233579820000000000000000000000000000000000000000000000
  77        857344057133513969630000000000000000000000000000000000000000000000
  78        792164236525224814910000000000000000000000000000000000000000000000
  79        671543709605070887820000000000000000000000000000000000000000000000
  80        517100368830120713220000000000000000000000000000000000000000000000
  81        356161619727417175860000000000000000000000000000000000000000000000
  82        213647064501130921220000000000000000000000000000000000000000000000
  83        105477852925714623980000000000000000000000000000000000000000000000
  84         36027721472797545945000000000000000000000000000000000000000000000
 
TOTAL:     7717880162220473943600000000000000000000000000000000000000000000000

A board of size nxn has n²/2 - n pieces at most. Summarizing:

Code: Select all

* Upper bound
Board     Positions *
 4x4         6087
 6x6      6.3838e+10
 8x8      5.0100e+20
10x10     2.3020e+33
12x12     5.7329e+48
14x14     7.7179e+66

I am aware that there is not a 100% match between Schaeffer's numbers and my own results in 8x8 checkers.

There are simple fits with high R²:

Code: Select all

x: size (4, 6, 8, ...)
y: log10(positions)

Fit 1:
y = 0.34619771x² + 0.08326459x - 2.11415228
R² = 0.99999860

Code: Select all

x: playable squares (8, 18, 32, ...) --> size n (board nxn); playable squares = n²/2
y: log10(positions)

Fit 2:
y = 0.70140962x - 1.78242938
R² = 0.99999425

Code: Select all

x: maximum number of pieces (n²/2 - n)
y: log10(positions)

Fit 3:
y = 0.78622525x + 1.36380707
R² = 0.99952407

Just for fun, extrapolating huge boards of 16x16, 18x18 and 20x20:

Code: Select all

16x16:
Fit 1 ~ 6.9935e+87 positions (upper bound)
Fit 2 ~ 9.9541e+87 positions (upper bound)
Fit 3 ~ 2.6365e+89 positions (upper bound)

18x18:
Fit 1 ~ 3.5700e+111 positions (upper bound)
Fit 2 ~ 7.0134e+111 positions (upper bound)
Fit 3 ~ 3.8040e+114 positions (upper bound)

20x20:
Fit 1 ~ 1.0721e+138 positions (upper bound)
Fit 2 ~ 3.1586e+138 positions (upper bound)
Fit 3 ~ 7.6622e+142 positions (upper bound)

I hope no typos. Differences are very big between different fits, specially with fit 3, which also has the lower R². Anyway, you can compare those upper bounds with the Shannon number and see the complexity of other board game such as checkers. Chess is not the only board game.

------------------------

Aart, Paul... any chance of Perft(29) of English draughts?

Regards from Spain.

Ajedrecista.