In 2001, a new generation of computers allowed the team to replicate its previous seven years of work in a single month. By the time the program worked backward to include all scenarios with any combination of 10 or fewer pieces, it had built a database of 39 trillion possible board positions, according to the paper.
The next trick was to find the fastest way to get games to the point where only 10 pieces were left.
Traditionally, American checkers players begin by lining up their 12 pieces staggered across three rows, but tournament players consider this boring. Instead, they allow the three opening moves to be chosen for them, often at random.
Of the approximately 300 such openings, the researchers determined that more than 100 were duplicates. Of those that remained, obvious losing paths of play were eliminated because they would never be chosen by a perfect player, Schaeffer said. Only 19 openings were needed for the proof.
The program followed each line of play for about 70 moves until only 10 pieces remained, Schaeffer said. Then they melded the databases together to complete their proof.
The entire solution includes 500,995,484,682,338,672,639 possible board configurations, according to the study, which was funded by the Canadian and Alberta governments.
Murray Campbell, a member of the original Deep Blue team, said the scope of the solution was a testament to the complexity of the game.
"Checkers is actually quite a difficult game -- much more difficult than most people give it credit for," said Campbell, a research staff member at IBM's T.J. Watson Research Center in Yorktown Heights, N.Y.
The computer method, however, still isn't powerful enough to solve chess.
"Even 100 years from now, it won't scale," Campbell said. "Some new idea is going to be needed. Maybe quantum computing. I don't know what the idea would be."
The insights gleaned from teaching computers how to play checkers can be applied to practical, computation-intensive problems. For example, Schaeffer said, the technology could be used to determine the optimal schedule for a huge construction project like the one at ground zero in New York.
Schaeffer co-founded a company to use the same approach to hunt for meaningful patterns in long strings of DNA and other biological building blocks.
The company's bestseller, however, has turned out to be a computer poker game.
Schaeffer's latest poker program, Polaris, will compete in the First Man-Machine Poker Championship, to be held next week in Vancouver.
--
karen.kaplan@latimes.com
