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 pieces on an 8-by-8 checkerboard, and he or she moves a piece by sliding it forward and diagonally one square. A piece captures an enemy by jumping diagonally across it into an open square. The last player with pieces on the board wins.
Beginning in 1989, Schaeffer used as many as 200 computers simultaneously to grind out the problem. He started with the endgame, putting just two pieces on the board and calculating every possible outcome for each position they might assume. Then he did the same for three pieces, then four, and so on up to 10. At that point, 39 trillion positions were possible.
Each step in this process took 10 times as much work as the previous step, so continuing in this way was impractical. Instead, Schaeffer turned to the beginning of a game, calculating all the positions that could result from one move, then two moves, then three moves, and so on. The program continued the game until there were only 10 pieces left, at which point it checked its database of endgames to find the outcome. Ultimately, the analysis included somewhere between 100 trillion and a quadrillion checkers positions. Schaeffer and his colleagues report their results in the Sept. 14 Science.
“We’re pushing the frontiers of what computers can solve,” Schaeffer says. “If we had waited 10 or 20 years, the machines would be faster,” making the problem easy. As it was, he and his team had to invent clever ways of storing and searching the data.
For example, they stored the outcomes for the 39 trillion possible positions for endgames in a mere 237 gigabytes of computer-storage space, an average of 154 positions per byte. The mathematicians are now applying these techniques to bioinformatics, looking for ways to manage the massive quantity of data generated by the sequencing of genomes.
“It’s just a prodigious amount of work,” says Ken Thompson of Mountain View, Calif.–based Google, who in 1983 developed the first master-level chess computer program. Thompson says that solving checkers brings computers a step closer to being able to solve more-complicated games, such as chess or go. However, he estimates that those tasks will take another 100 years to complete. Chess has about 1020 times as many positions as checkers does, Schaeffer says.
