Combinatorial Game Theory
who wins, and by how much
Series

Hackenbush — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    Hackenbush is a numeral

    Draw a stalk of coloured edges. Read it as a string, blue for one and red for zero, and the string is the binary expansion of what the position is worth. Not approximately — exactly, and the site computes it both ways and refuses to build if they disagree.

    part 1 · positions
  2. 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.

    part 2 · positions
  3. 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.

    part 3 · positions
  4. 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.

    part 4 · positions
  5. 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.

    part 5 · positions

All series