Professor Jonathan Schaeffer has finally mounted checkers up on his wall along with the moose, bear, and whatever else they mount on walls in Alberta. After nearly 20 years his famous checker champion program Chinook has broken the game down. As he points out in several items, this isn't a mathematical proof. It is a computational proof that shows through brute force analysis that the game is drawn with best play and that his program will never lose. The bottom of this ChessBase item links to some of the coverage.
I met Professor Schaeffer a few years ago at the Junior-Kasparov match (I was doing commentary and he was on the rules and appeal committee) and also greatly enjoyed his book on Chinook and its matches against checkers legend Marion Tinsley, "One Jump Ahead."
From the project website:
Checkers has a search space of 5x10^20, a daunting number. Almost continuously since 1989 (with a gap in the 1997 to 2001 period), dozens of computers have been working around the clock to solve the game. On April 29, 2007, we were pleased to announce that checkers is now solved. From the standard starting position, Black (who moves first) is guaranteed a draw with perfect play. White (moving second) is also guaranteed a draw, regardless of what Black plays as the opening move. Checkers is the largest game that has been solved to date, more than one million times larger than Connect Four and 100 million times larger than Awari.
I did a brief email interview with Professor Schaeffer yesterday.
1) How close to your original and updated predictions for completion was this date? How much did the process change during this time, or was it more a question of adding more firepower to the basic process you came up with at the start?
In 1989 I was naive in estimating the amount of work needed to solve checkers. I was grossly underestimating the size of the problem for a long time. Not until we started making real progress at propagating proven values to positions near the start of the game (in late 2004) did I know for sure that we could solve checkers within a few years. At the time I thought it would take another 5-10 years. Now I was too pessimistic. It ended up taking 2.5 years more.
So much for my limited ability to make reliable predictions :(
2) Aren't the people quoted in some of the coverage as saying 2060 for solving chess being dunderheads and picking numbers out of thin air? Or is that actually based on a potential timeline of technological development? It sure ain't gonna happen by then by Moore's Law. From my understanding, mostly poached from Nunn, we'd need as many computers as there are atoms in the solar system working on it for a few [insert very long time here] to do it, the numbers are so big.
I have been asked many times when chess will be solved and I refuse to say anything other than it can't be done for a very long time unless there is a fundamentally new breakthrough. The computing models that we have today -- even if they are a billion times faster -- won't make a dent in chess. We need something *much* better. The answer might be quantum computing, but this technology is still in its infancy and remains unproven.
3) Since poker is a game of bluffing and calculated irrationality as much as it is one of odds and calculation, can a computer ever dream [sic?] of beating the best humans? Or will it reveal that those factors really aren't as important as we'd like to think?
Find out next week...
By an odd-coincidence, we have the First Man-Machine Poker Match next week. Two US pros are playing our software (the computer world champion) in a $50K event. We will be competitive, but I am not sure we are good enough to win yet. http://www.cs.ualberta.ca/~games/poker/man-machine/
4) Do you like to play checkers? Play at all anymore?
I never played checkers, except to test the program. Chess is my first love (ooops, besides my wife, that is). Checkers is a great game, but I know what it takes to master chess and I don't have the heart to repeat that process with checkers.
5) Thinking of writing a sequel to One Jump Ahead now? Great book.
I want to do a second edition. The publisher has given me the OK, but now I have to find the time.