You are here

More Games of No Chance

Richard J. Nowakowski, editor
Cambridge University Press
Publication Date: 
Number of Pages: 
[Reviewed by
Ed Sandifer
, on

Has it been a while since you beat your computer in chess? It's not just that your new computer is a million times faster than your first one was, or that its memory is measured in Megs and Gigs instead of K. The theory of such games has developed rapidly over the last several years, and that, too, has made it even tougher to beat your computer. For that, in part, you have the contributors to this book to blame.

The fundamental subject of this book is a class of games called Games of No Chance, part of the larger field of combinatorial game theory. These are two-player games, like Chess or Go, that might be called "strategy games." Players take turns moving, and each player knows everything about the position of the game and the legal moves. There are, as the name suggests, no dice, no flipping coins, no shuffling of cards. They involve only pure strategy. Assuming both players play perfectly, then, as Laplace said of the Universe almost 200 years ago, if you know the rules, if you know the initial position, and if you can do the calculations, then you know how things should come out.

More Games of No Chance, edited by Richard Nowakowski, is a sequel to the 1994 Mathematical Sciences Research Institute publication Games of No Chance. The 32 articles in this volume show that much progress was made in eight years. In the 1994 volume, the main tools were the values of games, what are sometimes called "numbers", other times called "surreal numbers." These ideas were developed in 1972 by John Conway in On Numbers and Games and in 1982 by Berlekamp, Conway and Guy in Winning Ways for your Mathematical Plays. This 2002 volume incorporates a variety of other tools and ideas, for example those of complexity theory, temperature, cellular automata and lattice structures.

Martin Gardner seems to be a kind of beloved uncle and role model for this whole field of combinatorial games. His fans have held four weekend "Gatherings for Gardner," G4G's, at which they discuss and play mathematical games, puzzles and magic. In "The 4G4G4G4G4 Problems and Solutions," Elwyn Berlekamp describes some problems and solutions that came up at the fourth of these gatherings, G4G4. In particular, he describes a particular sum of four combinatorial games, a Go game, a Domineering game, a Checkers game and a Chess game. On each move, a player must decide in which game he/she will make a move, and also decide what move to make in that game. Berlekamp calls this particular combination 4G4G, "Four Games for Gardner." There are a few ambiguities about how games should be combined. For example, since Checkers may have a "must capture" rule, does this mean that a player who has a capture available in the Checkers portion of the game must make the next move in Checkers, or does it mean that, if he/she chooses to play in Checkers, then the move must be a capture? In Chess, the condition of check raises similar issues. Berlekamp shows the resolution of these issues do not change the nature of the game. Then he shows that a strategy of play based on temperature almost always produces winning play.

Practitioners of this subject sometimes seem to invent games rather haphazardly. This is not quite the case. More often, these cleverly named games are designed to test a new idea or to exploit a new technique of analysis. One such game is Amazons, the subject of two articles, "Experiments in Computer Amazons" by Martin Müller and Theodore Tegos, and "Exhaustive Search in the Game Amazons" by Raymond Georg Snatzke. Amazons was invented by Walter Zamkauskas in 1988. It is played on a 10x10 board. Each player gets four pieces that move like queens in Chess. Each turn has two parts, a "move" and a "shoot." After the move, the piece shoots an arrow in any of eight directions. When the arrow cannot move any farther, either because it reaches the edge of the board or because it reaches another piece or because it reaches a space that has already been hit, it hits the last vacant space, and that space is removed from play. No pieces are ever captured or injured by arrows, though they may become trapped and unable to move. The first player with no legal move loses the game. Since each turn removes a space from play, and the game begins with 92 vacant spaces, the game must end after at most 92 turns.

A game of Amazons tends to divide the board into regions blocked by arrows and by pieces. Regions blocked by pieces may be only incompletely defined or, if the blocking pieces move, temporarily defined. The tools of combinatorial game theory are well equipped to handle partitioned games. Amazons, though, is only incompletely or partially partitioned, so its analysis challenges theorists to extend and refine their tools.

Articles in this book cover a rich variety of particular games, Go, Chomp, Hex, Hypercube Tic-Tac-Toe, Domineering, Phutball, as well as theories and techniques that apply to combinatorial games in general. The material is often difficult, but usually fascinating.

In conclusion, despite the fun and games at its heart, this is a research volume. These guys (and for the most part, they are "guys." Only four of the 55 authors, counting multiplicity, are women) still have a lot of fun, but it is serious mathematics. The mathematics is sometimes difficult, and much of it has substantial prerequisites. Combinatorial game theory is an exciting and rapidly developing new field. This volume will be popular among practitioners in the field, and should attract a good number of new people to the field.

Ed Sandifer ( is professor of mathematics at Western Connecticut State University and has run the Boston Marathon 30 times.

Part I. The Big Picture: 1. Idempotents among partisan games Elwyn Berlekamp; 2. On the lattice Structure of finite games Dan Calistrate, Marc Paulhus and David Wolfe; 3. More infinite games John H. Conway; 4. Alpha-Beta pruning under partial orders Matthew L. Ginsberg; 5. The abstract structure of the group of games David Moews; Part II. The Old Classics: 6. Higher numbers in pawn endgames on large chessboards Noam D. Elkies; 7. Restoring fairness to Dukego Greg Martin; 8. Go thermography: the 4/21/98 Jiang-Rui endgame Bill Spight; 9.An application of mathematical game theory to go endgames: some width-two-entrance rooms with and without Kos Takenobu Takizawa; 10. Go endgames are PSPACE-hard David Wolfe; 11.Global threats in combinatorial games: a computation model with applications to chess endgames Fabian Mäser; 12. The games of hex: the hierarchical approach Vadim V. Anshelevich; 13. Hypercube tic-tac-toe Solomon W. Golomb and Alfred W. Hales; 14. Transfinite chomp Scott Huddleston and Jerry Shurman; 15. A memory efficient retrograde algorithm and its application to Chinese chess endgames Ren Wu and Donald F. Beal; Part III. The New Classics: 16: The 4G4G4G4G4 problems and solutions Elwyn Berlekamp; 17. Experiments in computer amazons Martin Müller and Theodore Tegos; 18. Exhaustive search in Amazons Raymond Georg Snatzke; 19. Two-player games on cellular automata Aviezri S. Fraenkel; 20. Who wins domineering on rectangular boards? Michael Lachmann, Christopher Moore and Ivan Rapaport; 21. Forcing your opponent to stay in control of a loony dot-and-boxes endgame Elwyn Berlekamp and Katherine Scott; 22. 1 x n Konane: a summary of results Alice Chan and Alice Tsai; 23. 1-dimensional peg solitaire, and duotaire Christopher Moore and David Eppstein; 24. Phutball endgames are hard Erik D. Demaine, Martin L. Demaine and David Eppstein, 25. One-dimensional phutball J. P. Grossman and Richard J. Nowakowski; 26. A symmetric strategy in graph avoidance games Frank Harary, Wolfgang Slany and Oleg Verbitsky; 27. A simple FSM-based proof of the additive periodicity of the Sprague-Grundy function of Wythoff's games Howard Landman; Part IV. Puzzles and Life: 28. The complexity of clickomania Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen and Ian Munro; 29. Coin-moving puzzles Erik D. Demaine, Martin L. Demaine and Helena A. Verrill; 30. Searching for spaceships David Eppstein; Part V: Surveys: 31. Unsolved puzzles in combinatorial game theory: updated Richard K. Guy and Richard J. Nowakowski; Bibliography of combinatorial games: updated Aviezri S. Fraenkel.