Combinatorial Game Theory
who wins, and by how much
Concept

Welters game — where it appears

Nim played with coins on a strip, each sliding to a lower empty square, where no two coins may ever share a square. Its value is an exclusive-or of a pairwise function of the squares, and a matching of the coins chosen by their lowest binary digits reads it.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

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.

impartial · Welter 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.

impartial · Welter

Named alongside it

The objects these essays reach for when they reach for this one.

Grundy valueImpartialNimNim-sumNormal playBinaryClosed formDisjunctive sumEnumerationExhaustive searchPairingParity

All concepts