Combinatorial game theory

Publication date 20 August 2013

Published in Graduate Studies in Mathematics (Search for Journal in Brave)

canonical form combinatorial game theory impartial game loopy game mathematical plays partizan game Sprague-Grundy theory surreal numbers tame game temperature theory transfinite games Wythoff game

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to game theory, economics, and finance (91-01) 2-person games (91A05) Games involving graphs (91A43) Combinatorial games (91A46)

Review text

More than thirty years after the pioneer [\textit{E. R. Berlekamp} et al., Winning ways for your mathematical plays. Vol. 1: Games in general. Vol. 2: Games in particular. London etc.: Academic Press (1982; Zbl 0485.00025)], this comprehensive book introduces the reader to combinatorial game theory and the analysis of combinatorial games. It greatly benefits from a rigorous presentation. The book is self-contained (one can find all the necessary mathematical prerequisites such as partial order and ordinals in an appendix). The reader should also appreciate the clear exposition and the formal presentation of the subject. Note that the book is intended to serve at the first- or second-year graduate level. Let us present the different chapters briefly.NEWLINENEWLINEChapter~1 introduces, through examples, basic notions and results in combinatorial game theory. Chapter~2 is about \textit{short games}, which have finitely many subpositions and are loop-free (no infinite run). The set \(G\) of values of short games is a partially ordered abelian group. Then some classes of games are introduced: numbers and infinitesimals. The notion of temperature quantifies the urgency of a move. Finally, reduced canonical form and automatic weights are two other invariants that are discussed. Chapter~3 studies the abstract structure of the group \(G\) itself. Chapter~4 is about \textit{impartial games} (same moves for both players in contrast with partizan games). Using the Sprague-Grundy theorem, a Nim value is associated with every impartial game. Heap games and Wythoff-type games are also discussed in this chapter.NEWLINENEWLINEIn the first four chapters, the \textit{normal-play convention}, i.e., the player who makes the last move wins, was assumed. Chapter~5 is about \textit{misère-convention} games, i.e., the last move loses. In this context, the situation is often more complicated, and one cannot simply replicate normal-play theory. The reader is introduced to misère Nim and tame games, misère canonical form and quotient, and generalization to partizan games (distinct moves for each player). In contrast with short games, Chapter~6 discusses \textit{loopy games}, where repetitions are allowed. In particular, the class of stopper-sided games are studied.NEWLINENEWLINEThe last two chapters of the book under review cover more advanced material such as generalized temperature theory, transfinite games, surreal numbers and their structure, and transfinite arithmetic.NEWLINENEWLINEThis up-to-date presentation also includes a list of open problems, and the description and analysis of approximatively 60 games. The reader will also enjoy some historical perspectives about combinatorial game theory.

Recommendations

Cited in

(only showing first 100 items - show all)

This page was built for publication: Combinatorial game theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2844833)