Combinatorial Game Theory
who wins, and by how much
Particular games

Hackenbush is a numeral

Draw a stalk of coloured edges. Read it as a string, blue for one and red for zero, and the string is the binary expansion of what the position is worth. Not approximately — exactly, and the site computes it both ways and refuses to build if they disagree.
18 min read 9 figures The value is computableWho moves lastNot every game is a number

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 picture is the numeralBlue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number.1blue2blue blue1/2blue red3/4blue red blue1/4blue red red3/8blue red red blueeach string is worth a number, and the string spells itblue is Left · red is Right · the ground is what holds it up
Fig. 1 Stalks and their values. The first edge sets the sign and the integer part, and every edge after the first colour change contributes one bit — so the picture is a numeral.

The simplest stalks

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

nn 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 nn.

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

Add another red edge above: {0∣12}\{0 \mid \tfrac12\}, worth 14\tfrac14. Another: 18\tfrac18.

The halving is unmistakable, and it is the beginning of the correspondence.

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: kk blue edges before the first red gives +k+k; kk red before the first blue gives −k-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 22, then the first change, then −12-\tfrac12 from the R and +14+\tfrac14 from the L — total 1341\tfrac34.

And LRRL is 1−12−14+18=381 - \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.

Which numbers the strings reachEvery blue-red Hackenbush string of up to four edges, placed at its value. Short strings give integers, longer ones fill in halves and quarters, and the pattern continues — the reachable values are exactly the dyadic rationals, and nothing else.-2-1012121/2-1−1/2-21234edgesone more edge halves the gap — and every value is a fraction with a power of two underneath
Fig. 2 Short stalks placed on the number line at their computed values. The strings are ordered exactly as the binary numerals they spell, which is what the correspondence asserts.

Why it works

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

Consider a stalk whose value is xx, 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 { something∣x }\{\,\text{something} \mid x\,\}, and the simplicity rule picks the simplest number below xx and above whatever Left can reach — which is xx 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+1, no bits. Value 11.

LL — two blue, no change. Value 22.

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

LRR — integer part 11; −12-\tfrac12 then −14-\tfrac14. Value 14\tfrac14.

LRL — integer part 11; −12-\tfrac12 then +14+\tfrac14. Value 34\tfrac34.

LLRL — integer part 22; −12-\tfrac12 then +14+\tfrac14. Value 1341\tfrac34.

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

RRLR — integer part −2-2; +12+\tfrac12 then −14-\tfrac14. Value −134-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 34\tfrac34 and LRR is 14\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 value of LRR is computed, not readOne string with every option drawn. Left's moves are the blue edges she may cut, Right's the red ones; each leaves the part of the string still standing. The value follows from those options by the same recursion that defines every game in the subject.1/4the positionLeft cuts blue, leaving0Right cuts red, leaving11/2{0 | 1/2}
Fig. 3 One stalk with every position reachable from it. Each cut truncates the string at some point and drops everything above, so the reachable values are exactly the numerals the string’s prefixes spell.

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 22, 12\tfrac12, −12-\tfrac12 or −2-2. A stalk of length six can be worth any dyadic with denominator up to 3232 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 numbers, by the day they are bornZero on the first day, ±1 on the second, and thereafter the simplest number in each remaining gap. Every number reachable in finitely many days is a fraction with a power of two underneath, and every such fraction appears — which is a strange thing for a construction with no arithmetic in it to produce.day 00day 1-11day 2-2−1/21/22day 3-3−3/2−3/4−1/41/43/43/23each new number is the simplest one in a gap — which is the simplicity rule, applied everywhere at once
Fig. 4 The number tree, which is the same object as the set of stalks. A stalk of height four is a path four steps down this tree, and its value is where the path lands.

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∣0}=∗\{0 \mid 0\} = \ast, confused with zero rather than placed beside it.

A stalk of nn green edges is worth ∗n\ast n, the nimber. Cutting at height kk leaves a stalk of kk, 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.

A green edge is not a numberGreen edges may be cut by either player, which makes the position impartial in that part. A single green edge is worth ∗ — a value that is neither positive, negative nor zero, and which no number can equal.∗not a numberoutcome N∗2not a numberoutcome N{1 | 1}not a numberoutcome L↑∗not a numberoutcome Ngreen may be cut by either playerand that is enough to leave the number line
Fig. 5 Green edges and the values they produce. A green stalk is a Nim heap; a green edge under a blue one gives an infinitesimal; and none of these values sits on the number line.

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 00. Right can only cut the green edge, taking everything, leaving 00.

So the position is {0,∗∣0}\{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.

A position is the sum of its partsFour separate Hackenbush sprigs. A move is a move in one of them, so the position is their disjunctive sum, and its value is the sum of their values. Which part to play in is the entire decision, and the values are what makes it decidable.{1 | 1}+↑∗+1/2={3/2 | {3/2 | 3/2}}outcome Leach sprig is a separate game; a move is a move in one of themthe total was computed by adding the games, not the labels
Fig. 6 Mixed stalks summed. The numeric parts add as numerals, the star parts add by exclusive-or, and the infinitesimal remainder is what decides the position when the first two cancel.

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.

Hackenbush from LLRL and RRRL — and who winsTwo Hackenbush stalks with the total stated before anybody moves. Left cuts blue, Right cuts red, and everything no longer joined to the ground falls off. The total is negative, so Right wins whoever starts, and every reply the machine makes was computed at build time from the same recursion the essays describe.the total is −3/4Right wins whoever movesstated before a move is madeyou cut blue · it cuts redwith the script running, the blue edges become clickable and this claim can be tested
Fig. 7 Two stalks reading 1¾ and −2½, so the picture is worth −¾ and Right wins it whoever starts. The reader cuts blue and moves first. The value was read off the strings; the replies come from the game recursion; the two agree, which is the check this site runs on every build.

What the solver computed

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

For every Hackenbush figure, lib/games.js computes each string’s value 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 in lib/cgt.js. 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 nn greens must canonicalise to ∗n\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 value of LRL is computed, not readOne string with every option drawn. Left's moves are the blue edges she may cut, Right's the red ones; each leaves the part of the string still standing. The value follows from those options by the same recursion that defines every game in the subject.3/4the positionLeft cuts blue, leaving01/2Right cuts red, leaving1{1/2 | 1}
Fig. 8 Every position reachable from one stalk, with its value. Each cut moves the value by a computable amount, and choosing between them is arithmetic rather than search.

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 38\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.

Which numbers the strings reachEvery blue-red Hackenbush string of up to four edges, placed at its value. Short strings give integers, longer ones fill in halves and quarters, and the pattern continues — the reachable values are exactly the dyadic rationals, and nothing else.-2-1012121/2-1−1/2-21234edgesone more edge halves the gap — and every value is a fraction with a power of two underneath
Fig. 9 Stalks on the number line, which is the whole of what the reading gives. The positions of the marks are exact; everything about how to play them is elsewhere.

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.

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.

Where this goes next

011/2{0 | 1}021{0 | 2}-550{-5 | 5}1/43/41/2{1/4 | 3/4}13/25/4{1 | 3/2}the marked point is the value; the hollow one, where it differs, is the midpoint The simplicity rule When both players' options are numbers, the position is worth the simplest number strictly between them. Not the midpoint, not the average, and the difference between "simplest" and "middle" is the entire content of the rule. ↑{0 | {0 | 0}}> 0< 1/1024outcome L⇑{0 | {{0 | 0}, 0 | 0}}> 0< 1/1024outcome L↑∗{{0 | 0}, 0 | 0}‖ 0< 1/1024outcome N∗{0 | 0}‖ 0< 1/1024outcome N↓{{0 | 0} | 0}< 0< 1/1024outcome Rvaluecanonical formagainst 0against a thousandth↑ is positive and smaller than every positive number — which no real number is∗ is none of greater, smaller or equal — the order is partial, and that is the point Infinitesimals Some positions are positive — Left wins them whoever moves first — and smaller than every positive number, including a millionth and a millionth of that. They are the values that decide close games, and the smallest of them is a single move's worth of nothing. 0outcome P= 0whoever must move, loses10outcome L> 0Left wins, whoever starts-10outcome R< 0Right wins, whoever starts∗00outcome N‖ 0whoever moves first, winsblue edges are Left's moves, red are Right'sthree of the four are comparisons with zero; the fourth is not Who moves last The player who cannot move loses. That single convention generates the whole theory — and it produces four outcomes rather than three, because a position can be confused with zero rather than greater, smaller or equal to it.