At checkers, Chinook is unbeatable
Computer program developed with help of game's best goes beyond human ability
You wouldn't think checkers could get so complicated.
After working for six years with a network of up to 200 computers, Jonathan Schaeffer says he has developed a program that can never lose at checkers. At best, a human (or computer) opponent can achieve a draw.
The program was designed with help from some of the world's top checkers players, but the computers did what no player could ever do: analyze 64 million positions on the board each second.
"We've taken things to beyond what humans can do," said Schaeffer, chairman of the computer science department at the University of Alberta in Canada.
The work, reported online yesterday by the journal Science, earned praise from computer scientists and programmers who design computer games.
"What's amazing is there are so many possible situations in checkers, and they were able to explore all of the ones that mattered," said Jason Eisner, a computer science professor at the Johns Hopkins University.
Checkers might seem simple, but try to design a flawless game and the numbers get complicated pretty quickly. Each player has 12 pieces, and, with 64 squares on the board, the possible number of positions on the board runs up to 500 quintillion - that's a five followed by 20 zeroes.
Schaeffer didn't have to examine possible outcomes for every one. He narrowed the search by first identifying the fatal moves that would put a player in an unwinnable position as a game neared completion. He then spent two years running programs dedicated to avoiding those mistakes.
Experts say Schaeffer's work sheds light on the difficulties of trying to create machines that solve everyday problems or mimic simple human tasks.
"It's really a profound scientific discovery," said Ed Trice, who has developed computer programs to play both checkers and chess. "In 2007, if we're just solving the game of checkers, think about trying to create programs that can help determine the right course of treatment for a patient, and how complicated things like that can get."
Computer programs have been beating some of the world's great checkers - and chess - masters since the 1990s and have improved steadily over the years.
"You can't beat these programs nowadays; they're just too good," said Gerry Lopez, 85, a retired teacher and coach who has repeatedly won state checker tournaments in California.
When IBM's Deep Blue defeated chess legend Garry Kasparov in 1997, it was a stunning upset. A member of Deep Blue's original design team was among the computer experts who reviewed Schaeffer's paper this week.
"I think it's a monumental piece of work. I admire their persistence," said Murray Campbell, 49, who is still a researcher at the IBM T.J. Watson Research Center in New York where Deep Blue was designed.
Campbell, who is a native of Alberta and has visited Schaeffer's lab, said that Deep Blue was "by no means perfect" and would occasionally make a bad move on the chessboard.
Creating a perfect chess program is probably several years away and will require an entirely different computer programming approach, he said. But Schaeffer's group and the IBM team shared a strategy, he said.
"I think what they did was they relied on waiting for computers to become powerful enough to do the job, and, in essence, that's what we did," Campbell said.
Deep Blue's victory over Kasparov was heralded in news accounts worldwide as the machine's victory over mankind.
"It was an amazing time," Campbell said.