Perhaps Chinook, the checker-playing computer program, should be renamed "King Me."
Canadian researchers report they have "solved" checkers, developing a program that cannot lose in a game popular with young and old alike for more than a thousand years.
"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.
"Clearly ... the world is not going to be revolutionized" by this, said Jonathan Schaeffer, chairman of the department of computing science at the University of Alberta.
The important thing is the approach, he said. In the past, game-playing programs have used rules of thumb — which are right most of the time, he said — to make decisions.
People are also reading…
"What we've done is show that you can take nontrivial problems, very large problems, and you can do the same kind of reasoning with perfection. There is no error in the Chinook result. ... Every decision point is 100 percent."
Schaeffer's team started with the end of a game with just one checker on the board. Then the team looked at every possible position with two checkers, on up to 10 checkers on the board.
Every combination of 10 checkers offers 39 trillion positions for the endgame, he said. Chinook can calculate them all.
The calculations required up to hundreds of computers working since 1989 to analyze all possible board combinations of checkers, roughly 500 billion scenarios.
"Had I known 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."
It does not matter how the players make it to 10 checkers left because from that point on, the computer cannot lose, Schaeffer said. For two players who never make a mistake, every game would be a draw, he said.
" 'Checkers is solved' is an intriguing title for this wonderful and delightful article about another former human skill falling to the ubiquitous computer," said Ernest L. Hall, director of the Center for Robotics at the University of Cincinnati.
That does not mean an end to people playing checkers, said Hall, who was not part of Schaeffer's research team. Even though a computer beat the world chess champion, people still enjoy and play that game.
"Anything we can do to encourage the further study of science and engineering, of developing problem solvers for the many known needs of the world, should be encouraged," Hall said.
"So I applaud Schaeffer for making a breakthrough in computer problem solving for the game of checkers.
"It may encourage others to solve the other games we encounter in life."
On the Net
• Play against the computer: http://games.cs.ualberta.ca/ ~chinook/cgi-bin/player.cgi
