Hackenbush is a numeral

Hackenbush is played on a picture made of coloured line segments, some of them attached to the ground. Left cuts blue edges, Right cuts red ones, either may cut green. When an edge is cut, everything no longer connected to the ground falls off and is gone. The player with no move loses.

That is the whole game, and it is the best small example in the subject, because its positions can be read.

The simplest stalks #

A single blue edge: Left cuts it and nothing remains; Right cannot move at all. So it is $\{0 \mid \;\}$, which is $1$ — one free move for Left.

$n$ blue edges stacked: Left cuts the bottom one and takes everything, or cuts higher and leaves a shorter stalk. Right still cannot move. The value is $n$. That is the whole of what a stalk of one colour does, and it is worth seeing before the second colour arrives, because it fixes what every later edge is a refinement of.

A blue edge with a red edge on top: Left’s only move cuts the blue edge, taking both, leaving $0$. Right’s only move cuts the red edge, leaving one blue edge, worth $1$. So the position is $\{0 \mid 1\}$, and the simplicity rule gives $\tfrac12$.

Add another red edge above: $\{0 \mid \tfrac12\}$, worth $\tfrac14$. Another: $\tfrac18$. The halving is unmistakable, and it is the beginning of the correspondence — one blue edge with a growing red cap, each new edge worth exactly half the last.

Two stacks, two behaviours, and the difference is entirely the colour change. All one colour and the edges count; past the first change and they halve.

The reading rule #

Write the stalk from the ground up as a string of L and R.

The leading run of one colour gives the integer part: $k$ blue edges before the first red gives $+k$; $k$ red before the first blue gives $-k$.

Every edge after the first colour change contributes a bit, halving each time. A blue edge adds, a red edge subtracts.

So LLRL is $2$, then the first change, then $-\tfrac12$ from the R and $+\tfrac14$ from the L — total $1\tfrac34$.

And LRRL is $1 - \tfrac12 - \tfrac14 + \tfrac18 = \tfrac38$.

The string is a numeral. Not a mnemonic for the value, not an approximation to it — the value, exactly, for every finite stalk.

Why it works #

The reason is the simplicity rule doing the same thing at every level.

Consider a stalk whose value is $x$, and add one edge on top. If the new edge is red, Right gains a move that leaves the stalk one shorter; the position becomes $\{\,\text{something} \mid x\,\}$, and the simplicity rule picks the simplest number below $x$ and above whatever Left can reach — which is $x$ minus half the current increment.

Each added edge halves the increment because each one is one level further from the ground, and cutting it leaves everything below intact. The recursion is the binary expansion’s recursion, and the values are the dyadic rationals because those are exactly the numbers born on finite days.

There is a second, sharper way to see it. Conway’s sign expansion writes every surreal number as a sequence of pluses and minuses recording the path down the number tree: go right, go left, go right. The Hackenbush string is that path, edge for edge, with blue as plus and red as minus. The stalk is not merely worth a number — it is the number’s construction, drawn.

Reading a few, slowly #

The rule is quick to state and worth exercising, because getting the leading run right is where mistakes happen.

L — one blue edge, no colour change. Integer part $+1$, no bits. Value $1$.

LL — two blue, no change. Value $2$.

LR — leading run of one blue, then a change. Integer part $1$; the R contributes $-\tfrac12$. Value $\tfrac12$.

LRR — integer part $1$; $-\tfrac12$ then $-\tfrac14$. Value $\tfrac14$.

LRL — integer part $1$; $-\tfrac12$ then $+\tfrac14$. Value $\tfrac34$.

LLRL — integer part $2$; $-\tfrac12$ then $+\tfrac14$. Value $1\tfrac34$.

RL — leading run of one red. Integer part $-1$; the L contributes $+\tfrac12$. Value $-\tfrac12$.

RRLR — integer part $-2$; $+\tfrac12$ then $-\tfrac14$. Value $-1\tfrac34$.

The pattern to internalise is that the first colour change ends the integer part and starts the bits, and that every subsequent edge halves whatever the last one contributed. A string of all one colour is a whole number; a string that alternates immediately is a fraction close to one.

Note also what the ordering does. LRL is $\tfrac34$ and LRR is $\tfrac14$, so among strings starting LR the third edge decides which half of the interval. That is the binary search the number tree performs, drawn as a stalk.

The sign works the same way and is worth reading off a picture rather than trusting to the rule, because it is the half that a reader who has seen only positive examples will get wrong. A leading red edge does everything a leading blue one does, in the other direction.

Nothing about that is a convention chosen to make the arithmetic tidy. Exchanging blue for red exchanges Left for Right, and exchanging the players is what negation means for every game in the subject; the numerals inherit it.

The value moves the way the picture does #

The correspondence has a consequence that makes Hackenbush unusually pleasant to look at: taller stalks are more precise, not more valuable.

A stalk of length two can be worth $2$, $\tfrac12$, $-\tfrac12$ or $-2$. A stalk of length six can be worth any dyadic with denominator up to $32$ in a bounded range. Adding edges does not push the value outwards; after the first colour change it pushes the value into finer and finer distinctions between values already bracketed.

So the picture’s height is the value’s birthday, and the picture’s shape is the value’s path down the number tree. Two stalks of the same height are values born the same day; a stalk of height four cannot be worth a number that needs five days.

That is the sign expansion made physical, and it is the reason this game is the one Conway used to introduce the surreal numbers. The construction that would otherwise be an abstract recursion is a drawing that can be pointed at — the number tree is the set of stalks, a path down it is a string, and the value is where the path lands.

The refinement claim is checkable on four stalks. Take the two strings of three edges that begin LR, and the two of four edges that extend one of them, and see whether the extra edge moves the value further out or splits an interval that was already bracketed.

Green edges, and the values that are not numbers #

Add a colour. A green edge may be cut by either player.

A single green edge: whoever cuts it takes it and leaves nothing. So it is $\{0 \mid 0\} = \ast$, confused with zero rather than placed beside it.

A stalk of $n$ green edges is worth $\ast n$, the nimber. Cutting at height $k$ leaves a stalk of $k$, so the options are every shorter green stalk — which is precisely the option structure of a Nim heap, and the mex rule gives the heap size.

So green Hackenbush is Nim, and a picture mixing colours mixes numbers with nimbers.

The binary reading has nothing to say about any of that, and there is a second reading that does. A stalk is the ordinal sum of its edges from the ground up — blue contributes $1$, red $-1$, green $\ast$ — and folding those from the bottom gives the value of every stalk, green ones included. On a blue-red string the fold reproduces the binary expansion exactly; on a green one it produces a nimber, which is a number no expansion in ones and zeros could have reached.

That is the honest generalisation of the numeral. The string is still read from the ground up, one edge at a time, and each edge still acts on everything below it — but the operation being iterated is the ordinal sum rather than the addition of a bit, and only in the two-colour case does it collapse into place-value arithmetic.

Infinitesimals in the picture #

Mixing colours produces values that are neither numbers nor nimbers, and the smallest of them is worth locating precisely.

Take a green edge on the ground with a blue edge above it. Left can cut either — the blue one, leaving a green edge worth $\ast$, or the green one, taking everything and leaving $0$. Right can only cut the green edge, taking everything, leaving $0$.

So the position is $\{0, \ast \mid 0\}$, which reduces to $\uparrow$: positive and smaller than every positive number.

The picture explains why. Left has a real advantage — the blue edge is Left’s and Right cannot touch it — and the advantage is contingent, because it stands on an edge Right can remove. It is worth something and not worth a whole move, and not worth any fraction of one either. It is worth an up.

Reverse the colours and the value is $\downarrow$. Put the green edge on top instead of underneath and the value changes again, because what falls off when it is cut is different.

This is where Hackenbush stops being a reading exercise and becomes a game with the full range of values in it. A picture of a dozen mixed stalks has a value that is a number plus a nimber plus an infinitesimal, and only the first part is legible from the string. Several such stalks side by side are a disjunctive sum and their values add — the numeric parts as numerals, the star parts by exclusive or, and the infinitesimal remainder deciding the position when the first two cancel. A green edge on a blue one is the essay that computes those mixtures; here they mark the boundary of the reading and no more.

The colon principle, in one line #

Trees are the first thing past stalks, and there is a rule for them worth stating even though it is not a reading.

A branch hanging off a stalk can be replaced by a stalk of the same value, attached at the same point. That is the colon principle, and it turns any tree into a stalk by working from the leaves inwards.

The subtlety is that the branch’s value has to be computed with the whole branch considered as a game in its own right, and that value then becomes a length of edges at the attachment point. So the reduction is real and it is not free — evaluating the branch is the expensive part, and the principle only saves the work of evaluating the tree as a whole.

For green trees there is a stronger and stranger result, the fusion principle: any two vertices joined by a cycle may be fused into one, and loops become single edges. That reduces green Hackenbush on an arbitrary graph to green Hackenbush on a tree, and the colon principle then reduces that to a stalk. So green Hackenbush on any graph is a Nim heap, computable by two graph reductions and no search at all.

Blue-red Hackenbush on an arbitrary graph has no comparable result, which is the honest shape of the subject: the impartial case reduces completely and the partizan case does not.

Where the numeral reading stops #

The reading rule is for stalks — single chains of edges, each attached to the one below. Most Hackenbush pictures are not stalks, and the moment the picture branches or loops, the numeral reading fails.

A tree of edges — branches from a common trunk — has a value computable by the recursion but not by reading a string. There is a rule for trees, the colon principle, which replaces a branch by an equivalent stalk, and it is a genuine theorem rather than a reading.

A picture with loops or with edges connecting two ground points is harder still, and general Hackenbush with arbitrary graphs is where the subject gets difficult. Green Hackenbush on a general graph reduces by a fusion argument to a tree; blue-red Hackenbush on a general graph does not have a comparably simple answer.

So the elegance is real and it is local. Stalks are numerals; everything else needs the recursion.

What the solver computed #

This is the place where this site’s build check is most direct.

For every Hackenbush figure, each string’s value is computed twice. hackenbushString builds the position as a game — options are the positions reachable by cutting each edge of the appropriate colour, with everything above falling off — and evaluates it through canonical, the same recursion the rest of this site runs on. hackenbushBinary reads the string as a numeral by the rule above, in exact dyadic arithmetic.

The build asserts the two agree. Every blue-red string up to length six is checked — 126 strings — and if any disagreed, nothing would render.

That check is not decoration. It is the strongest form of the site’s rule that values are computed rather than quoted: two independent implementations, one from the game recursion and one from the arithmetic, agreeing on every case. A transcription error in either would be caught immediately, and a misunderstanding of the reading rule would be caught on the first string where the two diverge.

The green-edge values are checked differently, against the nimber they should be: a stalk of $n$ greens must canonicalise to $\ast n$, and assertValue confirms it.

Playing it #

Hackenbush is worth actually playing, because the correspondence changes what play feels like.

Given a picture of several stalks, the value is the sum of the strings read as numerals. If the total is positive, Left wins; negative, Right; zero, the second player. That is a complete solution for pictures of stalks, and it is arrived at by reading rather than searching.

The strategy that implements it is the interesting part. A player ahead by a positive amount should reduce the opponent’s advantage while preserving their own, which in numeral terms means cutting so as to change the opponent’s leading bits. In practice that usually means cutting low in the opponent’s tallest stalk — and the correspondence says exactly how much each cut is worth, which is not obvious from the picture.

The options of a stalk are its own prefixes, since a cut takes everything above it away, so choosing a move is comparing a handful of numerals rather than searching a tree. Cutting the top edge of LRL leaves LR, worth $\tfrac12$ against the position’s $\tfrac34$; cutting the bottom leaves nothing at all. Every cut moves the value by an amount the reading gives, and the size of the move is the whole of what a player needs.

What the picture cannot show #

The correspondence is so clean that it is worth being explicit about its edges.

It does not show the value of a sum. Two stalks side by side are worth the sum of their numerals, and there is no way to read that off the picture without doing the arithmetic. The drawing shows two numbers; the addition is separate.

It does not show a move. Knowing a stalk is worth $\tfrac38$ says nothing about which edge to cut, and the answer depends on what else is on the board. A value is not a strategy, and the numeral reading is a value.

It does not extend past stalks. A branching picture has a value and no numeral, and the reading rule fails silently rather than obviously — a tree can be read as a string if somebody is careless enough, and the answer is wrong.

It does not survive green edges. One green edge anywhere and the position is no longer a number, so the string is no longer a numeral. The prose above treats the two-colour and three-colour games separately for exactly this reason.

So what the picture shows is one number, exactly, for one stalk. That is a great deal for a drawing to carry, and it is less than a reader who has just seen the correspondence tends to assume.

Who invented it, and when #

Hackenbush is Conway’s, from the 1970s, and it appears in On Numbers and Games as the running example — the game used to make the surreal construction concrete. The name is his, and the “hack” is meant literally.

Its role in the exposition is unusual: it is not a game anybody plays for pleasure, and it was invented for the purpose it serves. That is worth noticing, because the correspondence between stalks and numerals is not a discovery about a pre-existing game. It is a game designed so that the correspondence would hold, and the design is what makes it the clearest illustration available.

Winning Ways develops the tree and general-graph cases, including the colon principle and the fusion argument for green graphs, and it is where the harder half of the theory lives.

What makes a game readable as a numeral #

Hackenbush strings are read as binary expansions, and it is worth asking what the game had to supply for that to be possible, because the answer identifies a small family and this is its clearest member.

A numeral is a sequence of independent digits. For a reading to be a numeral, each position in the string has to contribute a fixed amount, decided by its symbol and its place, with no contribution depending on what else is in the string.

Hackenbush supplies that through the ground. An edge can only be cut if everything below it stays attached, so an edge’s effect is determined by its colour and its distance from the ground — and cutting low removes everything above, which is what makes each place worth half the one before rather than some amount depending on its neighbours.

Take the ground away and the reading goes. A string floating free is not a numeral, because the edges stop having places; a graph with cycles is not one either, until fusion collapses the cycles and restores a tree with a root.

So the family of games readable as numerals is the family with a distinguished base and a monotone dependence on distance from it — which is why a Push strip is another member, with its wall doing the ground’s job, and why a Push strip cut in half stops being readable the moment the second piece loses its wall.

That is the general lesson and it is a geometric one. A numeral needs an origin, and a game supplies one only when its rules single out a place that every move is measured against.

Where the model stops #

Stalks only, for the numeral reading. Trees and graphs need the recursion or the specialised principles.

Finite pictures. An infinite stalk would be worth a non-dyadic number, which is exactly how the surreal construction reaches beyond the dyadics, and none of the finite arguments apply.

The reading is exact, and the pictures are small. Every value here was computed on a picture small enough for exact evaluation, which is the standing limit.

Normal play, throughout.

The elegance is engineered. Hackenbush was built to make this correspondence visible. It is a demonstration that the theory’s values are natural, not evidence that natural games have tidy values — Domineering is the corrective.

The ladder from here #

Nearby: the colon principle and Hackenbush trees; the fusion argument for green graphs; blue-red Hackenbush on general graphs, where the tidiness ends; and infinite stalks, which reach the non-dyadic surreals.

Then across to the games that were not designed for the purpose — Domineering, whose values are ugly, and Toads and Frogs, whose values are infinitesimal — where the same machinery has to work without the picture helping.