iii. Hackenbush and Partizan Games

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): impartial, solved by Grundy numbers.
• Blue / Red edges (only Left cuts blue, only Right cuts red): partizan, solved by game values (surreal numbers).

Green Hackenbush

Colon principle. A branch hanging at a vertex may be replaced by a single stalk whose length is the branch’s Grundy value. For a tree rooted at the ground:
$g(v)={⨁}_{c\text{ child of }v}(g(c)+1).$

Fusion principle (Winning Ways, ch. 7). All vertices of a cycle may be fused into one vertex, each cycle edge becoming a self-loop; a loop is worth a stalk of length 1, so an odd cycle reduces to a single edge and an even cycle vanishes. Together the principles reduce any green graph to a tree: contract every 2-edge-connected component (bridges stay as tree edges; the ground is one vertex), a component with $E$ internal edges contributes $E\mathrm{mod}2$ at its vertex.

int greenTree(int v, int p, const vector<vector<int>>& adj) {      // rooted tree; use iteratively for deep trees
    int res = 0;
    for (int c : adj[v]) if (c != p) res ^= greenTree(c, v, adj) + 1;
    return res;
}
 
// Any green graph: vertices 0..n-1, vertex 0 = the ground (merge all ground vertices into it first). O(V + E).
int greenGraph(int n, const vector<pair<int, int>>& edges) {
    int m = sz(edges); vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; i++) { auto [u, v] = edges[i]; adj[u].push_back({v, i}); adj[v].push_back({u, i}); }
    vector<int> tin(n, -1), low(n), comp(n, -1); vector<char> bridge(m, 0); int timer = 0;
    auto dfs = [&](auto&& self, int v, int pe) -> void {           // bridges (loops and multi-edges are never bridges)
        tin[v] = low[v] = timer++;
        for (auto [u, id] : adj[v]) {
            if (id == pe) continue;
            if (tin[u] == -1) { self(self, u, id); low[v] = min(low[v], low[u]); if (low[u] > tin[v]) bridge[id] = 1; }
            else low[v] = min(low[v], tin[u]);
        }
    };
    dfs(dfs, 0, -1);                                                // parts not connected to the ground never matter
    int C = 0;
    for (int s = 0; s < n; s++) if (tin[s] != -1 && comp[s] == -1) {   // 2-edge-connected components
        vector<int> st{s}; comp[s] = C;
        while (!st.empty()) { int v = st.back(); st.pop_back(); for (auto [u, id] : adj[v]) if (!bridge[id] && comp[u] == -1) comp[u] = C, st.push_back(u); }
        C++;
    }
    vector<int> loops(C, 0); vector<vector<int>> tree(C);
    for (int i = 0; i < m; i++) {
        auto [u, v] = edges[i]; if (tin[u] == -1) continue;
        if (bridge[i]) tree[comp[u]].push_back(comp[v]), tree[comp[v]].push_back(comp[u]);
        else loops[comp[u]] ^= 1;
    }
    auto val = [&](auto&& self, int c, int p) -> int {
        int r = loops[c];
        for (int d : tree[c]) if (d != p) r ^= self(self, d, c) + 1;
        return r;
    };
    return val(val, comp[0], -1);
}

Proof: stalks, the colon principle and the tree formula

Stalks. Cutting edge $i$ of a stalk of $n$ edges leaves a stalk of $i-1$ edges, so the options have values $0,\dots ,n-1$ by induction and the stalk has value $n$: it is the Nim heap $\ast n$.

Colon principle. Let $e:G$ denote an edge from the attachment point with $G$ hanging on its top end. If $G\equiv H$ (equal Grundy values), then $e:G\equiv e:H$: in $e:G+e:H$ the second player answers a cut of either $e$ by cutting the other $e$ (leaving $0$), and answers moves inside $G$ or $H$ with the second-player strategy of $G+H$; the first player eventually runs out of moves. Branches at a vertex are disjoint games (cutting in one never disconnects another), so the vertex’s value is the XOR of its branch values.

Trees. By induction the subtree hanging at child $c$ is equivalent to a stalk of length $g(c)$; with the edge to $c$ underneath it becomes a stalk of length $g(c)+1$, worth $g(c)+1$; XOR over the children. The fusion principle is quoted from Winning Ways (its proof is a longer strategy argument); greenGraph was checked against exhaustive search over all edge subsets on random graphs with up to 9 edges, including loops, parallel edges and pieces not attached to the ground.

Partizan games and game values

With coloured edges Grundy numbers no longer apply. Each position has a value, a measure of how many free moves one player has in reserve; values of sums add.

Position (edges listed from the ground up)	Value
nothing	$0$ (second player wins)
one blue edge	$+1$ (Left is one move ahead)
one red edge	$-1$
blue, then red on top	$+\frac{1}{2}$
red, then blue on top	$-\frac{1}{2}$
blue, red, red	$+\frac{1}{4}$
a single green edge	$\ast$ (a Nim heap of size 1, not a number)
stalk in general (Berlekamp’s rule)	$\pm k$ for the first run of $k$ edges of one colour, then $\pm 2^{-1},\pm 2^{-2},\dots$ for the following edges (blue $+$, red $-$)

Outcome from the value: $v>0$: Left wins whoever starts; $v<0$: Right wins; $v=0$: the second player wins; $v\parallel 0$ (fuzzy, like $\ast$): the first player wins. Blue-Red Hackenbush positions always have number values.

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 (finite birthdays), all real numbers, infinite and infinitesimal numbers ($\omega$, $\frac{1}{\omega }$, $\epsilon$), and non-numbers like $\ast$, $\uparrow$, $\downarrow$ that are incomparable with 0.

Simplicity rule. If every left option is a number less than every right option, $\{L\mid R\}$ is the simplest number strictly between $\max L$ and $\min R$: the integer of least absolute value if one fits, otherwise the dyadic rational with the smallest denominator (unique). This is the same question as the Stern–Brocot “simplest fraction in an interval”, restricted to dyadics.

Symbol	Definition	Meaning
$0$	$\{\mid \}$	second player wins
$\ast$	$\{0\mid 0\}$	first player wins (Nim heap of size 1)
$\ast n$	Nim heap of size $n$	impartial games always have values $\ast n$: Sprague–Grundy in this language
$\uparrow$	$\{0\mid \ast \}$	positive but smaller than every positive number
$\downarrow$	$\{\ast \mid 0\}$	its negative
$\pm x$	$\{x\mid -x\}$	a “switch”: whoever moves first takes it (hot game)

Typical number-valued games: Blue-Red Hackenbush, Cutcake, and most Toads and Frogs positions (toads facing right, frogs facing left, on a strip of squares; each hops or slides one square in its facing direction, or jumps over exactly one opposing piece into an empty square) — though Toads and Frogs is also the standard example of a partizan game whose value is not always a number: once toads and frogs are adjacent and can jump each other, some positions evaluate to switches ($\pm x$) or other non-numbers, which is exactly why it is the usual teaching example for “numbers aren’t everything.”

Beyond numbers: temperature and atomic weight (cited, not derived). For games whose value is a genuinely hot position ($\max L\ge \min R$, i.e. not a number), Winning Ways’ thermography assigns a temperature $t(G)$ — informally, the amount both players are willing to “pay” to move — via a cooling operator $G_t=G-t$ applied until the game becomes stable (a number plus at most an infinitesimal); the mast value at that point is the game’s mean value, and optimal play in a sum of hot games follows the thermostatic strategy: play in the component with the highest temperature first. Separately, for infinitesimally-close-to-zero games (like many all-small Hackenbush/Nim-like positions), the atomic weight (a generalization of the $\uparrow /\downarrow$ ordering used in the table above) orders infinitesimals well enough to decide long sums of them. Both theories are genuinely deep (full chapters of Winning Ways vol. 1 and On Numbers and Games) and almost never needed directly in a contest, where positions are normally arranged to be clean impartial sums or exact Blue-Red Hackenbush — but the vocabulary is worth recognising if a problem’s flavour text is quoting CGT literature.

struct Dyadic {                                     // value = num / 2^k, normalized: k == 0 or num odd
    ll num = 0; int k = 0;
    Dyadic(ll n = 0, int kk = 0) : num(n), k(kk) { while (k > 0 && num % 2 == 0) num /= 2, k--; }
    ll floorAt(int level) const { return level >= k ? num * (1LL << (level - k)) : num >> (k - level); }   // floor(v * 2^level)
    Dyadic operator-() const { return Dyadic(-num, k); }
    friend Dyadic operator+(const Dyadic& a, const Dyadic& b) {
        int k = max(a.k, b.k);
        return Dyadic(a.num * (1LL << (k - a.k)) + b.num * (1LL << (k - b.k)), k);
    }
    friend Dyadic operator-(const Dyadic& a, const Dyadic& b) { return a + (-b); }
    friend strong_ordering operator<=>(const Dyadic& a, const Dyadic& b) {
        int k = max(a.k, b.k);
        return (i128)a.num * ((i128)1 << (k - a.k)) <=> (i128)b.num * ((i128)1 << (k - b.k));
    }
    friend bool operator==(const Dyadic& a, const Dyadic& b) { return a.num == b.num && a.k == b.k; }
};
 
Dyadic simplestBetween(optional<Dyadic> lo, optional<Dyadic> hi) {   // nullopt = unbounded; needs lo < hi
    bool below = !lo || *lo < Dyadic(0), above = !hi || *hi > Dyadic(0);
    if (below && above) return Dyadic(0);
    if (!below) { Dyadic c(lo->floorAt(0) + 1); if (!hi || c < *hi) return c; }     // lo >= 0: smallest integer > lo
    else { Dyadic c(-((-*hi).floorAt(0) + 1)); if (!lo || c > *lo) return c; }       // hi <= 0: largest integer < hi
    for (int level = 1;; level++) { Dyadic c(lo->floorAt(level) + 1, level); if (c < *hi) return c; }
}
 
optional<Dyadic> numberGame(const vector<Dyadic>& L, const vector<Dyadic>& R) {   // value of {L | R} if it is a number
    optional<Dyadic> lo, hi;
    for (auto& x : L) if (!lo || x > *lo) lo = x;
    for (auto& x : R) if (!hi || x < *hi) hi = x;
    if (lo && hi && !(*lo < *hi)) return nullopt;  // max L >= min R: a hot game, not a number
    return simplestBetween(lo, hi);
}
 
Dyadic stalkValue(const string& s) {                // Blue-Red stalk from the ground up, 'B' / 'R' (Berlekamp's rule)
    Dyadic v(0); int i = 0, n = sz(s);
    while (i < n && s[i] == s[0]) v = v + Dyadic(s[0] == 'B' ? 1 : -1), i++;
    for (int j = 1; i < n; i++, j++) v = v + Dyadic(s[i] == 'B' ? 1 : -1, j);
    return v;
}

Complexity: $O(1)$ arithmetic (values must fit $|\text{num}|<2^{62}$), $O(\log )$ per simplestBetween.

Proof: simplestBetween, and Berlekamp's rule for stalks

Simplest number. If $0$ lies strictly inside, it is the simplest (birthday 0). If the interval is in the positives, integers are simpler than non-integers and smaller positive integers are simpler, so the answer is the least integer $>lo$ if it is $<hi$. Otherwise no integer lies inside, and among the dyadics in the interval the one with the smallest denominator $2^{\ell }$ is unique: two such numbers would have a number of denominator $2^{\ell -1}$ between them. The loop tries $\ell =1,2,\dots$ and takes the least multiple of $2^{-\ell }$ greater than $lo$; the first $\ell$ for which it is below $hi$ is the answer. Negative intervals are symmetric. Checked against an enumeration of all dyadics by birthday.

Stalks. Induction on the length; write $v_i$ for the claimed value of the bottom $i$ edges. A monochromatic stalk of $k$ blue edges is $\{k-1\mid \}=k$ (red symmetric). Otherwise the options of the full stalk are the $v_{i-1}$ over cut edges $i$ (Left’s for blue edges, Right’s for red), which are numbers by induction. For a tail edge of weight $\pm 2^{-j}$ all later weights sum to less than $2^{-j}$ in absolute value, so cutting a blue edge gives a value below $v_n$ and cutting a red edge a value above $v_n$; run edges satisfy the same (the run’s partial sums are integers at distance $\ge 1$ inside, while the tail moves $v_n$ by less than 1). Say the top edge $n$ is blue with weight $2^{-J}$: Left’s best option is $v_{n-1}=v_n-2^{-J}$; the topmost red edge $i^{\ast }$ is followed only by blue edges with weights $2^{-j_{i^{\ast }}-1},\dots ,2^{-J}$, which sum to $2^{-j_{i^{\ast }}}-2^{-J}$, so Right’s best option is $v_{i^{\ast }-1}=v_n+2^{-J}$; all other options are farther away by the same tail inequality. Hence the stalk is $\{v_n-2^{-J}\mid v_n+2^{-J}\}$, and $v_n$, an odd multiple of $2^{-J}$, is the only number of denominator at most $2^J$ in that open interval: by the simplicity rule the value is $v_n$. A red top edge is symmetric. stalkValue was checked against the recursive definition (options evaluated with numberGame) for all stalks of up to 12 edges, and the table entries are such stalks.

Why this matters for contests

Directly, rarely. Indirectly, three transferable ideas: decomposition (a game splitting into independent parts is solved per part and combined: XOR for impartial games, addition for partizan values; recognising independence is the key skill), value beyond win/lose (when the question is “who wins and by how much”, compute a number: the advantage DP is the practical version), and fusion / reduction (collapsing cycles and branches into one equivalent value, the same instinct as condensation, bridge trees and virtual trees).

Related notes

• Sprague–Grundy
• Bridges and Biconnectivity
• Big Integers and Fractions (Stern–Brocot)