A coalition counts to three

What survives a coalition took three-player Nim, which has no winner at all until somebody says what a losing player prefers, and fixed one assumption: player one alone, players two and three a team whose only aim is to stop player one making the last move. That is a two-sided game again, every position has a winner whichever of the three players is to move, and the winner turned out to have a rule that fits in a table. Count the heaps of one modulo three, count the heaps of two or more up to two, and nothing else about the position matters. Among positions of up to two heaps that leaves six classes, and a heap of two is the same heap as a heap of eight.

The reason was a property of Nim’s heaps. A heap of two or more is a store of tempo: whoever touches it can take it all or leave one, and so choose whether the move count changes by one or by two. With one such store the lone player can spend it first; with two, the allies always have one left. Every Nim heap past one is a store, so every Nim heap past one is interchangeable, and the quotient is counting.

That essay ended on the obvious test. In a game where some heaps leave no choice about what remains, the heaps are not all stores. If the coalition’s classes there are still ones and the rest, the collapse is the whole story of what a coalition does to an impartial game. If they are not, the coalition quotient has a structure of its own, the way misère quotients do for the games misère play breaks.

Six rulesets and the heaps each one keeps apart #

The test is run on Nim and five rulesets chosen to differ in exactly the way that matters. Three are subtraction games — a move takes one or two counters, or one or three, or two or three — in which a heap can shrink only by a fixed amount and a large heap can never be emptied at once. Two are games that split a row: Kayles, where a move knocks down one pin or two adjacent ones and may leave two rows, and Dawson’s Kayles, where it knocks down exactly two.

For each ruleset, each heap is added to every test position of up to three further heaps, and the three outcomes — whether the lone player wins with themselves, the first ally or the second ally to move — are recorded. Two heaps whose records agree against every test are in one class. That is the construction the Nim essay used, the same one a misère quotient is built from, run here on single heaps up to twenty for the subtraction games and up to twelve and sixteen for the splitting games.

None of the five collapses to Nim’s three. Subtraction {1, 2} keeps five kinds of heap: nothing, one, two, three, and everything from four up. Kayles keeps six, from nought to four and then everything from five up. Subtraction {1, 3} keeps ten, subtraction {2, 3} twelve and Dawson’s Kayles ten. In each the large heaps do eventually become interchangeable, but the size at which that happens is a property of the rule — two for Nim, four for {1, 2}, five for Kayles, ten for {1, 3}, fourteen for {2, 3}, thirteen for Dawson’s Kayles.

And three of them do something no count of stores would predict. In subtraction {1, 3} the heap of seven belongs to the large class while eight and nine do not; in {2, 3} it is the heap of nine, with ten to thirteen still apart; in Dawson’s Kayles it is eleven, with twelve apart. A heap can behave like a large one before the heaps just above it do.

Counts that stop moving #

A class count from a finite test set is only as good as the tests. Two heaps in one class might be separated by a test larger than any tried, and a count that is still climbing at the edge of the range is a count of the range rather than of the game.

So the census is run at several ranges, with the positions and the tests widened together. A wider test can split a class and can never join two, so the count can only rise or stay put. It stays put in every row before the range ends. Nim gives six classes of up-to-two-heap positions at eight, twelve, sixteen and twenty, which is the six the earlier essay found. Subtraction {1, 2} gives eight throughout. Kayles gives nine at eight, ten and twelve. Subtraction {1, 3} rises from twenty to twenty-two at twelve and then stops; {2, 3} rises to twenty-six at sixteen and holds at twenty; Dawson’s Kayles reaches thirteen at twelve and holds at sixteen.

That is evidence, not proof. Nothing here excludes a separating test with a heap of forty in it. What it does exclude is the reading in which the classes are an artefact of a small range — a quotient whose count grows with every heap added, as a function with no formula found on the wild side of an octal game. On these six rules, one against two is a finite object on every range measured, and it has settled.

The splitting games are run to smaller ranges for a reason worth knowing. A split multiplies the positions a test reaches — a heap of sixteen in Kayles breaks into every pair of rows summing to fourteen or fifteen — and Kayles at sixteen takes a minute where Nim at twenty takes five seconds. The subtraction games are cheap because a heap stays one heap.

One large heap is enough, except in Nim #

The table of classes says which heaps are alike. It does not say what the large class is, and that is where the five new rulesets differ from Nim most sharply.

A short list of tests is enough to tell subtraction {2, 3}'s twelve kinds of heap apart: the heap alone, and the heap beside one + one + five, one + five + ten and one + two + ten. Read down the columns and the large class stands out at once. A heap of nine, or of fourteen or more, wins for the coalition whoever is to move, against every test. Put one such heap on the board and the lone player cannot win, whoever moves first and whatever else is there. The class is absorbing: it is the zero of the coalition’s arithmetic, the element that turns every sum into a loss for the lone player.

The same is true of the large class in all five new rulesets, checked against every test in each range. It is not true of Nim. A single large Nim heap is a win for the lone player moving first unless the heaps of one number one more than a multiple of three, and it takes a second large heap to hand the coalition the game — which is why Nim’s rule counts large heaps up to two, and why the new rulesets need no such count.

The difference has a plain source. Nim is the only one of the six in which every heap can be emptied in a single move. A lone player moving into a large Nim heap can decide whether it ends now or later, and that one decision is the store the earlier essay described. In the other five a large heap cannot be finished at once, so it lasts several rounds, and in every round the team moves twice to the lone player’s once. A heap that outlasts the lone player’s choices is a store the team controls. That is an argument for the pattern, and the census is its only check; it does not say where each rule’s threshold falls, and it does not explain the early members — why nine behaves like fourteen in {2, 3} while ten to thirteen do not — which no argument about rounds alone can tell apart.

An arithmetic that closes on three heaps #

Classes of single heaps are only half of a quotient. The other half is whether they add: whether the class of a position is determined by the classes of the heaps in it, so that a reader holding a letter for each heap can say what the board is without searching it. Nim’s coalition passes that test by its rule, and the earlier essay checked it on positions of up to four heaps. For the five new rulesets it has to be measured.

Every position of up to three heaps — heaps up to ten in the subtraction games and Nim, up to eight in the splitting games — is given two labels: the multiset of its heaps’ classes, and its own record of outcomes against every test. The arithmetic closes if two positions with the same first label always have the same second one. It closes on all six rulesets: not one position breaks it. A position of subtraction {2, 3} made of a heap in class C, a heap in class F and a heap in class J behaves the same way whichever heaps of those classes it is made of.

It also collapses, and the collapse is the absorbing class at work. Subtraction {2, 3} offers 220 ways of choosing the classes of three heaps from its range, and they fall into 28 classes of position; subtraction {1, 3}'s 220 fall into 24; Dawson’s Kayles’s 84 into 10. Most of the combinations contain a heap from the large class, and every one of those is the coalition’s, whatever else is in it. What is left is the arithmetic of the small heaps among themselves — a few dozen elements at most, and ten for subtraction {1, 2}, which is small enough to write out.

Parity against a count of three #

The last comparison is the one the whole construction invites. Two-player play has its own classes of heaps, and they are the Grundy values: every impartial game is a Nim heap, two heaps with the same value are interchangeable in any sum, and two with different values are not. The coalition’s classes are the same idea with three players. It is natural to expect one to be a coarsening of the other.

Subtraction {1, 3} is the sharpest case. Every move takes an odd number of counters, so every move changes the parity of the heap, and the Grundy value of a heap is nothing but its parity: nought, one, nought, one, for ever. To two players a heap of two and a heap of eight are the same heap. To one against two they are not, and nor are any two heaps from nought to nine. A coalition wins or loses by the number of moves modulo three, and a heap’s parity says nothing about that; what the heap offers — how many ones and threes it can be spent as, in what orders — says a great deal.

Kayles goes the other way. Its Grundy values run 0, 1, 2, 3, 1, 4, 3, 2, 1, 4, 2, 6, 4 over the first thirteen heaps and change irregularly for another seventy before settling into a period, which is what Grundy sequences is about. The coalition stops distinguishing Kayles heaps at five.

Counted over pairs of heaps, neither sorting refines the other in any of the five. In subtraction {1, 3} the coalition keeps apart 70 of 210 pairs that Grundy joins and joins 36 that Grundy keeps apart. In Kayles it joins 24 of 78 pairs with different values and splits 6 pairs with the same one. Only Nim is one-sided: every heap past one is a different Grundy value and the same coalition class, so the coalition joins 171 of 210 pairs and splits none. The earlier essay’s picture — a coalition as a coarse version of two-player play — was a picture of Nim. On a rule whose heaps are not all alike, the coalition reads something the two-player value does not carry at all.

What the tables cannot show #

The classes are measured on finite ranges. The counts stop moving before each range ends, and a class can only be split by a larger test and never joined, so what could change is that some class splits under a test beyond the range. That the large class is absorbing is checked against every test in the range, not proved.

The arithmetic is checked on three heaps, not proved for all. That the class of a position is read off its heaps’ classes holds on every position of up to three heaps in each range. A fourth heap could in principle expose a pair of three-heap positions that the tests treat alike and a larger position does not; the absorbing class makes that unlikely for any position containing a large heap, and says nothing about the rest.

And there is no rule a reader could carry. Nim’s coalition has one: two counts and a table. The five new rulesets have arithmetics that close, which means each has such a table in principle, but the table here is found by testing and not derived — the threshold is read off the census, and the early members of the large class are observed rather than explained. A description of subtraction {2, 3} under one against two as compact as Nim’s would have to say why nine behaves like fourteen and ten does not, and nothing on this page does.

How the positions were searched #

Positions are multisets of heap sizes, and a split in Kayles or Dawson’s Kayles replaces one heap by two. The lone player is player one and the team is players two and three. The search is a two-outcome recursion over positions and whose turn it is: at a position with no move the lone player wins exactly when they made the last move; the lone player needs one option that wins and each ally needs one that does not. Every heap and every test position of up to three heaps is searched with each of the three players to move, and a class is a set of positions whose three outcomes agree against every test. Grundy values are computed by the mex rule on the same move lists.

The surprise: the parity game has ten kinds of heap #

The rule that looks simplest on this page is subtraction {1, 3}, and it is the one where the coalition’s view and the two-player view are furthest apart. Two players see a game about parity: every heap is odd or even, an odd heap is a win for the mover, and the whole of the theory is one bit. Three players, two of them allied, see ten kinds of heap below ten counters and a large class that begins at seven, skips eight and nine, and resumes at ten.

That is the clearest statement of what changes when a third player joins. The two-player theory of an impartial game is a theory of who moves last modulo two, and who moves last is where that reading of normal play is set out. One against two is a theory of who moves last modulo three, with one side moving twice per round. A rule designed so that the first count is trivial — every move changes the parity — leaves the second count wide open, because taking one and taking three differ by two, and two is a whole round’s worth of moves to a coalition.

Still open: a rule the size of Nim’s #

Nim’s coalition fits in a table because its classes are generated by two things, a heap of one and a heap that is a store, and the table says how they combine: ones add modulo three, stores add and stop at two. The five rulesets here have arithmetics that close on three heaps, so each has a table of the same kind, and none has been written down. Subtraction {1, 2} is the one to write first — five kinds of heap, ten classes of position of up to three heaps, and a large class that absorbs — and the question to ask of it is whether its table has a description as short as Nim’s, a count of something modulo three beside a count of something up to a cap. If it does, the rule is the thing to try on {2, 3}, where the early member at nine is what any such description would have to account for. If it does not, the coalition’s arithmetic is a finite object with no shorter name than its table, which is what misère quotients usually turn out to be. The sum is the object is the principle the test would be checking, and three players and no answer is where the question of what a third player does to a sum was first asked.