Beginning in 1989, a research team in the Department of Computing Science at the University of Alberta began work. While the team did not actually calculate all 500,995,484,682,338,672,639 possible board positions for a match on an eight-by-eight checkerboard, the researchers did identify the moves that proved the game would end in a draw.

This kind of game-strategy overkill has made the team's checkers-playing program, known by the single name of Chinook, invincible. Chinook has its own place in the Guinness Book of World Records as the first program to win a human world championship.

The Champion, Chinook

It wasn't exactly a walk in the park for Chinook, though. The program lost the first attempted checkers championship match in 1992 against the legendary Marion Tinsley. In a rematch in 1994, Chinook won only by default, when Tinsley had to withdraw for health reasons. But, like Rocky the boxer, Chinook trained and trained and, finally, beat the top human player in 1996.

By then, according the research team, it was obvious that the program was much stronger than any human. And so, to protect the fragile ego of those of the carbon persuasion, Chinook was retired.

But team-leader Jonathan Schaeffer and other researchers at the University of Alberta thought they could do better than simply embarrass the human species. They thought they could solve the game.

"Had I known 18 years ago it was this big of a problem," Schaeffer told reporters, "I probably would've done something else. But once I started, I had to finish."

Chinook Is No Deep Blue

You might think that Chinook is simply a Canadian Deep Blue that plays checkers. Deep Blue, IBM's master chess-playing program, became a celebrity by defeating chess grandmaster Garry Kasparov in 1997.

But the University of Alberta researchers said that Deep Blue uses artificial intelligence technology "to generate strong heuristic-based game-playing programs." In other words, it uses rules-of-thumb to make decisions. Chinook solves the game "by replacing the heuristics with perfection."

Checkers is the largest game to be so solved, a million times larger than the next-largest solved game, the checker-stacking game Connect Four.

The game of tic-tac-toe, with many fewer possible combinations, was an early game that was solved by computers, noted Michael Gartenberg, an analyst with Jupiter Research. "Checkers is the same kind of game," he noted, but chess has so many more possible combinations.

The key to Chinook's invincibility is perfect play, he said. "Computers never make mistakes," and humans do, he said, so checkers-playing computer programs will always have an advantage.

The end of the road for checkers is reported in the current online edition of Science magazine.