Combinatorial Game Theory
who wins, and by how much
Generator

Welter positions and what they are worth

Welter positions and what they are worth
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.

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.

4 essays call welter-coins. 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

19 distinct positions, harvested by drawing the figure again at the options each essay asked for.

PositionWorth OutcomeDrawn in
0, 1 0 P No two heaps alike
0, 1, 2 0 P No two heaps alike
0, 1, 4, 5 0 P No two heaps alike
0, 2, 4, 6 0 P No two heaps alike
0, 2, 5, 7 0 P No two heaps alike
0, 3 ∗2 N No two heaps alike
0, 3, 4 0 P No two heaps alike
0, 6 ∗5 N No two heaps alike
1, 3, 5 0 P No two heaps alike
1, 3, 6 ∗7 N No two heaps alike
1, 4 ∗4 N No two heaps alike
1, 4, 6 0 P No two heaps alike
2, 3 0 P No two heaps alike
2, 3, 8, 9 0 P No two heaps alike
2, 4, 5 0 P No two heaps alike
2, 5 ∗6 N No two heaps alike
3, 7 ∗3 N No two heaps alike
4, 5 0 P No two heaps alike
6, 7 0 P No two heaps alike

Where it is called

Every one of these figures is a drawing of the same construction, so a correction to it corrects them all.

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.

 Four readings, one game. The closed form, the strict mating, the cancelling matching and the parity term, with how much of the game each accounts for. Impartial games

The pairing the formula hides

Welter's closed form sums a function over every pair of coins and needs an extra term when the count is odd, which looked like a surprise. Read as a matching it is not: an odd number of coins cannot be paired, the left-over coin contributes its own square, and some matching gives the value on every position measured.

 The trie a matching is read from. The squares 1, 2, 4, 7, 9 and 11 drawn as paths down a binary trie that reads bit 0 first, with the low-bit matching drawn as arcs: 1 with 9, 7 with 11, 2 with 4. Nodes where both sides hold an odd number of coins are filled, and each carries exactly one of the matching's pairs. Impartial games

The pairs are read from the bottom bits

Some matching of Welter's coins reads the position's value, and usually only one does — but which? The rule is short: pair the two coins whose squares agree in the most low-order bits, and repeat. It reads the value on every one of 3,696 positions of two to eight coins, where no other natural rule manages half. And it has a proof two lines long, because x − 1 flips a number's trailing bits, so a pair's animating value depends on where its squares part on the binary trie read from the bottom. What it is not is a strategy: a move from a lost position can be answered inside its pair only two times in five.

 Each coin has one square that wins. For the Welter position {3, 5, 6}, of value 3, one row per coin giving the value of the position when that coin alone is moved to each square from 0 to 11. Every row takes each value at most once and reaches nought exactly once, at square 0 for the coin on 3, square 2 for the coin on 5, square 1 for the coin on 6. Impartial games

One square for every coin

Nim's strategy has two halves: every heap has exactly one target, the nim-sum of the others, and the heaps carrying the top bit of the nim-sum are the ones that can reach it. Welter's game keeps the first half on every one of 18,470 coins tried — one square per coin makes the value nought, and the winning moves are the coins above theirs — and the square is found by walking up the binary trie from the value of the other coins. It loses the second half. And at four coins it loses nothing: the losses and the winning moves are Nim's exactly, by a two-line proof, while at six coins no Welter loss is ever a Nim loss, because the last bit of a losing position is a count of pairs.

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