You are here

Games of No Chance

Richard J. Nowakowski, editor
Publisher: 
Cambridge University Press
Publication Date: 
1998
Number of Pages: 
549
Format: 
Hardcover
Series: 
Mathematical Sciences Research Institute Publications 29
Price: 
105.00
ISBN: 
978-0521574112
Category: 
Anthology
[Reviewed by
Ed Sandifer
, on
02/11/1999
]

Some books make mathematics look like so much fun! This collection of 35 articles and a comprehensive bibliography is a marvelous and alluring account of a 1994 MSRI two week workshop on combinatorial game theory. This could be a menace to the rest of mathematics; those folks seem to be having such a good time playing games that the rest of us might abandon "serious" mathematics and join the party.

Even the technical terms are laced with humor. A sampling of the vocabulary of the subject includes: all small, remote star, fuzzy, domination, hackenbush, switches and tinies, hot and cold games, and loopy games. They still have their additive homomorphisms and perfect matchings, multilinear algebra, lemmas and propositions, but the fun is obvious.

The first of the books five sections is an introduction to and review of the subject of combinatorial game theory. Most readers would not be able to finish the book with only the background provided in these hundred pages, but they do point to the literature so a beginner could get a fast start, particularly to Berlekamp, Conway and Guy's "Winning Ways for your Mathematical Plays," often called just WW, and to Conway's "On Numbers and Games," ONAG for short.

The introductory section includes Julian West's account of the two tournaments featured at the workshop, one in Dots-and-Boxes, game many of us remember from childhood as "Dots," and the other in Domineering, a game partially analyzed in WW and in ONAG. How did West's dean react when he learned that West goes to meetings to play games?

The second section turns the tools of combinatorial game theory to classical games, Chess, Checkers, Nine Men's Morris and Go. Ralph Gasser describes the analysis of Nine Men's Morris that showed the game to be a draw, if both players play perfectly. Johathan Schaeffer describes analyses of Checkers and gives a great account of the best Checkers player in history, the late Marion Tinsley, and how he enthusiastically cooperated in the analysis.

The third section deals with games related to the ones in WW and in ONAG, Toads and Frogs, Pentominoes, and others. The notations get complicated and the names of the theorems get colorful, "The Death Leap Principle," "The Terminal Toads Theorem," and "The Finished Frogs Formula," for example.

Both the second and third sections rely on teamwork between the classical mathematical methodology of proving theorems and the modern use of case by case computer analyses, all guided by the experience gained by actually playing the games. Many of the results would be impossible without computers. The analysis of Checkers, for example, required assembling a database of all 443,748,401,247 positions with eight or fewer pieces on the board. On the other hand, the database would be useless without the theorems that govern the use and efficacy of proof trees. People who want to talk about the role of computers in research mathematics ought to take a close look at the interplay between human and machine that produced these results.

The fourth section describes some extensions to combinatorial game theory, games with slightly imperfect information, error correcting codes, and economics.

The fifth and last section lists 52 unsolved problems and a bibliography of 666 works in the subject.

Anyone who enjoyed either "Winning Ways" or "On Numbers and Games" will probably enjoy "Games of No Chance" as well. The writing and editing is excellent, the mathematics is interesting, and there are enough interesting games to fill thousands of napkins and placemats.


Ed Sandifer (sandifer@wcsu.ctstateu.edu) is a professor of mathematics at Western Connecticut State University and Contributed Papers Coordinator for the North East Section of the MAA

Part I. All Games Bright and Beautiful: 1. The angel problem John H. Conway; 2. Scenic trails ascending from sea-level Nim to Alpine chess Aviezri Fraenkel; 3. What is a game? Richard K. Guy; 4. Impartial games Richard K. Guy; 5. Championship-level play of dots-and-boxes Julian West; 6. Championship-level play of domineering Julian West; 7. The gamesman’s toolkit David Wolfe; Part II. Strides on Classical Ground: 8. Solving Nine Men's Morris Ralph Gasser; 9. Marion Tinsley: human perfection at checkers? Jonathan Schaeffer; 10. Solving the game of checkers Jonathan Schaeffer and Robert Lake; 11. On numbers and endgames: combinatorial game theory in chess endgames Noam D. Elkies; 12. Multilinear algebra and chess endgames Lewis Stiller; 13. Using similar positions to search game trees Yasuhito Kawano; 14. Where is the ‘Thousand-Dollar Ko’? Elwyn Berlekamp and Yonghoan Kim; 15. Eyespace values in Go Howard A. Landman; 16. Loopy games and Go David Moews; 17. Experiments in computer Go endgames Martin Müller and Ralph Gasser; Part III. Taming the Menagerie: 18. Sowing games Jeff Erickson; 19. New toads and frogs results Jeff Erickson; 20. X-dom: a graphical, x-based front-end for domineering Dan Garcia; 21. Infinitesimals and coin-sliding David Moews; 22. Geography played on products of directed cycles Richard J. Nowakowski and David G. Poole; 23. Pentominoes: a first player win Hilarie K. Orman; 24. New values for top entails Julian West; 25. Take-away games Michael Zieve; Part IV. New Theoretical Vistas: 26. The economist’s view of combinatorial games Elwyn Berlekamp; 27. Games with infinitely many moves and slightly imperfect information (extended abstract) David Blackwell; 28. The reduced canonical form of a game Dan Calistrate; 29. Error-correcting codes derived from combinatorial games Aviezri Fraenkel; 30. Tutoring strategies in game-tree search (extended abstract) Hiroyuki Iida, Yoshiyuki Kotani and Jos W. H. M. Uiterwijk; 31. About David Richman James G. Propp; 32. Richman games Andrew J. Lazarus, Daniel E. Loeb, James G. Propp and Daniel Ullman; 33. Stable winning coalitions Daniel E. Loeb; Part V. Coda: 34. Unsolved problems in combinatorial games Richard K. Guy; 35. Combinatorial games: selected bibliography with a succinct gourmet introduction Aviezri Fraenkel.