Checkers computer becomes invincible

Checkers champions, meet your match.

An invincible checkers-playing program named Chinook has solved a game whose origins date back several millennia, scientists reported Thursday on the journal Science's Web site. By playing out every possible move — about 500 billion billion in all — the computer proved it can never be beaten. Even if its opponent also played flawlessly, the outcome would be a draw.

Chinook, created by computer scientists from the University of Alberta in 1989, wrapped up its work less than three months ago. In doing so, its programmers say the newly crowned checkers king has solved the most challenging game yet cracked by a machine — even outdoing the chess-playing wizardry of IBM’s Deep Blue.

The new achievement, led by the University of Alberta’s Jonathan Schaeffer, has been likened by other scientists to scaling Mount Everest.  More tangibly, the work could ramp up artificial intelligence and parallel computing know-how and lessen the load for other programs trying to sift through vast DNA databases or produce machine-assisted language translations.

Michael Littman, a professor of computer science at Rutgers University in Piscataway, N.J.,  said Schaeffer’s checkers program had succeeded in “not just taking on the best human being, but taking on the game itself.”

Littman, who has designed a computer program to complete crossword puzzles, said creating a program that can beat any human competitor may be a sociologically important landmark. But by beating “anything that could possibly play the game,” he said, Chinook stands out as a significant mathematical accomplishment to boot.

Memorizing every move
Checkers — or draughts, as the game is known in Britain — is played on a board of 64 dark and light squares, though each opponent’s 12 game pieces are allowed to move only diagonally along the dark squares. Chinook was not designed to “think” through all permitted strategies on its own but to memorize the consequences of every possible move, allowing it map out a start-to-finish strategy that would, at worst, result in a draw.

With assistance from some of the world’s best checkers players, Schaeffer and his team introduced rules of thumb into their massive computer program and then allowed it to capture information about winning and losing moves, tweaking it along the way. In building the database, the program assembled the 39 trillion pieces of information needed to determine all possible outcomes when 10 or fewer checkers remain on the board.

Next, the team built a database of beginning moves that would eventually lead players to the endgame. The final challenge was to forge tight links between the game’s start and finish.

“The whole strategy in solving a game is to shrink that middle part until it disappears, so your beginning game and your end game connect,” Littman said.

On April 29, Chinook did exactly that when it determined that perfect play by both sides would always lead to a draw.

‘Stunned disbelief’ at the end
Schaeffer said his initial reaction was “sort of stunned disbelief.” After all, the computer program had been a daily part of his life, except for a four-year hiatus between 1997 and 2001.

“The computation that I do today feeds into the computation that I do tomorrow,” he said, meaning that past errors must be detected and weeded out before they skew the entire computation going forward. Even a single mistake could scuttle months or years of work,  requiring Schaeffer and his colleagues to monitor up to 200 computers working simultaneously — and recheck even mundane tasks like copying files onto discs.

“Typically, at least once a month there would be a disc error that would need to be detected and corrected,” he said. The team even had to contend with “bit rot,” which refers to the corruption of previously correct data through the gradual degradation of the computer disc containing the data.

MORE FROM FRONTIERS

Tourist or terrorist? Computer knows

Tourist or terrorist? Computer knows Climbing no obstacle for snakebots The next 'American Idol'? Ask your computer How a deadly avalanche can be triggered Green alternative to plastics: liquid wood Getting lost for better architecture Turning air into drinking water Revving up the race for fuel efficiency How to be a disagreeable (but likable) robot Can concept of clean coal be salvaged?   Add Frontiers headlines to your news reader: