Combinatorial Game Theory
who wins, and by how much
Generator

A grid of coins, and a multiplication table

A grid of coins, and a multiplication table
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 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.

3 essays call tartan-grid. 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.

Where it is called

Changing this generator changes every one of these figures.

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. Impartial games

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.

 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. Impartial games

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.

 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. Impartial games

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.

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