Checkers, in its English version called Draughts, is played on an 8 × 8 board and not 10 × 10 like the similar french Jeu de Dames. It is a very popular game in the Anglo-Saxon world, as popular as Chess, Go or Othello. Of these four games, it was the most likely to lead to a final win against the computer. Hope confirmed: a few months ago, a team of researchers from the Canadian University of Alberta unveiled an optimal strategy for this game of English Checkers.
The game of Checkers is played on a 64 squares checkerboard (a). 12 white pieces and 12 black ones are placed on each side. The numbering of the checkerboard boxes is used to describe the position of the pieces. The movement of a piece must always be made on the black squares, diagonally one square at a time. A pawn takes an opponent’s piece by jumping over it. The square of arrival must be empty. Several takes can be made successively by the same piece at the same time.
Pawns cannot take back. When a piece arrives on the extreme opposing line of the board, it becomes King.
Unlike chess pieces, the Checkers ones do not “fly”: a king must act as a simple piece and jump one by one by landing behind each pawn taken. But, a king can move and take backward. When a take is possible, the player is forced to make it. When multiple takes are possible, the player is not obliged to choose the longest but must make the chosen take until the end. The game stops when a player has no more pieces or can no longer move; the other player wins in this case.
Checkers against the computer
A machine can beat human players at board games by playing well enough for the human player to lose or draw, every time he plays against the computer. The game of English Checkers has been in this situation since 1994. The game of Chess has been similarly mastered since the famous game between Garry Kasparov and the machine Deeper Blue in May 1997. The superiority of the machine over the man in Chess has been confirmed in December 2006 by the Deep Fritz program’s victory against the reigning world champion Vladimir Kramnik.
However, in theory, nothing can prevent a particularly perceptive human player from developing a game strategy exploiting the weaknesses of the program and thus succeeding in beating it. The algorithms used to write these top-level programs are based on “heuristics”, processes that work well in general, but which cannot be guaranteed to work every time. A good game is not a perfect game.
To make programs that win infallibly, finer analytical work is essential. You have to sort of plan all the possible moves during a game. The machine thus irreparably beat the human player in only a few simple games, including the lice on a 15 × 15 chessboard (also called Go-Moku ) in 1996.