Nim: The Pile-Taking Game That XOR Turns Into Solved Mathematics

Put a few heaps of coins on a table. On your turn, take as many as you like — one, several, or a whole heap — but all from a single heap. Whoever grabs the last coin wins. It sounds like a game of nerve and luck. It isn't. In 1901 Charles Bouton proved Nim is completely solved, and the entire strategy fits in one bitwise operation.

The whole game is a list of numbers

There is no board and there are no pieces. The position is just an array of heap sizes, say [3, 4, 5]. A move subtracts from one entry. The game ends when every heap is zero.

function applyMove(heaps, heap, take){ heaps[heap] -= take; }
function isOver(heaps){ return heaps.every(h => h === 0); }

That's the easy part. The magic is deciding which move to make.

The nim-sum: XOR every heap together

Fold all the heap sizes with bitwise XOR and you get one number, the nim-sum:

function nimSum(heaps){
  return heaps.reduce((a, h) => a ^ h, 0);  // XOR fold
}
// [3,4,5] → 3 ^ 4 ^ 5 = 2

XOR is binary addition with the carries thrown away, so each bit of the nim-sum is 1 exactly when an odd number of heaps have that bit set. A nim-sum of zero means every binary column is balanced.

Bouton's theorem

Here is the whole game in one sentence: a position is a loss for the player about to move if and only if its nim-sum is zero.

The proof is a two-line invariant. From a balanced position (sum 0), any move touches one heap, flips some bits, and must unbalance a column — you always hand back a non-zero sum. From an unbalanced position (sum ≠ 0), there is always a move back to zero. So a player who keeps handing over zero can never be forced off it, and the final empty position — sum zero, no move — is the loss.

The winning move always zeroes the nim-sum

Turning the theorem into a move is three lines. When the nim-sum x is non-zero, look at each heap's target size h ^ x. The heap sharing x's highest set bit has that bit cleared, so h ^ x < h — you can legally shrink it:

function winningMove(heaps){
  const x = nimSum(heaps);
  if (x === 0) return null;                 // balanced → no winning move
  for (let i = 0; i < heaps.length; i++){
    const target = heaps[i] ^ x;            // where this heap must land
    if (target < heaps[i])                  // can only ever SHRINK a heap
      return { heap:i, take: heaps[i] - target };
  }
}

Why does it work? The new nim-sum is x ^ h ^ (h ^ x) = 0. You've rebalanced every column and handed your opponent a dead position.

Misère flips only at the very end

Play the variant where taking the last coin loses and the surprise is how little changes. You play the identical nim-sum strategy right up until at most one heap has more than one object. Only then do you switch goals: leave your opponent an odd number of single-object heaps, because a player facing an odd count of lone coins is forced to take the last one.

function bestMove(heaps, misere){
  const big  = heaps.filter(h => h > 1).length;
  const ones = heaps.filter(h => h === 1).length;
  if (misere && big <= 1){                     // the misère endgame — and ONLY here
    if (big === 1){
      const i = heaps.findIndex(h => h > 1);
      const target = ones % 2 === 0 ? 1 : 0;   // leave an ODD number of 1s
      return { heap:i, take: heaps[i] - target };
    }
    const i = heaps.findIndex(h => h === 1);
    return { heap:i, take:1 };
  }
  return winningMove(heaps) || playOn(heaps);  // otherwise: normal nim-sum theory
}

A provably perfect opponent in about ten lines — and a human who understands the trick beats it every time by moving first from a non-zero position and always handing back a zero.

Play against the nim-sum AI, watch the binary columns balance live, and copy the full engine here: https://dev48v.infy.uk/game/day55-nim.html