Well, Now We Know: You Can Play Checkers to a Draw!

July 27, 2007

Researchers from the University of Alberta have used computers to solve the game of checkers. The bottom line? Perfect play by both sides leads to a draw.

Computer scientist Jonathan Schaeffer and his colleagues, who study games as test cases for research into artificial intelligence, report their results in a paper titled simply "Checkers Is Solved" and published in Science.

To reach this conclusion, the researchers used dozens of computers with state-of-the-art artificial intelligence techniques, going at it full time almost continuously since 1989. "The end result is one of the longest running computations completed to date," Schaeffer and his colleagues say.

Schaeffer estimates that checkers has about 500 billion billion possible positions. The computational proof that checkers is a draw consists of an explicit strategy that never loses. In effect, the researchers say, "the program can achieve at least a draw against any opponent, playing either the black or white pieces."

"That checkers is a draw is not a surprise; grandmaster players have conjectured this for decades," the researchers concede. At the same time, "checkers is the most challenging popular game to be solved to date."

Using these results, Schaeffer and his team have developed a checkers-playing computer program, named Chinook, that can't be beaten. An earlier version was the first computer program to win a human world championship, a feat recognized by the Guinness Book of World Records.

"I think we've raised the bar — and raised it quite a bit — in terms of what can be achieved in computer technology and artificial intelligence," Schaeffer said. "With Chinook, we've pushed the envelope about one million times more than anything that's been done before."

Source: University of Alberta, July 19, 2007; Science, July 19, 2007.