4/29/2007

Jonathan Schaeffer and his team at the University of Alberta announced on April 29, 2007 that the game of checkers was "solved". Perfect play led to a draw.

"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.' " (http://www.newscientist.com/article/dn12296-checkers-solved-after-years-of-number-crunching.html, accessed 01-24-2010).

Based on this proof, Schaeffer's checkers-playing program Chinook, could no longer be beaten. The best an opponent could hope for is a draw.