Science of winning checkers solved

Researchers say find a key to artificial intelligence

Boston Globe photo by David L. Ryan, August 15, 1994

Dr. Marion Tinsley plays checkers in a rematch against Chinook, a super computer, at the Boston Computer Museum in Boston on Aug. 15, 1994. Tinsley won his his first match-up against the computer in 1992 in London but lost the rematch after he was unable to complete round seven due to illness. The first six games had been a draw.

Now, the programmers behind Chinook have fully solved the game, creating an unbeatable program that will choose the best move in every possible situation.

'The program can achieve at least a draw against any opponent, playing either the black or white pieces,'' the researchers say in this week's online edition of the journal Science.

With its uniform pieces and simple moves, checkers may seem like a simple kid's game. But it took hundreds of computers running continuously for nearly 20 years before researchers announced today that the game has officially been solved, a major benchmark in the development of artificial intelligence.

Thirteen years ago, a program named Chinook beat the reigning human world checkers champion, a feat that preceded Deep Blue's famous chess defeat of grandmaster Gerry Kasparov by three years.

"In artificial intelligence, the chess and checkers groups have gone beyond the pale of what we thought we could do," said Michael Genesereth, an associate professor of computer science at Stanford University. "At one point, we thought we never could solve them in this way."

The team, led by University of Alberta computer science professor Jonathan Schaeffer, detailed the process Thursday on the Web site of the journal Science. The effort required up to hundreds of computers working since 1989 to analyze all possible board combinations of checkers, roughly 500 billion-billion scenarios.

"Had I known it 18 years ago it was this big of a problem, I probably would've done something else," Schaeffer said. "But once I started, I had to finish."

Beyond accomplishing absolute mastery of checkers, methods developed by Schaeffer's team in the process of solving the game may be applicable to other areas, such as business and biology. As opposed to previous "brute force" applications like Deep Blue, the program's searches save time by testing only the most relevant moves from the enormous number of possible board combinations.

"We built a huge database and had to compress it into something that was manageable, and could be accessed and searched fast by people," Schaeffer said. "That core infrastructure that we developed is generic enough for other applications."

The resulting program proves conclusively that checkers is a "draw" game; in other words, perfect play by both players will always result in a draw.

However, checkers players predict that solving the game will not affect face-to-face play.

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

Beckwith notes that the most significant impact of increasingly smart checkers programs has been to eliminate the practice of "correspondence games," where moves were sent between players by mail.

"People use programs to make moves, so you don't see people lose games any more," he said.

On Thursday, the Alberta team made the new program available to play against on the Internet at http://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."

Source : Chicago Tribune & Sun Times