Generator

Nim from 1, 2, 3 — and who wins

A Nim position with the outcome stated before anybody moves. The reply to every move a reader can make was computed in advance from the nim-sum, so the machine is not searching or guessing — it is following the theorem, and there is no line of play in which it loses.

6 essays call play-nim. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

4 distinct positions, harvested by running this generator again at the options each essay passed it.

Position	Worth	Outcome	Drawn in
`heaps 1, 2, 3`	`0`	P	A pass is not a move · A token on a graph · The move that gives counters back · Nim is easy, in binary · Misère play · Nim, and the nim-sum · Tame and wild · The patch that generalised · The sentence that solved the other convention · The theorem that needed none of the theory · Three players and no answer · What a value leaves out · What a wider pool rescues
`heaps 2, 2`	`0`	P	A pass is not a move · Misère play · Nim, and the nim-sum · Tame and wild · The patch that generalised · The sentence that solved the other convention · What a tame heap may be replaced by · What a value leaves out · What a wider pool rescues · Who moves last
`heaps 3, 5, 6`	`0`	P	Nim, and the nim-sum · Taking from several heaps at once · A row of coins is already a sum
`heaps 3, 5, 7`	`∗1`	N	Nim, and the nim-sum · The theorem that needed none of the theory

It plays back

The winner is named before a move is made, and every reply was worked out in advance.

A row of coins is already a sum — Nim from 3, 5, 6 — and who wins, worth 0, P, 70 positions solved before the page was served.
Nim, and the nim-sum — Nim from 1, 2, 3 — and who wins, worth 0, P, 14 positions solved before the page was served.
Taking from several heaps at once — Nim from 3, 5, 6 — and who wins, worth 0, P, 70 positions solved before the page was served.
The move that gives counters back — Nim from 1, 2, 3 — and who wins, worth 0, P, 14 positions solved before the page was served.
The theorem that needed none of the theory — Nim from 3, 5, 7 — and who wins, worth ∗1, N, 88 positions solved before the page was served.
Who moves last — Nim from 2, 2 — and who wins, worth 0, P, 6 positions solved before the page was served.

Where it is called

Changing this generator changes every one of these figures.

Nim with heaps of 3, 5, 7. Heaps of counters; a move takes any number from one heap. The position is a loss for the player to move exactly when the binary digits of the heap sizes cancel in every column — the nim-sum — and that is the whole of the theory of Nim.

Impartial games

Nim, and the nim-sum

Three heaps of counters, take as many as you like from one of them, and the player who takes the last counter wins. The winning condition is not a search, not a table, and not a heuristic — it is the bitwise exclusive-or of the heap sizes, and it was found in 1901.

Four things a position can be. Every position falls into one of four outcome classes, and only three of them correspond to a comparison with zero. The fourth — first player wins — is a position confused with zero, neither greater, smaller nor equal, and it is where the subject departs from arithmetic.

Values

Who moves last

The player who cannot move loses. That single convention generates the whole theory — and it produces four outcomes rather than three, because a position can be confused with zero rather than greater, smaller or equal to it.

Bouton's invariant, checked over 512 positions. Nim positions in binary, one column per bit. Bouton's 1901 argument is that a position is a loss for the mover exactly when every column holds an even number of marks — and that from such a position every move breaks a column, while from any other position some move repairs them all. Both halves are checked here over every position in the range rather than illustrated once, and the middle row shows the repairing move being made.

How it was found

The theorem that needed none of the theory

Bouton solved Nim completely in 1901, with an argument that mentions no value, no sum of games and no Grundy number, because none of the three existed. The argument is two closure properties and it is airtight — and run on any other game it fails at the step that does the work.

Poker Nim from 3, 5, 7, with reserves of 4 and 4. Nim with one extra kind of move: a player may put any number of counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. They cannot, and the winner is decided by exactly the same nim-sum as ordinary Nim — checked here over every position within a stated range rather than argued.

Impartial games

The move that gives counters back

Poker Nim adds one rule to Nim — a player may put counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. The winner is decided by exactly the same nim-sum, and the reason is the single most useful idea in the whole reduction apparatus.

Turning Turtles: a row of 12 coins. A row of coins, some heads and some tails. A move turns some of them over, and the rightmost coin turned must go from heads to tails — which is what makes the game end. The number under each place is what a lone head there is worth, and the row is worth the exclusive or of the places showing heads.

Impartial games

A row of coins is already a sum

Everywhere else on this site a sum is several positions side by side. In a coin-turning game it is one row — each coin showing heads is a game in its own right, and the row is worth the exclusive or of them. The decomposition is inside a single picture.

Moore's Nim with k = 2: the columns, divided by 3. The heap sizes in binary, with each column added as an ordinary sum rather than exclusive-or. In Moore's Nim a move may take from as many as k heaps at once, and the position is lost for the player to move exactly when every column sum is divisible by k + 1. Ordinary Nim is k = 1, where divisible by two means an even number of ones — the same picture with a different divisor.

Impartial games

Taking from several heaps at once

Moore's Nim lets a move take from as many as k heaps at a time, and the losing positions are still read off the binary columns — divisible by k + 1 rather than by two. The rule agrees with exhaustive search over 54,264 positions and never disagrees, and it decides every outcome while supplying no value at all: reading the same columns as a base-3 number gets the Grundy value right on 42 of 330 positions.

The whole library · The position index · The figures that play back