Combinatorial Game Theory
who wins, and by how much
Generator

Nim with heaps of 3, 5, 7

Nim with heaps of 3, 5, 7
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.

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.

6 essays call nim-heaps. 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

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

PositionWorth OutcomeDrawn in
heaps 1, 1, 1 ∗1 N A pass is not a move · 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 · Two misère outcomes are not enough · What a tame heap may be replaced by
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 1, 2, 3, 1 ∗1 N A pass is not a move
heaps 1, 4 ∗5 N No two heaps alike
heaps 2, 1, 2 ∗1 N Taking from the ends
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
heaps 4, 4 0 P Nim, and the nim-sum · What a value leaves out
heaps 6 ∗6 N Nim, and the nim-sum

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.

 Generalized Geography. A token on a directed graph. A move slides it along an edge to a vertex not yet visited, and a player who cannot move loses. That is the whole game, and deciding who wins it is as hard as anything decidable in polynomial space — which is the strongest hardness claim anybody makes about a combinatorial game. Impartial games

A token on a graph

Geography is an impartial game whose position is a vertex and a history, so a ten-vertex graph has ten thousand states rather than ten. Take the arrows off and the same game is decided by a maximum matching — first player wins exactly when every maximum matching covers the start, verified on 41 vertices across eight graphs. One word in the rules separates a polynomial criterion from a PSPACE-complete problem.

 The same position, two conventions, two winners. Three-player Nim with the last counter winning. The two columns differ only in what a player does when they cannot win themselves, which is a question the rules do not answer — and the answer decides who wins. Where it stops

Three players and no answer

Every theorem here is about two players, and the reason is not convenience. With two players the game is zero-sum, so 'play well' needs no further explanation. Add a third and the winner of a Nim position becomes a fact about the convention: two reasonable ones disagree on 56 of the 71 positions swept. The one question no convention touches — can a player force a win against the other two together — is answered 'nobody' in 65 of the 71.

 A pass that may not end the game is not a component at all. The same grouping with the pass forbidden as the final move. Each group now holds several values, and a group with several values is a proof that the parts do not determine the whole. Where it stops

A pass is not a move

Put a single pass token on a Nim board and one clause decides everything. If it may be taken at any time — including as the move that ends the game — the value of the whole is the nim-sum with a one added, in all 120 positions swept: the pass is a heap of one. Forbid it as the final move and the value stops being a function of the nim-sum at all, and 3 and 1 + 2 come apart.

 End-Nim: a player at each end of the row. Rows of heaps in which Left may take from the leftmost heap and Right from the rightmost. The value beside each row was computed by the game recursion and reduced to canonical form; the outcome beside it says who wins. A single heap is a Nim heap, because both players may take from it — and that is the last thing about this game that looks like Nim. Particular games

Taking from the ends

End-Nim is Nim's board with a player at each end, and it takes one sentence to state. Not one of its 5,460 small positions is worth a non-zero number — the game is all-small, so zero is the only number any of them can reach — and there are 2,693 distinct values between them. The outcome says a great deal more: 4,738 of those positions are won by the same player whoever moves, and on two heaps the rule is that the larger end wins.

 Welter positions and what they are worth. Coins on a strip, with the Grundy value the recursion returns and the nim-sum the squares would have if they were independent heaps. The two columns are the essay: they hardly ever agree. Impartial games

No two heaps alike

Welter's game is Nim with one extra clause — no two heaps may be the same size — and the clause is fatal to the nim-sum, which gives the right answer in none of the 120 three-coin positions. What replaces it is a function of pairs: ⟨a | b⟩ = (a ⊕ b) − 1, exact on all 55 two-coin positions, and nim-added over every pair it is exact on the whole board provided the number of coins is even.

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