A compound of two different games

The number nobody needs worked out what the suspense number governs, found it governs the shortened selective compound and that remoteness governs it equally well, and closed by naming the objection every rule on the page invites:

Real broken boards are not all one game, and every rule here is stated for a compound of one. Whether the minimum-remoteness rule survives components from different rulesets is a computation this machinery could make with a different pool, and it is the question a solver author would actually ask.

The computation has been made and nothing breaks. That is the answer, and taken alone it is a dull one; what makes it worth a page is why nothing breaks, and what does.

The sweep #

Eight subtraction games: take one, two or three; take one or two; take two or three; take one, three or four; take one or four; take two, four or five; take a square number; take a Fibonacci number. Every ordered pair of them — sixty-four cells, including the eight pure ones — with heaps running from the smallest legal size up by eight.

That gives 5,184 positions with a move available in every component, which is the class the rules are stated for. Fifty-six of the sixty-four cells are genuinely mixed and eight are the pure diagonal, which is what makes the pure and mixed error rates in the last section comparable: the same rule, the same heaps, the same solver, and the only difference is whether the two components obey the same table. Each is solved directly: the compound is built as a game over tuples and searched, with no rule assumed anywhere in the computation.

Three rules are then asked to predict the answer:

• the conjunctive compound, where every component must move and a player who cannot move in some component loses, is claimed to go to the mover exactly when the smallest remoteness is odd;
• the shortened selective compound, where a move is a move in any non-empty set of components and the game stops as soon as any component stops, is claimed to go to the mover exactly when some component has an odd suspense number;
• and the same, with remoteness in place of suspense.

All three are right on all 5,184. Triples are the same story: 7,560 positions across every unordered triple of the eight rulesets, 2,160 of them with three different rules in play, and the minimum-remoteness rule is right on every one.

Why nothing breaks #

The rules are not robust because they are strong. They are robust because of what they look at.

Remoteness is a function of one component: how long that component lasts under play in which the player who is winning it hurries and the player who is losing it stalls. It is computed by a recursion inside the component and it depends on nothing outside. The same is true of the suspense number and of the Grundy value.

And a number does not remember where it came from. Once a heap of five in the game take one, three or four has been given remoteness 3, the rule that compares remoteness across components has no way of asking which game produced the 3, because the 3 is all it is given.

So the rules cannot break under mixing, in the way a statement cannot be falsified by a variable it does not contain. The computation above is a check that the compound solver and the component recursions describe the same game, and it is worth having for that reason; it is not evidence that the rules are deep. It is the same shape of reassurance the disjunctive sum gets from Sprague–Grundy: the theorem is about numbers, and numbers travel.

The interesting consequence is the converse. Any rule for a compound that does break under mixing must be reading something other than a per-component quantity — and the rule a reader actually uses is exactly such a rule.

The habit that does break #

Ask a player which component of a conjunctive compound decides it and the answer is the one that ends first, and the way they will find it is by looking at the heaps: the smaller heap ends sooner.

That is right 96.3 per cent of the time when both components obey the same rule. Across two different rules it is right 90.6 per cent of the time — an error rate of one in eleven against one in twenty-seven, so mixing roughly triples it.

The failures are easy to see once the sequences are on the page. A heap of five in take one, two or three has remoteness 3; a heap of five in take two, four or five has remoteness 1. So a compound of a five and a six is decided by the six if the six is drawn from the second game, and the shortcut compares the wrong pair of numbers.

Within one ruleset the shortcut survives because remoteness is nearly monotone in the heap — which is the same near-monotonicity that makes the single-ruleset rule feel like arithmetic — it climbs in steps, so a smaller heap usually has a smaller remoteness. Across rulesets there is no reason for it to be, because the steps are at different places and of different heights.

What mixing damages is therefore not the theory but the intuition the theory replaces, and that is the useful form of the finding for anybody writing a solver: the number to carry per component is the remoteness and not the size, and the difference only shows up once the components stop being the same game.

Why the shortcut is right at all #

Nine cases in ten is a high hit rate for a rule that is wrong in principle, and it is worth saying where it comes from rather than treating it as luck.

Remoteness counts moves, and a heap of n in a subtraction game with smallest element d cannot last more than n/d moves or fewer than one. So the remoteness of a heap is bounded above and below by functions of the heap size, and the bounds are not far apart for the games here — every subtraction set in the sweep has 1 or 2 as its smallest element.

Two heaps whose sizes are far apart therefore have remotenesses that are usually ordered the same way, whatever the rules. The shortcut fails when the sizes are close, or when the two smallest elements differ, and both of those are common enough to give one failure in eleven and not common enough to give more.

That is a description of when to distrust it, which is more useful than the percentage: compare heaps only when the two games take in similar-sized bites, and never when the sizes are within a bite of one another.

A rule that would have broken #

To see that the survival is about the shape of the rules rather than about compounds being easy, it helps to have a rule that mixing does destroy, and one is available without inventing anything.

Take the conjunctive rule and state it the way a reader of one ruleset would: the mover wins when the smallest heap is not a multiple of four. That is exactly right in take one, two or three, where the remoteness of a heap is 2⌊n/4⌋ plus one unless four divides it, so the parity of the remoteness is decided by divisibility by four alone. It is a correct rule, checkable, and it makes no mention of remoteness at all.

Put a component from take two, four or five beside it and the rule collapses. That game’s remoteness sequence runs 0 0 1 1 1 1 1 2 2 3 3 3 3, which has nothing to do with fours, and the rule’s prediction is wrong on well over half the cells of that column.

The difference between the two rules is where the ruleset enters. The remoteness rule mentions the ruleset once, inside the definition of remoteness, and then never again; the divisibility rule has the ruleset baked into a constant. A rule with a constant in it is a rule about one game wearing the clothes of a rule about compounds, and mixing is precisely the test that undresses it.

That is the general form of what this page found, and it is worth more than the counts: a compound rule survives mixing exactly when the only thing it knows about a component is a number the component computed for itself.

What the shortened compound adds #

The second rule in the table is the one the previous rung established and immediately undercut: the suspense number governs the shortened selective compound, and so does the plain remoteness, because the two never differ in parity.

Mixing does not disturb that either, and the coincidence survives across rulesets that have different suspense sequences. So the shortened compound has three quantities that all decide it — suspense, remoteness and, through the selective compound it shares a winner with, the Grundy value — and none of them is the one the compound was named for.

The reason this is worth restating here is that mixing is the natural place a coincidence of that kind would break. Two quantities that agree in parity inside every one of eight rulesets might easily disagree once a compound has one of each, and they do not: 5,184 positions, three rules, no exception.

A coincidence that survives being mixed is a coincidence with a reason, and the reason is presumably that both recursions alternate the same way — each adds one per move and each is odd exactly when the mover wins the component alone. Stating that properly is a proof and not a sweep.

What a solver should carry #

The practical form of all this is one sentence and it is worth extracting, because it is what the rung below said a solver author would actually ask.

Carry the remoteness, not the size. A component of a conjunctive compound needs one number and that number is its remoteness; the size is a proxy that costs nothing to compute and is wrong once in eleven when the components are different games. Carrying the size and comparing is the ordinary implementation and it is the ordinary bug.

The cost of carrying the right number is the recursion that computes it, which for a subtraction game is a pass over the heap sizes below and is cheap. For a game whose components are positions rather than heaps it is a search, and then the comparison starts to cost what an evaluation costs — at which point the shortcut becomes tempting again for the reason shortcuts always do.

And the second sentence: a compound of two games is not harder than a compound of one. Nothing in the sweep took longer, nothing needed a new rule, and no cell of the sixty-four behaved differently from the eight on its diagonal. Mixing is a stress test the theory passes, and it passes it for a reason that is visible in advance.

An unfalsifiable test is still worth running #

A sweep that could not have failed is usually a wasted sweep, and this one is an exception worth defending, because what it establishes is not about the rule.

The rule reads one number per component and combines the numbers. A ruleset is not one of its inputs, so no arrangement of components from different games can present it with an input it has not already seen. The pass was guaranteed before the first position was evaluated.

What the sweep is really testing is the claim that the rule has that shape — that the implementation does read only the number, that nothing about a component’s origin leaks into the combination, and that the numbers computed for two rulesets are commensurable in the first place. Any of those could be false in an implementation while the mathematics is fine, and a mixed sweep is the direct way to find out.

It also tests the reader. The habit a reader develops is to reason about a component from its shape — this is a heap, that is a strip, this one is nearly exhausted — and those habits are not commensurable across rulesets. A mixed compound is where they break, and the sweep’s real output is the demonstration that the rule survives what the intuition does not.

So the right way to report a result like this is with the argument rather than with the count. The count says the implementation agrees with the mathematics; the argument says why no count could have said anything else — and quoting the count alone would suggest a fact about games where there is only a fact about arity.

What the sweep does not say #

Three limits, and the first is the one that most narrows the claim.

Every component is a subtraction game. Eight different rule tables is a real spread — the sequences on the page share no pattern — and it is eight instances of one kind of game. A compound with a Nim heap in one component and a Toads and Frogs strip in another is a fair reading of different rulesets and is not what was swept, because the compound solver here works over heaps.

Only positions with a move in every component are counted. That is the class the conjunctive rule is stated for, and a compound with a stopped component has already ended, so the restriction is definitional rather than convenient. It does mean the counts are not counts of all tuples.

The three rules are three rules and not the theory. A compound has a full analysis in the same sense a disjunctive sum does, and what has been tested here is the outcome rule for each of three compounds. Whether anything richer — a value, a comparison, a substitution licence — survives mixing is a question this page does not touch, and for the conjunctive compound there is no such richer object on this site to test.

And the shortcut’s error rate is a property of this pool. Ninety per cent against ninety-six is a comparison between the mixed and pure cells of one sweep, with heaps running eight above the smallest legal size. A pool with wilder subtraction sets in it — one whose smallest element is five, say — would separate the two much further, and one with eight near-identical sets would not separate them at all.

The convention, named #

Normal play throughout, and the compounds are the ones three ways to add the same games sets out. In a conjunctive compound a move is a move in every component and a player unable to move somewhere loses; in a selective compound a move is a move in any non-empty set of components; the shortened selective compound is the selective one with the game ending as soon as any component ends.

Remoteness is computed by the recursion with the winner hurrying and the loser stalling; the suspense number by the same recursion with both preferences reversed. Every compound outcome is computed by direct search over tuples of heap sizes, with each component keeping its own subtraction set, and the rules are asked to predict the result rather than being used to produce it.

Where the ladder goes next #

The remoteness anchor has three rungs: the rule stated, checked and sabotaged; the fourth quantity and what it decides; and now what happens when the components stop being the same game.

The rung above is the one this page had to leave out. Every component here is a subtraction game, so different rulesets means eight different rule tables over the same kind of position. A compound one of whose components is a Nim heap and another a strip of Toads and Frogs is the honest version of the question, and it needs a compound solver that works over positions rather than over numbers — which this site has for the disjunctive sum and does not have for the other two.

Two neighbours are worth the trip. The number nobody needs is the rung below, where the suspense number is computed and found to decide nothing that remoteness does not. And independence is a claim is the same scepticism applied to the disjunctive sum: there the question is whether the parts are parts, and here it is whether the rule cares what kind of part they are.