The computer wears the crown in checkers

"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.