TITLE: Checkers -- Solved! AUTHOR: Eugene Wallingford DATE: July 19, 2007 3:03 PM DESC: ----- BODY: I told the story of Jonathan Schaeffer's SIGCSE talk on the history of Chinook back in March. In that talk, he said that his team was a few months away from solving checkers. They have done it, as this Scientific American article reports:
Jonathan Schaeffer's quest for the perfect game of checkers has ended. ... after putting dozens of computers to work night and day for 18 years -- jump, jump, jump -- he says he has solved the game -- king me!. "The starting position, assuming no side makes a mistake, is a draw," he says.
The proof is on-line, but the best proof is Chinook, Schaeffer's checker-playing program that is now the one player in the wold that will never lose a game of checkers. You can still play Chinook on-line, if you got game. This is easily the most complex game to be solved by computation, and the result depends on several different areas of computer science: AI, distributed computing, parallel programming, and databases most prominent among them. Chinook's endgame database now contains approximately 39 trillion positions and is the practical keystone of its play. Chinook searches deep, like many masters, but now it can relatively quickly terminate its analysis not with a heuristic static evaluation function but a database look-up that guarantees correctness. So even analytical mistakes early in the game can be corrected for as soon as the program reaches a solved position. I am a game player, primarily chess, and I know some folks who will call this database an unfair advantage. But the best game players I know have always capitalized on their better memories and better computational skills; I don't know why Chinook or any other program should be held to a different standard. But what a memory that is! I am finally ready to believe that, if Chinook were to play Marion Tinsley -- may he rest in peace [*] -- in another match, it would not lose, and most likely would win. Even the great Tinsley made an occasional error. And if you have not yet read Schaeffer's book One Jump Ahead on my earlier recommendation, well, shame on you. Do so now. But is checkers really dead, as the popular press is now saying? Not at all. It is still a fun game for people to play, and a great mental battlefield. It's just that now we have an objective standard against which to measure ourselves. ---- [*] Or should that be "rest in piece"? -----