Checkers solved

Jonathan Schaeffer's quest for the perfect game of checkers has ended. . .

Schaeffer's proof, described today in Science (and freely available here for others to verify), would make checkers the most complex game yet solved by machines, beating out the checker-stacking game Connect Four in difficulty by a factor of a million. . .

So what game will fall to computers next? Schaeffer and colleagues speculate it will be Othello, an eight-by-eight disk-flipping game. Chess presents a far mightier challenge, but researchers are "in the realm of thinking about" solving it, Herik says, which he calls "a tremendous achievement."

The great white whale of games remains the Asian pastime Go. Although programs have recently become competitive with grand masters on nine-by-nine boards, they remain toothless on the full 19-by-19 game.

Posted by David on July 22, 2007 2:11 PM