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.
