Computer plays perfect checkersStory Highlights
Canadian researchers solve checkers

Checker-playing computer program called Chinook

Chinook cannot lose at checkers, it can achieve at least a draw

Next Article in Technology »




WASHINGTON (AP) -- Perhaps Chinook, the checker-playing computer
program, should be renamed "King Me."


Chinook can play a perfect game of checkers, according to researchers
at the University of Alberta.

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

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.

Don't Miss
Chinook
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. E-mail to
a friend