Status & Theory · Hackenbush Lab
An honest account of the combinatorial game theory behind Hackenbush Lab: the parts that are exact and tested, the parts that are heuristic or approximate, and the parts that are genuinely out of reach. The book to read alongside it is Winning Ways for Your Mathematical Plays (Berlekamp, Conway & Guy).
This is a practical tool for small and medium Red-Blue-Green Hackenbush positions, not a complete combinatorial-game engine. It computes exact answers within a budget by recursively unfolding game trees. That recursion is exponential in the worst case: green edges (playable by either side) and stable “no-fall” edges multiply the branching, and around a dozen live edges a single tangled component can already become slow — or, on adversarial inputs, take effectively forever. The heaviest curated positions (the Boss tier) solve off the main thread in a Web Worker, behind a Solve button with a live state counter and a Cancel button — but every other analysis, including each edit in Create and each move in Play, still runs synchronously on the main thread, so a hard position you build yourself can still freeze the page. Finite values are reduced to canonical form (domination plus reversible-option bypass), so what is displayed is the game’s simplest name; some theoretical refinements (deep transfinite arithmetic, a full thermal solver, misère quotients) remain deliberately not implemented. The sections below say exactly where the lines are.
The clearest visual introduction to this whole world is Owen Maitzen’s HACKENBUSH video. It walks from cutting colored edges all the way up to the surreal numbers, and it is the best way to build intuition before poking at the lab.
Here is how the ideas the video shows line up with what this engine actually computes:
| In the video | In this engine |
|---|---|
| Blue-Red Hackenbush; who wins a position | ✓ fully — and it adds Green (impartial) edges the video doesn’t cover |
| Giving a position a numeric value | ✓ exact dyadic / surreal value for cold positions |
| The “simplest number” rule & the number tree; dyadic fractions (½, ¾…) | ✓ with a day-by-day construction path |
| Adding two positions together | ✓ disjunctive sum + component decomposition |
| An infinite blue stalk = ω | ✓ for the infinite shapes it recognizes (ω, ω±n, ω·n, ω², grass) |
| That any infinite Hackenbush position yields a surreal number (⅓ from an infinite zig-zag, ε, …) | × not general. The engine pattern-matches a fixed family of infinite shapes from edge topology; it does not evaluate an arbitrary infinite Blue-Red path to its exact surreal value |
So the engine is a faithful calculator for the finite story the video tells (and adds impartial Green/Nim on top), but the video’s grand finale — that every surreal number falls out of infinite Hackenbush — is exactly the part this engine only approximates, for a handful of recognized patterns.
Hackenbush is played on a graph of colored edges standing on the ground (a baseline). On your turn you cut one edge of a color you control; any edges left disconnected from the ground then fall away.
The player who cannot move loses (normal play). The whole point of the theory is to assign each position a value that says who wins, by how much, and how the position behaves when added to others.
Every position is read as a partizan game G = { Blue options | Red options } and analyzed recursively. The concepts below are the ones the engine actually computes; each is annotated with where it sits in the literature.
Positions are compared with Conway’s order relations (G ≥ H defined recursively), which yields the four outcome classes (Left wins / Right wins / first player wins / second player wins). Winning Ways, Ch. 1–2; On Numbers and Games, Conway.
When a position is a genuine number — every Blue option strictly below every Red option, and all options themselves numbers — the engine extracts the exact dyadic/surreal value via the simplicity (“simplest number”) rule, and can show the day-by-day construction and birthday. Crucially, it does not pretend every position is a number: hot and fuzzy positions are shown as their raw short-game forms instead. Winning Ways, Ch. 2 (“Whose Game?”).
Independent grounded subgraphs are solved separately and combined as a disjunctive sum, which keeps many real positions tractable. This decomposition is transfinite-aware (it carries infinite components through the sum). Winning Ways, Ch. 2.
Green “bamboo” stalks are impartial: the engine computes their nim-values with the mex rule and recognizes *n symbolically. Winning Ways, Ch. 3 (“Nim”); Sprague–Grundy.
The named infinitesimals that show up next to numbers are recognized for display: star *, up/down ↑ ↓, ↑*, double-up/down ⇑ ⇓, and tiny(n)/miny(n). Winning Ways, Ch. 3–4 (“Uppitiness”).
Hot positions of the form {a | b} with a > b are detected as switches; for the cases it recognizes directly the engine reports the mean value and temperature and draws a thermograph (a frozen vertical wall for cold numbers, a V for switches). This is the engine’s weakest area — see the partial list. Winning Ways, Ch. 6 (“Heating, Cooling…”).
Edges flagged infinite stand for unbounded stalks. From the edge topology the engine pattern-matches ordinal values ω, -ω, ω±n, ω·n, ω², and combines parallel infinite green “grass” into ω*[n] by a stalk-count rule. This is heuristic pattern-matching, not general ordinal arithmetic — it is deliberately guarded by negative regression tests so it does not over-fire (e.g. two bridged ω’s must not collapse to plain ω). ONAG (ordinals as games); transfinite Hackenbush.
Edges flagged loop invoke loopy values: on, off, over, under, dud, with real arithmetic for sums, comparison, outcome and display. This covers the five named values and their shifts, not the whole of Conway’s loopy theory. Winning Ways, Ch. 11 (“Survival in the Lost World”).
To avoid re-solving isomorphic subpositions, the memo keys positions by a Weisfeiler–Lehman color-refinement hash (~17× state reduction on symmetric positions). Note: this de-duplicates graph-isomorphic positions; it is not the same as reducing a game to canonical form by domination and reversibility (see below).
These behave correctly end-to-end on the tested range:
*n recognized.{a|b}, a>b detected; mean & temperature reported.*, ↑, ↓, ↑*, ⇑, ⇓, tiny(n), miny(n) in display.loop attribute.Also solid (tooling rather than theory): auto-play / AI vs AI, multi-edge curving, floating-vertex cues, component thumbnails, light/dark theme, and shareable-position URLs.
These work in common cases but have documented gaps or fall back to weaker answers:
approximate; move-by-move scoring is suppressed.ω²·n, ω²+ω are not derived.{X|X}-style switches with temperature 0 — no clean V-shape thermograph. This is the engine’s thinnest area.{on|over} falls back to dominance).{ * | * } now print as the 0 they always were. Verified by an invariant run (no outcome and no search size changed anywhere), by fuzzing G + (−G) = 0, and by over-simplification guards ({1|1} stays {1|1}). Loopy and transfinite games are left untouched — the theory does not cover them — and are badged red Heuristic, since they were pattern-matched rather than derived in the first place. Measured across all 98 loadable positions the badges now come out 9 Proved, 78 Exact, 11 Heuristic and zero Not simplified: the amber level survives only as a fail-open signal, for the case where the simplifier hits its iteration guard and returns an unreduced form rather than a wrong one.↑↑ from ↑+↑ beyond pattern matching.loop edges.Three honest constraints, in order of how often they bite:
approximate result) rather than a false clean value.The design choice throughout is honesty over false precision: when the engine cannot prove a clean value it says so — showing a raw short-game form, an approximate tag, or a fuzzy outcome — instead of guessing a tidy number. That is also why it is best described as a workbench for small and medium exact studies, not a general-purpose Hackenbush solver.
An in-app regression harness (the Run Self-Test button) currently runs 88 cases across 14 categories, asserting on the analyzer’s computed value fields. Coverage is uneven — deliberately heaviest where bugs have bitten, lightest exactly where the theory is weakest:
| Category | Cases | What it guards |
|---|---|---|
| Gallery | 18 | curated named positions keep their solved values |
| Loopy | 14 | on/off/over/under/dud arithmetic; incl. 4 fixes for ω being dropped in mixed sums |
| Numbers | 9 | surreal/dyadic extraction |
| SignExpansion | 7 | L/R sign strings |
| Thermograph | 7 | wall/temperature plotting |
| Structural | 6 | normalization & pruning despite visual defects |
| Transfinite | 5 | ω family pattern matching |
| Nimbers · AtomicWeight · ShareableURL | 4 each | mex values · uptimal weights · URL round-trips |
| Regression · Construction | 3 each | negative guards on the transfinite matcher · day-by-day paths |
| Hot · Composites | 2 each | switches/temperature & basic sums — the least-guarded, and the weakest, areas |
Two caveats worth stating. These in-browser checks are separate from the npm test suite, which adds 137 Node tests (165 with HB_SLOW=1, which re-solves every curated position instead of the cheap subset) covering the engine primitives, canonical form, the Fusion Principle, misère play, and locking every curated position's winner against a golden file. Most importantly, Hot and Composites have only two cases each, and one Hot check passes on a loose condition — so the thermal/switch behavior is the part you should trust least.
And it did not survive checking. Measuring every position in the app found that not one has a positive temperature: all seven “Hot Games”, and 3,398 randomly generated mixed boards, come out at temperature 0. Several positions had been labelled “±1”, “switch” or “hot” purely because their value printed with braces — but { X | X } is tepid, not a switch, and the partisan options here keep resolving to infinitesimals. Those labels have been corrected to state the winner instead, and a test now refuses any entry that advertises heat the solver cannot find. Whether Blue-Red-Green Hackenbush can be hot at these sizes is left open; what is certain is that nothing in this library is.