Introduction

Nim is about as simple as a game gets. Lay out a few heaps of coins. Players take turns; on your turn you pick one heap and remove as many coins as you like from it — at least one. Whoever takes the last coin wins.

That's the whole game. No board, no dice, no hidden information. And yet, if you sit a beginner down against someone who knows the trick, the beginner will lose every single time — the expert can announce the winner before a coin is touched.

The reason is not cleverness or memory. It is a single arithmetic operation hiding inside the pile sizes. Nim is one of the rare games that mathematics has not just studied but completely solved: there is a known formula that tells you the perfect move in every position.

Play It

Here are three heaps of coins. On your turn, click a heap to remove coins from it; then the engine moves. The panel shows each heap size in binary and the XOR (the bitwise digital sum) of the column counts.

<p class="hint">Three heaps of coins. Click a coin to remove it and every coin <b>above</b> it in that heap, then press <b>Take &amp; let engine move</b>. The engine XORs the heap sizes and plays perfectly — it always hands you a position whose XOR is <b>0</b>, the losing position. Whoever takes the last coin wins.</p>
<div id="heaps" class="heaps"></div>
<div class="panel">
  <div class="panel-title">Heap sizes in binary &amp; their XOR (digital sum)</div>
  <div id="bits" class="bits"></div>
</div>
<div class="status" id="status">Your move: take some coins from one heap.</div>
<div class="btns">
  <button id="go" type="button">Take &amp; let engine move</button>
  <button id="reset" type="button" class="ghost">New game</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.heaps { display: flex; gap: 1.6rem; align-items: flex-end; min-height: 150px; margin: .4rem 0 .6rem; }
.heap { display: flex; flex-direction: column-reverse; gap: 4px; align-items: center; }
.heap-label { margin-top: .4rem; font: 600 13px system-ui; color: #1d3557; }
.coin { width: 34px; height: 14px; border-radius: 7px; background: #f1c40f; border: 1px solid #c79f0c; cursor: pointer; transition: transform .08s; }
.coin:hover, .coin.hl { transform: translateX(4px); background: #f7d33a; }
.coin.sel { background: #e63946; border-color: #c92f3c; }
.panel { background: #f4f7fa; border: 1px solid #d7e0e8; border-radius: 8px; padding: .55rem .7rem; margin: .3rem 0; }
.panel-title { font: 600 12px system-ui; color: #56657a; margin-bottom: .35rem; }
.bits { font: 700 15px ui-monospace, monospace; line-height: 1.5; white-space: pre; color: #1d3557; }
.bits .x0 { color: #0a7d33; }
.bits .x1 { color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Nim is COMPLETELY SOLVED (Bouton, 1901). For heaps h0,h1,h2 compute the XOR
//   x = h0 ^ h1 ^ h2  (the "binary digital sum"/Nim-sum).
// x == 0  -> position is LOSING for the player to move (P-position).
// x != 0  -> WINNING: there is a heap whose new size = heap ^ x is smaller,
//            and moving it there makes the XOR zero. That is the perfect move.
let heaps = [3, 4, 5];
let pendingHeap = -1, pendingTake = 0; // player's staged move

const xorAll = h => h.reduce((a, b) => a ^ b, 0);

function render() {
  const cont = document.getElementById('heaps'); cont.innerHTML = '';
  heaps.forEach((n, hi) => {
    const col = document.createElement('div'); col.className = 'heap';
    for (let i = 0; i < n; i++) {
      const c = document.createElement('div'); c.className = 'coin';
      // coins removed = those at height >= (n - take) when this heap is staged
      if (hi === pendingHeap && i >= n - pendingTake) c.classList.add('sel');
      c.addEventListener('click', () => stage(hi, n - i)); // take from this coin upward
      c.addEventListener('mouseenter', () => hover(hi, n - i, col));
      c.addEventListener('mouseleave', () => render());
      col.appendChild(c);
    }
    const lab = document.createElement('div'); lab.className = 'heap-label';
    lab.textContent = fmt('Heap %hi%%v% (%n%)', { hi: hi, v: 1, n: n });
    col.appendChild(lab);
    cont.appendChild(col);
  });
  renderBits();
}
function hover(hi, take, col) {
  const coins = [...col.querySelectorAll('.coin')];
  coins.forEach((c, i) => { if (i >= heaps[hi] - take) c.classList.add('hl'); });
}
function stage(hi, take) {
  pendingHeap = hi; pendingTake = take; render();
  setStatus(fmt('Taking %take% from heap %hi%%v%. Press the button to confirm.', { take: take, hi: hi, v: 1 }), '');
}
function pad(n, w) { return n.toString(2).padStart(w, '0'); }
function renderBits() {
  const w = Math.max(3, ...heaps.map(h => h.toString(2).length));
  const x = xorAll(heaps);
  let s = '';
  heaps.forEach((h, i) => { s += '  ' + pad(h, w) + '   = ' + h + '\n'; });
  s += '  ' + '-'.repeat(w) + '\n';
  const xs = pad(x, w).split('').map(b => '<span class="x' + b + '">' + b + '</span>').join('');
  s += '  ' + xs + '   XOR = ' + x + (x === 0 ? '  (you lose)' : '  (you can win)');
  document.getElementById('bits').innerHTML = s;
}
function setStatus(t, cls) { const e = document.getElementById('status'); e.textContent = t; e.className = 'status ' + cls; }

// Perfect engine move: pick heap i with (heap[i] ^ x) < heap[i], reduce it to heap[i]^x.
function engineMove() {
  const x = xorAll(heaps);
  if (x === 0) { // engine is in a losing position; make any legal move (take 1 from largest)
    let i = heaps.indexOf(Math.max(...heaps)); heaps[i] -= 1; return false;
  }
  for (let i = 0; i < heaps.length; i++) {
    const target = heaps[i] ^ x;
    if (target < heaps[i]) { heaps[i] = target; return true; }
  }
  return true;
}
function confirm() {
  if (pendingHeap < 0 || pendingTake <= 0) { setStatus('Click coins in a heap first.', 'bad'); return; }
  heaps[pendingHeap] -= pendingTake; pendingHeap = -1; pendingTake = 0;
  if (heaps.every(h => h === 0)) { render(); setStatus('You took the last coin — you win! (Only possible if you started from XOR = 0.)', 'ok'); end(); return; }
  // engine replies
  engineMove();
  render();
  if (heaps.every(h => h === 0)) { setStatus('The engine took the last coin — the engine wins.', 'bad'); end(); return; }
  const x = xorAll(heaps);
  setStatus(x === 0 ? 'Engine moved. XOR is now 0 — you are in the losing position. Your move.'
                    : 'Engine moved. Your move.', x === 0 ? 'bad' : '');
}
function end() { document.getElementById('go').disabled = true; }
function reset() {
  heaps = [3, 4, 5]; pendingHeap = -1; pendingTake = 0;
  document.getElementById('go').disabled = false;
  render(); setStatus('Your move: take some coins from one heap.', '');
}
document.getElementById('go').addEventListener('click', confirm);
document.getElementById('reset').addEventListener('click', reset);
render();
Result
Console

Watch the XOR line. The engine always tries to hand you a position where the XOR is zero — and from a zero position there is no move that keeps it zero, so you are forced to break it and the engine restores it. If you start from a position whose XOR is already zero, the engine is lost and you can win; otherwise it never slips. That single number is the entire theory of the game, made visible bit by bit.

The Real Complexity

How hard is Nim, really? The astonishing answer: not hard at all — it is completely solved.

  • The winning rule. Compute the XOR (bitwise "exclusive or", also called the binary digital sum) of all the heap sizes. If it is nonzero, the player to move can win; if it is zero, the player to move will lose against perfect play. The winning move is always the one that makes the XOR zero again.
  • Proven in 1901. The mathematician Charles L. Bouton of Harvard published the full analysis and the name "Nim", proving the XOR rule is both necessary and sufficient. This is a solved game in the strongest sense: optimal play is a closed-form formula, computable in time linear in the number of bits.
  • It generalizes. The Sprague-Grundy theorem (Roland Sprague, 1935; Patrick Grundy, 1939) showed that every impartial game — every game where both players have the same moves and the last move wins — is equivalent to a single Nim heap of some size, its Grundy value. Nim is not just one solved game; it is the universal building block for an entire class of them.
  • Where it sits. Finding the winning move is in P — trivially fast. This is the opposite end of the spectrum from games like chess, whose perfect play is intractable.

So Nim is the rare trophy: a game with no luck, no hidden state, and a complete, provably optimal strategy that fits in one line of arithmetic.

Where It Matters

A game solved by one XOR turns out to touch a surprising amount of mathematics and computing:

  • Combinatorial game theory: via Sprague-Grundy, the analysis of Nim becomes a toolkit for solving whole families of impartial games by reducing each to a Grundy value and XOR-ing them.
  • The power of XOR: the same bitwise digital sum drives parity checks, RAID storage, simple checksums and the classic "find the unpaired element" trick. Nim is XOR's most charming demo.
  • Error-correcting codes and puzzles: XOR-balanced positions are exactly the idea behind certain coin-weighing and hat-guessing puzzles, and behind parity-based codes.
  • Teaching strategy: because the optimal rule is short and provable, Nim is a favorite first example of what it means to truly solve a game.

Understand Nim and you've met the cleanest example of a perfectly solved game — the bright opposite of the open and intractable problems like P vs NP.

Conclusion

Nim is a small miracle of certainty. There is no opening theory to memorize, no endgame database to consult — just a single rule: XOR the heaps, and move to make it zero. Bouton settled it in 1901, and Sprague and Grundy showed that this one game secretly contains every impartial game.

That is what "solved" really means. While most interesting questions in computing stay hard, open, or even provably undecidable, Nim sits at the other extreme — a game whose entire future you can read off one number. The next time you face those heaps of coins, you don't have to play well. You just have to count in binary.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/nim/Content licensed under CC BY-NC 4.0.