Winning game

Computer scientists at the University of Alberta have solved checkers, the popular board game with a history that dates back to 3,000 BC.

After more than 18 years and sifting through 500 billion billion checkers positions, Jonathan Schaeffer and his colleagues have built a checkers-playing computer program that cannot be beaten.

Completed in late April, the so-called Chinook program may be played to a draw but will never be defeated.

Checkers is the largest non-trivial game of skill to be solved - it is more than one million times bigger than Connect Four and Awari, the previously biggest games that have been solved, Schaeffer added.

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

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 recognised by the Guinness Book of World Records.

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

The checkers researcher was supported by the Natural Sciences and Engineering Research Council of Canada, iCORE, the Canada Foundation for Innovation, Western Canada Research Grid, and the University of Alberta.