American Scientist

Games of No Chance: Combinatorial Games at MSRI, 1994. Richard J. Nowakowski, ed. 537 pp. Mathematical Sciences Research Institute Publications 29. Cambridge University Press, 1996. $49.95.

This book is the outgrowth of a workshop on combinatorial games held in July 1994 at the Mathematical Sciences Research Institute on the campus of the University of California, Berkeley. Many published collections of "papers at a symposium" are non-books, with little connection or consistency from one chapter to the next, but this one is a welcome exception. These proceedings underwent considerable fine editing prior to publication, so that the reader learns gradually, from the first seven chapters, the scope and methodologies of the rest of the book. The next 10 chapters discuss "classical" games, including checkers, chess, shogi (Japanese chess) and go. The third section (eight chapters) covers "games mathematicians play," including domineering, toads-and-frogs and pentominoes. The eight chapters in the fourth section are more technical mathematically, and deal with theoretical aspects and further generalizations of the family of games under consideration. The last two chapters, which comprise the fifth section, are a listing and brief description by Richard K. Guy of 52 unsolved problems, and a master bibliography of 666 entries.

The title Games of No Chance might conjure up an image of the offerings at a crooked casino, but it actually refers to "two-person full-information games," such as checkers, chess, go and others; dice, card shuffles, rotating wheels and the like play no role. The book heralds the launching of the third phase in the history of the mathematical analysis of such games.

The first phase began with the publication by Charles L. Bouton (in Annals of Mathematics, series 2, 1901–02) of the winning strategy, based on binary numbers, for a then-popular and rather simple carnival game called Nim. In the mid- to late 1930s, R. Sprague and P. M. Grundy independently extended Bouton's results and invented an evaluation function for finding winning positions in a large class of Nim-like games. With the advent of computers, games such as three-dimensional (4 ? 4 ? 4) tic-tac-toe and even checkers were analyzed computationally, although with less initial success than was widely supposed.

The second phase was ushered in by the publication of the two-volume Winning Ways—For Your Mathematical Plays, written by E. R. Berlekamp, J. H. Conway and R. K. Guy in 1982. The Sprague-Grundy function assigned a fairly conventional type of number to each game position, whereas Winning Ways dramatically revised and increased the subtlety of positional evaluation, using infinitesimals of various orders, and even certain types of symbol-values that were not directly comparable (in isolation) with one another. This actually required a major expansion of the classical real-number system to something vastly larger (first described in J. H. Conway's 1976 book On Numbers and Games ), named the "surreal numbers" by Donald Knuth. From this viewpoint, games are a generalization of numbers.

Although it is written in a highly entertaining style, Winning Ways requires great determination and considerable mathematical sophistication to fathom its deeper mathematical concepts. In contrast, Games of No Chance demonstrates the wide dissemination and assimilation of the concepts of Winning Ways, by the 1994 conference, into the analysis of classical two-person board games, as well as to more mathematician-oriented games.

In Mathematical Go (1994), by E. R. Berlekamp and D. Wolfe, it was shown that some of the most subtle mathematical concepts of Winning Ways were applicable to many endgame situations in go. Games of No Chance takes go endings at least one step beyond Mathematical Go. This reviewer is especially impressed by Harvardian Noam Elkies's contribution, because he successfully constructs chess endings of comparable subtlety, typically involving double Zugzwang—positions in which White to move must lose, but also Black to move must lose. Games of the complexity of go, chess or shogi are by no means solved, but these new techniques enable the reader to find the very best move when the game has reached a sufficiently advanced stage. Gradually, as the theory matures, this "advanced stage" will occur earlier and earlier in the game. Surprisingly, far simpler games, such as checkers, dots and boxes (still played by children in elementary schools), hex and domineering (the last two being simple-looking competitions between a horizontal-playing competitor and a vertical-playing competitor) are not completely solved, although superior strategies for them are described in this book.

In a chapter by Hilarie K. Orman, it is shown that the reviewer's Pentomino game is a theoretical win for the first player, and it goes on to exhibit two different winning first moves, plus one losing first move. There are nearly 300 other possible first moves, whose status as "winning" or "losing" has not yet been determined. For each first move, the second player has literally hundreds of distinct possible replies, but because the game can continue for no more than 12 moves, a complete search of the "game tree" is possible. For games of the complexity of chess and go, a complete search of the game tree appears "forever" infeasible. It is for these currently "unsearchable" games of no chance that the methods described in this book represent the most significant progress.

This book must be read by every serious student of two-person full-information games, and it provides an excellent presentation for anyone seeking a proper introduction to this fascinating subject.—Solomon W. Golomb, Mathematics and Electrical Engineering, University of Southern California