By Randolph E. Schmid, Associated Press
WASHINGTON — 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.
"What we've done is show that you can take
non-trivial 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%."
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.
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 the 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."
Schaeffer's proof is what is called a "weakly
solved" result. It calculates the result from an initial position — 10
pieces on the board — rather than from the beginning of the game.
Could Schaeffer's team produce a "strong
solution" by calculating every position from the beginning of a game?
Maybe, but there is not enough computer power available, he said. It
took more than 18 years to get where they are now.
How about chess? Current chess computers still
rely on rules of thumb rather than trying to study every possible
position, Schaeffer noted.
"Checkers has roughly the square root of the
number of positions in chess," the researchers said. "Given the effort
required to solve checkers, chess will remain unsolved for a long time,
barring the invention of new technology."
Next week, Polaris, a poker-playing
computer program built by Schaeffer and his colleagues, will challenge
two poker professionals in a $50,000 man versus machine poker game in
Vancouver, British Columbia, as part of the annual conference for the
Association for the Advancement of Artificial Intelligence.
The checkers research was supported by the
Natural Sciences and Engineering Research Council of Canada, Alberta's
provincial technology organization iCORE, Canada Foundation for
Innovation, Western Canada Research Grid and the University of Alberta.