Combinatorial Game Theory
who wins, and by how much
Series

Multiplayer — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. The same position, two conventions, two winners. Three-player Nim with the last counter winning. The two columns differ only in what a player does when they cannot win themselves, which is a question the rules do not answer — and the answer decides who wins.

    Three players and no answer

    Every theorem here is about two players, and the reason is not convenience. With two players the game is zero-sum, so 'play well' needs no further explanation. Add a third and the winner of a Nim position becomes a fact about the convention: two reasonable ones disagree on 56 of the 71 positions swept. The one question no convention touches — can a player force a win against the other two together — is answered 'nobody' in 65 of the 71.

    part 1 · limits
  2. What each assumption buys back. Forty-five positions of up to two heaps of up to eight, sorted into classes that no test position of up to three heaps can tell apart, under four rules. Two-player Nim has sixteen classes, both three-player conventions have forty-five, and one player against a coalition of two has six.

    What survives a coalition

    Three-player Nim has no winner without a convention and no sum theory at all. Fix one player against the other two and both come back: every position has a winner, the winner is read off the number of heaps of one modulo three and the number of larger heaps, and forty-five positions fall into six interchangeable classes — fewer than Nim's sixteen. Fix a scoring rule instead and the winner comes back, identical to one of the conventions, and nothing else does: no two positions are interchangeable.

    part 2 · limits
  3. Six rulesets, and the heaps that stop mattering. Single heaps of six impartial rulesets classified under three-player play with one player against a coalition of two. Nim's heaps fall into three classes; subtraction {1, 2} keeps five, Kayles six, subtraction {1, 3} ten, subtraction {2, 3} twelve and Dawson's Kayles ten before every larger heap is interchangeable, and three rulesets have a smaller heap that joins the large class early.

    A coalition counts to three

    Three-player Nim with one player against two collapses to six classes, because every heap of two or more is a store of tempo either side can draw on. Put the same coalition on games whose heaps are not all stores and it does not collapse: subtraction {1, 2} keeps five kinds of heap, Kayles six, subtraction {1, 3} ten and {2, 3} twelve, each count settling as the range grows. Past a threshold the large heaps are interchangeable again — and in every one of the five, unlike Nim, a single large heap hands the game to the coalition. The classes neither refine the two-player values nor coarsen them: {1, 3} has two Grundy values and ten coalition classes.

    part 3 · limits
  4. Ten classes, and a rule to name them. The classes of subtraction {1, 2} with one player against two: a grid of heaps of one counted modulo three against no other heap, a heap of two or a heap of three, each cell giving the lone player's result with each player to move, and a tenth class — anything with a heap of four or more, or two heaps from two and three — won by the coalition.

    Units modulo three, and one choice

    Nim's rule for one player against two has a shape: count the heaps that always last one move, modulo three, allow one heap that offers a choice, and give any second choice to the coalition. Subtraction {1, 2} has exactly that table — ten classes, nine of them a count of ones against nothing, a two or a three — and so do Kayles, where a heap of three is a heap of two with a unit beside it, and Dawson's Kayles. Subtraction {1, 3} and {2, 3} do not: a board with two choices on it can still be the lone player's, and the short key fails. And {2, 3} and Dawson's Kayles give every heap to ten exactly the same menu of game lengths, so what a coalition reads is not how long a heap can last.

    part 4 · limits

All series