A tree is still a number

Hackenbush is a numeral is the most direct result on this site. A stalk of coloured edges standing on the ground, read from the bottom up, blue for one and red for zero: the string is the binary expansion of what the position is worth, not approximately but exactly, and the solver computes it both ways and refuses to build if the two disagree.

The result is about strings. A Hackenbush position is a graph — any graph, provided every edge is connected to the ground — and the moment two edges leave the same node there is no string to read.

So the numeral runs out. What replaces it is the subject of this essay, and there are three separate claims, each checked over every forest of up to six edges — 10,066 of them.

Every one of them is a number #

The first claim is that nothing here gets hot. All 10,066 forests are worth numbers, which is a strong statement for a partizan game and is not what a reader arriving from Domineering or Toads and Frogs would expect.

The reason is the same one that makes the strings numbers. Every move deletes an edge, and deleting an edge is a concession: the player who does it has one fewer edge to delete later, which under normal play is the only currency there is. A position where every move costs the mover something is a position nobody wants to move in, and that is what a number is.

It matters that this is a property of blue-red Hackenbush and not of Hackenbush. Add a green edge — one either player may take — and the values stop being numbers immediately: a green edge on a blue one is worth something with a star in it, and green Hackenbush is entirely made of nimbers. Colour is what decides whether the game is cold.

Several trees at once are a sum #

The second claim is the easiest and is worth stating because the picture makes it invisible.

Two trees standing side by side on the ground are two independent games. Nothing a player does to one changes the other, so the position is their disjunctive sum and its value is the sum of their values. Over the 6,828 forests in the census with more than one trunk, the arithmetic agrees every time.

The reason to check it rather than assume it is the ground. In a Hackenbush position the ground is drawn, and everything standing on it is connected to it, so the picture presents the whole board as one object. A reader who has learned that an edge is deleted when its support is cut may reasonably wonder whether the ground is a shared support and whether cutting somewhere on one tree could affect another. It cannot: the ground is not an edge and cannot be cut.

The trunk, and everything above it #

The third claim is the one that does the work. A tree with a single trunk is not a sum — cutting the trunk destroys everything above it, which is exactly not independence — and the operation that describes it is the other one.

The ordinal sum $G : H$ is the other sum, the one that nests. A move in $G$ — the base — wipes out $H$ entirely; a move in $H$ leaves $G$ alone. That is precisely the relationship between a trunk and what stands on it, and the correspondence holds on every single-trunk tree in the census: 3,238 of them, no exceptions.

Written as a rule:

$$\text{value of a tree} \;=\; (\pm 1) : (\text{the forest above the trunk})$$

with $+1$ for a blue trunk and $-1$ for a red one. Applied recursively — since the forest above the trunk is itself trees, each of which is a trunk with a forest above it — this computes any tree at all from the shape of the picture, without ever building the game.

Why that is the same rule as the string #

The satisfying part is that the string result is a special case rather than a different theorem.

A string is a tree in which every node carries exactly one edge, so the forest above each trunk is a single tree, and the recursion is a chain of ordinal sums:

$$\text{value of } b_1b_2b_3\ldots \;=\; (\pm 1) : \big( (\pm 1) : ( (\pm 1) : \cdots ) \big)$$

Working that out for a blue base gives $1$, then $1 : (\pm 1)$ gives $\tfrac32$ or $\tfrac12$, then another level gives quarters, and the halvings that produce the binary expansion appear from the arithmetic of the ordinal sum rather than being put in by hand. So “the string is a numeral” and “a tree is a nest of ordinal sums” are one statement, and the first is what the second looks like when the tree has no branches.

Every halving in the binary reading is one level of that nesting, which is why the reading never needed a justification of its own: LRRL is $1 : (-1) : (-1) : 1$, and folding those four edges from the ground gives $\tfrac38$ with no place-value arithmetic invoked anywhere. What the tree case adds is the possibility of two things at one level, and that is the single case a place-value notation has no way to express — a digit has one place, and a fork puts two whole forests in it.

What the reading does when there is a fork #

Given a tree, the numeral has one thing it can try: walk up the leftmost branch at every fork and read the colours that walk passes. That is a definite procedure and it produces a definite number, and the census asks how often that number is the value.

762 times out of 10,066. Of those, 126 are positions that are paths, where the walk passes every edge and the reading is the theorem. The other 636 are coincidences — trees where the discarded branches happen to contribute nothing net, or where two errors cancel.

The reason no reading can work is structural rather than arithmetical. A place-value numeral is an ordered sequence of digits, and the order is what gives each digit its weight. A tree has no order at a fork. Two branches leaving one node are simultaneous — neither is before the other in any sense the game respects — and the ordinal sum handles them by adding them together first and then nesting the result, which is an operation with no place-value analogue.

Most of the coincidences are not coincidences #

Calling the successful readings coincidences is too quick, and the colon rule says why: there is a condition under which discarding a branch is provably harmless, and it accounts for most of them.

The reading walks the leftmost branch and throws the rest away. The tree’s value is $(\pm1) : F$ where $F$ is the whole forest above the trunk; the reading computes $(\pm1) : F'$ where $F'$ is the leftmost tree of $F$ alone. The ordinal sum respects equality on its right argument — that is the colon principle — so the two agree whenever $F$ and $F'$ are worth the same.

Which gives a condition, applied at every fork the walk passes:

At every node on the leftmost spine, the forest above it is worth what its own leftmost tree is worth.

That is the discarded branches cancel, stated so that it can be checked.

Over the 3,238 single-trunk trees of the census, 358 satisfy it, and every one of the 358 reads correctly. No exceptions in that direction at all — which is what a sufficient condition looks like when it is genuine rather than fitted.

The reading is right on 406 of those trees. So 358 of the successes have a reason and 48 are accidents — trees where the discarded branches do not cancel and two errors happen to. Eighty-eight per cent of the successes are the colon principle doing exactly what it promises, and the residue is small enough to call what it is.

Which sharpens what the numeral has lost #

That is a better account of the failure than “there is no leftmost anything”, because it says precisely what the reading is assuming and when the assumption holds.

The numeral is not blind to branches. It is assuming that what it skips is worth nothing, and on a string that assumption is free, because there is nothing to skip. On a tree it is a real hypothesis, checkable in advance, and false 88% of the time.

So the reading is not a broken procedure. It is a correct procedure with an unstated precondition, and the precondition is exactly the one the colon principle needs — which is a much more useful thing for a reader to carry than a count of failures. Given a tree, look at each fork on the leftmost path and ask whether the branches being discarded cancel among themselves. If they do, read the spine and stop. If they do not, the ordinal sum has to be run.

And it explains why no repair to the reading exists. A place-value numeral could be extended to handle skipped branches only if their contribution were a function of their position in the string — a digit’s worth of correction at a digit’s place. It is not: the correction is the value of a whole forest, computed by the same machinery the reading was trying to avoid. There is no shorter description of what was discarded than the thing itself.

That is the honest shape of the boundary. The numeral survives exactly as far as the discarded part is empty or worthless, and the moment it is neither, the only available account of it is the recursion.

The green case, which does the opposite #

There is a version of this argument on the green side of the game, and comparing them is instructive because they point in opposite directions.

In green Hackenbush the colon principle is a simplification: it takes a complicated graph and reduces it to one number, because nimbers under ordinal sum behave simply. In blue-red Hackenbush the same principle is a computation: it gives the value and gives no collapse, because the ordinal sum of numbers is not a number operation anybody would recognise. Same rule, and the difference is entirely in what it is being applied to.

That is worth carrying. The colon principle is often introduced as a Hackenbush trick for green edges, and it is not a trick and not about green edges. It is the statement that a position standing on a support behaves as an ordinal sum, and it holds whatever colour the support is.

Working one out by hand #

The cherry is small enough to do completely, and doing it is the fastest way to see why the fork is the obstruction.

The position is a blue trunk with one blue edge and one red edge standing on top of it. Left has two moves: cut the trunk, which takes the whole thing away and leaves nothing, worth $0$; or cut the blue edge above, leaving a blue trunk with a red edge on it, which is the string LR and is worth $\tfrac12$. Right has one move: cut the red edge above, leaving the string LL, worth $2$.

So the position is $\{0, \tfrac12 \mid 2\}$. The Left option $0$ is dominated by $\tfrac12$, so the form is $\{\tfrac12 \mid 2\}$, and the simplicity rule gives the simplest number strictly between a half and two, which is $1$.

Now the reading. The leftmost path from the ground goes trunk, then the blue edge above it — two blue edges — and reads as $2$. The value is $1$. The discarded red edge was worth a great deal more than the numeral’s next digit could have expressed, because at that level the numeral’s next digit is worth a half and the red edge shifted the answer by a whole point.

A string has none of that trouble, and the contrast is what makes the fork the culprit rather than the arithmetic. Every cut in a string takes the edges above it away, so its options are its own prefixes — an ordered family, one per level, which is exactly what a place-value reading needs. The cherry’s fork gives two options at the same level, and there is no digit position for the second one.

What the solver computed, and how #

A forest is a nested list: each entry is a colour and the forest sitting on the far end of that edge. Deleting an edge is a splice at the right depth, and everything above it goes with the splice, which is the rule about disconnection implemented rather than checked.

Every forest of one to six edges is enumerated by size — a first tree of $k$ edges and a rest of $n-k$ — and each is evaluated once and cached against its own written form. For each, three things are asked. Is the value a number? For single-trunk trees, does the ordinal sum of the trunk’s value with the forest above it equal it? For multi-trunk forests, is it the sum of the separate trees? And separately, does the leftmost reading give it, which is asked of every position including the ones where it has no right to work.

The comparisons are exact. The ordinal-sum check compares canonical forms, and the sum check compares the value as a rational, so a match is a match rather than a coincidence of printed strings.

Why the trees are worth having as a family #

A reader may ask what the tree case buys, given that the strings were already exact and the trees need an operation to compute. Three things.

It separates two properties that the string result runs together. Being worth a number is one fact; being readable is another; and on strings they coincide so completely that the second looks like an explanation of the first. The trees are worth numbers and are not readable, so the coincidence is broken and the first fact needs its own reason — which turns out to be the one about moves being concessions, and has nothing to do with notation.

It gives the ordinal sum something to do that is not green, and something whose answer is not already known by another route. The other sum that nests is introduced on this site through Hackenbush stalks and used through nimbers, and both of those are cases where the answer collapses. Here it neither collapses nor fails: it computes.

And it supplies the smallest position on the site where a reader’s first guess is definitely wrong and the correction is one line. The cherry is four edges. Anyone who has read the string essay will guess two, and the answer is one.

Not even the sign reads off the picture #

A reader looking for something salvageable will try the crudest reading of all: count the edges. More blue than red should mean a win for Left, since normal play makes moves the currency and a player with more edges has more moves to spend.

It fails, and not rarely. Of the 10,066 forests in the census, 7,338 have unequal counts of blue and red edges, and in 916 of them the sign of the value disagrees with the majority colour. The smallest is a red trunk carrying two blue edges: two blue against one red, and the position is worth $-\tfrac14$.

The reason is the trunk. Cutting the red trunk takes both blue edges with it, so Left’s two extra edges are hostages rather than reserves — Right can destroy them with a single move that costs one edge and removes three. A count of edges is a count of moves only when the edges are independent, and in a tree they are the opposite of independent.

So the position is worse than “the value is not readable”. Nothing about the value is readable — not the size, not the sign — and the only route to either is the recursion or the rule that stands in for it.

Where the model stops #

Six edges, which is 10,066 positions and is enough for the counts to mean something. Beyond that the enumeration grows fast and the evaluation grows faster, and nothing here is a proof: three claims that hold on every position tried are three claims that hold on every position tried.

The tree rule also does not extend to Hackenbush in general. 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. Blue-red Hackenbush on general graphs is still worth numbers — the argument about moves being concessions does not care about cycles — but the numbers are not computed by anything drawn here, and the general case is genuinely hard.

Where the ladder goes next #

The three rungs below this one take Hackenbush from a string to a graph: the numeral, the green fusion, and the mixed case. This rung is what happens to the numeral when the string becomes a tree. The rung above is the cycle, where the decomposition stops and nothing on this site replaces it.

Two neighbours are worth following. When the nested sum only sees the value is about the ordinal sum’s one dangerous property — that it reads the form of its base rather than the value — which is why the rule above is stated in terms of a trunk and not in terms of what the trunk is worth. And nothing worth fighting over is the other cold partizan game on this site, and the one where no reading of the board works at all.