Checkers Solved: It's a Draw

July 19, 2007 — What do you call a game with 500,000,000,000,000,000,000 possible play positions? Checkers, of course. That's according to computer scientists who have succeeded in "solving" the well-known game for every possible smart move.

They found that in a perfectly played game, checkers is a draw.

The feat was accomplished by running checkers games on dozens of computers for 18 years, using cutting-edge artificial intelligence. And although it seems like a brute force approach to solving a game, it's not really, says computer scientist Jonathan Schaeffer of University of Alberta in Edmonton, Canada.

"What people do today is use intelligent force," Schaeffer told Discovery News.

In other words, the artificial intelligence they have developed and used over the years to play checkers can throw out mistakes and focus only on smart moves. That's not something a purely brute force method could do. Neither can those powerful but imperfect game programs, even if they can sometimes beat human opponents.

"Perfection implies solving a game: determining the final result…when neither player makes a mistake," report Schaeffer and his team in a paper on the achievement appearing in the July 19 issue of ScienceXpress, the online publication of the journal Science.

"The (computational) proof consists of an explicit strategy that never loses," write Schaeffer and his team. "The program can achieve at least a draw against any opponent, playing either the black or white pieces."

This result is not necessarily a surprise, said David Levy, president of the International Computer Games Association. For decades, matches between checkers grandmasters have usually ended in draws. This made many people suspect that a draw was the solution to a perfectly-played game.

Checkers is now the most complex game solved to be solved, after such games as Connect Four, Qubic, Go-Moku, Nine Men's Morris and Awari.

"I think it's an astounding achievement," Levy told Discovery News. "Jonathan always knew how to do it, but he needed the computer power."

So what's next, chess? Not likely, says Schaeffer. At least not any time soon. Whereas checkers has a mere 500-billion-billion positions (5 followed by 20 zeroes), chess is though to have about a billion-trillion-trillion-trillion positions (1 followed by 45 zeroes).

"Given the effort required to solve checkers," Schaeffer reports, "chess will remain unsolved for a long time, barring the invention of new technology."

In the meantime, the lessons learned are expected to help in solving more practical problems with specific, desired outcomes in areas like bioinformatics, machine translation and even scheduling.

"This kind of brute force intelligence is a valid sort of tool to solve certain types of problems," said Murray Campbell, IBM Researcher at IBM's TJ Watson Research Center in Hawthorne, NY. Murray is the co-developer of Deep Blue chess machine.

"This is not an approach that would occur naturally," Campbell said. It's entirely different from how the human mind or even Darwinian evolution solves problems, he said. "This is an exhaustive exploration of a space with an optimal solution." And once you find the solution, it's nailed for good, he said.

And that's the case for checkers, said Campbell: "I think it's a milestone."