In this textbook, the author develops the basic theory of combinatorial games. These are games in which two players take turns, with the players having perfect information about the state of the game. There are no elements of random chance. In the normal form considered here, the last player who makes a legal move wins the game. (In the more complicated misère form, the last player to move loses the game. Misère play is not considered in this book.) Many popular games, such as tic-tac-toe and the game of Nim, satisfy these requirements.
The first attempts to analyze combinatorial games in a general way were made by Sprague and Grundy. However, the theory developed substantially in the 1970s when the notion of disjunctive sums of games and Conway's surreal numbers were first used in the analysis of games. These ideas were developed in the encyclopedic book Winning Ways by Berlekamp, Conway, and Guy and in Conway's book, On Numbers and Games. Since the 1970s, this has been a field of active research. However, the present volume is the first book to present combinatorial game theory in the form of a textbook suitable for students at the advanced undergraduate level.
After an introductory chapter that defines terminology and a second introductory chapter that explains some basic techniques used throughout the book, the authors dive into the development of the theory. The fundamental theorem of combinatorial game theory asserts that for a two-player combinatorial game, one of the two players must have a winning strategy. The next goal is to determine for any position which player should win with perfect play. After developing the theory to solve this problem, the authors go on to consider some special cases of the theory, including impartial games, hot games, and all-small games. The book concludes with a chapter that introduces the reader to more advanced topics.
Although the authors state and prove theorems in a rigorous fashion, the presentation is enlivened with many concrete examples. Each chapter is accompanied by exercises. Brief solutions to many of the exercises are given in an appendix. Another appendix describes CGSuite, a software package that can be used to analyze combinatorial games.
This is an outstanding textbook for advanced undergraduate students with sufficient mathematical maturity and an appropriate background in discrete mathematics. It will also be of interest to more advanced readers who want an introduction to combinatorial game theory.
E. R. Berlekamp, J. H. Conway, and R. K. Guy. Winning Ways for Your Mathematical Plays, second edition, four volumes. A K Peters, Natick MA, 2001.
J. H. Conway. On Numbers and Games, second edition. A K Peters, Natick MA, 2001.
D. E. Knuth. Surreal Numbers. Addison-Wesley Publishing Company, Reading, MA, 1974.
Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.