Where the numeral stops

Three rungs of this anchor read a Hackenbush position off its shape. A string is a numeral: walk it from the ground, and the colours spell the value in binary. A tree is still a number: find the trunk, read the forest above it, and combine them with an ordinal sum. Each rung takes a wider class of positions and keeps the same promise — the value is a reading of the picture, not a search through it.

The fourth rung is where the promise runs out, and the previous one said so:

A position whose graph has a cycle is not a tree, cutting one edge of a cycle disconnects nothing, and the trunk-and-forest decomposition has no meaning.

That paragraph named the problem and left the obvious hope unexamined, because there is a rule for cycles in Hackenbush and it is on this very anchor. Squash every loop to a point is the fusion principle: identify the vertices of a cycle, and the value does not change. It turns any green graph into a bouquet of loops at the ground, and a loop is a single edge, so the whole green game collapses to a Nim heap.

The question this rung is for is whether that survives the colours.

It is worth being clear what “the reading” is, because it is the thing at stake. On a tree, every edge is joined to the ground by exactly one path, so deleting an edge deletes exactly the subtree above it and the position falls apart in a way the picture shows. The trunk-and-forest rule is a description of that falling-apart. A cycle breaks it at the first step: an edge on a cycle has two paths to the ground, deleting it removes nothing but itself, and there is no subtree above it to speak of.

Where it holds #

It holds further than seems reasonable.

On a three-edge cycle — a triangle with one vertex on the ground — fusion is right on all eight colourings. LLL is worth 3 and three blue loops are worth 3. LRR is worth −1 and one blue loop with two red is worth −1. Every one.

The LLL case is the one to look at first, because it also disposes of a simpler guess. A triangle of three blue edges is worth 3, and every tree made by cutting one of its edges is worth 2 — so the cycle is worth strictly more than any tree inside it, and no amount of choosing which edge to cut will ever reach it. That is the first sign that a cycle is not a tree with an extra edge; it is a different kind of object, and its extra edge is worth a whole move because the first edge removed from a ring costs nobody anything.

Raise the triangle onto a stalk and it still holds, on all sixteen colourings of stalk and triangle together: a blue stalk under a red triangle is worth 1/8, and a blue edge with three red loops on top of it — which is what the fusion produces — is worth 1/8 too. That is not an obvious agreement. The ordinal sum that computes a stalk-with-a-forest reads the form of its base, so a rule that moves edges about has every opportunity to disturb it, and here it does not.

Two triangles sharing the ground vertex: right on all sixty-four.

At that point the reasonable conclusion is that fusion is a theorem about Hackenbush rather than about green Hackenbush, and the rung is a short page.

Where it stops #

Add one edge to the cycle.

A four-edge cycle standing on the ground, its two ground edges blue and its two far edges red, is worth one. Fused, it is two blue loops and two red loops at the ground, which is 1 + 1 − 1 − 1 = nought. The rule is wrong by a whole move on a position with four edges in it.

The reason is visible once the value is. Both of Right’s edges are on the far side of the ring, joined to the ground only through Left’s. Right cannot remove either of them without Left’s edges continuing to hold up the rest, and Left can take one of hers and leave Right holding a piece that falls off the moment she takes the other. The position is not symmetric in the players even though the edge counts are, and the asymmetry is entirely a fact about which edges touch the ground.

Fusing puts every edge on the ground. That is precisely the fact it destroys.

The mirror position, with the colours exchanged, is worth −1 and fuses to nought in the same way, which is a small check worth having: the game is symmetric under exchanging the colours and negating, so a sweep that broke that symmetry would be reporting an implementation error rather than a fact. Both failures at four edges are that one position and its mirror, and there are no others.

A three-edge cycle has no room for the arrangement — with three edges and two colours, one colour has a single edge, and a single edge on a three-cycle always touches the ground vertex or is adjacent to one that does. Four is the first length where two edges of one colour can sit entirely beyond two of the other, and four is where fusion fails.

How fast it stops #

The share fusion gets right does not merely dip at four; it falls, and keeps falling.

Eight of eight at three edges. Fourteen of sixteen at four. Twenty of thirty-two at five. Thirty of sixty-four at six — under half. By six edges there are more colourings the rule gets wrong than right, and the sweep asserts the fall rather than reporting it, so a length at which the rule recovered would refuse to draw.

That shape matters more than the counterexample. A rule that failed on a handful of exotic positions would be a rule with exceptions, and the exceptions would be worth naming. A rule whose accuracy decays towards chance as the position grows is not a rule at all; it is a coincidence that runs out, and the three-edge case where it is perfect is the smallest case rather than the typical one.

It is worth saying what makes the green case different, since the difference is not a technicality. In green Hackenbush every edge is available to both players, so an edge’s value to a player does not depend on which other edges are holding it up — any edge that is connected is a move for whoever wants it. Fusion moves edges without changing who can take them, and in green that is the whole of what an edge is. In blue-red an edge belongs to one player and its availability depends on a chain of edges below it that may belong to the other. Fusion preserves the first fact and destroys the second, and the second is the only thing the numeral was ever reading.

This also explains why fusion survived the raised triangle and the two triangles sharing a vertex, which looked like harder tests and were not. In both of those every edge of every cycle is the same distance from the ground in the sense that matters — either they all touch it, or they all hang off the same stalk — so there is no dependence between the cycle’s own edges for the fusion to lose. The four-edge ring is the first shape where a cycle’s edges differ from one another in what holds them up, and it fails immediately.

The other thing to try #

If the cycle cannot be fused, it can be cut. Delete one edge and what is left is a tree, which the rung below can read exactly.

There are four cuts and they give a quarter, three halves, three halves and a quarter. The cycle is worth one. Not one of the four is the value; the two answers disagree with each other by more than a whole move; and one is worth checking is not the mean of them, nor their greatest, nor their least.

The failure is not that the cut is a bad approximation. It is that a cut is not an approximation at all. Deleting an edge produces a different position, and which position depends on which edge, and the tree rule then reads that position perfectly — the reading is exact and the thing being read is the wrong game. There is nothing to tune.

That also disposes of the spanning-tree idea in its general form. A cycle of k edges has k spanning trees; each is readable; they disagree; and there is no principled way to choose among them, because the cycle’s edges are not interchangeable — the two that touch the ground are doing something the other two are not.

There is one more variant worth ruling out explicitly, since it is the natural repair. Cutting an edge loses a move, so perhaps the cycle is worth its best spanning tree plus something — a correction for the edge that was thrown away. On the all-blue triangle that works: every tree is worth 2, the cycle is worth 3, and the correction is exactly one blue move. On the four-edge counterexample it does not: the trees are worth a quarter and three halves, the cycle is worth one, and one is neither of those plus a whole move in either direction. A correction that has to be a different size on different colourings is not a correction; it is the answer, restated.

What is left #

Three readings and a search. The numeral says a quarter, the fusion says nought, the spanning tree says a quarter, and the value is one. The search is right and it is a search: every subset of the edges, with a connectivity test at each step to find what has fallen off, which is exponential in the edges and reads nothing off the picture at all.

Set that beside the census the rung below ran and the contrast is the whole of this page. On trees, two of the three rules are exact and the third is close; on one four-edge graph, all three are wrong and they are wrong in three different directions. The move from a tree to a graph is not a widening of the class the rules cover with some loss at the edges — it is the point at which they stop being rules.

So the honest statement of where this anchor stands is that the readings cover strings and trees and stop. Blue-red Hackenbush on a general graph is still worth a number — nothing about cycles disturbs the argument that every move is a concession, so no position is ever a fight — but which number is not computed by anything on this site except a search, and there is no reason from these four rungs to expect a reading to exist.

That is a narrower failure than it sounds and worth stating precisely. The general theory is fine: the values are numbers, the sums add, the comparison works. What has failed is the specific programme of these four rungs, which was to read the value off the shape. On a tree the shape determines everything, because a tree’s shape is the dependency between its edges. On a graph the dependency is a relation rather than a hierarchy, and no walk of the picture recovers it.

Why the values are still numbers #

One thing does survive intact, and it is worth separating from the wreckage because it is easy to assume it went with the rest.

Every blue-red Hackenbush position is worth a number, cycles included. The argument does not mention shape at all: every move removes an edge, an edge is worth something to exactly one player, and removing one’s own edge can never help its owner — so whatever the position, one player is ahead by a definite amount and neither has anything to gain from moving. That is the same argument the first rung of this anchor makes for a string, and nothing in it cares whether the picture is a tree.

So the situation is not that cycles make the game harder in the way that a game with hot positions is harder. There is no fight anywhere, no temperature, no switch. Every position on every graph is a plain number, and every sum of them adds by ordinary arithmetic. What has gone is only the ability to say which number without searching, which is a statement about the reading and not about the game.

That distinction is worth holding onto because the two are routinely confused. A game whose values are all numbers is a solved game in the sense that matters for playing a sum of them: compute the numbers, add them, and the sign says who wins. The numeral was never necessary for that. It was a way of computing the numbers cheaply, and what this rung establishes is that the cheap way stops at trees.

Two things the sweep does not settle #

The counterexample is small and the sweep is small. Cycles to six edges, on the ground, with an added handful of raised and decorated cases — a few hundred positions. That is enough to refute fusion and not enough to say what replaces it. It is entirely possible that some corrected fusion works, with the ground edges given a different treatment, and nothing here has looked for one.

And nothing here says the general problem is hard. Blue-red Hackenbush on general graphs is a well-studied question and this page has not been near the literature; what it has established is that the two rules this site has — the numeral and the green fusion — do not cover it, and that the failure begins at four edges rather than somewhere far out.

The sweep is also bounded by what a graph costs to evaluate. A position is a subset of the edges and each move needs a connectivity search to find what has fallen off, so twenty edges is a million positions and each of them a search — which is why the counts above stop at six-edge cycles and why the decorated cases are handfuls rather than censuses. A check in front of a search applies in its usual form: the numbers here are about what was looked at.

Where the ladder goes next #

The hackenbush anchor has five rungs: the numeral, the green fusion, the mixed case, the tree, and now the cycle where the tree reading ends.

The rung above is the corrected rule, if there is one. Everything here points at one place to look: fusion is wrong exactly when it moves an edge that was depending on another player’s edge onto the ground, so a fusion that kept a record of what each edge was standing on might survive. The smallest counterexample is four edges and the failures are enumerable to six, so a candidate rule can be tested against a few hundred positions before anybody has to believe it — which is more than the fusion principle got here, and is the reason this page could refute it in an afternoon.

Two neighbours are worth the trip. When the nested sum only sees the value is about the ordinal sum reading the form of its base rather than its value, which is why a rule that rearranges edges is dangerous even when it preserves every value in sight. And squash every loop to a point is the rule this page tried and broke, worth rereading for what its proof actually uses — because what it uses is exactly what blue and red take away.