Nim

“Count how many are left” — tested

“Nim is about taking the last object, so the winning idea is to count how many are left.”

That is the sentence this app was built to check. The verdict is that it is false as a general rule and exactly right on one describable set — and the set explains why the sentence is so tempting.

Counting as a prediction

Take the claim at its word: guess that the player to move has lost whenever an even number of counters is left. Over every Nim position in two enumerated spaces ( positions of four heaps of 0–7 and of six heaps of 0–4, in all) that guess is right times and wrong times — % accurate, 95% CI –%. Its smallest counterexample is a single heap of two: two counters left, and the player to move wins by taking both.

Where it is exactly right, and why

On the positions whose every heap holds 0 or 1 counter, counting is right every single time. That is not luck. When every heap is a single counter the nim‑sum is the parity of the count: the binary columns collapse to one column, and XOR of a column of ones is exactly “odd or even”. The counting rule is the real rule with all but one bit thrown away. Everywhere else the discarded bits decide the game.

Counting as a strategy

Sharper test: hand each strategy a position that is already won and make it play out against perfect defence. A perfect player converts every one ( of ). A player who always moves to leave an even total converts of — %, 95% CI –%. Random play converts of (%). The counting player really is better than chance — two‑proportion z = — and it still throws away about games in 100 that it had already won.

Misere: where the rule changes, exactly

Play the same game with taking the last counter a loss and almost nothing changes. Two statements, both checked against brute force on all positions:

• Outcomes differ between the two conventions on exactly those positions in which every heap holds 0 or 1 counters — of . Nowhere else.
• Winning moves differ on exactly the non-empty positions with at most one heap holding more than one counter — of , %.

“Only at the very end” is right, but it is not rare. Over misere games played out perfectly from random openings, every single one passed through a position where the two strategies part company. The mean game lasts moves and the first divergence arrives at move ; % of all moves played (95% CI –%) are ones where knowing the misere rule matters. A player who knows only the normal-play rule does not lose misere Nim occasionally; they lose the endgame of every game they should have won.

What was verified, and how

The engine is checked by assertions. The Grundy values are re-derived a second time by a brute-force search that knows only the move rules and who moved last — no XOR, no mex — recovering each position's value as the one Nim heap size that makes the sum a loss for the mover ( positions, plus checks that no other heap size works). Five deliberately broken rules were each proven to break the match before anything they guard was believed; a sixth — a mex that starts counting at 1 — turned out to change nothing at all on Kayles, because no row of pins is ever a loss for the player to move, so it is recorded as inert rather than counted as a pass.

Kayles, recomputed

Kayles is a row of bowling pins; a move knocks down one pin, or two adjacent pins, which can split one row into two. It looks nothing like Nim. Every position is a Nim heap anyway, and the table below is the size of that heap for a single unbroken row of n pins.

These numbers are computed in your browser when this page loads, from the move rule alone. They are then compared — in the build harness, not here — against two independent publications of the same sequence: the table in the Wikipedia article on Kayles (n = 0…83) and the OEIS entry A002186 (n = 0…104). All terms agree.

The pattern settles down: after the exceptions run out the same values repeat for ever, and no value in the whole range ever exceeds . There are exceptions and the last is at n = .

A small correction to the textbooks. Accounts of Kayles say the sequence is periodic “from n = ”. The smallest preperiod is actually : the last value that breaks the pattern sits at n = , so everything from onwards already repeats. is where the printed table's row happens to start, being a multiple of . Both statements are true; only one is tight.

How to play

Nim. Click a counter to take it and everything to its right in that heap. Take at least one; take from one heap only.

Kayles. Click a pin to knock it down. Click the gap between two neighbouring pins to knock both down at once. A gap in the middle of a row splits it into two rows that are then played separately.

Subtraction. Click one of the last three counters of a heap to take that many.

Normal play means the player who takes the last object wins. Misere means that player loses.

The lens above the move list shows each heap's Grundy value, the binary columns, and the one Nim heap the whole position is equal to. A value of zero means the player about to move is lost against perfect play. Turn it off if you would rather work it out yourself.

What is faithful, and what is mine

This is an independent reimplementation written from published rules, not a port of any existing program. No code, artwork, sound or data file from any other implementation is used.

• Nim — the rules and the winning theory are Charles L. Bouton's, published as “Nim, A Game with a Complete Mathematical Theory”, Annals of Mathematics, Second Series, Vol. 3, No. 1/4 (1901–1902), pp. 35–39, Mathematics Department, Princeton University. Bouton coined the name; the game itself is far older and is in the public domain. Bouton describes three heaps and generalises at the end; this app lets you play any number. The misere rule the opponent uses is Bouton's own, from section 6 of that paper.
• Kayles — invented by Henry Dudeney, The Canterbury Puzzles, 1908, puzzle 73 (pp. 118–119). The normal-play analysis is R. K. Guy and C. A. B. Smith, “The G-values of various games”, Proceedings of the Cambridge Philosophical Society 52 (1956), 514–526. The nim-value sequence is OEIS A002186.
• The Sprague–Grundy theorem — discovered independently by R. P. Sprague (1935/36) and P. M. Grundy (1939). It is what lets one number stand for a whole position, and it is the reason Kayles and the subtraction game appear here alongside Nim.
• Mine, not theirs: the board and pin drawing, the lens panel, the three-game picker, the opponent's imperfect settings, the move log, the recomputed Kayles table with its exceptions found rather than quoted, and everything in “What the numbers say”.
• What differs on purpose: the subtraction game shown here is the simple S = {1, 2, 3} game, which is neither Dudeney's nor Bouton's. Misere play is offered for all three games, but by two different mechanisms, and the difference is deliberate. For Nim the opponent uses Bouton's rule from section 6 of the 1901 paper, which is exact and instant. For Kayles and the subtraction game there is no such rule — misere Kayles was solved by William Sibert in 1973 and published only in 1989, and its solution is nothing like a one-liner — so this app solves those positions by exhaustive search instead, and simply refuses to answer for a position too large to search rather than guessing. That is why misere openings are kept small.

Credits

Nim is public domain. Kayles is Henry Dudeney's, 1908, and also long out of copyright. The names “Nim” and “Kayles” are used descriptively, for the games themselves. No affiliation with, or endorsement by, any publisher is claimed. Full text in CREDITS.txt; licence in LICENSE.txt.

This page runs entirely in your browser. It makes no network requests, sends nothing anywhere, and stores only your settings and a win/loss tally on this device.