How long it lasts

Other ways to add put three compounds beside each other and asked why the theory picks one of them.

• Disjunctive — move in exactly one component, and the game ends when no component has a move. This is the sum the whole subject is built on.
• Conjunctive — move in every component, and the game ends the moment any one of them ends.
• Selective — move in any non-empty set of components, and the game ends when they all have.

The answer that essay gave is that only the disjunctive one has values that add. It closed by naming what it kept deferring: remoteness, the quantity that does for the conjunctive compound what a value does for the disjunctive one.

What a conjunctive compound is like to play #

Three heaps, and a move consists of taking from all three. When one heap empties, the game is over and whoever cannot complete a move has lost.

That changes what a player wants. In a disjunctive sum the aim is to be the one making the last move anywhere; here the aim is to be the one making the last move at all, and the game ends as soon as the shortest component does. So a player who is winning wants the game short and a player who is losing wants it long — and every component the loser can stretch is a component the winner has to outlast.

Nothing about that is measured by a Grundy value. A Grundy value says which Nim heap a position behaves like in a disjunctive sum, and behaving like a Nim heap of size three says nothing about how many moves the position has left in it.

The number that does measure it #

Define $R(G) = 0$ when $G$ has no moves, which under normal play is a loss for the player to move. Otherwise:

$$R(G) \;=\; 1 + \min\{R(G') : R(G') \text{ even}\}$$

if any option has even remoteness, and

$$R(G) \;=\; 1 + \max\{R(G')\}$$

if none does.

Read the two clauses as the two players’ preferences and they stop looking arbitrary. An even remoteness is a position the mover loses, so a player who can move to one wants to — and wants to get there as fast as possible, hence the minimum. A player with no such option is losing whatever happens, and wants the game to last as long as possible, hence the maximum.

An odd remoteness is a win for the player to move; an even one is a loss.

The theorem, and the check #

The remoteness of a conjunctive compound is the minimum of its components’ remotenesses. The shortest component decides, because it is the one that ends the game.

That is checked rather than quoted. For each of four subtraction games, every triple of heaps up to eight, eight and six — 567 positions a game, 2,268 in all — the compound was solved directly, by building the game over tuples and searching it, and the answer compared with what the rule predicts.

Two thousand two hundred and sixty-eight agreements and no disagreements.

The selective compound needs nothing new #

The third compound is the one a reader expects to be hardest and it is the easiest.

Move in any non-empty set of components, and the game ends when all of them have. A player facing a position in which some component is a first-player win simply moves in all the winning components at once, leaving the opponent a position in which every component is a loss for the mover — and repeats.

So the selective compound is a first-player win exactly when some component is. No new number, no recursion, no table: the outcome classes of the parts decide the whole. Checked over 1,792 positions across the same four games, with no exceptions.

That is a striking thing to find in a subject whose repeated finding is that the parts do not decide the whole. Here they do, and the reason is that the selective rule lets a player act on every component at once, which is exactly the ability the disjunctive rule withholds.

The four sequences, read across #

The sequences are worth reading rather than merely counting, because each one says something the Grundy sequence beside it does not.

Take one, two or three. Grundy values run $0,1,2,3$ over and over — the game is Nim in disguise, and the disjunctive theory of it is finished in a line. The remoteness runs $0,1,1,1,2,3,3,3,4,\dots$: a plateau of three ones, then a two, then a plateau of three threes. The plateaus are the positions from which the mover can finish in one move; the isolated even entries are the multiples of four, which are the losses.

Take one or two. Grundy values run $0,1,2$ and repeat with period three. Remoteness runs $0,1,1,2,3,3,4,5,5,\dots$ — period three again, but the pattern inside the period is different, and the values grow at two-thirds the rate of the heap rather than three-quarters.

Take two or three. Both sequences start with two zeroes, because a heap of one is dead: nothing can be taken from it. That single fact makes the remoteness of a heap of one equal to nought, and a conjunctive compound containing a heap of one is over before it starts.

Take one, three or four. The Grundy sequence has period seven and the remoteness sequence does not settle into anything as tidy inside the range computed — $0,1,2,1,1,3,3,4,5,6,5,5,7$ — going up and down where the Grundy values march. Two quantities from one tree, and only one of them is periodic here.

A worked position #

Three heaps of five, six and seven, in take-one-two-or-three.

Their remotenesses are $3$, $3$ and $3$. The minimum is three, which is odd, so the player to move wins — and the game will last exactly three more moves, because that is what the remoteness of the compound counts.

Their Grundy values are $1$, $2$ and $3$, whose exclusive or is nought. So under the disjunctive rule the same three heaps are a loss for the player to move.

The same three heaps, the same rule table, two ways of adding them: one is a first-player win over in three moves, the other a second-player win. Nothing about the heaps has changed and the two answers are not related.

Neither number determines the other #

The two sequences are computed from the same game tree and neither is a function of the other, which the tables make visible in both directions.

In take-one-two-or-three, heaps of one and five both have Grundy value one and have remotenesses one and three. So knowing the Grundy value does not tell how long the position lasts.

In the same game, heaps of one and two both have remoteness one and have Grundy values one and two. So knowing the remoteness does not tell what the position is worth in a disjunctive sum.

Every one of the four games has pairs of both kinds inside its first dozen heaps. The two numbers agree on exactly one thing: a position is a loss for the player to move if and only if its Grundy value is nought, and if and only if its remoteness is even. That agreement is forced — both are computed from the same win-loss recursion — and it is the whole of the overlap.

Why the conjunctive rule is a minimum and the selective one is not #

The two rules pull in opposite directions and the reason is a single clause about when the game stops.

A conjunctive compound stops when the first component stops, so the shortest component is the clock. Stretching a long component achieves nothing; the game will be over before the extra moves are needed. Hence the minimum, and hence a player wanting to lose slowly has to stretch the shortest one — which is exactly what the parity clause in the recursion arranges.

A selective compound stops when the last component stops, so a player may work on all of them and finish them in whatever order suits. Nothing is a clock, no component constrains any other, and the outcome falls out of the outcomes. Hence no new number.

The disjunctive rule sits between the two and is the hardest of the three, which is worth noticing. It stops when the last component stops, like the selective one, but permits only one component to be touched per move, like nothing else — and that combination is what forces a whole theory of values rather than a rule about outcomes or a rule about lengths. The sum is the object is where that theory begins, and the two compounds here are what it looks like when either half of the disjunctive clause is relaxed.

Where these compounds actually arise #

They are not artificial. Sprouts and several other games decompose into components that must all be advanced, and the classic setting for the conjunctive rule is a race — several tasks, all progressing, the whole finishing when the first does.

The selective compound is the rule for a board where a player may do several things at once, which is unusual in board games and common in the games this theory gets applied to outside them. And the shortened selective compound, which needs the third number, is the rule for a race in which every task may be advanced and the first to finish ends it.

The three of them together are worth carrying because the difference between them in the rules is one short clause, and the difference in what has to be computed is total: a table of values, a table of lengths, or nothing at all.

What the two numbers are each throwing away #

There is a way of seeing why they have to differ, and it is in the two recursions rather than in the games.

A Grundy value is a statement about substitutability: it says the position may be replaced by a Nim heap of that size in any disjunctive sum, which is a claim about how the position interacts with company. It is deliberately blind to length, because length is not preserved by that substitution — heap three and a subtraction position with Grundy value three behave identically in a sum and can take wildly different numbers of moves to play out.

A remoteness is a statement about length under optimal play, with the two players pulling in opposite directions. It is deliberately blind to which Nim heap the position resembles, because that is not what decides a race.

The two recursions say as much about themselves. A Grundy value is a mex over the options’ values — a least number not among them, which is an operation on a set of labels and has no way of asking how far below that set the game has left to run. A remoteness is a minimum or a maximum over the options’ remotenesses, picked by parity — an operation that sees nothing but distance and never asks which labels are missing. Neither operation is given the other’s input, so neither could recover the other’s answer even in principle.

So the two numbers are answers to two questions, and a position carries both. Where the impartial theory stops is where one number per position runs out for partizan games; this is the same lesson inside impartial play, where one number per position runs out as soon as the components are added a different way.

Take-one-three-or-four is where the divergence is easiest to watch, because it is the one game of the four whose two sequences do not even have the same shape. The Grundy values march round a period of seven; the remotenesses fall as readily as they rise, and the first fall happens at the third heap.

The sabotage, and the game where it fails to fail #

A rule that has never rejected anything has not been tested, so the check is run again with the rule deliberately broken, in two ways.

Take the largest remoteness instead of the smallest. The longest component looks like the one that matters — it is the one still going when the others have stopped — and it is the wrong one, because the game is over before it gets there. Broken this way the rule is wrong on 1,120 of the 2,268 positions.

Drop the parity clause and always take the minimum. This is the rule for a game in which the mover only ever wants to finish, and it ignores that a losing player wants to stretch. Broken this way the rule is wrong on 116 positions.

And on one of the four games — take-two-or-three — the second sabotage is wrong on nothing at all. Its remoteness sequence happens to be one where the losing player’s stretching never changes an answer inside the range swept, so a solver tested only on that game would ship the broken rule and see nothing.

That is the argument for four games rather than one, and it is the same finding this site keeps making in different clothes: a test that cannot fail is not a test, and whether it can fail is a property of the pool rather than of the rule.

Why one number per component is such a strong constraint #

The rules on this page all have the same shape — read a number off each component, combine them with a minimum or a parity — and it is worth saying what that shape rules out, because it is what makes the theory portable and what makes it fragile in one specific way.

A rule of that shape can only see a component through its number. Two components carrying the same number are interchangeable for every purpose the rule has, whatever they are made of, however large they are, and whichever ruleset they came from. That is an enormous claim and it is what a number is in this subject: the whole content of the Sprague–Grundy theorem is that such a number exists for impartial disjunctive sums, and the compound theory is the same demand made of two other ways of combining games.

The consequence is that these rules cannot be broken by mixing. A ruleset is not part of the input, so a sweep over components drawn from several games is testing the same statement as a sweep over components from one — it is only testing it on a wider set of number combinations. A rule that survives the wider set was never in danger from the wider set.

And the consequence in the other direction is that a game whose components do not carry a number is outside the theory entirely. Not badly served by it: outside it. There is no approximate version, because the rule has nowhere to put a component it cannot summarise, and the games that break the sum break it here for the same reason and at the same point.

So the compound theory’s portability and its brittleness are one property. It works on anything that reduces to a number and it has nothing at all to say about anything that does not, and there is no middle.

What the sweep cannot say #

All four games are subtraction games with finite subtraction sets, so every component is a single heap and every option removes a fixed amount. That is the simplest possible setting for the compounds and it is where the theory is cleanest.

Nothing here touches partizan games. Remoteness as defined above is an impartial notion — the two clauses are about the mover and the waiter rather than about Left and Right — and the conjunctive compound of two partizan games is a well-defined object whose analysis is not this one.

Nothing here computes the compound of components from different games, which is the situation the theory is really for: a conjunctive compound of a Nim heap and a Kayles row is legitimate and its remoteness is the minimum of two numbers computed in two different games. The sweep uses one game at a time because the direct solve has to know one rule table, and the rule is stated to cover the mixed case without evidence for it.

Where the ladder goes next #

remoteness opens here, with the rule stated, checked and sabotaged. Two rungs stand above it, and both answer a question this page raises by finding the question smaller than it looked.

The number nobody needs computes the suspense number — the third quantity of the compound theory, obtained by running the remoteness recursion with both preferences reversed — and asks what it buys. It governs the shortened selective compound correctly, which is what it is for. So does remoteness. So does the plain Grundy value. And over 1,176 positions the shortening does not change the winner at all, so the compound the third number was invented for is a compound the first two already settle.

That is a genuine deflation and it is the right kind: the quantity is not wrong, it is redundant on everything anybody has measured, and saying so is more useful than adding it to the toolbox.

A compound of two different games then tests the claim this page states and does not check — that the minimum-remoteness rule survives components drawn from different rulesets. It survives exactly: right on all 5,184 mixed pairs and all 7,560 triples. And the reason is worth more than the result. Each rule of the compound theory reads one number per component, and a number carries no memory of which ruleset produced it, so mixing cannot reach the rule at all.

What mixing does damage is the shortcut a reader carries instead of the rule — the habit of guessing from the shape of a component rather than from its number — and that is what the sweep catches going wrong.

The direction neither rung takes is the one this page names last. Remoteness is the length under optimal play, so it answers how long will this take for a whole class of positions. What a value leaves out lists length first among the quantities the equivalence discards, and this is the number that measures it.