Combinatorial Games: Tic-Tac-Toe Theory

Combinatorial Games: Tic-Tac-Toe Theory is a monograph on the mathematics of tic-tac-toe and other positional games, written by József Beck. It was published in 2008 by the Cambridge University Press as volume 114 of their Encyclopedia of Mathematics and its Applications book series (ISBN 978-0-521-46100-9).

Topics

A positional game is a game in which players alternate in taking possession of a given set of elements, with the goal of forming a winning configuration of elements; for instance, in tic-tac-toe and gomoku, the elements are the squares of a grid, and the winning configurations are lines of squares. These examples are symmetric: both players have the same winning configurations. However, positional games also include other possibilities such as the maker-breaker games in which one player (the "maker") tries to form a winning configuration and the other (the "breaker") tries to put off that outcome indefinitely or until the end of the game. In symmetric positional games one can use a strategy-stealing argument to prove that the first player has an advantage, but realizing this advantage by a constructive strategy can be very difficult.

According to the Hales–Jewett theorem, in tic-tac-toe-like games involving forming lines on a grid or higher-dimensional lattice, grids that are small relative to their dimension cannot lead to a drawn game: once the whole grid is partitioned between the two players, one of them will necessarily have a line. One of the main results of the book is that somewhat larger grids lead to a "weak win", a game in which one player can always force the formation of a line (not necessarily before the other player does), but that grid sizes beyond a certain threshold lead to a "strong draw", a game in which both players can prevent the other from forming a line. Moreover, the threshold between a weak win and a strong draw can often be determined precisely. The proof of this result uses a combination of the probabilistic method, to prove the existence of strategies for achieving the desired outcome, and derandomization, to make those strategies explicit.

The book is long (732 pages), organized into 49 chapters and four sections. Part A looks at the distinction between weak wins (the player can force the existence of a winning configuration) and strong wins (the winning configuration can be forced to exist before the other player gets a win). It shows that, for maker-breaker games over the points on the plane in which the players attempt to create a congruent copy of some finite point set, the maker always has a weak win, but to do so must sometimes allow the breaker to form a winning configuration earlier. It also includes an extensive analysis of tic-tac-toe-like symmetric line-forming games, and discusses the Erdős–Selfridge theorem according to which sparse-enough sets of winning configurations lead to drawn maker-breaker games. Part B of the book discusses the potential-based method by which the Erdős–Selfridge theorem was proven, and extends it to additional examples, including some in which the maker wins. Part C covers more advanced techniques of determining the outcome of a positional game, and introduces more complex games of this type, including picker-chooser games in which one player picks two unchosen elements and the other player chooses which one to give to each player. Part D includes the decomposition of games and the use of techniques from Ramsey theory to prove theorems about games. A collection of open problems in this area is provided at the end of the book.

Audience and reception

This is a monograph, aimed at researchers in this area rather than at a popular audience. Reviewer William Gasarch writes that, although this work assumes little background knowledge of its readers, beyond low-level combinatorics and probability, "the material is still difficult". Similarly, reviewer Kyle Burke complains that "many definitions and explanations are awkwardly 'math heavy'; undefined terms from advanced mathematics abound in small examples, where simpler descriptions would suffice".

Much of the book concerns new research rather than merely summarizing what was previously known. Reviewer Ales Pultr calls this book "a most thorough and useful treatment of the subject (so far insufficiently presented in the literature), with an enormous store of results, links with other theories, and interesting open problems". Gasarch agrees: "Once you get through it you will have learned a great deal of mathematics." A pseudonymous reviewer for the European Mathematical Society adds that the book could be "a milestone in the development of combinatorial game theory".