Nim, Grundy Numbers & Winning Positions
In short: in Nim, two players alternate taking any positive number of stones from one heap, and whoever takes the last stone wins. There's no searching needed to know who's winning: XOR every heap size together. If the result is 0, the player about to move is already losing against perfect play. If it's anything else, there's always a move — take from the heap whose own bit pattern can absorb the difference — that brings the XOR back to 0 and hands the loss to the opponent instead. Grundy numbers extend this idea past Nim to any "take-away" game: the Grundy number of a position is the mex (minimum excludant — the smallest non-negative integer not reachable in one move) of the Grundy numbers of everywhere one move can reach, and a position is a loss for the mover exactly when its Grundy number is 0.
Why XOR, and why zero loses
Each bit column is its own tiny vote. XOR of a column is 1 exactly when an odd number of heaps have a 1 there.
Column b2: 0, 1, 1 — two 1s, an even number, so XOR is 0. 4 by 3 table. 10 of 12 cells filled.
A losing position (XOR already 0) stays losing no matter what the mover does, because changing one heap always flips at least one bit somewhere, which can never bring an all-even column count back to all-even everywhere at once:
Finding the winning move
A winning position (XOR nonzero) always has at least one heap whose bits can absorb the difference — shrinking that one heap clears the whole XOR row:
def nim_winning_move(heaps):
total = 0
for h in heaps:
total ^= h
if total == 0:
return None
for i, h in enumerate(heaps):
target = h ^ total
if target < h:
return (i, target)
return None
print([nim_winning_move([3, 4, 5]), nim_winning_move([1, 1])])Check the fix actually works by recomputing the XOR after the move — it should land on 0, handing the losing position to the opponent:
This prints 1 instead of 0. Make the loop cover every heap, not heaps[1:].
Grundy numbers: Nim's idea, generalised
A single Nim heap of size n is trivially its own Grundy number — any move
reaches any smaller size, so mex of {0, 1, ..., n-1} is n. The real
value of the idea shows up on a different game: take 1, 2, or 3 stones from
one heap (not plain Nim's "any amount"):
The pattern repeats every 4: 0,1,2,3,0,1,2,3,0. Every multiple of 4 is a
loss for the mover — exactly what you'd find by hand-analysing this
well-known game, just arrived at by the same mechanical mex rule that works
on any take-away game, not only this one.
Quick practice
print(3 ^ 4 ^ 5, 1 ^ 1, 2 ^ 3 ^ 1)def mex(values):
result = 0
while result in values:
result += 1
return result
print(mex({0, 1, 3}), mex({1, 2, 3}), mex(set()))🎯 Your turn
Build nim_winning_move(heaps). XOR every heap together. If the result is
0, return None — the position is already a loss for whoever moves next.
Otherwise find a heap h where h XOR total is smaller than h, and
return {"heap_index": ..., "remove": ..., "new_size": ...} for the move
that shrinks it there.
nim_winning_move([3, 4, 5])→{"heap_index": 0, "remove": 2, "new_size": 1}.nim_winning_move([1, 1])→None.
Hint: for each heap in turn, compute h ^ total; the first one that's
smaller than h names both the heap and its new size.
Press ▶ Run, try the Live App chips, then ✓ Check.