Combinatorial game theory is the subsection of game theory dedicated to studying games in which neither chance nor hidden information is involved. At first pass it might seem like this would make the study of games much easier, note that examples of combinatorial games include chess, checkers, Go and Connect Four. And as anyone who has played these games knows (and I imagine that this includes just about anyone reading this review), combinatorial games get very complex very quickly, and understanding the strategies involved is often an NP-complete problem. In June of 2005 a workshop on the study of combinatorial game theory was held at Banff International Research Station, and the proceedings of this conference have been edited by Michael H. Albert and Richard J. Nowakowski and released as the third book in a series entitled Games of No Chance. (The first book in this series was reviewed in Read This! back in 1999 and the second in 2003.)
The chapters of the book are divided into several different parts. The first part is filled with “Surveys” which are intended to introduce the reader to some of the subjects at hand, and includes chapters entitled “Algorithmic combinatorial game theory”, “Advances in losing” (in which the author discusses how one can think of the positions of a game as a monoid, and in this way better understand games in which the last player to move loses rather than wins, as is the traditional convention), “Coping with cycles” (where games in which one can repeatedly return to the same position are considered), and “On day n.” These articles are all quite engaging and well-written, although it should be pointed out that they do assume some familiarity with the field of combinatorial game theory (and in some cases more than this reviewer had), at the level of Conway’s On Numbers and Games or Berlekamp, Conway, and Guy’s Winning Ways.
The second part of the book begins the more traditional research articles with a set of articles on “Standards”; that is, articles on games such as Go and Hex, as well as the Toads and Frogs that readers of Winning Ways will undoubtedly recall. The third section has a pair of articles analyzing the complexity of the Dyson Telescopes puzzle, the game of Amazon, and the ancient Hawaiian game Konane. The fourth section is on “Impartial” games such as Chomp and Nim. The fifth section has articles on games with infinitesimal values, including articles on partizan games and an article by Berlekamp on Yellow-Brown Hackenbush. (As an aside, some of the fun in reading about combinatorial game theory clearly comes from the names of these games!)
The final part of the book consists of two “Columns”, which will be incredibly useful to anyone hoping to dip their toes into research in this field. The first chapter, by Richard Guy and Richard Nowakowski lists many unsolved problems in the field, several of which this reviewer spent quite a bit of time thinking about and trying to make progress on. (It should be noted that he did not succeed.) Finally, Avi Fraenkel has compiled a bibliography of over a thousand (1360, to be exact!) references in the field, which is surely more than enough for anyone whose appetite has been whetted by the 21 articles in this volume.
Darren Glass is an Associate Professor of Mathematics at Gettysburg College. He can be reached at dglass@gettysburg.edu.