Combinatorial Game Theory
who wins, and by how much
Concept

Fusion — where it appears

Squashing every vertex on a cycle into one point, which turns a green graph into loops whose nimbers add. It is a statement about cycles rather than about branches, and it is the half of the green reduction the colon principle does not cover.

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

a triangle on a stalk, worth ∗2. A Hackenbush position in which every edge is green, so either player may cut any of them and the position is impartial. Its value is a single Nim heap. Two principles find which one: fusion, which collapses every cycle to a point and leaves that many loops behind, and the colon principle, which replaces a branch by a stalk as long as the branch's own value.

Squash every loop to a point

Colour every Hackenbush edge green and the game becomes impartial, so the whole picture is worth a single Nim heap. Two principles find which one without playing anything — fuse the cycles, then run one pass up the tree — and a nine-vertex lattice that costs 1,283 positions to solve costs twelve steps to read.

positions · Hackenbush The picture is the numeral. Blue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number.

The other sum, the one that nests

A move in one part wipes the other out entirely. That is the ordinal sum, it is what a Hackenbush stalk actually is — 1 : (−1) is a half, and 1 : (−1) : 1 is three quarters — and it is not an operation on values at all: three positions all worth zero give three different answers under it.

sums · Ordinal sum 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.

A tree is still a number

A Hackenbush string spells its own value in binary. Put a fork in it and the numeral has nothing to read — there is no leftmost anything. The value is still a number, in all 10,066 forests up to six edges; it is still computable, by the ordinal sum, in all 3,238 single-trunk trees; and the reading is right on 762 of them, of which 126 are the strings it was written for.

positions · Hackenbush 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

Named alongside it

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

HackenbushColon principleExhaustive searchGreen hackenbushOrdinal sumBinaryClosed formDisjunctive sumNimberNumbersPartizanComparison

All concepts