Game over. Computer scientists at the University of Alberta in Canada have solved checkers, the popular board game with a history that dates back to 3,000 B.C.

The results of this research are published Thursday in U.S. academic journal Science.

After 18-and-a-half years and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions, Dr. Jonathan Schaeffer and colleagues have built a checkers-playing computer program that cannot be beaten.

Completed in late April this year, the program, Chinook, may be played to a draw but will never be defeated. Checkers is the most challenging popular game that computers have solved to date.

With the help of some top-level checkers players, Schaeffer programmed heuristics ("rules of thumb") into a computer software program that captured knowledge of successful and unsuccessful checkers moves. Then he and his team let the program run, while they painstakingly monitored, fixed, tweaked, and updated it as it went.

An average of 50 computers were used everyday to compute the knowledge necessary to complete Chinook. Now that it is complete, the program no longer needs heuristics -- it has become a database of information that "knows" the best move to play in every situation of a game. If Chinook's opponent also plays perfectly the game would end in a draw.

Schaeffer started the Chinook project in 1989, with the initial goal of winning the human world checkers championship. In 1990 it earned the right to play for the championship. The program went on to lose in the championship match in 1992, but won it in 1994, becoming the first computer program to win a human world championship in any game--a feat recognized by the Guinness Book of World Records.

Chinook remained undefeated until the program was "retired" in 1997. With his sights set on developing Chinook into the perfect checkers program, Schaeffer restarted the project in 2001.

"I'm thrilled with this achievement," Schaeffer said. "Solving checkers has been something of an obsession of mine for nearly two decades, and it's really satisfying to see it through to its conclusion."