Thursday, July 19, 2007
Thursday, July 19, 2007
For an exercise in futility, go play checkers against a computer program named Chinook.
Related ArticleDeveloped by computer scientists at the University of Alberta in Canada, Chinook vanquished human competitors at tournaments more than a decade ago. Now, in an article published today on the Web site of the journal Science, the scientists report that they have rigorously proved that Chinook, in a slightly improved version, cannot ever lose. An opponent, no matter how skilled, practiced or determined, can at best achieve a draw.
In essence, that reduces checkers to the level of tic-tac-toe, where the ideal game-playing strategy has been codified into a series of immutable rules. But checkers — or draughts as it is known in Great Britain — is much more complex, with 500 billion billion theoretically possible board positions; it is the most complex game that has been solved to date.
Jonathan Schaeffer, a professor of computer science at the University of Alberta, set out on his checkers-playing quest in 1989, aiming to write software that could challenge the world checkers champion. He and his colleagues finished their computations 18 years later, in April.
“From my point of view, thank god it’s over,” Dr. Schaeffer said.
Even with the advances in computers over the past two decades, it is still impossible, in practical terms, to compute moves for all 500 billion billion board positions. Instead, the researchers took the usual starting position and then looked only at the positions that would occur during the normal course of play.
“It’s a computational proof,” Dr. Schaeffer said. “It’s certainly not a formal mathematical proof.”
Because of the vast numbers of calculations, the researchers had to painstakingly keep track of every bit of data. The miscopying of a single bit — the type of glitch that did occur every few months — could render their result incorrect if it were not caught and corrected.
Anyone can play a game against the perfect Chinook at http://www.cs.ualberta.ca/~chinook/. (It is limited to 24 matches at a time.)
The earlier incarnation of Chinook, relying on artificial intelligence techniques and the combined computing power of many computers, competed in the 1990 United States championship and placed second behind Marion Tinsley, the world champion who had won every tournament he had played in since 1950.
That achievement should have earned Chinook the right to challenge Dr. Tinsley, a professor of mathematics at Florida State University, for the world championship, but the American Checkers Federation and the English Draughts Association refused to sanction the match. After much wrangling in the checkers world, Dr. Tinsley and Chinook battled for the Man-Machine checkers title in 1992.
Dr. Tinsley won, 4 to 2 with 33 draws. Chinook’s two wins were only the sixth and seventh losses for Dr. Tinsley since 1950. In a rematch two years later, Dr. Tinsley withdrew after six draws, citing health reasons. Cancer was diagnosed, and Dr. Tinsley died seven months later.
In subsequent tournaments, Chinook handily triumphed over other human challengers, but the unfinished match against Dr. Tinsley left a lingering question of whether Chinook could claim to be the best of all time.
The new research proves that Chinook is invincible in the traditional game of checkers. But in most tournament play, a match starts with three moves chosen at random. In solving the traditional game, the researchers have also solved 21 of the 156 three-move openings, leaving a crack of hope for humans, at least for now.
For Dr. Schaeffer, the next game he hopes to conquer is poker. Next week, his program, Polaris, will take on two professional poker players in Texas Hold’em for the $50,000 man vs. machine world championship.