In Science, Researchers Detail the Perfect Game of Checkers

Almost continuously since 1989, dozens of computers have been playing checkers with state-of-the-art artificial intelligence techniques, playing a total of about 500 billion possible positions. After all of that, computer scientist Jonathan Schaeffer and his coauthors say in the 20 July issue of Science, the research has yielded an intriguing conclusion:

If black moves first, and the opponents execute perfect play, the game ends in a draw.

"That checkers is a draw is not a surprise," the authors say. "Grandmaster players have conjectured this for decades."

But the proof is a milestone, and not just for checkers players, but also in the annals of artificial intelligence, or AI. Computer scientists use games as test cases for AI research, and checkers is the most challenging popular game they've ever solved. It's roughly 1 million times more complex than Connect Four, the authors say.

A Science news story on the checkers breakthrough, also in the 20 July issue, said that Schaeffer and his team suspended their project from 1997 to 2001 to wait for more technological firepower—the 64-bit processor.

Games with a small search space (all possible moves) can be completely solved with computers by examining every possible set of moves from a given starting position. Researchers won't try to conquer chess yet since it has such an immense search space that even the fastest computers would need eons to solve it.

The researchers' article was first published online on 19 July at the Science Express Web site. Schaeffer is a computer scientist at the University of Alberta in Edmonton, Canada.

Evelyn Brown and Edward W. Lempinen

20 July 2007