But few programmers were focused on checkers when Schaeffer set to work in 1989. He wanted to silence fans of the game who were skeptical that a computer could ever beat the best. His plan was to defeat the retired math teacher from Ohio who was considered the world's best checker player, the late Marion Tinsley.

"There were people who said we would never beat Tinsley, and I just decided these guys didn't know what they were talking about," Schaeffer said.

In 1992, Tinsley defeated Schaeffer's program in a London tournament, but in a rematch in Boston two years later, Tinsley and the computer played to a draw for six matches before he fell ill and was forced to withdraw. He was later diagnosed with pancreatic cancer and died the next year, Schaeffer said.

"The question went unanswered, who was better, the computer or Tinsley," Schaeffer said. "It was all very upsetting."

Schaeffer said he stopped working on the program, which he calls Chinook, until 2001, when improved computer technology made it possible to "solve" checkers. The name is a play on words. A Chinook is a type of wind, and in England, checkers are known as "draughts," which is pronounced as drafts.

Players can challenge a modified version of his program by going to the university's Web site: http://www.cs.ualberta.ca/~chinook/. It's one of many free checkers programs on the Internet.

"Thousands and thousands and thousands of people play online. It's just phenomenal," said Alan Millhone, 58, an Ohio building contractor who is president of the 400-member American Checker Federation.

He and others said the game enjoys a steady popularity. The federation expects 60 players from around the world to compete for prize money next week at its annual tournament in Las Vegas.

There's an International Checker Hall of Fame in Petal, Miss., and when it reopens after repairs, the public will be able to see a bust of Tinsley along with other memorabilia.

The attraction opened in 1979 and in the past has drawn thousands of visitors, said Deloris Walker, who runs the hall with her husband, Charles.

Schaeffer, a self-described awful checkers player, also has developed a poker program that will compete against two professional poker players July 23 at the American Association for the Advancement of Artificial Intelligence conference in Vancouver, British Columbia.

At checkers, Chinook is unbeatable

Computer program developed with help of game's best goes beyond human ability

By Dennis O'Brien | Sun reporter July 20, 2007

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.