Combinatorial Game Theory
who wins, and by how much
Concept

Linear code — where it appears

A set of binary words closed under exclusive-or, so that it is the kernel of a linear map and can be described by equations rather than listed. Bouton's losing set for Nim is one, and finding that a game's losing set is one is finding that it has a rule rather than a table.

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

Mock Turtles on 8 coins: every lost position. The rows a player to move has already lost, drawn in full. A filled disc is a coin showing heads. The set is closed under turning over every coin two of its members disagree about, which is what makes it a linear code, and the count of heads in the sparsest of them is the fewest coin turns that separate two lost positions.

The losing positions are a code

Turn over one, two or three coins, and the rows a player has already lost turn out to be closed under adding two of them together. That makes them a linear code — and on eight coins it is the extended Hamming code exactly, sixteen words with a weight enumerator of 1 + 14x⁴ + x⁸, produced by a move rule that knows nothing about codes.

impartial · Codes Four conditions. The four linear conditions whose kernels are the losing sets, with the cases each covers.

The parameter was the difference

The losing words of bounded Moore's Nim form a linear subspace and no map was known whose kernel they are. The equations exist, four conditions cover all thirteen cases at three to six heaps, and they are indexed not by the heap count but by the heaps less the width of a move — which turns the failure at six heaps into a prediction about seven.

impartial · Moores-nim Five of six. The six predictions made for seven heaps by the difference reading, each scored against the sweep that was declined at the time.

The family with two witnesses

Six predictions about seven heaps were written down and deliberately not run. Five of them held. The one that broke is the condition that had been checked against two cases when it was proposed — the fewest of the four — and at seven heaps it does not merely give the wrong answer, it asks a question the parity word has stopped being able to answer.

impartial · Moores-nim The dual is the value table's span. The dual code against the span of the bit-planes of the one-coin Grundy values, on every game measured.

The dual was the value table

A coin-turning game's losing rows form a linear code, and a code has a dual that nothing in the game appeared to read. It reads it constantly: the dual is spanned by the bit-planes of the Grundy values — the parity checks are the value table stood on end — and on Mock Turtles over eight coins the losing rows are exactly the span of the table that decides them.

impartial · Codes Two squares a key never needs. A 4 × 5 Domineering board shaded like a chessboard, with two squares of the same shade in rows 1 and 2 marked. Because a domino covers one square of each shade, a vertical domino covers one square in an odd row and one in an even row, and turns alternate, the other eighteen squares determine both marked squares: a key that leaves them out confuses none of the 48,670 reachable positions.

A key is a code, and two squares come free

The families of positions a Zobrist key confuses are the words of a binary linear code — the sets of squares whose words cancel — so choosing a key is choosing a code. On 4 × 5 Domineering the textbook choice, a code with the largest minimum distance, confuses more stored positions than a random key at fourteen, sixteen and nineteen bits. The choice that reads the board confuses none at eighteen: two squares of one shade, in rows of different parity, are decided by the other eighteen, and no seventeen-bit key is exact.

complexity · Identification

Named alongside it

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

ImpartialParityEnumerationInvariantNormal playSecond-player winCoin-turningCounterexampleExhaustive searchGrundy valueMexMoores-nim

All concepts