19 July 2007—You might have to find a new game to play on your computer or cellphone soon, because checkers will only frustrate you. Even if you play it perfectly—without any mistakes, choosing the best strategy in each situation—you’ll have absolutely no chance of winning. One of the most popular board games in history, checkers has been definitively proved to end in a draw when played perfectly by both sides, according to Jonathan Schaeffer, professor of computer science, and his colleagues at the University of Alberta, Edmonton, Canada. They published their proof today on the Web site of the journal Science .

It took Schaeffer nearly 16 years to complete his checkers odyssey. He began by inventing Chinook, the world’s first computer program to win a world championship against a human in checkers, or any other game, for that matter. The program, created in 1989, draws from a library of stored opening moves that had been played by grandmasters, an endgame database that traces backward from the final results of games (wins, losses, or draws), and a deep-search algorithm that makes decisions during play based on evaluating all possible outcomes a certain number of moves ahead.

Photo: Jonathan Schaeffer

MAN VS. MACHINE: Chinook, a checkers playing computer program, played champion Marion Tinsley [right] at the first Man v. Machine World Championship match in 1992, in London. Tinsley, beat the program then, but had to withdraw from a rematch in 1994. Chinook played a key role in proving that checkers, when played perfectly by both sides always ends in a draw.

In 1990, Chinook won the right to compete in the World Championship by coming in second place at the United States National Open Checkers Championship to Marion Tinsley, considered to be the greatest checkers player who ever lived. Chinook was all set to face Tinsley in the World Championship, but the American Checker Federation (ACF) and the English Draughts Association (EDA) had not sanctioned the match. Tinsley, wanting to face the program, resigned his title in protest. The ACF and EDA soon created the Man vs. Machine World Championship to accommodate the match. Chinook lost to Tinsley, with two wins to Tinsley’s four. In 1994, Chinook was retooled with more information, including previous strategies used by Tinsley, and faced off against the grandmaster in a rematch. All six games played resulted in draws. Tinsley, who was suffering from pancreatic cancer, withdrew from the tournament and died seven months later. Chinook was declared the Man vs. Machine World Champion and went on to defend its title against grandmaster Don Lafferty by winning one match, losing one, and then drawing 18. After that defense, Schaeffer retired Chinook from playing and put it to use in helping to solve checkers.

Solving checkers, a game played on a board with 64 squares using 12 black and 12 white or red pieces, was a daunting task. There are 500 billion billion (5 x 10²⁰) possible situations that could arise while playing. Strongly solving the game or computing all of these possible positions would have taken decades, says Schaeffer. Instead, he implemented a two-pronged search technique that concluded with the game being a draw by examining only a fraction of all the possible game scenarios.

First, he constructed databases of endgames, building backward from all the possible wins, losses, or draws that checkers could conclude with. A so-called backward-searching algorithm built the path of situations that would have led to these endgames all the way to the point where there were 10 game pieces on the board. The result is a database of 39 trillion positions compressed using a homebrew algorithm into an average of 237 gigabytes for an average of 154 positions per byte of data.

When Schaeffer first developed these databases, it took him seven years—from 1989 to 1996—to build backward from the endgame to the point where there were eight pieces on the board. Deeming that there wasn’t enough horsepower or RAM available to compute any further, in 1997 he suspended the project. When he resumed the project in 2001, computing power had so improved that the endgame databases that had taken years to compute were redone in the course of a month. From there the eight-piece scenarios were extended back to 10-piece scenarios.

The next step was to use a forward-search technique, such as the ones chess software typically rely on to figure out how to get to those 10-piece situations from the beginning of the game, when all 24 pieces are on the board.

This forward search, however, was not performed in the way Chinook or IBM’s Deep Blue—the chess-playing computer that defeated world champion Garry Kasparov 10 years ago—would have done it. Those programs used deep-search algorithms to make their next moves by analyzing all possible situations that are one-move deep, then all possible situations that are two-moves deep, and so on.

Instead, Schaeffer and his colleagues used a technique called “best first” to prioritize searching various positions and lines of play. At a given position in the game there are several possible moves that can be made. Instead of exploring all of these moves to their final outcomes using deep search, Schaeffer's team used Chinook to provide a measure of what the strongest line of play would be—what would most likely result in a win in the fewest moves. This line of play was evaluated first. If it did result in a win, then there was no need to search any other parallel lines of play, because the entire line was already known to result in a strong win. A win in such an instance is not a characteristic of perfect play by both sides; perfect play means that each side will try to win in as few moves as possible, or delay losing in as many moves as possible. Since a win was achieved so quickly, it means the losing side made a mistake and did not play perfectly. Entire lines of play branching from various positions were eliminated this way, vastly reducing the number of lines that had to be deeply explored. By applying such a technique, Schaeffer’s team was able to solve checkers using the least amount of effort. Of the 5 x 10²⁰ possible positions, Schaeffer needed to evaluate only 10¹⁴ to prove that checkers, played perfectly, results in a draw.

Players had suspected for a while that checkers would result in a draw, says Schaeffer. Human players draw so frequently when playing that since 1934 championship tournaments require the first three half-moves (black-white-black) to be done randomly from a list of accepted openings in order to reduce the number of draws. Schaeffer’s proof solved checkers for 19 different openings, all of which end in draws. There are 300 total tournament openings, but many of these were determined to either be mirrors of other positions or altogether irrelevant to the proof because they lead to positions common to other openings.

Solving checkers has taken a big monkey off Schaefer’s back. The fact that the game wasn’t solved for every possible position and then tucked away in a database doesn’t seem to bother him. “Well, the checkers players would love it, because [then] you’ve got this oracle that can tell them everything—answer every single unanswered question in the game of checkers,” he says. “But first of all, I don’t have the patience to do it. And second of all, I don’t have the technology to do it.” Even with the best data-compression techniques, Schaeffer says, the amount of storage required to solve all possible positions of checkers would exceed even the capacity of the world’s biggest supercomputers with tens of petabytes (10¹⁵) of storage by an order of magnitude. That puts it—at the earliest—at least a decade away.

But there is little motivation for Schaeffer to pursue such a quest. He has solved checkers and has painstakingly verified that none of the data were corrupt or inaccurate. Vasik Rajlich, an international chess master [profiled in “Dream Jobs,” IEEE Spectrum, February 2007 described the accomplishment as the latest in a line of games that have been solved computationally. “Every now and then some game is solved,” he says. “And now we can ‘check this box’ for a rather major game.” So far researchers have solved Connect Four, Qubic, Go-Moku, Nine Men’s Morris, and Awari.

As for the question of solving a game like chess, which people suspect will also result in a draw, the amount of data is even more monstrous. The number of positions in checkers is thought to be roughly the square root of the number of positions in chess. That’s somewhere in the order of 10⁴⁰ to 10⁵⁰ positions. Schaeffer says that even with the two-pronged technique he used in solving checkers, a breakthrough such as quantum computing would be needed to even attempt to solve chess. But he isn’t quick to rule out the possibility. “The one thing I’ve learned in all of this is to never underestimate the advances in technology,” he says.