 |  |  |  |  |
Fit To Be Tied
by James Case
Checkers, like tic-tac-toe, always ends in a tie unless one of the players errs. The recent demonstration* of this fact is the latest and perhaps most notable triumph to date of game theory. As in other branches of mathematics, progress in the field is best measured by the nature and difficulty of the problems solved. The proof that checkers is a tie game—announced in July by Jonathan Schaeffer, leader of a team of eight computer scientists at the University of Alberta—is a signal achievement comparable in every way to the verification of Kepler’s spherepacking conjecture and Guthrie’s four-color conjecture. Needless to say, it is also subject to the lingering shreds of doubt that cling to any computer-aided proof.
Checkers is by no means the first nontrivial game to be completely solved. Connect Four, Qubic, Go-Moku, Nine Men’s Morris, and Awari are others for which explicit saddlepoint solutions are known.† Checkers is the most complex of these games, in terms of both the number of possible board positions (about 5 × 1020) and the difficulty of choosing the best move to make from a particular position. Awari, with about 1012 board positions, and Connect Four, with about 1014, represent the previous state of the art. Chess, with about 1046 such positions, and Go, with perhaps 10100, seem likely to remain incompletely solved for generations to come.
Whereas most branches of mathematics are at liberty to choose their own “grand challenge” problems, society itself chooses the questions addressed by game theory. It is all very well for game theorists to devise and solve games that demonstrate the capabilities of their often ingenious methods, but the exercise seems rather pointless unless—sooner or later—it enables people to compete more effectively in contests of practical interest, either for recreation, as in chess and checkers; for material gain, as in warfare, commerce, and professional sport; or for their very survival, as in a duel or knifefight. Checkers is the first genuinely popular recreational game to be solved completely. Computer game specialists believe that backgammon, along with the two-player versions of Scrabble and Monopoly, might be solved within the next few years. Schaeffer has announced an interest in solving poker.
Rufus Isaacs (1914–1981), who invented differential games while working on pursuit– evasion problems at the RAND Corporation in the 1950s, used to argue that recreational games furnish the most reliable yardstick for measuring progress in game theory: They are intended to be intellectually challenging, and typically are—more so than the games arising in commerce, warfare, and/or athletic competition. And because the published rules dictate the geometry of each and every node in the associated decision tree, the modeling of such games is already complete.
More than eighty years have elapsed since von Neumann proved his perfect information theorem, asserting that all two-person zero-sum games with perfect information— including such familiar board games as chess, checkers, backgammon, and Go—have saddle-point solutions in pure (non-randomized) strategies. (Games of imperfect information include Scrabble, in which a player doesn’t know what unplayed letters his opponent holds, and casino poker, in which a player doesn’t know his opponent’s face-down cards.) Until then, no one had been able to explain precisely what it even means to play flawlessly in such a game. Yet because of the labor involved, von Neumann’s demonstration spawned no immediate attempt to solve the more common board games.
Only with the development of programmable electronic computers following World War II did serious scientists contemplate solving such games. Those who did soon realized that the primitive machines of the day were manifestly unequal to the task. As late as 1997, the Alberta researchers set aside their work on checkers for the better part of four years, pending the availability of faster computers. As they wrote this year in their announcement in Science, the “dramatic increase in on-chip parallelism that multi-core computing will soon offer” will further increase the effectiveness of their search algorithms.
Schaeffer began the Alberta checkers project in 1989 as an attempt to build a computer program—it would later be named Chinook—capable of challenging the world champion. In 1990, Chinook earned the right to play for the world championship. In 1992, world champion Marion Tinsley (who had not been beaten in tournament play since 1950, and is widely regarded as the most accomplished checkers player of all time) narrowly defeated Chinook in the title match. Tinsley withdrew from a 1994 rematch after several games because of ill
health, and died of cancer eight months later. The 1996 version of Chinook was stronger than any human player, and subsequent versions (with faster computers to run on) have only widened the gap.
The “closing book” database has been an important part of every version of Chinook. In the original (1989) version, the book contained (at least implicitly) the saddle-point solution of every “checkers problem” (a.k.a. subgame of checkers) that begins with at most four pieces still on the board. By 1994, for the Tinsley rematch, the book had grown to include the saddle-point solutions of all seven-piece and many eight-piece subgames. By 1996, the eight-piece database was complete, prompting team members to speculate that a complete solution of the game was within reach. But slow progress caused the researchers to stop work on the project the following year. It had taken seven years (1989–1996) to complete the eight-piece database. In 2001, when work resumed on newer and faster computers, the eight-piece database was recomputed within a month.
By 2005, the complete 10-piece database, representing (albeit implicitly) some 39 trillion saddle-point solutions, was complete. The data within are compressed into a “mere” 237 gigabytes, for an average of 154 saddle-point solutions per byte! A custom compression algorithm allowed for cheap/rapid decompression of the information required by the search algorithms used to complete the proof.
In theory, the closing book could simply have been expanded to include saddle-point solutions for all 11-piece subgames, then all 12-piece subgames, and so on, until a solution was found for the 24-piece subgame beginning in the usual starting position, which is checkers itself. In practice, however, the time required would be prohibitive. Whereas “only” 39 trillion subgames begin with ten or fewer pieces on the board, some five trillion trillion begin with 24 or fewer pieces. Subtler methods were required to complete the proof that checkers is a tie game.
In a 1950 paper,‡ Claude Shannon explained how, “in principle,” a computer might be programmed to play a competent, if by no means flawless, game of chess. In 1997 the IBM computer Deep Blue II, based in essence on Shannon’s prescription, beat world chess champion Garry Kasparov two games to one (with three ties) in a series of six games. Deep Blue must have played competently, as Kasparov had never been defeated as a professional. But it cannot have played flawlessly, because Kasparov won the first game. Likewise beatable was the strategy Logistello, which defeated Takeshi Murakami—then the world champion player of Othello—four months later. So too was the 1994 version of Chinook to which Marion Tinsley graciously conceded defeat. Like human champions, these winning programs are destined to reign only temporarily. Chinook alone has claimed permanent possession of the title.
In practice, the earlier versions of Chinook functioned as design tools for the current version. The Alberta team used them to generate hypotheses concerning the moves that would lead to a known winning (or non-losing) board position. Each verification of such a hypothesis represented progress toward the proof. The existence of a closing book, which prevents searches from dragging on forever, simplifies the proof considerably. In a known 10-piece subgame, for instance, the underdog can postpone defeat for as many as 279 individual moves, and the existence of even longer end-game sequences is strongly suspected. Because the information contained in the 10-piece closing book is so tightly compressed, a great deal of effort would be required to determine the
length of the longest terminal sequence.
Although the Alberta researchers suggested in their announcement that their search techniques should apply with little if any modification to “problems such as optimization, planning, and bioinformatics,” there is a clear and present danger that the most direct benefits of their work will go unrealized: It stands to reason that methods developed for solving two-person zero-sum games should apply most readily to the solution of other two-person zero-sum games. Moreover, such contests are known to arise only in recreational games, athletic competition, and warfare. Competition in other walks of life tends to involve more than two contestants and is seldom zero-sum. Of the known spawning grounds for two-person zero-sum games, warfare has by far the greatest effect on the human condition.
Soon after the publication of Theory of Games and Economic Behavior by von Neumann and Morgenstern (1944), it was noted that game theory made it possible to solve certain war games that had defied the best efforts of scientists pressed into service during World War II. And, keenly aware of the invaluable contributions of science and mathematics to the allied victory, high-ranking members of the military were eager to learn what other benefits the new discipline might provide. To them, invincible war-game strategies sounded like something worth looking into. By 1950, all three services had assembled high-powered teams of experts to evaluate the potential of game theory.
The Air Force made the most determined attempt to exploit the new theory,
through its sponsorship of RAND. There—and at various places in the USSR—the applications of game theory to warfare were systematically explored. Despite initial success, progress on both sides of the Iron Curtain soon ground to a halt for lack of computing power. The machines of the day simply were not powerful enough to handle war games of realistic size and complexity. Moreover, the unpopularity of the Vietnam war caused many able scientists (including mathematical scientists) to abandon military research, determined never to return.
The newfound invincibility of hinook, together with the growing number of game-playing computer programs able to perform at superhuman levels, suggests that it may now be possible to solve war games of realistic size and complexity. An early resumption of the effort—on the scale of the game theory group within the math department at RAND during the 1950s and 1960s—to formulate and at least partially solve complex war games could hardly fail to reap important dividends: There is little doubt that lives are saved when a country is prepared to fight smarter, and not only harder, than the enemy.
At least in the beginning, such a group would have to focus on matters of modeling, because that performed during the 1950s and 1960s did not—for obvious reasons—approach the level of detail military planners need and expect. For many of the same reasons that caused the Alberta team to abandon the checkers project between 1997 and 2001, most attempts to model military conflicts as games amenable to (at least partial) solution seem to have been discontinued after 1970.
James Case writes from Baltimore, Maryland. His book Competition: The Birth of a New Science was published this year by Hill and Wang.
*Published online, Science Express, July 19, 2007; published in print, Science,
September 14, 2007, Vol. 317, No. 5844, 1518–1522; DOI: 10.1126/ science.1144079; www.sciencemag.org.
† Brief descriptions of these little-known games, along with assessments of
ongoing efforts to solve them, can be found in the final chapter of Chips Challenging Champions: Games, Computers, and Artificial Intelligence, Jonathan
Schaeffer and Jaap van den Herik, eds., Elsevier Science B.V., Amsterdam, 2002.
‡ C. Shannon, “Programming a Computer for Playing Chess,” Philosophical Magazine, Series 7,Vol. 41, March 1950.
« Back to December 2007 Index