Checkers

Beeler et al. (1972, Item 93) estimated that there are about $10^{12}$ possible positions. However, this disagrees with the estimate of Jon Schaeffer of $5\times 10^{20}$ plausible positions, with $10^{18}$ reachable under the rules of the game. Because ``solving'' checkers may require only the Square Root of the number of positions in the search space (i.e., $10^9$), there is hope that some day checkers may be solved (i.e., it may be possible to guarantee a win for the first player to move before the game is even started; Dubuque 1996).

Depending on how they are counted, the number of Eulerian Circuits on an $n\times n$ checkerboard are either 1, 40, 793, 12800, 193721, ... (Sloane's A006240) or 1, 13, 108, 793, 5611, 39312, ... (Sloane's A006239).

See also Checkerboard, Checker-Jumping Problem

References

Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

Dubuque, W. ``Re: number of legal chess positions.'' math-fun@cs.arizona.edu posting, Aug 15, 1996.

Kraitchik, M. ``Chess and Checkers'' and ``Checkers (Draughts).'' §12.1.1 and 12.1.10 in Mathematical Recreations. New York: W. W. Norton, pp. 267-276 and 284-287, 1942.

Schaeffer, J. One Jump Ahead: Challenging Human Supremacy in Checkers. New York: Springer-Verlag, 1997.

Sloane, N. J. A. Sequences A006239/M4909 and A006240/M5271 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.