Millions of checkers players worldwide can put down
their pieces -- the ancient game has been solved, according to
researchers.
Chinook, a computer program
developed by researchers at the University of Alberta, can now play a
perfect game of checkers. Chinook can recognize every possible move made
in a checkers game and determine the correct counter move. If neither
player makes a mistake, the game will end in a draw.
"The checkers result pushes the boundary of artificial
intelligence," Dr. Jonathan Schaeffer, the head of the university's
computer science department, wrote in the paper that will be released
Friday in the journal Science.
Since 1989, an average of 50 computers at a time
worked around the clock to decipher the game's 500 billion billion
possible moves.
Schaeffer developed the Chinook program with the
initial goal of winning the Checkers World Championship against some of
the best human players in the world.
In 1992, the computer was narrowly defeated by world
champion Marion Tinsley, who is widely regarded as the best human
checkers player ever. In 1994 it won the championship in a rematch
against Tinsley. Chinook was then retooled to make it better and
stronger, and to solve the game of checkers. According to Schaeffer,
that goal was achieved.
"In 1994, it was extremely strong, but not perfect,"
he said. "The new program is perfect in the sense that it knows that if
it doesn't make mistake and you don't make a mistake [the match] will
always end in a draw."
Industrious players can study Schaeffer's proof to
become stronger players, he said.
"You can now see how to not lose every single play,"
he said.
Despite Chinook's advance, Schaeffer, who was once a
competitive chess player, doesn't believe that the solution will affect
tournament play.
"Why do you play a competitive game like checkers? The
intellectual challenge, the beauty of the creations that you make, the
social aspects of the game," he said.
Richard Beckwith, the players' representative for the
American Checkers Federation and a scientist at Ricerca Biosciences in
Concord, Ohio, agreed.
"I applaud Mr. Schaeffer's artificial intelligence
achievement, as he has been hard at work for many years on this project.
However, the fact that the game is a draw (if both players play
optimally) was known long ago as a result of much human analysis," he
said in an e-mailed statement. "I don't expect any impact on
face-to-face competition, as no human can possibly memorize the billions
of combinations that Mr. Schaeffer has covered. Checkers still remains a
highly strategic game when played head-to-head."
At high level competitions draws are already common,
as top level players are often very knowledgeable about the game's
strategy.
For Schaeffer, Chinook is just the beginning. The
first man-machine poker match is set to take place in Las Vegas next
week, and another University of Alberta computer will compete.
"The checkers is ending… and the poker is ongoing," he
said. "Finally we have programs that are competitive with players. This
will be a good test. … I hope it's not a painful lesson."