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