Units modulo three, and one choice

Three players cannot share an impartial game the way two can. The theory that makes every two-player position a Nim heap depends on there being a loser whenever there is a winner, and with three players somebody’s preference among the losers has to be assumed before any position has an answer — three players and no answer is the demonstration. What survives a coalition fixed the simplest assumption: player one plays alone, players two and three play as a team whose only aim is to stop player one making the last move. That makes the game two-sided again, and Nim under it has a rule a player can carry. Count the heaps of one modulo three; count the heaps of two or more, and stop at two; nothing else matters.

A coalition counts to three took the same coalition to five more rulesets — three subtraction games and two games that split a heap — and found that each has a finite arithmetic: positions fall into classes that no test position can tell apart, the class of a position of up to three heaps is fixed by the classes of its heaps, and past some size one large heap hands the game to the coalition outright. What it did not do was write any of those arithmetics down. It left the question of whether they have a description as short as Nim’s, and it named subtraction {1, 2} as the place to start.

It does, and the description is Nim’s with one word changed.

Nim’s rule is a shape, not a count #

The rule for Nim reads like two counts. It is better read as a shape with two kinds of heap in it, because that is what can be asked of another game.

A heap of one is a unit: every line of play inside it lasts exactly one move, and nobody decides anything about it except when to take it. Units matter only through their number, and since the lone player moves once for every two moves of the coalition, their number matters modulo three. A heap of two or more is a store, in the phrase the earlier essay used: whoever first touches it chooses whether it lasts one move or more, so it carries a decision about tempo. One store on the board is a decision the lone player may get to make. Two stores are a decision the allies can always keep in hand, and with two on the board the coalition wins whoever moves.

So the shape is: units counted modulo three, beside at most one heap that offers a choice, and any second choice belongs to the coalition. A ruleset has a table of Nim’s size when its positions the coalition does not already own contain at most one heap of the choosing kind, and when the count of units and the kind of that one heap decide the class. Both halves are checkable.

Two refinements make the shape usable on other rules. A heap every line of which lasts exactly k moves, for k larger than one, offers no choice either; it is k units, and it enters the count as k. And a heap that by itself hands the game to the coalition, from every phase against every test, needs no column at all, because the position containing it has already been decided. Everything else is flexible.

Subtraction {1, 2}: the table written down #

In subtraction {1, 2} a move takes one counter or two from a heap — the smallest of the subtraction games, whose two-player values repeat with period three. A heap of one is a unit. A heap of two can be taken in one move or in two, and a heap of three in two or in three; both are flexible. From four upward something different happens.

A heap of four can last two moves, three or four — three consecutive lengths, one of each remainder modulo three — and it is tempting to read that as the reason it is the coalition’s: whatever the count needs, some line of the heap supplies it. The reading is not enough on its own, because a Kayles row of four spans the same three lengths and is not the coalition’s, as the next section shows. What is measured is the fact: every heap from four upward is the coalition’s alone, against every test position of up to three heaps, from every phase. The earlier essay found this absorbing heap in all five of its new rulesets; here it is simply the reason the table stops at three.

What remains are units and the two flexible heaps, and the census of every position of up to five heaps built from them finds the shape exactly. No position the coalition does not own holds more than one flexible heap: a two beside a two, a two beside a three, a three beside a three are all the coalition’s, from every phase. And on every position of up to five heaps, the count of units modulo three together with the flexible heap — none, a two or a three — names the class, with no exception. That is nine classes, each a cell of the hero figure, and a tenth that swallows everything else.

So the answer to the question the earlier essay left is yes, and it can be said in one sentence: count the ones modulo three, note whether there is a two or a three, and if there is anything more the coalition has won. Against Nim’s sentence it differs in one place. Nim has one kind of store and subtraction {1, 2} has two, because a heap of two and a heap of three offer choices between different pairs of lengths — one or two moves, two or three — and a coalition counting modulo three can tell them apart.

The cells themselves repay reading. With no units and nothing else on the board, the only win for the lone player is the phase where the first ally must move from an empty board: the lone player made the last move. A single unit turns that around, so the lone player, moving first, takes it and wins. A heap of two on its own gives the same three results as one unit, since the lone player moving first can take it in one move; a heap of three on its own gives the same results as two units. But the heap of two is not a unit. Add a unit to each and they part company: two units still leave the lone player a win when the second ally is to move, and a unit beside a heap of two leaves the lone player nothing from any phase — the tests separate what the bare board could not.

Kayles folds three into two #

The shape has a second test, and it is a ruleset whose heaps split. In Kayles a move knocks down one pin or two adjacent pins from a row, which may break the row in two; it is one of the octal games, and its two-player values take seventy heaps to settle into a period.

Kayles fits the shape and then simplifies it. Rows of five or more pins are the coalition’s alone. Rows of two, three and four are flexible, and a board the coalition does not own never holds two of them. But the key — units modulo three and the kind of flexible row — has twelve values and only nine classes to land on, because a row of three is, to the coalition, a row of two with a unit beside it. The figure’s first footer lists the three coincidences, and they are one fact: shift the unit count by one and a three becomes a two.

That is a small, clean instance of what misère quotients are for. The quotient identifies positions that play the same in every company, and it can identify them across what look like different kinds of heap. Subtraction {1, 2} does not make that identification — its heap of three offers one line of forced length, the whole heap in two moves, where a Kayles row of three offers two, and the coalition’s table keeps them apart. The two rulesets have the same number of classes, and they got there by different routes.

Four rulesets have the shape, and two do not #

Dawson’s Kayles is the third splitting test — a close relative of the game Dawson’s chess problem turned out to be — and the two remaining subtraction games are the ones where the shape could fail.

Dawson’s Kayles has the shape even though no heap below eleven is the coalition’s alone. Its units are heaps of two and three, which can each be played in exactly one move; a heap of five always lasts two moves and counts as two units; and every other heap is flexible. No position of up to five heaps that the coalition does not own holds two flexible heaps, and the unit count and the flexible heap’s class decide the class on all 266 of them — thirteen classes in all, with six coincidences of the Kayles kind among the keys.

Subtraction {1, 3} and {2, 3} break the shape in the same way. Each has positions that hold two flexible heaps and are not the coalition’s, and in each the short key fails: in subtraction {1, 3}, six positions share a key with a position of a different class, and in {2, 3} eighteen do. The failure is not a matter of bookkeeping that a cleverer key would fix. Three of subtraction {1, 3}'s classes, and ten of {2, 3}'s, contain no position with fewer than two flexible heaps — their every member carries two choices — so a key that names at most one flexible heap cannot name them at all.

The positions in the figure are small. In subtraction {1, 3}, a heap of three can be played as one move or three and a heap of five as three moves or five; put both on the board and the lone player, moving first, wins. In subtraction {2, 3}, a heap of four can last one move or two and a heap of eight three or four, and again the lone player moving first wins. Nim’s reason for the second store belonging to the allies — they move twice to the lone player’s once, so they can always hold one choice back — does not reach these boards. The second choice exists, and it is not the coalition’s to spend.

The same lengths, and different tables #

The natural explanation for which rulesets have the shape is the one this essay has been using informally: a heap matters to a coalition through the numbers of moves it can last, because a coalition wins or loses on the count of moves modulo three. If that were the whole story, two rulesets offering the same menus of lengths would have the same tables.

Subtraction {2, 3} and Dawson’s Kayles are exactly such a pair. In subtraction {2, 3} a move takes two counters or three; in Dawson’s Kayles it removes two adjacent pins and may split the row. A heap of one is dead in both, heaps of two and three last one move in both, a heap of five lasts exactly two in both, and every heap from one to ten offers precisely the same set of possible lengths in the two games. And the tables are not alike at all: one has Nim’s shape with thirteen classes, the other breaks it with twenty-eight, and a heap of nine that belongs to the coalition in one is an ordinary flexible heap in the other.

So a menu of lengths is not what a coalition reads. What the menu leaves out is the order in which the choices fall — who faces each fork in the lines, and when. A split in Dawson’s Kayles leaves two pieces on the board where subtraction {2, 3} leaves one heap, and each piece is a place a later player can choose to move or not; the same lengths are reached through a different sequence of decisions, and the decisions are what the table records. The sum is the object is the principle in its general form: what a component contributes to a sum is its whole behaviour in company, not a summary of its own lines.

Twenty rules, and no line between them #

Two failures in five invite the obvious next step: run the same question over every small subtraction rule, and look for the property of the rulebook that sorts them.

Thirteen of the twenty have Nim’s shape and seven do not, and the two properties that distinguish subtraction {1, 2} from the failures above both fail to sort the rest. Being able to take a single counter is not it: {1, 3}, {1, 4}, {1, 5} and {1, 3, 5} all contain 1 and all fail, while {2, 4}, {3, 4} and {3, 5} lack it and hold. Taking consecutive sizes is not it either: {2, 3} is consecutive and fails, {1, 3, 4} is not and holds. One member of the list is explained: {2, 4} is subtraction {1, 2} played with the counters glued in pairs, so its table is {1, 2}'s table with every heap halved, and the shape comes with it.

The three-size sets are the most suggestive. Adding a size to a failing rule can repair it — {1, 3} fails and {1, 3, 4} holds, {2, 3} fails and {2, 3, 4} and {2, 3, 5} hold — and can also leave it failing: {1, 3, 5} and {1, 4, 5} do not recover. Every three-size set containing both 1 and 2 holds. So a second choice is kept from the lone player by something about the whole set of sizes together, and nothing as simple as one size or one difference names it.

How the positions were searched #

Positions are multisets of heap sizes; a split replaces one heap by two. The lone player is player one and the allies are players two and three, moving in turn. A position is searched with each of the three players to move: where no move exists, 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. Two positions share a class when their three results agree against every test position of up to three heaps of up to ten. A heap is the coalition’s alone when it loses for the lone player from every phase against every such test.

The lengths of a heap are the numbers of moves in the lines of play inside that heap alone, to the end. The census of each ruleset is every position of up to five heaps, drawn from the heaps up to ten that are neither dead nor the coalition’s alone, stopping any branch as soon as a position is the coalition’s. Nim’s census is fifty-one positions and subtraction {2, 3}'s is 392.

The convention every count depends on #

Everything above assumes the one fixed alliance: player one alone, players two and three together, and the aim is the last move. A different alliance — the lone player in second seat, or an alliance that forms only when one player is ahead — would give different classes, and none of them is measured here. The units are counted modulo three because the alliance moves twice for every move of the lone player; a four-player game with the same structure would count modulo four, and nothing on this page says whether its tables would have the same shape.

What the tables cannot show #

The classes are measured against tests of up to three heaps. A larger test could split a class, never join two, so the counts could rise; they cannot fall. The census is of positions up to five heaps on heaps up to ten, so the claim that no board the coalition does not own holds two flexible heaps is a statement about those boards.

The shape is found, not derived. Why a second choice belongs to the allies in four rulesets and not in two is not explained here; the identical lengths of subtraction {2, 3} and Dawson’s Kayles rule out the obvious explanation without supplying another, and the twenty-set sweep rules out two more. The sweep’s own census is smaller than the main one, so a set it places on the shape’s side could still have a failing board with five heaps or larger ones. And the coincidences in Kayles and Dawson’s Kayles — a three that is a two and a unit — are observed on every position counted rather than proved.

Still open: the property of the rule #

Nim, subtraction {1, 2}, Kayles and Dawson’s Kayles share a table because in each of them a second flexible heap is the coalition’s, and thirteen of the twenty small subtraction rules join them. The seven that do not are not picked out by any single size, by consecutiveness, or by the lengths a heap can last, which is the one explanation a coalition counting moves modulo three seemed to offer. What is left is the order in which a rule hands out its choices, and the measurement that could name it is a finer one than this page takes: for each flexible heap, not the menu of lengths but the tree of who picks among them, compared across a failing rule and a holding one with the same menus — {2, 3} against Dawson’s Kayles is the pair to start from, because everything else about them already agrees. If a property of that tree sorts the twenty, the rulebook will say which side a new rule falls on before any census is run. Who moves last is the two-player version of the question, where the count is always modulo two and the rules never have to be consulted; the period is small and the proof does not say so is the reminder that on subtraction games a sweep can be far more regular than any proof yet explains.