Squash every loop to a point

A drawing standing on the ground, made of edges that either player may cut. Cut one, and everything that is left hanging — no longer joined to the ground by any path — falls off with it. The player who cannot cut loses.

That is Hackenbush with the colours removed, and removing them changes the game completely. A blue-red string is worth a number, and reading it from the ground upward gives that number’s binary expansion. When every edge is green the two players have identical moves, so the game is impartial, and Sprague and Grundy say the whole drawing is worth a single Nim heap.

The question is which heap, and the interesting part is that nobody has to play the game to find out.

A green stalk is a Nim heap #

Start with the case where there is nothing to fuse. A path of $k$ green edges rising from the ground is exactly a Nim heap of $k$: a cut at height $j$ removes the edge and everything above it, leaving a path of $j - 1$, so the moves from $k$ reach every smaller path. That is the definition of a heap.

Several separate stalks are a disjunctive sum of heaps, so their value is the exclusive or of their lengths. A drawing made only of stalks needs no theory beyond the nim-sum.

Everything harder than that comes from two features a general drawing has and a stalk does not: branches, where several edges meet at a vertex, and cycles, where a path returns to where it started.

The contrast with the coloured game is worth holding on to while reading the rest of this, because the same picture supports two completely different arithmetics depending only on how the edges are painted.

The colon principle: a branch becomes a stalk #

Take a vertex $v$ with several branches growing out of it. Each branch, considered on its own as a game standing on $v$, has some Grundy value.

The colon principle says a branch may be replaced by a stalk as long as that value, and nothing about the rest of the drawing changes. The rest of the position cannot tell the difference, because the branch and the stalk have the same value and equal games are interchangeable in every sum.

Apply it repeatedly, from the leaves down, and a tree collapses. If $v$ has children $c_1, \dots, c_k$, each subtree worth $g(c_i)$, then the edge from $v$ to $c_i$ plus a stalk of length $g(c_i)$ is a stalk of length $g(c_i) + 1$ — so

$$g(v) \;=\; \bigl(g(c_1) + 1\bigr) \oplus \cdots \oplus \bigl(g(c_k) + 1\bigr),$$

with ordinary addition inside the brackets and exclusive or between them. The mixture of the two arithmetics is not a slip: adding one is lengthening a stalk, and exclusive-or is adding independent games.

The fusion principle: a cycle becomes a point #

Cycles are where the argument stops being obvious.

The fusion principle says that the vertices lying on any cycle may be fused into a single vertex without changing the value of the position. Fusing them turns each edge of the cycle into a loop — an edge whose two ends are the same point.

A loop is worth $\ast$. Cutting it removes exactly itself, nothing falls, and the position left behind is the rest of the drawing; so a loop is a heap of one. Two loops at the same point are therefore worth $\ast + \ast = 0$, and only the parity of the loops at a fused vertex survives.

That is a startling amount of collapse for one rule. An odd cycle of any length is worth $\ast$ and an even cycle of any length is worth nothing at all, so a square standing on the ground is a loss for whoever must move, and so is a hexagon, and so is a cycle of two hundred edges.

Notice how little the shape is doing there. Two drawings can look nothing alike — a triangle and a single edge, a hexagon and an empty picture — and be the same game. That is the ordinary situation once values exist, and it is the thing a picture is worst at conveying: the eye reads a triangle as three times as much as an edge, and the arithmetic says they are equal. A figure of a green drawing can show what the position is; only the value can say what it is worth.

Working one graph by hand #

The triangle on a stalk is small enough to do completely, and doing it once makes both rules concrete.

The drawing has four edges: one from the ground up to a vertex, and a triangle sitting on that vertex. Three of its vertices lie on the cycle, so those three fuse into a single point. The three triangle edges become three loops there, worth $\ast + \ast + \ast = \ast$, since two of them cancel.

What is left is a stalk of one edge, standing on the ground, with a point on top carrying one loop’s worth of value — so the subtree above the ground edge is worth $\ast$, which is a Grundy value of one. The colon principle replaces that subtree by a stalk of length one, and the ground edge below it makes a stalk of length two.

$$g(\text{ground}) = g(\text{top}) + 1 = 1 + 1 = 2.$$

The whole drawing is worth $\ast 2$: a Nim heap of two, whatever it looks like. A reader can confirm it by playing — cutting the ground edge leaves nothing, cutting a triangle edge leaves a path of three, and the moves available match a heap of two once the equal positions are identified.

That last step is worth naming. The correspondence is not that the drawing resembles a heap of two; it is that the drawing and the heap have the same value, so either may be substituted for the other inside any larger position and nobody’s winning chances move. That is what equality means here, and it is a much stronger statement than a resemblance.

Both routes, on every graph #

The pair of principles turns a graph into a number in one pass: find the edges that lie on no cycle, fuse everything else, count loops modulo two, and run the colon recursion up what remains.

The alternative is to play the game out — enumerate every subset of edges the play can reach, take a mex at each, and work down to the answer knowing no theory at all. That is exponential in the number of edges.

The site computes both, for every graph it draws, and the figure does not build unless they agree. That is the strongest form the argument can take here: the structural route is fast and depends on two theorems; the search is slow and depends on nothing; and a disagreement would mean one of them is wrong, with no way to tell which from the picture alone.

Over the ten graphs in the site’s repertoire the search visits 1,438 positions in total, and the two routes agree on all ten.

The agreement is not a formality. A structural rule of this kind is exactly the sort of thing that is right on the examples its author had in mind and wrong on a case nobody drew — a graph with parallel edges, a graph whose ground vertex is inside a cycle, a tree hanging off a fused blob. Every one of those shapes is in the repertoire specifically because it is where the rule could go wrong, and the search is the only thing in a position to say that it did not.

The formula is two operations, and it says which #

The colon recursion mixes ordinary addition with exclusive-or, and the essay calls that “not a slip”. It is more than not a slip: each of the two operations is a named construction on games, and the formula is a sentence about which one applies where.

$$g(v) \;=\; \bigl(g(c_1) + 1\bigr) \oplus \cdots \oplus \bigl(g(c_k) + 1\bigr)$$

The exclusive-or is the disjunctive sum. The branches at $v$ are independent: a cut in one leaves the others untouched, because they meet only at $v$ and $v$ is still attached to the ground. So they add the way every independent thing on this site adds.

The $+1$ is the ordinal sum. A branch sits above the edge that carries it, and cutting that edge deletes the whole branch — which is exactly the nesting operation, not the disjunctive one. On green stalks the ordinal sum of a heap with an edge under it is a heap one longer, which is why the operation shows up in the formula as a plain increment.

So a green tree is a disjunctive sum of ordinal sums, and the two arithmetics in one line are the two ways a Hackenbush drawing can put pieces together: side by side at a vertex, or one on top of another along an edge.

That also names what the colon principle is doing rather than merely what it says. Substituting a branch for a stalk of the same value is legitimate because the ordinal sum, restricted to impartial games, is a function of the value — which is a theorem with its own essay and is false for coloured edges. The whole reduction here rests on that restriction, and it is the same restriction that makes the game impartial in the first place.

What “fuse the cycles” means precisely #

Fusion is stated as “the vertices on any cycle may be fused”, and applied to a drawing with overlapping cycles that instruction needs an order of operations it does not supply. It has one, and stating it turns the rule into an algorithm.

Fusing repeatedly until nothing changes merges exactly the 2-edge-connected components — the maximal sets of vertices that stay joined when any single edge is removed. Equivalently, and more usefully: an edge is a bridge when cutting it disconnects the drawing, and every non-bridge edge ends up as a loop at the fused vertex of its component.

So the whole computation is:

1. Find the bridges, by an ordinary depth-first walk.
2. Contract everything that is not a bridge; each component contributes one loop if its edge count is odd and none if it is even.
3. Run the colon recursion on what remains, which is a tree by construction, since the bridges of a graph form one.

Step one is linear in the number of edges, step two is a parity, and step three visits each vertex once. The structural route is linear and the search it replaces is exponential — which is a sharper statement of the essay’s headline than “twelve steps against 1,283 positions”, because twelve and 1,283 are two numbers about one lattice and linear-against-exponential is a statement about every drawing.

It also explains why the repertoire contains the shapes it does. A graph whose ground vertex sits inside a cycle, a graph with parallel edges, a tree hanging off a fused blob — those are exactly the cases where “fuse the cycles” is ambiguous as English and unambiguous as contract the non-bridges, and they are in the set because that is where a reader following the sentence and a program following the algorithm could part company.

Why fusion is true, and where the intuition comes from #

The principles are stated here and proved in Winning Ways, but the reason fusion is plausible is worth having, because it is not obvious that squashing a picture leaves a game alone.

The key observation is about what a cut can disconnect. An edge on a cycle is never a bridge: cutting it cannot detach anything, because whatever it was holding up is still held by the other way round the cycle. So an edge on a cycle behaves exactly like a loop — cutting it removes one edge and nothing else — and a loop is what it becomes.

An edge not on a cycle is a bridge, and cutting it drops everything above. That distinction — bridge or not — is the whole of the fusion computation, and it is found by an ordinary depth-first walk of the graph.

What the solver computed, and how #

grundyBySearch treats the drawing as an ordinary impartial game. Its state is a bitmask of surviving edges; a move clears one bit and then re-walks the graph from the ground, dropping every edge no longer connected; the value is a mex over the results, memoised on the mask.

grundyByStructure never enumerates a position. It finds the bridges by the standard depth-first low-link walk, unions every pair of vertices joined by a non-bridge, counts the edges falling inside each fused blob as loops, and runs the colon recursion from the blob containing the ground. It returns the fused structure as well as the value, which is what the right-hand panel of each figure draws — so the picture of the reduction is the reduction, not an illustration of it.

greenValue calls both and throws if they differ. Every figure on this page goes through it.

The gate adds three things a figure cannot. It runs the pair over every graph in the repertoire rather than the ones an essay chose. It checks the two smallest cases by hand — a single green edge must be $\ast$, and two edges joining the same pair of points must cancel to nothing — because those are the cases where a bug in the loop-counting would be least visible. And it requires the parallel-edge case to come out at zero, which is the assertion that would fail first if fusion were counting edges rather than counting them modulo two.

Where the model stops #

The graphs are small. The largest here has twelve edges and 1,283 reachable positions. The structural route would handle a graph with a million edges; the search that checks it would not, so the checking is what bounds the sizes drawn, not the theory.

Green only. A drawing with green and coloured edges is not impartial, its value is not a nimber, and neither principle applies in the form given here. That game — Hackenbush Hotchpotch — needs atomic weights and is a different subject.

Fusion is used, not proved. The essay gives the reason it is plausible: an edge on a cycle can never disconnect anything. The actual proof is a strategy-stealing argument on the fused and unfused positions played together, and it is not carried out here.

The exponential is in the checking, not in the game. It is worth being exact about which side of this comparison is expensive. Playing a green Hackenbush position out is exponential in the edges; reading it by the two principles is linear. So the search here is not an alternative anybody would use — it is a witness, run at sizes where it is affordable, so that the fast route has something independent to be right against. The same relationship holds wherever a closed form exists, and the closed form is only worth trusting because somebody paid for the slow answer at least once.

One ground vertex. Every drawing here stands on a single point. A picture standing on a whole ground line is the usual presentation, and it amounts to fusing every ground vertex together first — which is fusion again, applied before anything else, and the site’s graphs simply start in that state.

Who found it, and when #

Green Hackenbush, fusion and the colon principle are all in Winning Ways (1982), where Berlekamp, Conway and Guy work through green, blue-red and hotchpotch versions in turn. The colon in the name is notation: $G : H$ denotes the game $G$ with $H$ planted on top of one of its vertices, and the principle says the value of $G : H$ depends on $H$ only through $H$’s Grundy value.

Hackenbush itself is Conway’s, from the 1970s, and its role in the subject is out of proportion to its rules. The blue-red version is where the surreal numbers come from; the green version is a complete impartial theory in a picture; and the mixed version is where the infinitesimals become unavoidable. Three quite different halves of the subject, one game, one page of rules.

Where the ladder goes next #

This is the second rung on the Hackenbush ladder, after the blue-red string that spells its own value. One gives the numbers, the other gives the nimbers, and between them they cover the two halves of the theory that are completely understood.

The rung after is the one where the two colours meet. A drawing with blue, red and green edges together is worth neither a number nor a nimber but something with both in it, and the machinery that handles it is the count of ups — which is why the infinitesimals ladder and this one converge rather than running side by side.