A green edge on a blue one

Two Hackenbush essays on this site each take one colour scheme and get a clean answer out of it. A blue-red stalk is a binary numeral — read the string from the ground up and the number is spelled out. An all-green graph is a Nim heap — fuse the loops and read off a single nimber.

The obvious next question is what happens when the colours are mixed, and the answer is not a compromise between the two. It is a third kind of object, and the shortest example needs two edges.

The two edges, and the two answers #

Take blue under green first. Left may cut either edge; Right may cut only the green one.

If Left cuts the green edge on top, a blue edge is left standing: worth 1. If Left cuts the blue edge at the bottom, everything above falls with it and nothing is left: worth 0. Right’s only cut is the green edge, leaving the blue one: worth 1.

So the position is {0, 1 | 1}, and the recursion reduces it to {1 | 1}, which is 1∗ — the number one with a star added. A player gets a point out of it and there is a move left over that neither player wants to be the one to lose.

Now green under blue. Left may cut either; Right may cut only the green one at the bottom — and cutting it drops the blue edge above with it.

Left cutting the blue top leaves a lone green edge, worth ∗. Left cutting the green bottom leaves nothing, worth 0. Right cutting the green bottom also leaves nothing, worth 0. So the position is {0, ∗ | 0}, which reduces to ↑∗.

Two edges, two orders, and the values are in different classes. 1∗ is a point plus a nimber; ↑∗ is infinitesimal — smaller than every positive number, larger than every negative one, and worth no points at all.

What the ground does #

The mechanism is the rule everybody meets on the first page of Hackenbush and stops thinking about: everything not connected to the ground falls off.

That rule makes a stalk an ordered object rather than a set of edges. An edge low down is worth more than the same edge high up, because cutting it destroys more, and the destruction runs one way only — nothing above protects anything below.

So the colour of the bottom edge decides what the whole stalk is made of, and the colours above it only modify. Blue at the bottom gives a position with a point in it; green at the bottom gives a position where both players can wipe the whole stalk out, which is a position with no points in it at all.

That figure is the tidy half of the answer. A green edge sitting above a blue-red stalk contributes a star and nothing else, because cutting it leaves the numeral intact and cutting into the numeral destroys it. The awkward half is when green sits below.

The rule for green on top, and its limit #

The pattern in that figure is a rule and it is worth stating exactly, because the exactness is where it stops.

A number with a green cap is that number with a star. One green edge above a blue-red stalk worth x gives x∗; two give x∗2; three give x∗3. The green edges above the numeral behave as a Nim heap of their own — which is what the all-green theory says they should — and the numeral underneath is untouched.

The reason is the ground rule again. A green edge above the numeral can be cut by either player without disturbing anything below it, so the two parts do not interact and the position is a number plus a nimber.

Now insert one blue edge above the green one and the nimber part of the rule goes.

What changed is that the top blue edge is now supported by the green one, so cutting the green edge takes a blue edge with it, and what sits above the ground stops being an impartial game.

But the rule has not collapsed — only the half of it that named the answer. The section below states the half that survives, and it predicts both of those values exactly.

The rule that survives #

The green-cap rule is a special case of something wider, and the wider version covers every stalk in this essay including the two the last section gives up on.

If the ground edge is blue or red, and everything above it is all-small, then the stalk is worth that number plus what is above it.

Not the ordinal sum of the two — the ordinary disjunctive sum. The nesting, which is the whole reason a stalk is not a set of edges, stops mattering the moment the base is a number and the top has no numbers in it.

Check it on the stalks already computed. LE has $\ast$ above a blue edge: $1 + \ast = 1\ast$. LEE has $\ast 2$: $1 + \ast 2 = 1\ast 2$. LEL has $\uparrow\!\ast$ above it — all-small, though not a nimber — and $1 + \uparrow\!\ast = 1{\uparrow}\ast$, which is exactly the value the search returns. And LERL has $\{0, \downarrow\!\ast \mid 0, \ast\}$ above it, which is all-small too, so the rule predicts $1 + \{0, \downarrow\!\ast \mid 0, \ast\} = \{1, 1{\downarrow}\ast \mid 1, 1\ast\}$ — the value with no name, produced by an addition rather than by a search.

Swept over every all-small value born by day two and a spread of numbers, the ordinal sum and the disjunctive sum agree in all 63 cases; over a sample of the day-three all-smalls, all 54. Where the top is not all-small the rule says nothing and means it: EL has the number $1$ above a green edge and comes out $\uparrow\!\ast$, which is not $\ast + 1$.

Why all-small is the condition #

The condition is not arbitrary and the reason says what the ground rule is really doing.

An ordinal sum differs from a disjunctive one because a move in the base deletes the top. That difference can only be worth something if the top was worth something — and an all-small game is worth nothing in the only currency the base deals in. Its stops are both zero, it has no numeric part, and destroying it costs the destroyer no points at all.

So when the top is all-small, deleting it and leaving it alone are worth the same, and the two sums coincide. When the top has a number in it, deleting that number is a real gain for whoever does it, and the nesting is worth exactly that gain.

Which is why the interesting stalks are the ones with a green edge low down. Green at the bottom means either player can destroy everything above, and the value of everything above is what that destruction is worth. Green at the top means the destruction available is destruction of nothing.

That is the honest boundary of the section above. Three edges is enough to leave the named values behind entirely once the ground edge is green, and nothing shorter does it.

That also puts the essay’s headline pair in its proper place. LE and EL differ not because order matters in general but because in one of them the deletable part is worth a point and in the other it is worth an infinitesimal — and a rule that reads which part is deletable, and what it is worth, gets both right without any search.

So the mixed theory is less lawless than the section above suggests. There is one condition, it is checkable from the picture — is anything above the ground edge worth points? — and where it holds the stalk is an addition. What has no shortcut is the case the condition excludes, and that is a narrower claim than “the general case is a recursion”.

Where the binary reading gives up #

The blue-red result is that a stalk is a numeral. The reading is completely explicit: blue is 1, red is 0, the first edge sets the integer part and everything above it is a binary expansion.

That reading has nothing to say about a green edge, and not because nobody has worked out the digit. There is no digit. The values that come out — ↑∗, ∗2, 1∗ — are not numbers, and a numeral system produces numbers.

Every value in this essay is missing from the line the blue-red stalks fill in, and the infinitesimal ones are missing in a specific way — they sit in no gap between two numbers, because there is no gap left to sit in.

So the honest statement is that the binary reading is a theorem about one colour scheme rather than about Hackenbush. What survives into the mixed case is something weaker and more interesting: the stalk is still an ordered construction, and the operation that builds it has a name.

The operation is the ordinal sum #

A stalk is not the disjunctive sum of its edges. Adding two edges as separate games gives a position where a move in one leaves the other alone, and that is not what a stalk does — cutting low destroys everything high.

The operation that does the right thing is the ordinal sum: G : H is the game where a move in G wipes H out entirely and a move in H leaves G standing. A stalk is exactly the ordinal sum of its edges from the ground up, and the site checks it: each figure that draws a mixed stalk computes the value twice, once by the game recursion on the picture and once by folding the edges with the ordinal sum, and refuses to draw if the two disagree.

That is why the order matters and why the mechanism is the ground rule. 1 : ∗ is 1∗ and ∗ : 1 is ↑∗, and the ordinal sum is not commutative in the way the disjunctive sum is. Set several stalks side by side instead of stacking them and the other arithmetic applies: a move is a move in one of them, the rest are untouched, and the total is the disjunctive sum of the separate values rather than a fold of the edges.

The values, ordered #

The three classes that turn up in mixed stalks can be told apart by comparison, which is the only way they can. ↑∗ is confused with ∗ and confused with 0, and ∗2 is confused with ∗ — none of which is visible in a picture of either position, because the relation is the outcome of a game rather than a property of a drawing. Comparing two games means playing their difference, and the answers here are computed the same way every other value on this site is.

That is also why the four outcome classes matter more than the sizes. 1∗ is a win for Left whoever moves; ↑∗ is a win for whoever moves first; and the difference between them is not a difference of size but of kind.

Why the infinitesimal turns up at all #

It is worth asking where ↑ comes from, because it is not obvious that a two-edge picture should produce the smallest interesting object in the subject.

Up is {0 | ∗}: a position Left wins whoever moves, by an amount smaller than every positive number. Green under blue produces exactly that shape — Left has a move to ∗ and a move to 0, Right has only the move to 0 — and the reduction turns {0, ∗ | 0} into ↑ with a star still attached.

The general reason is that a green edge is a move both players have, and a blue edge above it is a move only Left has. Stacking them gives Left one more option than Right in a position where the points cancel, and “one more option and no points” is what an infinitesimal is. That is the same mechanism that makes Clobber all-small, arrived at from a picture rather than from a rule about adjacency.

The size of the thing is a separate question and it is answered by comparison rather than by inspection: ↑∗ is confused with zero, ↑ is greater than zero and smaller than every positive number, and the ordering among the infinitesimals themselves is what tiny and miny is about. A stalk of two edges can produce a value that needs the whole of that apparatus to place, which is a reasonable answer to anybody who suspects Hackenbush of being a toy.

What the impartial theory keeps #

One thing does survive from the all-green case, and it is worth being precise about how little.

An all-green graph is impartial: both players have the same moves, so Sprague–Grundy applies, the whole graph is worth a single nimber, and fusion and the colon principle find it without playing anything out.

The moment a single blue or red edge appears, the game is partizan and the nimber apparatus is gone. What is left is the ordinary recursion — the one that computes every value on this site — applied to a position with an unusually clear geometry.

That is not a downgrade. It is the general situation, and the two clean colour schemes are the special cases.

What this costs to compute #

Hackenbush is the cheapest game on this site to evaluate and the mixed case is where that stops being obvious, so it is worth pricing.

A blue-red stalk of n edges needs no search at all: the binary reading gives the value in n steps, and the check that the recursion agrees is a convenience rather than a necessity. An all-green graph needs a walk over its edges to find the bridges, and fusion settles it without playing anything out.

A mixed stalk needs the recursion. Each edge cut produces a sub-stalk, each sub-stalk is evaluated in turn, and the values have to be compared to be reduced — so the cost is the cost of building and canonicalising a game tree, which is the same cost every other partizan position on this site carries.

The saving that remains is real but structural: a stalk decomposes as an ordinal sum, so an n-edge stalk is n nested one-edge problems rather than a search over subsets of edges. That is the difference between linear and exponential, and it is the reason this essay can quote values for stalks of five edges while a 4×4 Domineering board takes millions of nodes.

The general blue-red-green graph has neither the numeral shortcut nor the fusion one nor the ordinal-sum decomposition, and that is the honest boundary of what is settled here.

Where the model stops #

These are stalks, not graphs. Every mixed position here is a single path standing on the ground, and the values are folded up one edge at a time. A mixed graph — blue, red and green edges with cycles in them — has no such folding: the ordinal sum decomposes a stalk and does not decompose a graph, and the general blue-red-green Hackenbush position has no known reduction.

The star is a convenience of small examples. Every two-edge mixed stalk here came out as a number plus a nimber or as an infinitesimal with a familiar name. Longer mixed stalks produce values with no short name at all — LEL is worth 1↑∗, ELR is worth {0, ∗ | 0, ↑∗}, and EEL is worth {0, ∗2, ∗ | 0, ∗}, none of which is any tidier than the brace expression that prints it.

And nothing here is a strategy. Knowing a stalk is worth ↑∗ says who wins it in a sum; it does not say which edge to cut, and the figures that show options are the ones where the move can be read.

What the picture cannot show #

A Hackenbush drawing is unusually honest — the position really is the picture — and it still cannot show the thing this essay is about.

The value of a stalk depends on the order of its edges, and a drawing of a stalk shows the order perfectly. What it cannot show is that the order matters, because there is no way to draw the alternative alongside without drawing a second stalk. The figures here draw both, which is the only fix available, and a reader looking at a single mixed stalk in the wild has nothing to warn them.

The other thing not shown is the check. Every mixed stalk in this essay has its value computed twice — once from the drawn edges and once by folding the ordinal sum — and the agreement is what makes the claims here more than assertion. Neither computation appears in any figure; what appears is the answer they agree on.

The convention, named #

Normal play, and one convention specific to Hackenbush that decides everything above.

Green means either player may cut. That is what makes a green edge an impartial move inside a partizan game, and it is why a green edge contributes a nimber rather than a number. A different convention — green as an edge neither may cut, or one that only the player to move may cut — would produce a different game with the same picture, and every value on this page would change.

The second convention is the ground. Everything above depends on edges falling when their support is cut, which is what makes a stalk an ordinal sum rather than a disjunctive one. A version of Hackenbush where cut edges float is a different game, and it is the disjunctive one: each edge independent, values adding, and no essay in it.