Surreal Numbers and Hackenbush

Hackenbush is played on a graph attached to the ground. A move deletes one edge; everything no longer connected to the ground falls off. The player who cannot move loses.

• Green edges — either player may cut them → impartial, solved by Grundy numbers.
• Red/Blue edges — only Left cuts blue, only Right cuts red → partizan, solved by surreal numbers.

Green Hackenbush — the two principles

Colon principle. A branch hanging at a vertex may be replaced by a single stalk of length equal to that branch’s Grundy value.

For a tree:
$g(v)={⨁}_{c\text{child of}v}(g(c)+1).$

int hackenbush(int v, int p) {
    int res = 0;
    for (int c : adj[v]) if (c != p) res ^= hackenbush(c, v) + 1;
    return res;
}

Fusion principle. All vertices on a cycle may be fused into a single vertex, turning each cycle edge into a self-loop. A self-loop is a stalk of length 1 (value 1), and a cycle of odd length reduces to a single edge while an even cycle vanishes.

Together these reduce any green graph to a tree, and then to a single number.

Partizan Hackenbush and game values

With coloured edges the game is partizan, and Grundy numbers no longer apply. Instead each position has a value — a surreal number — measuring how many free moves one player has in reserve.

Position	Value
Nothing	$0$ (second player wins)
One blue edge	$+1$ (Left is one move ahead)
One red edge	$-1$
Blue on top of red	$+\frac{1}{2}$
Red on top of blue	$-\frac{1}{2}$
Blue, red, red	$+\frac{1}{4}$
A single green edge	$\ast$ (star — a Nim heap of size 1, not a number)

The sum of games has the sum of values, and:

$v>0$ → Left wins regardless of who starts; $v<0$ → Right wins; $v=0$ → the second player wins; $v\parallel 0$ (fuzzy, like $\ast$) → the first player wins.

Surreal numbers

Conway’s construction: a game is a pair $\{L\mid R\}$ of sets of simpler games.

$0=\{\mid \},1=\{0\mid \},-1=\{\mid 0\},\frac{1}{2}=\{0\mid 1\},\ast =\{0\mid 0\}.$

This single definition generates:

• all integers and dyadic rationals (at finite birthdays),
• all real numbers,
• infinite and infinitesimal numbers ($\omega$, $\frac{1}{\omega }$, $\epsilon$),
• non-numbers like $\ast$, $\uparrow$, $\downarrow$ — game values that are not comparable to 0.

The simplicity rule: $\{L\mid R\}$ equals the simplest number strictly between them — which is exactly the Stern-Brocot “simplest fraction in an interval” question.

Why any of this matters for contests

Directly, almost never. Indirectly, three transferable ideas:

1. Decomposition. A game splitting into independent parts is solved per part and combined — XOR for impartial, addition for partizan. Recognising independence is the key skill.
2. Value beyond win/lose. When the question is “who wins and by how much”, you need a number, not a boolean — the advantage DP is the practical version of this idea.
3. Fusion and reduction. Collapsing structure (cycles, branches) into a single equivalent value is the same instinct as condensation, bridge trees and virtual trees.

Named game values

Symbol	Definition	Meaning
$0$	$\{\mid \}$	second player wins
$\ast$	$\{0\mid 0\}$	first player wins (a Nim heap of 1)
$\ast n$	Nim heap of size $n$
$\uparrow$	$\{0\mid \ast \}$	infinitesimally positive
$\downarrow$	$\{\ast \mid 0\}$	infinitesimally negative
$\pm x$	$\{x\mid -x\}$	a “switch” — whoever moves takes it

Impartial games always have values of the form $\ast n$, which is precisely the Sprague-Grundy theorem restated in this language.

See also: Grundy Numbers · Combinatorial Games · Nim Variants