Combinatorial Game Theory
who wins, and by how much
Concept

Colon principle — where it appears

The rule that what sits above a fixed base may be compared on its own, which is what licenses replacing a branch by an equal one. It is what makes a green Hackenbush graph collapse to a single nimber without the game being played out.

Named by 6 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 A green edge is not a number. Green edges may be cut by either player, which makes the position impartial in that part. A single green edge is worth ∗ — a value that is neither positive, negative nor zero, and which no number can equal.

A green edge on a blue one

Blue over green and green over blue are the same two edges in the other order. One is worth 1∗ and the other ↑∗ — a number with a star on it against something smaller than every positive number — so a stalk with all three colours in it stops being a numeral and starts being a position whose value depends on what is underneath.

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 Swapping a branch for another of the same value. The ordinal sum of a base with a branch, and the same sum with the branch replaced by a heap of a different game carrying the same Grundy value. The two are compared by playing their difference, not by inspection — and they agree every time, which is what the colon principle claims and what the partizan case denies.

When the nested sum only sees the value

The ordinal sum reads the form and not the value: three positions all worth zero, placed under a star, give three different answers. On impartial games it reads the value after all — 72 substitutions of an equal-valued heap from a different game, and every ordinal sum comes back unchanged. That difference is the whole reason a green Hackenbush tree can be collapsed one branch at a time.

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 How much of the value the colon respects. Every form whose option lists are antichains of day-two values, grouped by the value it reduces to, and each group asked whether all its forms give the same ordinal sum with star. On 636 of the 640 groups they do.

What the colon respects

The ordinal sum reads the form of its base rather than its value, which is why the colon principle is stated for positions and not for values. Built over 9,604 forms it turns out to read the value on 636 of the 640 values that have more than one form, and the four it can tell apart are zero, one, minus one and star — the values born by day one, and no others.

sums · Ordinal sum

Named alongside it

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

HackenbushGreen hackenbushOrdinal sumDisjunctive sumBinaryExhaustive searchFusionImpartialNimberStar (∗)SubstitutionDecomposition

All concepts