Canadians create unbeatable computer at checkers
July 20, 2007
It took 18 years to figure out all 500 billion
billion combinations at checkers, but Canadian scientists have finally
programmed a computer that cannot be beat at the 5,000-year-old game.
The achievement, reported Thursday in Science magazine's latest
issue, is considered a milestone in the development of artificial
Called Chinook, the checkers champion computer is the brainchild of
Jonathan Schaeffer and his team of computer wizards at the University of
Completed in April, Chinook can never be beaten, and can only be tied at
checkers if its opponent makes all the right moves, Schaeffer said.
"I think we've raised the bar, and raised it quite a bit, in terms of what
can be achieved in computer technology and artificial intelligence," said
Schaeffer, who chairs the university's Department of Computing Science.
"With Chinook, we've pushed the envelope about 1 million times more than
anything that's been done before."
A self-described "awful" checkers player, Schaeffer created Chinook to
exploit the superior processing and memory capabilities of computers and
determine the best way to incorporate artificial intelligence principles in
order to play checkers.
He consulted the world's top checkers players in developing the program and
over 18 years ran an average of 50 computers - with more than 200 running at
peak times - daily to compute the knowledge necessary to complete Chinook,
albeit an interruption from 1997-2001.
Schaeffer said that the initial goal of the project was to have Chinook
conquer the world championship in checkers. It entered in 1990, reached the
finals in 1992 but lost, and in 1994 became the first computer to take the
Chinook plays by English draughts rules, also called international rules,
with an 8x8 board - not the Canadian variation with a 12x12 board.
Chinook has its own entry in the
Guinness Book of Records.
It remained undefeated until 1997 when it was "retired."
But Schaeffer did not stop there and in 2001 began tweaking Chinook to make
it completely unbeatable at the board game.
"I'm thrilled with this achievement," he said. "Solving checkers has been
something of an obsession of mine for nearly two decades, and it's really
satisfying to see it through to its conclusion."
At chess, however, computers have a long way to go - centuries scientists
estimate - before they can handle the astronomical combinations required to
master the game to the point of perfection.
Checkers boards have been found in Egyptian archaeological excavations.