CHECKERS IS SOLVED: Eighteen years of number crunching concludes that perfect checkers ends in a draw.
© ISTOCKPHOTO/CHRISTOPHER O DRISCOLL

Jonathan Schaeffer's quest for the perfect game of checkers has ended. The 50-year-old computer scientist from the University of Alberta in Edmonton left human players in the dust more than a decade ago after a trial by fire against the greatest checkers champion in history.

And now, after putting dozens of computers to work night and day for 18 years—jump, jump, jump—he says he has solved the game—king me!. "The starting position, assuming no side makes a mistake, is a draw," he says.

Schaeffer's proof, described today in Science (and freely available here for others to verify), would make checkers the most complex game yet solved by machines, beating out the checker-stacking game Connect Four in difficulty by a factor of a million.

"It's a milestone," says Murray Campbell, a computer scientist at IBM's T. J. Watson Research Center in Hawthorne, N.Y., and co-inventor of the chess program Deep Blue. "He's stretched the state of the art."

Although technological limits prohibit analyzing each of the 500 billion billion possible arrangements that may appear on an eight-by-eight checkerboard, Schaeffer and his team identified moves that guaranteed the game would end in a draw no matter how tough the competition.

Like any complicated mathematical proof, the result will have to withstand scrutiny. But "it's close to 100 percent," says computer scientist Jaap van den Herik of Maastricht University in the Netherlands, who has seen the details. "He has never published anything that was not completely true."

Opening Play: Walking a Precipice

Schaeffer's odyssey began in the late 1980s. He had written a top chess program but IBM was on the verge of pouring its far vaster resources into Deep Blue. "I like to be competitive," he says, so he turned his attention elsewhere. "I naively thought I could solve the game of checkers," he recalls. "You can teach somebody the rules in a minute."

Setting out in 1989 with 16 megabytes of computer memory, he quickly found that checkers, like chess, was too rich with possible positions to dash off a solution. So he switched gears, vowing to topple legendary checkers champion Marion Tinsley, who had lost only three games in tournament play since 1950.

In 1992 Schaeffer's program Chinook took on Tinsley, who had resigned as world champion when the American Checker Federation and English Draughts Association temporarily refused to sanction the man-computer matchup.

Tinsley was so good that his opponents played dull games in the hope of securing at least a draw, according to Schaeffer; Chinook apparently put the magic back in the game for the champ. "It played brash, aggressive moves—it walked on the edge of a precipice," Scheaffer anthropomorphizes. "It would do things people looked at and said, 'Man, is that program crazy?'"

The program actually beat Tinsley twice, but computer glitches led to a forfeit that gave the human a 3–2 lead with two games left in a best-of-40 match. Schaeffer set Chinook on an aggressive course to try to recoup, resulting in another loss for the computer that cost it and its creator the match, Schaeffer recounted in his book One Jump Ahead.

In a rematch two years later, Tinsley withdrew suddenly after six drawn games, citing health problems, making Chinook the winner of the Man–Machine World Championship by default. The checkers champ was diagnosed with pancreatic cancer, which killed him less than a year later.

Chinook soundly beat the top human player in 1996, but Schaeffer's memories of those years are bittersweet. "With hindsight, maybe winning was more important to me at that time than other things. I was a bit obsessed," he says. "My wife would say more than a bit obsessed."

Endgame: King Me!