TOPICS
Search

Checkers


Checkers is a two-player game with the most common variant played on an 8×8 checkerboard with each player starts with twelve pieces of a fixed color on opposite sites of the board. The most common variant of checkers is so-called "pool checkers," also called "Spanish pool checkers," draughts or draught (in the United Kingdom and some other countries), American checkers, and straight checkers. Play proceeds alternately between players, where all pieces may initially only move and capture in a forward diagonal direction. The allowable direction of play is modified for a piece if it is "crowned" by reaching the other side of the board, after which it may move either forwards or backwards. An opponent's piece may be captured by jumping over it diagonally, and the game is won by capturing all the opponents pieces or leaving the opponent with no legal moves.

The most widely available sets of checkers consist of black and red boards and pieces. In tournament play, however, the colors of the pieces are red and white instead of red and black and the colors of the checkerboard squares are usually olive green and buff, where "buff" is a color variously defined as a moderate orange yellow or a light to moderate yellow. (The colors of the squares are, however, are still referred to as "black" and "red.")

Schroeppel (1972) estimated that there are about 10^(12) possible positions. However, this disagrees with the estimate of Jonathan Schaeffer of 5×10^(20) plausible positions, with 10^(18) reachable under the rules of the game.

Checkers on an n×n board is known to be exptime complete (Fraenkel et al. 1978; Robson 1984).

Computer checkers programs have now become extremely good (Schaeffer 1997), and a program called Chinook has become the first computer program to win a world championship (University of Alberta Department of Computing Science). Schaeffer et al. (2007) solved checkers, proving that if both sides play a perfect game, the result will always be a draw. Schaeffer used multiple computers (an average of 50 of them) to "weakly" solve checkers, storing all the possible positions when there are ten or fewer pieces on the board and then using heuristic search algorithms that could determine the result of a perfect game. However, only 10^(14) positions were needed to be evaluated to "solve" checkers and confirm the commonly held theory that if both players play a perfect game the result will be a draw.

Depending on how they are counted, the number of Eulerian cycles on an n×n checkerboard are either 1, 40, 793, 12800, 193721, ... (OEIS A006240) or 1, 13, 108, 793, 5611, 39312, ... (OEIS A006239).


See also

Board, Chess, Chessboard, Connect-Four, Conway's Soldiers, Peg Solitaire

Explore with Wolfram|Alpha

References

Fraenkel, A. S.; Garey, M. R.; Johnson, D. S.; Schaefer, T.; and Yesha, Y. "The Complexity of Checkers on an n×n Board--Preliminary Report." In Proc. 19th Ann. Symp. Foundations of Computer Science (Ann Arbor, MI, Oct. 1978). Long Beach, CA: IEEE Computer Soc., pp. 55-64, 1978.Hopper, M. Win at Checkers. New York: Dover, 1956.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.Olson, A. H. "Pool Checkers: Rules of Play." http://ourworld.compuserve.com/homepages/Arthur_H_Olsen/poolchec.htm.Parlett, D. S. Oxford History of Board Games. Oxford, England: Oxford University Press, 1999.Robson, J. M. "n by n Checkers Is Exptime Complete." SIAM J. Comput. 13, 252-267, 1984.Schaeffer, J. One Jump Ahead: Challenging Human Supremacy in Checkers. New York: Springer-Verlag, 1997.Schaeffer, J.; Burch, N.; Bjornsson, Y.; Kishimoto, A.; Muller, M.; Lake, R.; Lu, P.; and Sutphen, S. "Checkers is Solved." Science 317, 1518-1522, 2007.Schaeffer, J.; Björnsson, Y.; Burch, N.; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; and Sutphen, S. "Solving Checkers." 2005. http://www.cs.ualberta.ca/~jonathan/Papers/Papers/ijcai05checkers.pdf.Schaeffer, J. and Lake, R. "Solving the Game of Checkers." In Games of No Chance, Proc. MSRI Workshop on Combinatorial Games, July, 1994 (Ed. R. J. Nowakowski.) Cambridge, England: Cambridge University Press, pp. 119-133, 1996.Schroeppel, R. Item 93 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 35, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/proposed.html#item93.Sloane, N. J. A. Sequences A006239/M4909 and A006240/M5271 in "The On-Line Encyclopedia of Integer Sequences."Sreedhar, S. "Checkers, Solved!" IEEE Spectrum Online. July 19, 2007. http://www.spectrum.ieee.org/jul07/5379.University of Alberta Department of Computing Science. "Chinook: World Man-Machine Checkers Champion." http://www.cs.ualberta.ca/~chinook/.

Referenced on Wolfram|Alpha

Checkers

Cite this as:

Weisstein, Eric W. "Checkers." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Checkers.html

Subject classifications