Nim Variants

Misère Nim

The player taking the last stone loses.

Play as in normal Nim, unless every heap has size 1 — then the first player wins iff the number of heaps is even.

bool misereWins(const vector<int>& a) {
    int S = 0, big = 0;
    for (int h : a) { S ^= h; if (h > 1) big++; }
    return big ? (S != 0) : (a.size() % 2 == 0);
}

Moore’s Nim${}_k$

A move may remove stones from up to $k$ heaps (at least one).

Losing iff, writing all heap sizes in binary, every bit column sums to $0\mathrm{mod}(k+1)$.

Ordinary Nim is $k=1$, where “sum $\equiv 0\mathrm{mod}2$” is exactly XOR $=0$.

bool mooreLoses(const vector<int>& a, int k) {
    for (int b = 0; b < 30; b++) {
        int s = 0;
        for (int h : a) s += (h >> b) & 1;
        if (s % (k + 1)) return false;
    }
    return true;
}

Staircase Nim

Coins sit on stairs $0,1,\dots ,n$. A move slides any number of coins from step $i$ to step $i-1$; coins reaching step 0 are out of play.

Equivalent to Nim on the odd-indexed steps — the losing condition is ${⨁}_{i\text{ odd}}{c}_i=0$.

Why: moves from odd to even steps behave as Nim moves; a move from an even to an odd step can always be mirrored by the opponent (moving the same coins one step further down), so even steps contribute nothing.

This reduction covers a whole family of “push tokens toward the exit” games — recognising it is more valuable than the formula itself.

Wythoff’s game

Two heaps. A move removes any positive number from one heap, or the same number from both.

Losing positions are $(\lfloor k\varphi \rfloor ,\lfloor k{\varphi }^2\rfloor )$ for $k=0,1,2,\dots$, with $\varphi =\frac{1+\sqrt{5}}{2}$.

$(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),\dots$

bool wythoffLoses(long long a, long long b) {
    if (a > b) swap(a, b);
    long long k = b - a;
    return a == (long long)(k * (1.0L + sqrtl(5.0L)) / 2);
}

Watch the precision for large values — use long double and verify $\pm 1$ around the computed value.

The losing pairs are exactly the Beatty sequences of $\varphi$ and ${\varphi }^2$, which partition the positive integers — a striking connection between game theory and the golden ratio.

Subtraction games

Remove $s\in S$ stones from a heap.

$S$	Grundy value
$\{1,\dots ,m\}$	$a\mathrm{mod}(m+1)$
$\{1,2\}$	$a\mathrm{mod}3$
$\{1,3,4\}$	period 7: $0,1,0,1,2,3,2$
$\{2,3\}$	period 5
any finite $S$	eventually periodic (a theorem)
all squares	irregular, no known formula
all primes	irregular

Because the sequence is eventually periodic for finite $S$, the method is: compute the first few hundred Grundy values, detect the period, and extrapolate.

Games that split

Game	Move
Kayles	remove 1 or 2 adjacent pins from a row → splits it
Dawson’s chess	equivalent to a subtraction/splitting game
Lasker’s Nim	remove any number, or split a heap in two
Cram / Domineering	place a domino (partizan in Domineering)
Green Hackenbush	cut an edge; the tree splits

For splitting games, the reachable set includes XORs of the parts:

for (int i = 0; i + 1 < n; i++) reachable.insert(g[i] ^ g[n - 2 - i]);

Kayles has Grundy period 12 (after an initial segment); Dawson’s chess has period 34. Both were found exactly this way.

Green Hackenbush — the colon principle

For a tree rooted at the ground, edges are cut and everything disconnected from the ground falls off.

Colon principle: a branch at a vertex may be replaced by a single stalk whose length is that branch’s Grundy value; the value at a vertex is the XOR of $(g(\text{child branch})+1)$ over its children.

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

Loops (in general Hackenbush) can be fused into a single vertex, converting any green graph into a tree — the “fusion principle”.

The general approach

For an unfamiliar variant:

1. Is it impartial? If not, minimax.
2. Does it decompose? Compute per-component Grundy values and XOR.
3. Brute-force small cases and look for a pattern.
4. Check OEIS with the first 10-15 Grundy values.
5. If the pattern is periodic, verify the period over a longer range before trusting it.

See also: Nim · Grundy Numbers · Hackenbush