Combinatorial Game Theory
who wins, and by how much
Generator

The smallest one missing

The smallest one missing
The smallest one missing. The Grundy value of a position is the least non-negative integer that is not the Grundy value of any option. That single rule turns any impartial game into a Nim heap, because a heap of that size has exactly the same set of reachable values.

The Grundy value of a position is the least non-negative integer that is not the Grundy value of any option. That single rule turns any impartial game into a Nim heap, because a heap of that size has exactly the same set of reachable values.

4 essays call mex-rule. 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.

Where it is called

Changing this generator changes every one of these figures.

Every impartial position is a Nim heap. A heap in a subtraction game, its Grundy value, and the Nim heap it is equivalent to. The equivalence is exact: the two positions have the same options up to value, so they behave identically in any sum, which is the Sprague–Grundy theorem. Impartial games

Every impartial game is a Nim heap

Sprague and Grundy proved, independently and four years apart, that any position in any impartial game is equivalent to a single heap of counters. Not similar to one — equal to one, interchangeable with it inside any larger game.

 Nim-multiplication below 16, and every field axiom checked. The nim-product, defined by taking the least value the product is not forced to be — the same manoeuvre as the mex rule, applied to a product rather than to a move. The result is that these values are not merely a group under nim-addition but a field: every axiom is checked over the whole table here, including an inverse for every non-zero value, and the sizes at which the axioms fail are reported rather than avoided. Impartial games

The nimbers multiply

Nim-addition is exclusive-or and everybody meets it first. There is also a multiplication, defined by the same take-the-least-value-not-forced manoeuvre as the mex — and it makes the nimbers below sixteen a field, with every axiom checked here and an inverse for every non-zero value.

 Top Entails, one heap at a time. Each heap with the outcome of playing it alone, the Grundy value an ordinary solver would give it, and the moves that win from it. Taking the top coin of a heap forces the opponent to answer in that heap, which is a kind of move no other game on this site has. Where it stops

A move that must be answered

Every argument on this site about sums assumes the parts are independent: a move in one leaves the others alone, and the reply may go anywhere. Top Entails denies it — take the top coin of a heap and the opponent must answer in that heap. The nim-sum then misreads 9 of 36 two-heap positions, and two heaps of two coins are a first-player win, which no impartial game the theory covers can be.

 Cram on 4 by 4: the pairing strategy. Cram is Domineering with the orientations shared: either player may place a domino either way up, so both players have exactly the same moves and the game is impartial. Every position therefore has a Grundy value, and this board's was computed by the mex rule over its own placements. Impartial games

Cram

Domineering with one word of the rule changed: both players may place a domino either way up. That makes the game impartial, and the entire partizan apparatus collapses into a single Grundy value — on the 4 × 4 board, Domineering's canonical form runs to 114 characters of nested braces and Cram's answer is the one character 0.

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