Checkers is only the latest and most complex game to be "solved" using computer programs.
Perhaps the best-known such game is Connect Four, which involves placing four pieces in a row (while preventing your opponent from doing the same). The researchers behind the Chinook checkers-playing program say they faced a challenge that was about a million times more complex than Connect Four, due to the wider range of possible moves.
You can play Chinook, review the proof, watch a video and listen to a podcast by clicking to the University of Alberta's Chinook Web page.
Here's a selection of other solved games, as listed by the Chinook team:
- An African board game in which players distribute stones or other playing pieces around rows of "pits" and captures stones according to the rules of the game. The game ends when one player captures all the opponent's stones. The University of Amsterdam has a Web site about the solution in 2002. If both players avoid making mistakes, the game would end in a draw.
- The game was solved independently in 1988 by James Allen and Victor Allis. This PDF file lays out Allis' solution, which showed that the first player is guaranteed to win if he or she plays flawlessly. This was what's known as a "weak" solution. More recently, John Tromp came up with a "strong" solution, which means each player's position can be analyzed to the eventual outcome at any point in the game.
- This Japanese pieces-on-a-grid game, sometimes known in English as "Connect Five," was solved by Victor Allis and his colleagues in 1994. The first player always wins if she or he doesn't make a mistake. The solution is laid out in this PDF file and this book-length analysis of several games including Qubic (see below).
- This is one of the oldest-known games, with its origins traced back to ancient Egypt in about 1400 B.C. Pegs are moved around a square board to "trap" the opponent. The game was solved in 1994, with Ralph Gasser showing that perfect play on both sides would end in a draw.
- Basically a three-dimensional tic-tac-toe game played using a 4-by-4-by-4 cube, Qubic was weakly solved in 1980 by Oren Patashnik and in 1994 by Victor Allis. Assuming perfect play, the first player always wins.
Among the partially solved games listed by the University of Alberta team, for limited play spaces, are:
- (7 x 7)
- (5 x 5)
- (5 x 5)
- (6 x 6)
This report was based on information from the University of Alberta.
