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.