Kings of the board: AI cracks checkers


CHICAGO – With its uniform pieces and simple moves, checkers may seem like a simple kid’s game. But it took hundreds of computers running continuously for nearly 20 years before researchers announced Thursday that the game has officially been solved, a major benchmark in the development of artificial intelligence.

Thirteen years ago, a program named Chinook beat the reigning human world checkers champion, a feat that preceded Deep Blue’s famous chess defeat of grandmaster Gerry Kasparov by three years.

Now, the programmers behind Chinook have fully solved the game, creating an unbeatable program that will choose the best move in every possible situation.

“In artificial intelligence, the chess and checkers groups have gone beyond the pale of what we thought we could do,” said Michael Genesereth, an associate professor of computer science at Stanford University. “At one point, we thought we never could solve them in this way.”

The team, led by University of Alberta computer science professor Jonathan Schaeffer, detailed the process Thursday on the Web site of the journal Science. The effort required up to hundreds of computers working since 1989 to analyze all possible board combinations of checkers, roughly 500 billion scenarios.

“Had I known it 18 years ago it was this big of a problem, I probably would’ve done something else,” Schaeffer said. “But once I started, I had to finish.”

Beyond accomplishing absolute mastery of checkers, methods developed by Schaeffer’s team in the process of solving the game may be applicable to other areas, such as business and biology. As opposed to previous “brute force” applications like Deep Blue, the program’s searches save time by testing only the most relevant moves from the enormous number of possible combinations.

“We built a huge database and had to compress it into something that was manageable, and could be accessed and searched fast by people,” Schaeffer said. “That core infrastructure that we developed is generic enough for other applications.”

The resulting program proves conclusively that checkers is a “draw” game; in other words, perfect play by both players will always result in a draw.

“No human can possibly memorize the billions of combinations that Dr. Schaeffer has covered,” said Richard Beckwith, player representative for the American Checkers Foundation.

“You still have to play as you see it, based on your own expertise and knowledge.”

Beckwith notes that the most significant impact of increasingly smart checkers programs has been to eliminate the practice of “correspondence games,” where moves were sent between players by mail.

“People use programs to make moves, so you don’t see people lose games any more,” he said.

“In some sense, it’s not interesting,” Schaeffer said. “People play games for fun, and knowing you can never beat it isn’t fun.”