brainwagon

I might actually get to constructing an endgame database for checkers sometime soon. To start, I decided to try to write code to reproduce the table that appears in Schaeffer’s paper on solving checkers. It basically is just a five nested loop that computes a big sum of some fairly obvious combinatorial terms. So, I coded it up in python, and ran it. It produced the numbers I was expecting, but slowly. Really slowly. Unacceptably slowly. Like well over an hour before I killed it.

Part of the code computes the binomial coefficients. I put in some code to memoize those numbers (don’t recalculate, just look them up in a dictionary if you’ve computed them before). Bam! 2 seconds later, and I had the following table.

 N     possible positions    
------------------------------
 1                         120
 2                       6,972
 3                     261,224
 4                   7,092,774
 5                 148,688,232
 6               2,503,611,964
 7              34,779,531,480
 8             406,309,208,481
 9           4,048,627,642,976
10          34,778,882,769,216
11         259,669,578,902,016
12       1,695,618,078,654,976
13       9,726,900,031,328,256
14      49,134,911,067,979,776
15     218,511,510,918,189,056
16     852,888,183,557,922,816
17   2,905,162,728,973,680,640
18   8,568,043,414,939,516,928
19  21,661,954,506,100,113,408
20  46,352,957,062,510,379,008
21  82,459,728,874,435,248,128
22 118,435,747,136,817,856,512
23 129,406,908,049,181,900,800
24  90,072,726,844,888,186,880
------------------------------
   500,995,484,682,338,672,639