Computerized checkers player can't be beaten

http://seattletimes.nwsource.com/html/nationworld/2003797714_checkers20.html

Computerized checkers player can't be beaten
By Robert Mitchum
Chicago Tribune

CHICAGO — With uniform pieces and diagonal moves, checkers is simple enough for a child to learn. But to achieve absolute mastery of the game, scientists needed to run hundreds of computers for nearly 20 years, analyzing roughly 500 billion billion scenarios.

By completing the project, a team of Canadian researchers have officially "solved" checkers, creating an unbeatable program that will choose the best move in every possible situation.

This achievement represents a major benchmark in the field of artificial intelligence, which uses games to develop complex problem-solving strategies for computers.

In 1994, a program named Chinook beat the reigning human world checkers champion, a feat that preceded Deep Blue's famous chess defeat of grandmaster Garry Kasparov by three years. But even after proving dominant over humans, finishing the calculations required to solve the game required 13 more years of research.

"Had I known 18 years ago it was this big of a problem, I probably would've done something else," said Jonathan Schaeffer, who led the project at the University of Alberta, "but once I started, I had to finish."

"It's 1 million times bigger than the biggest computation previously solved optimally," he said.

Detailed Thursday on the Web site of the journal Science, methods developed by Schaeffer's team in the process of solving the game may be applicable to other areas, such as business and biology. The resulting program proves that checkers is a "draw" game; in other words, perfect play by both players will always result in a draw.

However, checkers experts say there is no fear that the solving effort will ruin the game for traditional players, amateur or professional.

"No human can possibly memorize the billions of combinations that Dr. Schaeffer has covered," said Richard Beckwith, player representative for the American Checkers Foundation. "You still have to play as you see it, based on your own expertise and knowledge."

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 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 massive 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.

On Thursday, the Alberta team made the new solving program available to play against on the Internet at www.cs.ualberta.ca/~chinook. Schaeffer, however, doesn't expect it to be a runaway hit.

"In some sense it's not interesting," he said. "People play games for fun, and knowing you can never beat it isn't fun."

Meanwhile, Schaeffer's group has moved on to a more profitable game: designing a poker program capable of beating even professional players. Next week, their current program, named Polaris, will challenge two pros for a $50,000 prize in Vancouver, B.C., at the Association for the Advancement of Artificial Intelligence conference.

Schaeffer speculates that human supremacy at poker remains intact — for now.

"I think humans are still better, but it's inevitable that poker will succumb to technology," he said. "Computers will be better than humans eventually, probably in less than five years."

Additional information from Los Angeles Times