What survives a coalition

Three players and no answer takes Nim to three players and watches the theory come apart. A player who cannot win still has to move, and the rules say nothing about which opponent should get the win, so the winner of a position depends on a convention; two reasonable conventions disagree on 56 of the 71 positions swept. The one question no convention touches — can a player force a win against the other two acting together — is answered nobody in 65 of the 71. And the sum theory, the arithmetic the rest of the subject runs on, is gone entirely.

It ends by naming the next question: fix a coalition structure or a scoring rule, and ask what of the two-player theory survives. Each assumption buys back something definite, and they buy back different things. A coalition restores both a winner and an arithmetic, in the smallest form possible. A scoring rule restores a winner and no arithmetic at all.

The test for an arithmetic #

The hero figure is the measurement everything else explains, so it is worth being exact about what it measures.

Two positions belong to the same class when no third position can tell them apart: add the same test position to each, play the whole thing, and the winner is the same every time. That is the definition of equality equal in every company gives for two-player games, and the construction misère quotients use when the ordinary theory fails. If a rule has a sum theory, its classes are the values, and positions sharing a class may be swapped inside any sum.

Run on two-player Nim, the test finds what it should. The forty-five positions of up to two heaps of up to eight fall into sixteen classes, one for each nim-sum from nought to fifteen: the empty board sits with every pair of equal heaps, a heap of one with 2 + 3, 4 + 5 and 6 + 7. That is the nim-sum recovered from nothing but outcomes.

Run on three-player Nim under either convention — the downstream rule or the upstream rule — it finds forty-five classes: no two of the forty-five positions can be swapped in every sum. Whatever three-player Nim is, it has no values, not even coarse ones, over this range. The earlier essay said the sum theory had gone; this is what gone looks like when it is measured.

Run on one player against the other two, it finds six.

One against two #

The coalition game is three-player Nim with a fixed alliance: player one alone, players two and three a team sharing a goal, which is to stop player one from making the last move. It is zero-sum again, so the first theorem applies and every position has a winner from each of the three phases of the turn — the lone player to move, the first ally to move, or the second — and they can all be computed.

What comes out is a complete rule, and it fits in one table. Only two things about a position matter: how many heaps hold two or more counters, and how many heaps of one there are, modulo three.

With only heaps of one on the board, every move removes one heap, so the order of play is fixed and the count decides who moves last: the lone player wins from the phase that puts the last heap on their turn. Three heaps of one with the lone player to move go lone, ally, ally, and the team takes the last; four go lone, ally, ally, lone, and the lone player does. A count of who moves last modulo three replaces the parity that decides two-player play. With exactly one larger heap, the lone player wins by moving — and only by moving — unless the heaps of one number one more than a multiple of three. Moving first, they can take the large heap entirely or cut it to one, which changes the count of ones by one, and one of those two choices leaves the count the allies cannot handle; with a count of one more than a multiple of three, neither choice does. With two or more larger heaps, the coalition wins from every phase.

The rule was checked against the search on every position of up to four heaps of up to nine counters, from every phase: 2,142 checks, none wrong.

The last line is the heart of it, and the smallest case shows it. At 2 + 2 with the lone player to move, there are two kinds of move: take one heap entirely, leaving 2, or cut one to 1, leaving 1 + 2. Against 2 the first ally takes one counter and the second ally the last. Against 1 + 2 the first ally takes the whole heap of two and the second ally the heap of one. Either way the team moves last, and each of its replies spent the choice a heap of two offers — leave something behind or not — at the moment it was needed. The lone player had one such choice to spend and the team had the other.

That is the general point. The allies move twice for each move of the lone player, and a heap of two or more is a store of tempo: whoever touches it can choose whether to leave a heap behind or not, and so adjust the parity of what remains. With one such store the lone player can spend it first; with two, the allies always have one left after the lone player has used the other.

Six classes, and sizes that stop mattering #

The rule explains the six classes directly.

Since only the count of ones and the count of larger heaps matter, every heap of two or more is interchangeable with every other: a heap of two and a heap of eight are the same heap to a coalition, and 2 + 2 is the same position as 7 + 8. Among positions of up to two heaps that leaves six shapes — nothing, one, one and one, one large, one and one large, two large — and the test finds exactly those six, with twenty-eight positions in the last.

Taken over larger positions the test finds one more class and no others. Positions of up to four heaps of up to six, tested against positions of up to three, fall into seven classes, and they are exactly the shapes the rule reads: nothing, one and two heaps of one modulo three with no larger heap; the same three counts beside one larger heap; and everything with two or more larger heaps, which is a single class of 185 positions in that range. Adding positions adds their counts, so the seven classes form a small arithmetic of their own — the counts of ones add modulo three, the counts of larger heaps add and stop at two, and once two is reached nothing else matters. The sum is the object is the principle that values are whatever survives adding; here what survives is seven elements.

That is the reverse of what Nim does. In two-player Nim every heap size is a different value, and the whole theory is the arithmetic of those values. With a coalition, sizes past two carry no information at all, and the arithmetic that remains is counting ones modulo three and counting large heaps up to two. It is a sum theory in the strict sense — the class of a sum is determined by the classes of its parts — and it is smaller than Nim’s.

Why nobody can force a win in sixty-five of seventy-one #

The rule also answers the earlier essay’s convention-free question, and says why its answer was nearly always nobody.

A player who can force a win against the other two together is a lone player who beats the coalition, so the rule decides it. Of the seventy-one positions swept — every three-heap position up to five counters a heap and every two-heap position up to eight — fifty-eight have two or more heaps of two or more, and on those the pair against the one always wins, whoever is taken to be alone. None of them is forcible. The thirteen others have at most one large heap, and six of those are forcible: three heaps of one, two heaps of one, and two heaps of one beside a single larger heap of any size. The other seven are a heap of one beside a single larger heap, the row of the table that has no entry for the lone player in any phase.

So the sixty-five were never a mystery about three-player games in general. They are a fact about large heaps: a position with two stores of tempo on it is a position where any two players together can beat the third, and in a sweep of small Nim positions most positions have two.

A scoring rule in place of a convention #

The other assumption the earlier essay named is a scoring rule, and the natural one keeps the last move’s primacy while giving the second-to-last move something: two points for the last move, one for the move before it, none for the player who made neither. Each player maximises their own score.

A scoring rule could have simply moved the arbitrariness somewhere else — a player might face two moves worth the same to them and different to the others, and then the outcome would depend on how that tie was broken. It does not happen: over all seventy-one positions, with every tie followed both ways, the payoffs are the same. The scoring rule settles the winner everywhere, and the winner it settles is the upstream convention’s, on all seventy-one, and the downstream convention’s on fifteen.

There is a reason no tie can matter, and it makes the result less surprising than it looks. With three players, a player’s own score names the winner: two points means they made the last move themselves, one point means the player after them did, nought means the player before them did. So when a player compares two moves by their own score, they are comparing winners, and two moves with the same score for them have the same winner. The scoring rule gives every player a strict preference over the three possible winners, and a strict preference is all a convention ever supplied. The same would hold with more players under any scoring by recency, since a player’s place in the order of final moves fixes who moved last. What would let ties back in is a rule that pays two places the same — with four players, nought to everyone but the last two movers — because a player on nought could then be indifferent between two different winners, and a convention would be needed again to break the tie. The scoring rule works because it ranks every place, not because it is a scoring rule.

The smallest position with a choice shows which preference this is. At 1 + 2 the first player cannot win. Taking the heap of one, or the whole heap of two, leaves one heap for the second player to take: the second player wins, and the first player has made the move before the last, which scores one. Cutting the heap of two to one leaves 1 + 1, which the second and third players take in turn: the third player wins and the first player scores nothing. A player who would rather finish second than third hands the win to the player who moves next. That is what the upstream convention does. Three players and no answer described upstream the other way round — as rewarding the player who moved before — while its own computation gave the win to the next player; its description now matches its numbers, and the scoring rule is the reason the numbers are the natural ones.

What the scoring rule does not restore #

The winner is settled. The arithmetic is not. The hero figure’s third row is the upstream convention, and so the scoring rule: forty-five positions, forty-five classes. No two positions can be swapped in every sum, and nothing like a value exists over the range tested.

The reason is the one the earlier essay gave for the conventions and it applies unchanged. With three players a move in one component changes whose turn it is in every other component, and it advances the turn cycle by a third rather than by a half; whether a component is good for a player depends on which phase of the cycle the rest of the board leaves it in. A scoring rule decides what each player wants. It does nothing about the phase, and the phase is what a value would have to absorb.

The coalition succeeds for a different reason: it reduces three players to two sides. The turn cycle is still three long — lone, ally, ally — but only two interests remain, and the six classes are what that asymmetric two-sided game leaves.

How the positions were searched #

Heaps are unordered and positions are multisets of heap sizes. The coalition search is a two-outcome recursion with three turn labels: the lone player wins at a position with no moves exactly when they made the last move, maximises when to move and is minimised by either ally. The scoring search carries sets of payoff vectors, lets the mover keep every option that maximises their own score, and reports a tie only if the kept options differ in outcome. The classes use test positions of up to three heaps of up to eight, 165 tests, against positions of up to two heaps of up to eight; two positions share a class when every test gives the same winner — for one against two, the same winner from each of the three phases.

What the tables cannot show #

The classes are measured, and the two results are not equally final. Forty-five classes for the conventions means every pair of positions is already separated by some test; a larger test set can only split classes further, so that result cannot change for these positions. The coalition’s six could in principle split under larger tests. The rule is the stronger evidence there: it names the classes, and it holds on every position checked.

The scoring rule is tested on the earlier sweep only — seventy-one positions — but the argument that no tie can matter holds for every position, since it rests on what a score means rather than on any position’s structure.

Only Nim is tested. A coalition in another impartial game would still reduce to two sides and a three-phase cycle, but whether sizes stop mattering is a fact about Nim’s heaps, and nothing here says what a coalition does to Kayles or to Dawson’s chess.

And only one coalition and one scoring rule are tried. A coalition that changes during play, or a rule that pays by the number of counters each player takes, is a different game.

Still open: a coalition in a game with values #

Nim under a coalition collapses because a heap of two or more is a tempo store that any player can draw on, and every heap past one is such a store. The obvious test is a game whose heaps are not all stores — a subtraction game where some heap sizes leave no choice about what remains, or Kayles, where the value of a heap is set by how it splits. If one against two in such a game has a finite set of classes that is not simply ones and the rest, the coalition quotient is a real object with structure of its own, as misère quotients are for games that misère play breaks; if it always collapses to counting, the collapse is the whole story of what a coalition does to an impartial game.