Combinatorial Game Theory
who wins, and by how much
Concept

Field — where it appears

A number system with addition and multiplication that both invert, which the impartial values form under nim-addition and nim-multiplication. That nimbers form one is a fact about a game's values with no game-theoretic content whatever, which is why it is worth pointing at.

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

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.

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.

impartial · Nim A grid of coins, and a multiplication table. The Grundy values of a two-dimensional coin-turning game, computed from its own move rules by a mex at every cell. Down the left and across the top are the one-coin values of the two one-dimensional games it is built from. Every cell is the nimber product of its two edge values — the multiplication defined for the nimber field on algebraic grounds — and beside the grid are the three combining rules a reader would try first, each killed on a named cell.

The tartan theorem

The nimbers are a field, with a multiplication defined by a mex-style rule that looks like an algebraist's amusement. Lay two coin-turning games on a grid and the Grundy value of each square is the nimber product of its two coordinates — which is the point at which the multiplication stops being a curiosity and starts computing answers.

impartial · Nim What the theorem replaces. Every grid a brute-force solve can reach, valued both ways, with the grid the theorem is normally drawn at underneath. Twelve squares is four thousand arrangements against twelve products; sixty-four squares is eighteen quintillion against sixty-four.

Four hundred and seventy steps

The tartan theorem replaces a search with a multiplication. Measured on every grid a brute-force solve can reach, the two agree on all of them — and the ratio doubles with every square added. On the 8 × 8 grid the theorem is normally drawn at, the search would have to value eighteen quintillion arrangements; the theorem needs twenty-six different nimber products, and computing all of them by the rule that defines them looks at four hundred and seventy pairs.

impartial · Nim

Named alongside it

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

Exhaustive searchGrundy valueMexNim-sumNimberCoin-turningDecompositionImpartialXORClosureComplexityDisjunctive sum

All concepts