Checkers 'solved' after years of number crunching

  • 19:00 19 July 2007
  • NewScientist.com news service
  • Justin Mullins
Printable versionEmail to a friendRSS FeedSyndicate
 
Tools
digg thisAdd My YahooAdd Google Reader reddit submitNewsvineciteulike submit
 

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 24 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)

Add a comment
Comment subject
Comment
No HTML except lower case italic tags or lower case bold tags, please:
<i> or <b>
Your name
Your email
 

We need your email in case we need to contact you about the comment. We will not use it for any other purpose.

 
   
Printable versionEmail to a friendRSS FeedSyndicate
Cover of latest issue of New Scientist magazine
  • For exclusive news and expert analysis every week subscribe to New Scientist Print Edition
  • For what's in New Scientist magazine this week see contents
  • Search all stories
  • Contact us about this story
  • Sign up for our free newsletter
 
Subscriber Login
Subscriptions