Computers can now play a flawless game of checkers. A calculation that began almost 2 decades ago shows that if both players make perfect moves, the game will be a draw every time. The achievement makes checkers the most complicated game to have been solved completely.
Computers have been able to beat people at checkers since 1994, when a program called Chinook won the checkers world championship. The program, written by computer scientist Jonathan Schaeffer of the University of Alberta in Edmonton, used rules of thumb to guess the best available move, a method that imitates how people play. Now, Schaeffer has removed the guesswork with a program that examined every possible position that can occur on a checkerboard to find the best move every time.
The brute-force calculation underlying the new program was conceptually simple but logistically demanding, because checkers has approximately 500 billion billion (5 x 1020) possible positions. Each player starts with 12 piec