More Games of No Chance

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 ([email protected]) is professor of mathematics at Western Connecticut State University and has run the Boston Marathon 30 times.