Nim Game Theory: Winning With XOR

Learn to spot winning and losing Nim positions instantly using XOR, find the one move that forces a win, avoid the most common traps like misère endgames, and see how the same idea powers Sprague–Grundy analysis for many impartial games.

Nim feels like luck when you are guessing which heap to shrink. It stops feeling random the moment you treat each heap size as bits and combine them with exclusive OR (XOR). That one operation splits the entire game into positions that are dead cold and positions that are hot with a forced win. The punchline is simple and weird. If the XOR of all heap sizes is zero, you are losing with perfect play. If it is nonzero, you can always move to make it zero.

Why Nim looks random

Players usually notice patterns that do not generalize, like mirroring moves or always taking the most. Nim punishes that. The game state is not about totals or symmetry. It is about which bit positions have odd parity across the heaps.

A useful mental model is this.

• Cold position means every move hands your opponent a winning reply.
• Hot position means at least one move hands your opponent a cold position.
• The switch between cold and hot is controlled by the XOR of heap sizes, often called the nim-sum.

See how heap sizes line up in binary and where the nim-sum lights up.

When the highlighted nim-sum is all zeros, every bit column has even parity. Any move you make flips some columns from even to odd, giving your opponent a nonzero nim-sum to work with. When the nim-sum is nonzero, at least one highest bit is odd, and that is the handle you can grab to force the game back to zero.

Parity lens
Think in bit columns. Nim is a parity game disguised as a pile-taking game.

Bouton’s theorem, stated plainly

A Nim position is losing under normal play if and only if the XOR of all heap sizes is zero. From every winning position, there exists a move to a losing position, meaning a move that makes the XOR zero.

That is Bouton’s theorem. The reason it is so powerful is that it gives you both classification and a constructive strategy.

Look at how moves from one sample position branch into resulting nim-sums.

Why zero is losing

If the nim-sum is zero, every bit column has an even number of 1s across heaps. When you reduce one heap, you change that heap’s binary representation. At the highest bit where it changes, you flip the parity of that column from even to odd. That guarantees the new nim-sum is nonzero.

Why nonzero can reach zero

If the nim-sum is nonzero, let $k$ be the highest bit position where it has a 1. In that $k$ column, there are an odd number of heaps with a 1. Pick one of those heaps. You can reduce it so that, after the reduction, its bits match the nim-sum pattern needed to make every column even again. That produces nim-sum zero in one move.

Finding the winning move with XOR

Computing the nim-sum is easy, but the real skill is turning it into the exact heap reduction quickly and reliably. The algorithm is deterministic.

• Compute $S=a_1\oplus a_2\oplus\cdots\oplus a_n$.
• If $S=0$, there is no winning move against perfect play.
• If $S\neq0$, find the highest 1-bit in $S$ and choose a heap that also has that bit set.
• Reduce that heap from $a$ to $a' = a\oplus S$. This guarantees $a'<a$ and the new nim-sum becomes zero.

Explore how changing heaps changes the binary view and the suggested reduction.

A quick sanity check helps. You are only allowed to reduce a heap, never increase it. The formula $a' = a\oplus S$ looks like magic, but it only works when you pick a heap with the highest 1-bit of $S$ set. That condition makes $a'$ strictly smaller than $a$, so the move is legal.

One heap changes
A winning Nim move modifies exactly one heap. The rest stay unchanged, and the nim-sum becomes zero.

Misconceptions that lose games

Many losses come from using rules that work in special cases and then failing quietly outside them.

Before you trust a heuristic, it should survive tiny counterexamples. The fastest way to build intuition is to see how small positions break common advice.

Normal play vs misère

In normal play, taking the last object wins. In misère play, taking the last object loses. That single change makes endgames with heaps of size 1 behave differently, and it is where many people apply nim-sum and get burned.

Take the most

Greedy play often hands over a zero nim-sum. If you take a lot from a heap without checking bits, you might accidentally give your opponent the exact cold position they want.

Symmetry traps

Mirroring works only when the game is structurally symmetric under the legal moves you can maintain. XOR symmetry is different. Two equal heaps do cancel in nim-sum, but that does not mean copying moves will preserve a winning structure when there are three or more heaps or mixed sizes.

Beyond basic Nim

Nim is the gateway example because its analysis is clean. The bigger idea is that many impartial games can be translated into Nim heaps whose sizes are not physical objects but computed values.

Compare how strategy changes across common variants and related games.

Misère Nim rule change

For misère Nim, nim-sum still guides play until the endgame where all heaps are size 1. In that all-ones phase, the winning condition flips. You want to leave an odd number of 1-heaps to your opponent, because they are forced to take the last one.

Many impartial games are Nim underneath

The Sprague–Grundy theorem says every impartial game position under normal play is equivalent to a Nim heap of some size called its Grundy number. Disjunctive sums of games combine by XOR of Grundy numbers, just like heap sizes in Nim. Nim is not just a game. It is the arithmetic of impartial games.

Same math
When a game is impartial and uses normal play, the combination rule is XOR, even if nothing looks like heaps.

Work positions faster in your head

Speed comes from reducing friction, not from memorizing tons of cases. You want nim-sum quickly, then the highest 1-bit, then the one heap to adjust.

A few practical shortcuts:

• Convert only as much to binary as you need. Highest differing bit often settles the move.
• XOR in chunks. Pair equal numbers since $x\oplus x=0$.
• Track parity per bit position rather than full binary strings when heaps are small.
• When you have three heaps, often compute $a\oplus b$ first, then XOR the result with $c$.

Practice quick XOR facts and small losing positions until they feel automatic.

The goal is not mental math perfection. It is confidence that you can spot $S=0$ positions and, when $S\neq0$, identify one heap that must shrink.

Where to go next

Pick a real impartial game you like and try to turn positions into Grundy numbers. Start small. List the legal moves from each position, compute the mex, and watch Nim heaps appear where you did not expect them. Once you can do that for a toy game, Nim stops being a puzzle trick and becomes a reasoning tool you can reuse anywhere you see independent subgames that add together.