Checkers is a two-player game with the most common variant played on an 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 possible positions. However, this disagrees with the
estimate of Jonathan Schaeffer of plausible positions, with reachable under the rules of the game.
Checkers on an
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 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
checkerboard are either 1, 40, 793, 12800, 193721, ... (OEIS A006240)
or 1, 13, 108, 793, 5611, 39312, ... (OEIS A006239).