You are here

Games of No Chance 3

Michael H. Albert and Ricahrd J. Nowakowski, editors
Publisher: 
Cambridge University Press
Publication Date: 
2009
Number of Pages: 
575
Format: 
Paperback
Series: 
Mathematical Sciences Research Institute Publications 56
Price: 
39.99
ISBN: 
9780521678544
Category: 
Anthology
[Reviewed by
Darren Glass
, on
08/17/2009
]

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.

Part I. Surveys 
1. Playing games with algorithms: algorithmic combinatorial game theory Erik D. Demaine and Robert A. Hearn
2. Advances in losing Thane E. Plambeck
3. Coping with cycles Aaron N. Siegel
4. On day N David Wolfe

Part II. Standards
5. Goal threats, temperature and Monte-Carlo Go Tristan Cazenave
6. A puzzling hex primer Ryan B. Hayward
7. Tigers and goats is a draw Lim Yew Jin and Jurg Nievergelt
8. Counting liberties in Go capturing races Teigo Nakamura
9. Backsliding toads and frogs Aaron N. Siegel
10. Loopy games Aaron N. Siegel
11. A library of eyes in Go, I: a life-and-death definition consistent with bent-4 Thomas Wolf
12. A library of eyes in Go, II: monolithic eyes Thomas Wolf and Matthew Pratola

Part III. Complexity
13. The complexity of Dyson telescopes Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Robert A. Hearn, and Timo von Oertzen
14. Amazons, konane, and cross purposes are PSPACE-complete Robert A. Hearn

Part IV. Impartial
15. Monotonic sequence games M. H. Albert, R. E. L. Aldred, M. D. Atkinson, C. C. Handley, D. A. Holton, D. J. Mccaughan, and B. E. Sagan
16. The game of end-wythoff Aviezri S. Fraenkel and Elnatan Reisner
17. On the geometry of combinatorial games: a renormalization approach Eric J. Friedman and Adam S. Landsberg
18. More on the sprague–grundy function for wythoff's game Gabriel Nivasch

Part V. Theory of the Small
19. Yellow-brown hackenbush Elwyn Berlekamp
20. Ordinal partizan end nim Adam Duffy, Garrett Kolpin, and David Wolfe
21. Reductions of partizan games J. P. Grossman and Aaron N. Siegel
22. Partizan Splittles G. A. Mesdal III

Part VI. Columns
23. Unsolved problems in combinatorial games Richard K. Guy and Richard J. Nowakowski
24. Bibliography of combinatorial games Aviezri S. Fraenkel