Checkers

Beeler et al. (1972, Item 93) estimated that there are about possible positions. However, this disagrees with theestimate of Jon Schaeffer of plausible positions, with 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.,), there is hope that some day checkers may be solved (i.e., it may be possible to guarantee a win for the firstplayer to move before the game is even started; Dubuque 1996).

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

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. SequencesA006239/M4909and A006240/M5271in ``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.

• Ore's Theorem
• Orientable Surface
• Orientation (Plane Curve)
• Orientation-Preserving
• Orientation-Reversing
• Orientation (Vectors)
• Origami
• Origin
• Ornstein's Theorem
• Orr's Theorem
• Orthic Triangle
• Orthobicupola
• Orthobirotunda
• Orthocenter
• Orthocentric Coordinates
• Orthocentric Quadrilateral
• Orthocentric System
• Orthocupolarotunda
• Orthodrome
• Orthogonal Array
• Orthogonal Basis
• Orthogonal Circles
• Orthogonal Curves
• Orthogonal Functions
• Orthogonal Group