Draughts
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 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, 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).
