Combinatorial Game Theory
who wins, and by how much
Series

Pass — the series

4 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
  4. A line of losses. Positions made of up to 28 heaps of two and up to 28 heaps of four with a held pass, the losses filled. They are the empty board, four-heaps alone at 7, 13, 19 and 25, and a single diagonal line: 2k + 3 heaps of two beside 2k heaps of four.

    The table closes, until heaps of four

    Classes that no company can tell apart always combine, so the question left by the held pass is not whether it has an algebra but whether the algebra is finite. Computed the way a misère quotient is, it is: four classes for heaps of one where misère play needs two, eleven for heaps up to two, fourteen up to three, nineteen for Kayles rows up to five. Admit Nim heaps of four and the table never closes — a single line of losses, 2k + 3 heaps of two beside 2k heaps of four, gives every count of twos a class of its own. And at the bottom of every closed table sits the normal-play group, with the loss moved to nim-sum one: on a crowded board the held pass is a heap of one.

    part 4 · limits

All series