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.
All the right moves
How to play checkers
In the game of checkers, known as draughts in Britain, two players alternate moves on an eight-by-eight-inch checkerboard. Each side starts off with 12 pieces . Checkers move diagonally forward one square. Capturing an opponent's piece is done by jumping over a diagonally adjacent opponent piece and landing on an empty square. When a checker reaches the far end of the board, it is promoted to king. Kings move and capture as checkers, but they have the additional ability to go backward. A player loses when he runs out of pieces or when he has no legal moves.
History of the game
Although checkered playing boards and pieces have been found that date back to the Egyptian pyramids, there is no record of the ancient rules of play. Checkers as it is known today became popular in Spain in the mid-1500s, but it wasn't until William Payne's An Introduction to the Game of Draughts in 1756 that the game began to acquire a large following. Draughts quickly spread throughout England and Scotland. The popularity of the game spread to the rest of the English-speaking world, and by 1900, strong players began to emerge in North America.
How to play Chinook
In 1994, Chinook became the first computer program to win a human world championship. The program on the University of Alberta website is the champion but it has been reduced in strength to allow players to have a chance at drawing. To play, a player must select one of three levels: novice, amateur or intermediate. (Jonathan Schaeffer, Chinook's creator, plays at the novice level.) After the player submits his or her move, Chinook will respond within a minute or so.
Source: Department of Computing Science, University of Alberta