Image: Chinook proof
University of Alberta
This screen shot shows a "tree" of checkers moves that can be used to verify the mathematical claims for the invincibility of the Chinook game-playing program.
By
Special to msnbc.com
updated 7/19/2007 2:00:01 PM ET 2007-07-19T18:00:01

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.

Daunting task
Arriving at the right solution, Schaeffer said, was akin to accurately mapping out a grid covering Earth’s surface, where every square inch is divided into 1,000 pieces. Each of those pieces, he said, represents a possible checkers position.

Despite the daunting task, Chinook earned some early triumphs for its creators. In 1992, the computer won the right to challenge the reigning checkers world champion, Marion Tinsley, widely considered the best player ever. Chinook lost 4 to 2 with 33 draws in that title match, but won the 1994 rematch by default when Tinsley withdrew due to illness after six draws. It was the first time a computer program had won a human world championship, a feat recognized by the Guinness Book of World Records.

Thereafter, Chinook equaled or bested all of its opponents until its retirement in 1997, the same year that IBM’s chess-playing Deep Blue computer beat reigning world champion Gary Kasparov to far greater fanfare.

Although chess-playing programs have consistently beaten the best players in the world since Deep Blue’s triumph, they cannot claim the invincible status of Chinook. Solving chess, experts say, would require an effort so massive that the world’s fastest computers would need eons to play out every possible move.

Murray Campbell, one of Deep Blue’s designers and programmers, hailed the new checkers solution as “a very important milestone along the way toward machine intelligence.”

Campbell, based at IBM’s Thomas J. Watson Research Center in Hawthorne, N.Y., said the Chinook program uses an accumulated “brute-force intelligence” that could be applied to fields requiring computers to sift through enormous databases. Bioinformatics researchers, for example, often use a brute-force approach when comparing DNA or encoded proteins, while programmers have relied on similar methods to produce more realistic machine-aided translations from, say, English to French.

In 10 years, Chinook and “brute-force intelligence” applications like it may seem trivial, Campbell said. “For now, with what we’ve got available,  it’s quite an impressive accomplishment.”

Next up: poker
Schaeffer isn’t resting on his laurels, however.

Next week, the computer scientist and his colleagues will bring a poker-playing computer program dubbed Polaris to Vancouver, Canada, to challenge two professional players in a $50,000 world championship as part of the annual conference for the Association for the Advancement of Artificial Intelligence.

With games like checkers, Schaeffer said, the information is all out in the open. Not so for poker, when it can be impossible to tell whether your expressionless opponent has an ace of spades or a two of diamonds.

“The real world,” Schaeffer said, “is all about dealing with imperfect information,” meaning that the real test of artificial intelligence’s mettle could arrive in a hard-fought poker game. No one has yet come up with a “superhuman” poker program, though Schaeffer is betting that Polaris may just give some of the world’s best humans a good run for their money.

© 2013 MSNBC Interactive.  Reprints

Discuss:

Discussion comments

,

Most active discussions

  1. votes comments
  2. votes comments
  3. votes comments
  4. votes comments