A team at the University of Alberta has solved the game of checkers, creating a checkers-playing program that cannot be beaten.
Led by Jonathan Schaeffer, the team has been working on the program, known as Chinook, since 1989. In 1994, Chinook had developed to a point which allowed it to defeat reigning world champion Marion Tinsley; the same program has now completed all the calculations necessary to become unbeatable. At best, with a perfectly-played game, an opposing player can take Chinook to a draw.
A deceptively simple-looking game, there are actually 500 billion billion (5.0 * 10^20) possible moves over the course of a single game. To increase its efficiency, the team designed the program to search out only the moves required to win the game from each game position, which meant that only 1/5,000,000 of the possible moves were computed – a tiny 500,000 billion. Since the program has already worked out all the possible winning combinations, it needs virtually no time to think in response to a move.
Schaeffer said Chinook has implications beyond checkers: The same algorithms that power it could be useful with other massive databases, such as lists of biological information. “At the core, they both reduce to the same fundamental problem,” he said. “Large, compressed data sets that have to be accessed quickly.”
And unlike certain world champions of chess, his work doesn’t appear to be a target of resentment among the checkers elite. “People will keep right on playing checkers,” said Bob Newell, editor of The Checker Maven, the world’s foremost checkers publication. “People continued to run for sport after the invention of the automobile.”
Checkers aficionados can test their mettle against the unbeatable machine at the official Chinook website.
