Generator

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.

6 essays call green-graph. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

7 distinct positions, harvested by running this generator again at the options each essay passed it.

Position	Worth	Outcome	Drawn in
`a square with a roof`	`∗0`	P	Squash every loop to a point
`a three-by-three lattice on the ground`	`∗0`	P	Squash every loop to a point · Nim is easy, in binary
`a tree with two branches`	`∗4`	N	Squash every loop to a point · When the nested sum only sees the value
`a triangle on a stalk`	`∗2`	N	A tree is still a number · Squash every loop to a point
`a triangle standing on the ground`	`∗1`	N	Squash every loop to a point
`a triangle with a tail`	`∗0`	P	A green edge on a blue one
`two loops on one stalk`	`∗2`	N	A winning strategy that is a spanning tree

Where it is called

Changing this generator changes every one of these figures.

a path with every link doubled: the criterion and the game. A Shannon switching graph with the two marked vertices in gold. Short secures links and Cut deletes them; Short wins by joining the two marks. Lehman's criterion says Short wins moving second exactly when some subgraph holding both marks splits into two edge-disjoint spanning trees — drawn here in blue and red where one exists. The verdicts beside the graph come from playing the game out, and the criterion is computed without looking at the game at all.

Out in the world

A winning strategy that is a spanning tree

The Shannon switching game was sold in a box in 1960 and solved in 1964, and the solution is not an assertion that somebody wins. It is a property of the graph anybody can check, and the strategy falls straight out of it — whichever link the opponent cuts, take its partner in the other tree.

Particular games

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.

The same position, and two rulers to measure it with. Nim positions with the length of their input under two encodings — the heap sizes in binary, and the counters themselves — beside the work the nim-sum does. The work never changes. Which of the two lengths it is compared against decides whether the same algorithm reads as linear or as exponentially fast, and hardness claims are always made against one particular encoding.

What it costs

Nim is easy, in binary

Three heaps of a thousand counters take thirty bits to write down and three thousand counters to lay out. The nim-sum does three exclusive-ors either way. Whether that counts as fast depends entirely on which of the two numbers the work is compared against.

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.

Particular games

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.

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.

Sums and comparison

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.

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.

Particular games

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.

The whole library · The position index · The figures that play back