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 鈥渟olved鈥�.
Draughts is merely the latest in a steady stream of games to have been solved using computers, following games such as , which was solved more than 10 years ago.
The computer proof took , 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.
Advertisement
Draughts is played on an 8 x 8 chequered board with 24 pieces. This leads to 1020 different possible board positions. A player鈥檚 pieces capture the opponent鈥檚 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鈥檚 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鈥檚 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. 鈥淭his 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. 鈥淭he problem is such that if I made a mistake 10 years ago, all the work from then on would be wrong,鈥� says Schaeffer. 鈥淪o I鈥檝e 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. 鈥淲ith 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 , 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.
鈥淚 think Tinsley would be wistful about the proof,鈥� says Schaeffer.
The revamped Chinook, which is available online, cannot now be beaten. 鈥淭he best result you can get is a draw,鈥� he admits.
David Levy, president of the in London, UK, says he isn鈥檛 planning to play against Chinook. 鈥淭here would be a certain inevitability about the result.鈥�
Journal reference: (DOI: 10.1126/science.1144079)
