Checkers AI now unbeatable

It's unthinkable to most that chess would ever fall victim to something similar. I'm not so sure. I once took a computer course on the game of chess. On average there are about 42 choices per move if I remember correctly. Some 30 or 50 moves to the average game. As you can see at first glance chess seems impossible to program. You think you are dealing with 42**50 which could never be handled. Not at all like checkers. I bet somebody somewhere will figure out how to do it though. Say for example they might work backwards from different end game scenarios. So certain piece combinations, positioned in about any way, guarantees a win. This would eliminate a large percentage or possible choices. Likewise forced trades could eliminate many choices. As more creative types break the game of chess into various defined components maybe what's left could be totally handled. I bet in another hundred years they'll have Chess completely worked out.

Games capture imagination allowing people to put their very best into it.

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
Related Articles

* Robot learns to play dirty Scrabble
* 16 January 2007
* Software learns when it pays to deceive
* 30 May 2007
* Producing the ultimate game-playing bots
* 29 July 2006

* Search New Scientist
* Contact us

Web Links

* Chinook
* Jonathan Schaeffer
* International Computer Games Association



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)