Try your hand against the supercomputer

It is game over for draughts: scientists have created the ultimate computer player, which can be battled to a draw with a perfect strategy but can never be beaten.

Even the greatest human draughts grandmasters will never be able to compete with Chinook, a computer program developed by Canadian researchers that can sift through every one of the game’s 500 billion billion positions to pick the most advantageous move every time.

The best that a human player — or another computer — can hope for in a match against Chinook is a draw: even a mistake-free game will not end in victory but in stalemate. A single error means the computer will inevitably win.

The program took computer scientists at the University of Alberta in Edmonton 18 years to perfect, and in the final stages of the research an average of 50 powerful computers were used daily with more than 200 running at peak times.

Its success means that the game of draughts — known in North America as checkers — has essentially been solved. Every possible position has now been mapped by Chinook, which has proved mathematically that two players who make no mistakes at all will always cancel each other out.

This discovery, which is published in the journal Science, has come as no surprise to connoisseurs of the game: draughts grandmasters regularly play each other to a draw, and championships are generally decided on a handful of tiny mistakes that turn the occasional contest.

Draughts is by far the most complex game to have been solved by computer in this way, but while progams such as Deep Fritz and Deep Blue have been defeating chess grandmasters for a decade, it will be a long time yet before an infallible chess-playing machine can be developed.

Though the games are played on a similar board, twice as many squares are in play in chess as in draughts, and the greater range of moves that chess pieces can make make it many times more complicated. There are between 10^40 and 10^50 possible positions — that is a one followed by 40 or 50 noughts, compared to a five followed by 20 noughts for draughts.

Even with the most powerful computers available today, it would take thousands if not millions of years to map every possible chess move as Chinook has done for draughts. “Checkers has roughly the square root of the number of positions in chess,” said Jonathan Schaeffer, who led the Chinook team.

“Given the effort required to solve checkers, chess will remain unsolved for a long time, barring the invention of new technology.”

Games similar to draughts are said to date back to 3000BC, and the modern form of the game developed in the 15th and 16th centuries. In the standard version, known as English draughts or American checkers, each player has 12 disc-shaped counters, which move forward diagonally on an eight-by-eight chequered board.