Combinatorial Game Theory
who wins, and by how much
Series

Welter — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    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.

    part 1 · impartial
  2. 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.

    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.

    part 2 · impartial
  3. 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.

    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.

    part 3 · impartial
  4. 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.

    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.

    part 4 · impartial

All series