The computer wears the crown in checkers
After 13 years of brute-force computer analysis examining all 500 billion billion possible board positions, researchers announced Thursday that they had solved the centuries-old game of checkers.
A perfect game cannot be won or lost but will inevitably end in a draw, according to the research published in the journal Science online.
The proof demonstrates that even the most skilled player can’t count on executing a cunning move designed to win -- he or she can only avoid making a mistake that leads to a loss.
The complete solution to checkers marks a milestone in computing, achieving a goal that researchers had pondered since the earliest days of computers.
It is not a victory of pure machine intelligence, but one based largely on rote calculating ability.
The task of analyzing the game to its end was so difficult that from 1996 to 2001, the researchers had to put their efforts on hold because the most powerful computers of the time weren’t up to the task. The team had as many as 200 computers working full time on the problem.
“You’ve got 500 billion billion pieces of hay in your haystack, and you’ve got to find the needles,” said lead researcher Jonathan Schaeffer, chairman of computer science at the University of Alberta in Canada. “How do you do it in a smart way? If you don’t, you’ll spend centuries sifting through all this data.”
For checkers enthusiasts, the solving of their beloved game was met with admiration mixed with a sense of anticlimax.
“We kind of knew the game was a draw anyway, though we didn’t have the scientific proof,” said Richard Beckwith, the American Checker Federation’s player representative.
David Fogel, creator of the checkers-playing program Blondie24, said the machine’s achievement probably wouldn’t discourage the estimated 200 million people worldwide who play the game with friends, in tournaments or on the Internet.
“How many people in the world can play infallible checkers? The answer is probably nobody,” Fogel said. “As long as it’s human-versus-human, it should be as fun as before.”
Still, with checkers joining tick-tack-toe, Connect Four and Qubic on the list of games that have been solved, its overall appeal -- on the decline since the Great Depression -- will undoubtedly take a hit, Fogel said.
One likely casualty will be the 15-year-old Man-Machine Checkers Championships, said American Checker Federation President Alan Millhone.
“I don’t think a human would have a chance against a computer now,” he said.
The idea of a checkers-playing computer goes back to at least the 1940s, when scientists working on early mainframes began considering the meaning of machine intelligence.
They focused immediately on chess, with its combination of elegance and complexity.
But some researchers decided to concentrate on the simpler game of checkers.
Though both games are played on an 8-by-8-square grid, the 12 red and 12 black checker pieces all move in the same way and are restricted to half the squares. Chess is exponentially more complicated.
Chess was Schaeffer’s first love. He switched to checkers in 1989 after technology powerhouse IBM Corp. formed a team to build Deep Blue, the computer that ultimately defeated world chess champion Garry Kasparov in 1997.
“All the research problems are the same in checkers as in chess,” Schaeffer said. “I was intrigued because I thought checkers was solvable. I was pretty naive.”
Schaeffer’s first checkers program, Chinook, was designed to play the game, not solve it. Chinook analyzed positions, judged relative merits of different lines of play, and chose moves with the biggest calculated payoff.
Schaeffer’s goal was to have Chinook win a human world checkers championship. Though it essentially won the title in 1994, the victory came as a result of a default. Marion Tinsley, a mathematics professor widely regarded as the greatest checkers player in history, withdrew from the competition because of illness. Tinsley died eight months later of pancreatic cancer.
That left Schaeffer with only one way to prove his computer was better than Tinsley. He refocused his efforts on solving the game to demonstrate once and for all that a properly programmed computer could not be beat by a human.
Because there are fewer pieces on the board at the end of the game than the beginning, the Canadian team started by constructing a database of all possible endgames, Schaeffer said.
The researchers began by looking at all one-piece endings, which were obvious victories. The algorithm then figured out all the endings with two pieces and traced the outcome to a win, loss or draw. Then it moved on to calculating all of the three-piece endings, and so on.
By 1996, the researchers had completed the database for endgames with as many as eight pieces. But moving on to nine was beyond the ability of machines at the time.
In 2001, a new generation of computers allowed the team to replicate its previous seven years of work in a single month. By the time the program worked backward to include all scenarios with any combination of 10 or fewer pieces, it had built a database of 39 trillion possible board positions, according to the paper.
The next trick was to find the fastest way to get games to the point where only 10 pieces were left.
Traditionally, American checkers players begin by lining up their 12 pieces staggered across three rows, but tournament players consider this boring. Instead, they allow the three opening moves to be chosen for them, often at random.
Of the approximately 300 such openings, the researchers determined that more than 100 were duplicates. Of those that remained, obvious losing paths of play were eliminated because they would never be chosen by a perfect player, Schaeffer said. Only 19 openings were needed for the proof.
The program followed each line of play for about 70 moves until only 10 pieces remained, Schaeffer said. Then they melded the databases together to complete their proof.
The entire solution includes 500,995,484,682,338,672,639 possible board configurations, according to the study, which was funded by the Canadian and Alberta governments.
Murray Campbell, a member of the original Deep Blue team, said the scope of the solution was a testament to the complexity of the game.
“Checkers is actually quite a difficult game -- much more difficult than most people give it credit for,” said Campbell, a research staff member at IBM’s T.J. Watson Research Center in Yorktown Heights, N.Y.
The computer method, however, still isn’t powerful enough to solve chess.
“Even 100 years from now, it won’t scale,” Campbell said. “Some new idea is going to be needed. Maybe quantum computing. I don’t know what the idea would be.”
The insights gleaned from teaching computers how to play checkers can be applied to practical, computation-intensive problems. For example, Schaeffer said, the technology could be used to determine the optimal schedule for a huge construction project like the one at ground zero in New York.
Schaeffer co-founded a company to use the same approach to hunt for meaningful patterns in long strings of DNA and other biological building blocks.
The company’s bestseller, however, has turned out to be a computer poker game.
Schaeffer’s latest poker program, Polaris, will compete in the First Man-Machine Poker Championship, to be held next week in Vancouver.