Friday, July 20, 2007

"Not every problem can be solved with chess, Deep Blue. Someday you'll learn that."

A computer, Chinook, has perfected the game of checkers:
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.


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.

I think it's clear that the next step is global domination. We have no choice but to surrender to our robot, checkers-playing overlords.

No comments: