|
Checkers 'solved' after years of number crunching
* 19:00 19 July 2007
* NewScientist.com news service
* Justin Mullins
The ancient game of checkers (or draughts) has been pronounced dead. The game was killed by the publication of a mathematical proof showing that draughts always results in a draw when neither player makes a mistake. For computer-game aficionados, the game is now "solved".
Draughts is merely the latest in a steady stream of games to have been solved using computers, following games such as Connect Four, which was solved more than 10 years ago.
The computer proof took Jonathan Schaeffer, a computer-games expert at the University of Alberta in Canada, 18 years to complete and is one of the longest running computations in history.
Draughts is played on an 8 x 8 chequered board with 16 pieces. This leads to 1020 different possible board positions. A player's pieces capture the opponent's by jumping over them until all are removed. Large numbers of pieces are quickly removed from play towards the end of a game.
Endgame database
The crucial part of Schaeffer's computer proof involved playing out every possible endgame involving fewer than 10 pieces. The result is an endgame database of 39 trillion positions. By contrast, there are only 19 different opening moves in draughts. Schaeffer's proof shows that each of these leads to a draw in the endgame database, providing neither player makes a mistake.
Schaeffer was able to get his result by searching only a subset of board positions rather than all of them, since some of them can be considered equivalent. He carried out a mere 1014 calculations to complete the proof in under two decades. "This pushes the envelope as far as artificial intelligence is concerned," he says.
At its peak, Schaeffer had 200 desktop computers working on the problem full time, although in later years he reduced this to 50 or so. "The problem is such that if I made a mistake 10 years ago, all the work from then on would be wrong," says Schaeffer. "So I've been fanatical about checking for errors."
Schaeffer believes the techniques he has developed could be applied to many real-world problems. He gives the example of scheduling the time and work required to build a complex machine such as the space shuttle. "With these techniques, you could optimise the use of your resources to build the shuttle for the least time or cost," he says.
Inevitable result
Schaeffer has also released an updated version of a draughts-playing programme called Chinook. In the 1990s, this program failed to beat the then world champion Marion Tinsley, who is widely regarded as the greatest Checkers player ever. Before his death, in 1995, Tinsley lost only 9 games in a 45-year playing career.
"I think Tinsley would be wistful about the proof," says Schaeffer.
The revamped Chinook, which is available online, cannot now be beaten. "The best result you can get is a draw," he admits.
David Levy, president of the International Computer Games Association in London, UK, says he isn't planning to play against Chinook. "There would be a certain inevitability about the result."
Journal reference: Science (DOI: 10.1126/science.1144079)
|