Combinatorial Game Theory
who wins, and by how much
Concept

Graph — where it appears

A set of nodes joined by edges, used here for a game whose positions repeat rather than branch into a tree. Writing a position as a graph is what makes a loopy game computable and what makes a shared subposition storable once.

Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.

Trees, and what each is worth. A row of blue-red Hackenbush trees with the value the recursion returns under each. Every one is a number, and none of them is the binary reading of anything a reader can see in the picture.

Where the numeral stops

A Hackenbush string is a numeral and a tree is a trunk with a forest on it, so the obvious next question is a graph with a cycle in it. Green Hackenbush answers that by fusing the cycle to a point. In blue and red the fusion is right on every three-edge cycle, on fewer than half of the six-edge ones, and the smallest thing it gets wrong has four edges.

positions · Hackenbush The same game, written twice. A position as it arises and the same position reduced. Left would never move to 0 when 2 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form.

A reduction that reads a graph

The two reductions are defined as deletions from an option list, and the shared form has no option lists — a node is reached from several parents at once. Both restate as rewritings at a node, the rewriting is confluent, and its fixed point is the canonical form. What does not carry over is the sharing: four fifths of the shared nodes need a different answer under different parents.

values · Reversibility A bridge circuit, with a point on every link. The switching graph drawn as a bridge circuit, with a new point in the middle of every link in green and the original inner points in blue, already belonging to Short. Played as a game on the green points it gives the same verdict as the original game on links, because claiming a middle point is securing its link and deleting it is deleting the link.

A point with three neighbours

The switching game on links is settled by counting — enough links, arranged as two trees. Played on points instead, it is the game Hex belongs to, and the count is gone. The link game turns out to be the point game in which every contested point has exactly two neighbours; give one a third, and two graphs with the same points, the same links and the same number of separate routes can have opposite winners.

applied · Switching How much of a board the endgame theory reaches. Every subset of a board's strings, counted by whether the surviving coins fall into chains and loops. The share is taken over the positions with no free box on the table, since a position with a capture available is one a player takes rather than chooses from.

The endgame theory arrives late

Every component the chain-and-loop theory names has coins of degree two, so a position it can read is one where every surviving coin holds exactly two strings. Over a six-box board that is 1,033 of the 28,028 positions with no free box on the table — 3.7 per cent — and more than half of them only after twelve of the board's seventeen strings have been cut.

applied · Dots and Boxes The components the theory does not name. Grundy values of strings-and-coins components with a branching coin, grouped by the value. A chain or a loop is worth nothing on its own whatever its size; a coin with three strings takes four different values depending on its arms, and a coin with four strings is back to nothing.

A coin with three strings is worth something

Every chain and every loop is worth nought on its own, whatever its size, and that is exactly what makes their nim-sum useless. A coin with three strings on it is worth nought, one, two or three depending on its arms — 31 of the 35 measured are not nought, and the four that are are the ones whose arms are all long. A coin with four strings is back to nought every time.

applied · Dots and Boxes

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive searchComponentCounterexampleDecompositionDots and BoxesEndgameEnumerationImpartialNormal playStrings and coinsValueBoard

All concepts