perft for 8x8 checkers

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
abik
Posts: 770
Joined: Fri Dec 01, 2006 9:46 pm
Location: Mountain View, CA, USA
Full name: Aart Bik
Contact:

Re: perft for 8x8 checkers

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&#40;27&#41;
-------------------------------
12-16    =  516399283859880203
11-16    =  519502096014967805
11-15    =  476666239516455180
10-15    =  468705060101275533
10-14    =  400425747281243848
9-14    =  486493422418651579
9-13    =  631652334435528457
-------------------------------
perft&#40;27&#41; = 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
Posts: 1585
Joined: Wed Jul 13, 2011 7:04 pm
Contact:

Re: Perft for 8x8 checkers.

Hello Aart:
abik wrote: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&#40;27&#41;
-------------------------------
12-16    =  516399283859880203
11-16    =  519502096014967805
11-15    =  476666239516455180
10-15    =  468705060101275533
10-14    =  400425747281243848
9-14    =  486493422418651579
9-13    =  631652334435528457
-------------------------------
perft&#40;27&#41; = 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
Posts: 89
Joined: Mon Jun 13, 2011 10:09 am

Re: perft for 8x8 checkers

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
Posts: 770
Joined: Fri Dec 01, 2006 9:46 pm
Location: Mountain View, CA, USA
Full name: Aart Bik
Contact:

Re: perft for 8x8 checkers

ibid wrote: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
Posts: 770
Joined: Fri Dec 01, 2006 9:46 pm
Location: Mountain View, CA, USA
Full name: Aart Bik
Contact:

Re: perft for 8x8 checkers

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&#40;28&#41;
12-16 = 2400708339858199191
11-16 = 2431386196712611878
11-15 = 2231787529331259810
10-15 = 2186446356811761737
10-14 = 1872427919495823777
9-14 = 2285893686261887442
9-13 = 2969067990365356900
--------------------------- +
16377718018836900735   = perft&#40;28&#41;
``````

ibid
Posts: 89
Joined: Mon Jun 13, 2011 10:09 am

Re: perft for 8x8 checkers

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
Posts: 770
Joined: Fri Dec 01, 2006 9:46 pm
Location: Mountain View, CA, USA
Full name: Aart Bik
Contact:

Re: perft for 8x8 checkers

ibid wrote: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
Posts: 1585
Joined: Wed Jul 13, 2011 7:04 pm
Contact:

Re: Perft for 8x8 checkers.

Hello again:
abik wrote: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&#40;28&#41;
12-16 = 2400708339858199191
11-16 = 2431386196712611878
11-15 = 2231787529331259810
10-15 = 2186446356811761737
10-14 = 1872427919495823777
9-14 = 2285893686261887442
9-13 = 2969067990365356900
--------------------------- +
16377718018836900735   = perft&#40;28&#41;
``````
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&#40;29&#41; = bound&#40;29&#41; * factor&#40;29&#41;
BF&#40;29&#41; = Perft&#40;29&#41;/Perft&#40;28&#41;

Factor&#40;29&#41; ~ 0.9958; Perft&#40;29&#41; ~ 7.6113e+19 ---> BF&#40;29&#41; ~ 4.6473
Factor&#40;29&#41; ~ 0.9967; Perft&#40;29&#41; ~ 7.6182e+19 ---> BF&#40;29&#41; ~ 4.6515
Factor&#40;29&#41; = 1     ; Perft&#40;29&#41; ~ 7.6434e+19 ---> BF&#40;29&#41; ~ 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
Posts: 770
Joined: Fri Dec 01, 2006 9:46 pm
Location: Mountain View, CA, USA
Full name: Aart Bik
Contact:

Re: Perft for 8x8 checkers.

Ajedrecista wrote: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
Posts: 1585
Joined: Wed Jul 13, 2011 7:04 pm
Contact:

Search space complexity of the game of nxn checkers.

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&#58;

Pieces                                 Positions

1                                          28
2                                         342
3                                        1796
4                                        3921

TOTAL&#58;                                      6087``````

Code: Select all

``````Search space complexity of 6x6 checkers&#58;

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&#58;                               63838220543``````

Code: Select all

``````Search space complexity of 8x8 checkers&#58;

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&#58;                     500995484682338672640``````

Code: Select all

``````Search space complexity of 10x10 checkers&#58;

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&#58;        2301985676687843186100000000000000``````

Code: Select all

``````Search space complexity of 12x12 checkers&#58;

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&#58;   5732895173614141674400000000000000000000000000000``````

Code: Select all

``````Search space complexity of 14x14 checkers&#58;

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&#58;     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&#58; size &#40;4, 6, 8, ...)
y&#58; log10&#40;positions&#41;

Fit 1&#58;
y = 0.34619771x² + 0.08326459x - 2.11415228
R² = 0.99999860``````

Code: Select all

``````x&#58; playable squares &#40;8, 18, 32, ...) --> size n &#40;board nxn&#41;; playable squares = n²/2
y&#58; log10&#40;positions&#41;

Fit 2&#58;
y = 0.70140962x - 1.78242938
R² = 0.99999425``````

Code: Select all

``````x&#58; maximum number of pieces &#40;n²/2 - n&#41;
y&#58; log10&#40;positions&#41;

Fit 3&#58;
y = 0.78622525x + 1.36380707
R² = 0.99952407``````
Just for fun, extrapolating huge boards of 16x16, 18x18 and 20x20:

Code: Select all

``````16x16&#58;
Fit 1 ~ 6.9935e+87 positions &#40;upper bound&#41;
Fit 2 ~ 9.9541e+87 positions &#40;upper bound&#41;
Fit 3 ~ 2.6365e+89 positions &#40;upper bound&#41;

18x18&#58;
Fit 1 ~ 3.5700e+111 positions &#40;upper bound&#41;
Fit 2 ~ 7.0134e+111 positions &#40;upper bound&#41;
Fit 3 ~ 3.8040e+114 positions &#40;upper bound&#41;

20x20&#58;
Fit 1 ~ 1.0721e+138 positions &#40;upper bound&#41;
Fit 2 ~ 3.1586e+138 positions &#40;upper bound&#41;
Fit 3 ~ 7.6622e+142 positions &#40;upper bound&#41;``````
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.