Celebrate: Checkers is solved!

In today's Science online: wonderful title, wonderful article, wonderful research. Took quite a while, but the victory is sweet indeed...

"If two players face off at checkers and neither makes a wrong move, then the game will inevitably end in a draw. That's the result of a proof executed by hundreds of computers over nearly 2 decades and reported online by Science this week."

You can read the free abstract, but need a subscription to download the pdf (you can download the supporting online material). Caveat lector, however! If you were on the verge of thinking "and now to the final frontier: CHESS", you should hold your horses: solving that will still require a hell lot of time, as the conclusion of the article (pasted below) makes clear. So there is still plenty of scope to play some nice chess games, but from now on checkers is history from my point of view. In particular, this also means that all you fellows who liked and who'd like to challenge me in checkers, knowing you'd always lose from me in chess, need to find some other challenges :-)

The checkers computation pushes the boundary of what can be achieved by search-intensive algorithms. It provides compelling evidence of the power of limited-knowledge approaches to artificial intelligence. Deep search implicitly uncovers knowledge. Furthermore, search algorithms are well poised to take advantage of the dramatic increase in on-chip parallelism that multi-core computing will soon offer. Search-intensive approaches to AI will play an increasingly important role in the evolution of the field.

With checkers done, the obvious question is whether chess is solvable. Checkers has roughly the square root of the number of positions in chess (somewhere in the 10^40- 10^50 range). Given the effort required to solve checkers, chess will remain unsolved for a long time, barring the invention of new technology. The disk-flipping game of Othello is the next popular game that is likely to be solved, but it will require considerably more resources than were needed to solve checkers.