English Draughts

English draughts, also called American checkers, is a variant of checkers played on an checkerboard with twelve pieces per player (World Checkers/Draughts Federation).

Players move alternately, and uncrowned pieces move and capture only diagonally forwards. A piece is crowned when it reaches the opposite end of the checkerboard, after which it can move and capture diagonally forwards or backwards. An ordinary move is to an adjacent unoccupied square. Captures are made by jumping over an adjacent opposing piece to an unoccupied square beyond it, and are compulsory. A multiple capture must be completed, except that reaching the crowning row ends an uncrowned piece's turn. When several captures are available, the player may choose any one and need not maximize the number of pieces captured. The game is won by capturing all the opponent's pieces or leaving the opponent with no legal moves (World Checkers/Draughts Federation).

The World Checkers/Draughts Federation tournament rules specify red and white pieces and a green and white (or off-white/cream) checkerboard.

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.

For English draughts generalized to an board, determining whether a player can force a win from a given position is an EXPTIME-complete problem (Fraenkel et al. 1978, Robson 1984).

Computer programs for English draughts have become extremely good (Schaeffer 1997), and a program called Chinook became the first computer program to win a world championship (University of Alberta Department of Computing Science). Schaeffer et al. (2007) solved English draughts, proving that if both sides play a perfect game from the standard initial position, the result will be a draw. Schaeffer used multiple computers (an average of 50 of them) to "weakly" solve the game, 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" the game and confirm the commonly held theory that if both players play a perfect game from the standard initial position the result will be a draw.