You are here

Combinatorial Game Theory

Aaron N. Siegel
Publisher: 
American Mathematcial Society
Publication Date: 
2013
Number of Pages: 
523
Format: 
Hardcover
Series: 
Graduate Studies in Mathematics 146
Price: 
89.00
ISBN: 
9780821851906
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Richard Nowakowski
, on
12/31/2013
]

For those wishing to know about combinatorial games in depth this is the book to read.

Combinatorial Games encompass games of pure strategy between two players, Left and Right: there are no chance devices (dice or hidden cards); the players have perfect information and usually the winner is decided by who makes the last move, if there is one. This book considers combinatorial games that usually split into sub-games, the disjunctive sum, in which a player can only play in one of the sub-games, for example, Go, Domineering, Nim, Wythoff’s Nim and Amazons. The Normal play convention has the winner as the player who moves last, under the misère convention, the last player is the loser. Connection games, such as Hex ,and Maker-Beaker or Maker-Maker games like Tic-Tac-Toe and Go-moku, are another major variant but are not covered by this theory, instead, see J. Beck, Combinatorial Games: Tic-Tac-Toe Theory (Cambridge University Press, 2006).

Chapter 1 and Appendix C alone are almost worth the price of the book. In the Appendix, Siegel reports on the history and some personalities in the development of the theory, gained from talking and working with many of them. Chapter 1 is a mini-textbook in itself. For the somewhat-interested reader, this will allow you to impress colleagues and colloquium speakers when you ask “Is the misère version that much harder?” or “Is there an ordinal sum decomposition?” at the appropriate time. For graduate students and others it is an excellent source to find places to start brand new research.

The theory of this variety of Combinatorial Games can be traced from Sprague-Grundy in the 30s, through Guy-Smith in 50s, Conway 1976 (On Numbers and Games, 2nd edition, A K Peters, Ltd., 2001) and Berlekamp-Conway-Guy 1982 (Winning Ways for your Mathematical Plays, 2nd edition, A K Peters, Ltd., 2001–2004, volumes 1, 2, 3, and 4). Further developments in the theory have been episodic but include many beautiful and surprising results. Most of these are scattered and not particularly easy to find because they are usually presented within the context of analyzing a particular game. Aaron Siegel is currently the strongest researcher in the field and has been involved with many of the central developments. In this book, he has brought them together. Moreover, he includes asides and details that explain how and why certain directions were taken; important insights from an expert.

There are four outcome classes, Left-win — Left wins going first or second; Right-win; First-player win; and Second player win. That every position belongs to one of these classes is an important result, however, as Siegel points on pages 11 and 12, the definition of equality

\[G=H \text{ if and only if } o(G+X)= o(H+X) \text{ for all games } X \ldots \]

is fundamental and by changing “for all games” many new aspects have been discovered.

To take advantage of the disjunctive sum decomposition, the theory attempts to assign values to the components — as in 2-player, zero-sum games, one player, in this case Left, prefers positive values and Right prefers negative values — adding the values then gives the overall value. Fortunately, games are hard and finding these values is tough or else there would be little to say.

Chapters 2, 3 and 4 cover Normal play games that contain only a finite number of positions. The definition of equality is an equivalence relation and each equivalence class has a unique canonical form obtainable in an effective way. These constitute an ordered abelian group. Chapter 2 covers the basic normal play theory, which forms the standard by which all the other variants are measured. The chapter also includes two important approximation techniques: Atomic Weight for infinitesimals and Reduced Canonical form to eliminate infinitesimals. Siegel, with Grossman, re-introduced the latter (read the book) in 2009. It is an important tool to filter out many moves irrelevant in most contexts. Chapter 3 looks more at the abstract structures formed by games; Chapter 4 considers Impartial games (both players have the same moves), which were introduced by Sprague and Grundy.

Before 2004, there was no general theory for misère games. Plambeck, then Plambeck-Siegel, pushed forward a new theory of misère games based on the definition of equality but in which \(G\), \(H\), and \(X\)are restricted to positions obtainable from some given position \(F\). Even though this was originally developed for impartial games, Siegel includes the very recent applications to misère partizan games (the players have different moves) from as late as summer 2013.

A game is loopy if positions can re-appear. If Siegel is one of the few misère game gurus, he is the only guru of loopy games. Chapter 6 covers all that is known. The last sentence “This is a theory that’s ripe for further exploration” accurately sums up the state of affairs.

The temperature of a position is a measure of how urgent it is to move in that component, intuitively, how much can be gained. The basics are covered in Chapter 2 but most of the material in Chapter 7 has only been seen in papers concerned with the analysis of Go but the theory is perfectly general. In addition, the approximation technique known as Orthodox temperature theory, i.e., what should happen in a typical sum, developed by Berlekamp, is being presented in a general way for the first time.

Chapter 8 is a delight especially for those with a set-theory bent. It covers the values of games that have infinitely many positions in the game tree. These extend the finite surreal numbers and includes values such as \(\sqrt{\omega}\). Addition of games, via the disjunctive sum, is natural, that there is a multiplicative structure is not so clear. This chapter shows how the group structure can be extended to fields.

The author has kept the tone of the book light and infused it with history, anecdotes, and important observations making it an entertaining and as well as an educational read.


Richard Nowakowski is a professor at Dalhousie University and a serious dabbler in games. He can be contacted at r.nowakowski@dal.ca.