Combinatorial Game Theory
who wins, and by how much
Series

Pass — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. A pass that may not end the game is not a component at all. The same grouping with the pass forbidden as the final move. Each group now holds several values, and a group with several values is a proof that the parts do not determine the whole.

    A pass is not a move

    Put a single pass token on a Nim board and one clause decides everything. If it may be taken at any time — including as the move that ends the game — the value of the whole is the nim-sum with a one added, in all 120 positions swept: the pass is a heap of one. Forbid it as the final move and the value stops being a function of the nim-sum at all, and 3 and 1 + 2 come apart.

    part 1 · limits
  2. Two heaps and a held pass. Every pair of heaps up to 16 with one pass available that may not be the last move. Filled cells are the pairs the player to move loses: the empty board and the pairs one and two, three and four, five and six, and so on. Outlined cells are the equal pairs Nim calls lost, all of which are wins once the pass is there.

    Three heaps and a pass

    Nim with a single pass that may not end the game is easy on one heap and on two: a heap swaps each odd size with the even one above it, and two heaps lose exactly at (2k − 1, 2k). On three heaps the losses are known only as a list. Fix the smallest heap and each slice of the list settles into a pattern after an irregular start — period 4, 8, 10, then 160 at a smallest heap of ten, and nothing visible from eleven.

    part 2 · limits
  3. What a held pass can tell apart. Nim heaps, Kayles rows and heaps of Dawson's chess of sizes one to 8, grouped by whether any company of up to two of them gives a different outcome with a held pass on the board. The groups outnumber both the Grundy values and the pairs of Grundy value and held-pass value.

    What a component would have to carry

    For a held pass to be decided by a summary of each component, the summary must separate every pair of components some company tells apart. The Grundy value does not — Nim 1 and Kayles 8 are equal games that a held pass separates beside a single Nim heap of two. Nor does the Grundy value with the component's own held-pass value: Kayles 3 and Kayles 6 agree on both and are split by a company of two Nim heaps. Over twenty-four components, fifteen classes against fourteen pairs, and the gap widens as the pool grows.

    part 3 · limits

All series