News

In 1989, Jonathan Schaeffer, a computer scientist at the University of Alberta, punched a calculation into his computer and set it crunching numbers.

For 18 years, the computer dubbed Chinook kept running, on as many as 200 processors at once.

Prof. Schaeffer got married. He had a baby girl. He bought a bigger house. He received tenure. But at least twice a day — less a two-year period when he had to wait for the technology that could handle numbers that big — he checked his computer, lest the smallest error creep into the calculation. One number off, one tiny blip, and he'd have to start over.

He never went anywhere without his laptop. His friends suggested "he get a life." His wife began losing patience. He was, he admits, obsessed.

And then this spring — more precisely, on April 29 at 6:03 p.m. — the computer stopped.

It popped out a single word: Draw.

Prof. Schaeffer and his team had solved checkers.

While Chinook had easily beaten humans in games since the mid-90s, it can now perfectly play every game to a win or a draw.

"If I had have known it was going to take this long, I probably wouldn't have done it," Prof. Schaeffer said yesterday, the same day their ground-breaking research appeared in the academic journal Science.

Mathematicians had long assumed that checkers, if played perfectly, would end in a draw, but it was a theory that could never be proven. It would take more than a lifetime to do that kind of math.

Checkers has roughly 500 billion billion possible positions. Only a computer could answer the question, but not even Prof. Schaffer imagined it would take nearly two decades. The solution for checkers is roughly one million times more complex than Connect Four, until now the most complicated mathematical solution for a game.

Many devout checkers players around the world were wondering yesterday what Marion Tinsley would have made of the discovery coming out of Edmonton. Nicknamed "Terrible Tinsley," the American mathematician and academic is widely considered the greatest checkers player of all time.

He died of cancer in 1995, a year after he played against Chinook in Boston. Mr. Tinsley had beaten the computer in 1992, but left the 1994 match halfway through due to medical problems.

"At one time, [Mr. Tinsley] made the statement that no computer would ever beat him," Al Lyman, a lifetime member of the American Federation of Checkers, recalled in a telephone interview.

Mr. Lyman, who also runs checkerworld.com, a website dedicated to promoting the game, said Prof. Schaeffer and his colleagues' research will likely help checkers gain badly needed publicity and recognition.

"Checkers is a poor, poor world," the 67-year-old said with a sigh. "Chess has television coverage, corporate sponsorship and big prizes. Checkers simply doesn't have that and therefore it's a very small, small family."

While the game is played around the world, and there are associations in several countries including Canada and England (where it's call draughts), it has long struggled to be taken as seriously as its arch-rival, chess.

Prof. Schaeffer said people often consider the game — which uses 12 red and black pieces called checkers — simple because it is easy to learn the rules.

"It took me less than a minute to teach it to my daughter," he said. "But just because the rules of checkers are simple does not mean it's a simple game. It's a beautiful game with incredibly deep strategy."

He said their research is a major breakthrough in the field of artificial intelligence and that computer scientists have often used popular games such as chess and checkers as an experimental test bed because the "characteristics of intelligent behaviour are fundamental in those games."

While he's done computer research on chess in the 1980s, he has no immediate plans to try to solve that game unless there are major advancements in technology. "No, it's too big," he said. To put it in perspective: Checkers has roughly the square root of the number of positions in chess.

Instead, Prof. Schaeffer and his team have got their eye on another popular game: poker. Next week, Polaris, a poker-playing computer program they built will challenge two poker professionals in a $50,000 game at an artificial-intelligence conference in Vancouver.

With a report from Erin Anderssen