Solving Checkers

I attended a talk today at the Technion by Jonathan Schaeffer from the University of Alberta in Canada, the person behind Chinook. Chinook is practically the world champion in the game of checkers, if only the world checkers federations would allow computer programs to compete.

Solving checkers, according to Schaeffer, turns out to be much more a laborious process of solving lots of hardware problems, rather than artificial intelligence algorithms. It took 19 years to build a database of board positions sufficiently large to solve from any given position (and there are 5 billion billion such positions, mind you). Since relying on a wrong piece of data could be catastrophic to the complex calculation, there was a lot of dealing with disk failures, network failures, grid calculation. Sounds a lot like running a large-scale search engine, only that search engines can afford to say “Oops…”.

In one case, Schaeffer, who started out in 1989, reached the 32-bit limit in his files. He started refactoring his code and databases to accommodate 64-bit pointer arithmetic, but ended up deciding it’s better to wait 3 more years for 64-bit to become mainstream. So in fact sitting idle for 3 years can do wonders to your projects. In another case, a bug discovered in 2005 was traced back to data created in 1992, which forced a re-calculation of all the data that relied on it. Bummer.

But what I truly found most interesting was the human story behind it all. Chinook’s major opponent was the late Marion Tinsley, world champion and undisputably the best human checkers player ever, who in his career of thousands of games lost only five. Schaeffer tells of hate letters he received after Chinook beat Tinsley, who died shortly after, and of his decision then to prove that a human simply can not beat a machine in the game.

The bottom line? Schaeffer has now indeed proven that the best an opponent of Chinook can achieve is a draw. This positions humans as those who could err and lose. A beautiful definition…