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.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
"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!
Early this decade he decided that improved computer speed and memory had brought his goal of solving the game within reach. The first of the solution's two pieces builds on work begun during the Tinsley days. The Alberta researchers exhaustively checked the final stages of play for any arrangement of 10 pieces or less, identifying which of the 3.9 x 1013 positions won, lost or drew.
Next they identified 19 representative opening sequences and searched through subsequent moves for the easiest-to-find connections to final positions—win, lose or draw. To save time, they ignored pointless back-and-forth moves or those that did not turn a draw into a win.
If the sequence of possible moves branches like a tree, the group found that main branch after main branch led to a draw. On April 27, Schaeffer says, the program traced the final branches, completing his 18-year task. He had received his king.
The result itself was not surprising. "We expected that it should be a draw, because at the highest levels there are many games that end in a draw," Herik says.
What the proof does, Watson's Campbell says, is highlight the power of methodically checking outcomes one by one. The most robust chess programs such as Deep Blue and Deep Fritz have beaten world champions by combining swift number crunching with rules of thumb derived from years of human play.
The checkers solver is comparatively dumb, Campbell notes. "All it knows is this move wins or this move doesn't," he says. "It can't 'explain' what it knows."
For that reason, Herik says the results won't be much help to players until researchers can figure out how to translate them into rules or procedures the human mind can follow—a major challenge in itself.
Next Move?
So what game will fall to computers next? Schaeffer and colleagues speculate it will be Othello, an eight-by-eight disk-flipping game. Chess presents a far mightier challenge, but researchers are "in the realm of thinking about" solving it, Herik says, which he calls "a tremendous achievement."
The great white whale of games remains the Asian pastime Go. Although programs have recently become competitive with grand masters on nine-by-nine boards, they remain toothless on the full 19-by-19 game.
Schaeffer, a true game lover—his two dogs are named Scrabble and Rummicub—intends to pit his poker program against two top players next week in a 500-hand match designed to minimize the role of chance.
He has come a long way since being fixated on the world championship. Whatever games lie ahead, he can take satisfaction in his current victory. "Eighteen years later," he says, "I'm finally done."