Computer Solves Checkers
Solution Took More Than 18 Years and Analysis of 500 Billion Billion Moves
By ASHLEY PHILLIPS July 19, 2007
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.
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.
Computer Solves Checkers - Three other ABC Articles
Read All 9 Comments and Post Your Own
Fri, 20 Jul 2007
Checkers Solved, Unbeatable Database Created
Years ago I monkeyed around with AI and game design, mostly for fun but also looking for faster ways to solve certain switching and prediction problems. Ultimately I concluded that the most efficient way to solve these sorts of problems was a database lookup, because memory was a much more important factor in human intelligence than we generally believe.
At the time, however, silicon memory was quite expensive, and the average hard disk was 20MB, so there was no way for me to really run through a test of any scale, especially considering that it probably would've delved deeper into game theory, and the boss might've looked askance at that.
But this seems to back up my thinking - nice to know I was at least on the right track.
A story on the Nature site announced that a team of computer scientists at the University of Alberta has solved checkers. From the game's 500 billion billion positions (5 * 10^20), 'Chinook' has determined which 100,000 billion (10^14) are needed for their proof, and run through all relevant decision trees. They've set up a site where you can see the proof, traverse the logic, and play their unbeatable automaton. Jonathan Schaeffer notes that his research has implications beyond the checkers board. The same algorithms his team writes to solve games could be helpful in searching other databases, such as vast lists of biological information because, as he says, "At the core, they both reduce to the same fundamental problem: large, compressed data sets that have to be accessed quickly."
July 20, 2007 Middle East Times - "Canadians create unbeatable computer at checkers"
July 20, 2007 News & Record - Greensboro "Undisputed checkers champ"
July 20, 2007 Baltimoresun.com "At checkers, Chinook is unbeatable"
July 20, 2007 Toronto Sun.com - "Taking the fun out of checkers"