http://technology.timesonline.co.uk/...cle2105876.ece
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.
Counters jump over opponents’ pieces to capture them, and those that reach the opponent’s end of the board become “kings” and can move backwards as well as forwards.
Chinook was developed by teaching a computer to use rules of thumb or “heuristics” to know what move to make in particular situations. It became so sophisticated that in 1994 it became the first computer to win the human world championship in any game.
In a contest against Marion Tinsley, who lost only three tournament games in four decades and is considered the best player of all time, Chinook achieved a string of draws before Tinsley withdrew with health problems and conceded.
The new version of Chinook is more powerful still: even Tinsley could not have beaten it. “To this day, I still get people saying that you would never have beaten Tinsley,” Dr Schaeffer said. “The program today would never lose to Tinsley or anyone else, period.
“The program can achieve at least a draw against any opponent, playing either the black pieces or the white. That checkers is a draw is not a surprise: grandmaster players have conjectured this for decades.
“I think we’ve raised the bar — and raised it quite a bit, in terms of what can be achieved in computer technology and artificial intelligence. “With Chinook, we’ve pushed the envelope about one million times more than anything that’s been done before.
“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.”
Independent games experts said Chinook’s achievement was genuinely remarkable. David Levy, president of the International Computer Games Association, said: “It’s a huge accomplishment. It’s by far the most complex game ever solved.”
Jaap van den Herik, editor of the International Computer Games Journal, said: “This is a tremendous achievement — a truly significant advance in artificial intelligence.”
While chess is unlikely to give up its secrets to a computer soon, Dr Schaeffer is confident that other popular games will be “solved” by computers in the near future. “The disc-flipping game of Othello is the next popular game that is likely to be solved but it will require considerably more resources than were needed to solve checkers,” he said.
A poker program developed by the same team, known as Polaris, is also facing its first test next week, in a $50,000 challenge against two human professionals in Vancouver.
