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.