Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is a good reference material for elementary combinatorial game theory?

By combinatorial game theory I mean chiefly the study of zero-sum, deterministic two-player games (perhaps even more adjectives could be added), with a view to determining which of the players has the winning strategy, and perhaps determining the strategy where possible. Example games that fall under this heading are Nim, Hex, and nearly everything that might appear as a "game" at a mathematics contest.

By elementary I mean not going deep into a general theory, but rather exposing some elegant and accessible examples and ideas. For instance, the discussion of winning strategy for Nim, and the idea of strategy-stealing are topics that I would find welcome.

The request arises from the need to clear up some terminology and find additional examples for a talk that I am to give. Many thanks for all your help.

share|improve this question

3 Answers 3

up vote 10 down vote accepted

There are several standard texts. You may want to start with a short essay, "The History of Combinatorial Game Theory", by Richard J. Nowakowski. The paper lists the main texts you may want to consult. For a more exhaustive list of references, see "Combinatorial games: Selected bibliography with a succinct GourmetIntroduction", by Aviezri Fraenkel. Thomas Ferguson, at UCLA, has an online book on game theory, and its first chapter is on combinatorial games.

The absolute minimum is "On Numbers and Games" by Conway, and "Winning Ways for your mathematical plays", by Berlekamp, Conway, and Guy. "On numbers and games" develops the general theoretical framework, so it is perhaps not what you want to look at first; "Winning ways" has many examples and treats some in large amount of detail. For completeness, let me add "Fair Game: How to Play Impartial Combinatorial Games", by Richard K. Guy.

Berlekamp has at two books on specific games, which you may want to look at if you are more interested in specific examples than the general theory: "The Dots and Boxes Game: Sophisticated Child's Play", and "Mathematical Go: Chilling Gets the Last Point".

For a more advanced treatment of some subjects, see also "Games of no chance", edited by Nowakowski. You can download several of the articles in the collection at the link. The collection includes research papers, dealing with theoretical results, but also considers specific games, connections with other fields (including economics and set theory), and includes several accessible surveys. This book is the first of a series: We also have "More games of no chance", and "Games of no chance. 3".

A very recent work that I like very much is "Combinatorial games. Tic-Tac-Toe theory", by Beck. As Beck explains, the book begins to address some of the games that the theory of "Winning games" falls a bit short of; though several examples are treated in detail, the emphasis is on the general theory.

There is also a nice recent book, "Lessons in Play: An Introduction to Combinatorial Game Theory", by Albert, Nowakowski, and Wolfe. I have seen it recommended in many places, and I agree that it is excellent.

Very recently, Aaron Siegel has developed the theory of Misere games, and he has written a book on the subject that has just appeared, "Combinatorial game theory". He is responsible for the website "Combinatorial game suite".

You may want to also look at this MO question (though it does not restrict to the combinatorial side) and to this one (which is strictly about combinatorial game theory).

Thanks to user Mark S. for suggesting that last link. By the way, Mark has a blog on precisely this topic, that also provides quite a few useful links.

share|improve this answer
1  
There is an MO question that DOES restrict to combinatorial game theory: mathoverflow.net/questions/8263/… Also, I would second "Lessons in Play" for an 'elementary' text. –  Mark S. Feb 6 '13 at 16:02
    
Thanks for the link, @MarkS.! –  Andres Caicedo Feb 6 '13 at 16:22
    
(@MarkS. Nice blog! I added a link to it in the answer.) –  Andres Caicedo Feb 6 '13 at 16:28
    
Thirding "Lessons in Play" as an excellent choice; I got it for Christmas and it's chock full of good examples (including several newer ones that aren't in Winning Ways) and much less diverted in spots than that classic book is (for better and worse). –  Steven Stadnicki Feb 6 '13 at 16:43
    
Aaron Siegel's book, "Combinatorial Game Theory" has since come out, but while well written, it seems like Lessons in Play would suit the "elementary with many accessible examples" condition of the original question much better. –  Mark S. Nov 11 '13 at 2:33

This PDF might be a useful starting point. It also mentions a book Fair Game: How to Play Impartial Combinatorial Games, by Richard K. Guy. I’ve not seen it, but it was published by COMAP; the combination of author and publisher suggests that it might be well worth looking into. (There is of course the massive Winning Ways, by Berlekamp, Conway, & Guy, but I suspect that you’re aware of it, and in any case it’s likely to be overkill for your purposes.)

share|improve this answer

Winning Ways: For Your Mathematical Plays by Berlekamp, Conway, and Guy, is encyclopedic, and covers all the topics you mentioned, and many more.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.