What a component has to carry

Every impartial game is supposed to be a Nim heap. That is the theorem two people found four years apart, and it is the single most useful fact in the subject: compute one number per component, exclusive-or them, and the board is decided.

Three games on this site are impartial and are not covered by it. Each has a rule under which a component cannot answer what are my legal moves? on its own — it has to be told something about the past, or about the rest of the board. The heap is not the position named the class and left the question standing:

All three break the sum for the same reason — a component that cannot say what its own legal moves are — and what they have in common is a question nobody here has asked.

A quarter, a quarter, and nearly a half. Against a control where the same recipe cannot be wrong.

The numbers are worth reading twice before the mechanisms, because a reader’s expectation is usually one of two things and both are wrong. The pessimistic expectation is that a game outside the theorem is a game the theorem says nothing about, so the recipe should be no better than a coin. It is much better than a coin: three sums in four on two of the three games. The optimistic expectation is that a small departure from the rules produces a small departure from the answer. It does not: a single pass token, added to a game the theorem covers exactly, makes the recipe wrong nearly half the time.

The instrument, and why it is the same one #

Putting three different games on one axis needs the axis to mean the same thing in each, so it is worth being exact.

In every row the recipe is identical: look at each component alone, take the number it carries in isolation, exclusive-or the numbers, and read the outcome off the total — nought means the player to move loses, anything else means they win. For ordinary Nim that recipe is the Sprague–Grundy theorem and is a proof. For the other three it is a recipe applied to a game it was never proved for.

The control row is not decoration. It is asserted in the code: if Nim’s own recipe disagreed with Nim’s own outcomes on any sum, the instrument would be broken and the other three rows would be measuring nothing. It has never fired.

The recipe it is a control on is Sprague–Grundy: every impartial position is equivalent to a single Nim heap, and that equivalence is the whole of why one number per component is enough. A game where the recipe fails is a game where a component is not a number.

An instrument that has been run once has been run on one pool, so it is worth running again on a smaller one before any of its readings are compared.

What differs between the rows is only which number a component carries in isolation, and each choice is the honest one a reader would make.

What each game carries #

It is worth holding on to what a component looks like when it carries nothing. In a subtraction game a heap has one number, that number depends on the heap size and on nothing else, and the sequence of numbers repeats for ever. The three games below lose all three properties together, and they lose them for one reason.

Fibonacci Nim carries a cap. A move may take at most twice what the previous move took, so a heap’s legal moves depend on what was played in that heap last. In isolation, a heap of $n$ is a loss for whoever moves in it exactly when $n$ is a Fibonacci number — that is the whole of the one-heap theory — so the honest number is nought for a Fibonacci heap and one for everything else.

Top Entails carries an obligation. Splitting a heap compels the opponent to reply in one of the two new heaps — and the two new heaps are in this component, so a move here dictates where the whole board answers. In isolation a heap has a naive Grundy value, computed as though the compulsion did not reach outside.

A held pass carries a token. The pass may be used once and may not end the game, so whether it is legal at all depends on whether anything else on the board can move. In isolation, a pass that may be taken freely is exactly a Nim heap of one, so the honest prediction is the nim-sum exclusive-ored with one.

Three different things carried, three different mechanisms, and one instrument.

Each of those three isolation numbers is the right one to use, and none of them is arbitrary. That matters because the measurement would be worthless if the recipe had been handed a number nobody would actually pick: the point is not that some per-component number fails but that the natural one does, and that the natural one is in each case the answer the game’s own one-component theory supplies.

The smallest failures #

Counts say how bad, and the smallest witness says why.

Fibonacci Nim breaks at $4 + 6$. Neither four nor six is a Fibonacci number, so each carries a one, and the recipe says the two cancel and the mover loses. The mover wins. The reason is that the cap crosses no boundary — a move in the four does nothing to the six’s cap — but the timing does: a player forced to make a small move in one heap has their next move in that heap capped, and can play the other heap instead, which no per-heap number records.

Top Entails breaks at $2 + 2$. A game added to itself, which every impartial game without entailing moves settles at nought — copy the opponent in the other heap and always have an answer. That fails here because after a split the reply is compelled to be in the split component, and the mirror image is not a legal answer. A move that must be answered is the essay about that, and its smallest instance is the smallest instance here.

The held pass breaks at a single heap of one against three heaps of one. Both have nim-sum $1$, so under ordinary Nim they are the same game and either may be substituted for the other inside anything. With the pass on the board they are worth $2$ and $0$.

That last one is the sharpest, because it is not a failure of a prediction — it is a failure of substitution. Two positions with the same value are supposed to be interchangeable, and here they are not.

The order, and what it says #

The three failure rates on the pool the first table uses are twenty-six per cent, twenty-five per cent and forty-five per cent, and one comparison among them survives changing the pool and the other does not.

The one that survives is that the pass is worst. It reads forty-five per cent on every pool tried, and it is above both of the others on every one of them.

The one that does not is the near-tie at the top. Twenty-six against twenty-five is not two readings of one scale: on heaps to eight Fibonacci Nim reads seven per cent and on heaps to sixteen it reads thirty-two, so it crosses Top Entails somewhere in between and the ordering of those two is a fact about where the pool was cut. What is stable is that both of them are far better than chance, which is the claim the section makes.

Fibonacci Nim and Top Entails carry something about the component: a cap on this heap, an obligation to reply in this heap. The information is local even though the theorem does not survive it, and on the pools measured here a per-component number gets between two-thirds and nine-tenths of the sums right.

A held pass carries something about the board: whether the pass is legal depends on whether anything else can move, which is a question no component can be asked. That is the most severe of the three failures, and it is the one where the notion of a component has stopped applying rather than merely become inaccurate.

The move that gives counters back is the standing example of a rule that looks like it should break everything and breaks nothing. Set beside the pass, it isolates the property that matters.

What the pass is actually asking about #

The third failure is worth one more turn, because naming the missing information makes it a familiar quantity rather than a mystery.

The clause that does the damage is the pass may not be the move that ends the game. So whether the token is legal right now depends on whether anything else on the board can still move — and that is not a question about values. A heap of one and three heaps of one are the same game, worth $\ast$, interchangeable inside every ordinary sum. They differ in that one of them has one move left in it and the other has three.

The quantity a component would have to carry is its length, and length is precisely what a value is built to discard. What a value leaves out makes that omission a theorem rather than an oversight: length is invisible to every sum, so the equivalence throws it away, and any theory recording it would be separating positions no sum can separate. The held pass is the rule change that makes a sum able to separate them — it reaches into a component and asks is there anything left, which no other rule on this site does.

That reframes the ordering of the three rates. Fibonacci Nim asks a component about its own past and Top Entails asks it about an obligation it created; both are questions a bigger component could answer. The pass asks a component how much life it has left, and the answer is one the value theory deleted on purpose, three layers down, for reasons that were good and that this rule is the price of.

It also explains why the free version breaks nothing. A pass that may end the game asks no such question — it is available whatever else is on the board, so it is a component in its own right, and a component that offers exactly one move is a Nim heap of one. Drop the clause and the token stops being a predicate over the board and becomes a heap, which is the whole difference between a rule the theorem survives and a rule it does not.

Why the sum is what breaks, and not the game #

Each of the three games is perfectly well-defined and perfectly solvable on its own. Fibonacci Nim has a complete one-heap theory with a closed form. Top Entails has a solved heap table. Nim with a pass on one heap is a finite game with an outcome.

What fails is decomposition — the ability to solve the parts and add. The board falls apart is the essay about what decomposition buys, and it is the only exponential saving this subject has: six trees walked separately beat one tree of their product by an enormous margin.

So the cost of carrying state is not a wrong answer. It is a lost saving, and the size of the loss is the size of the whole board’s tree against the sum of its parts’ trees.

What the three cost a solver #

The counts above are about correctness. There is a second cost and it is the one a program feels.

A component in ordinary Nim is a number. A component in Fibonacci Nim is a pair — the heap and its cap — so the table a solver keeps is larger by a factor of the number of caps a heap can have, which is bounded by the heap size. That is a polynomial cost and it is survivable.

A component in Top Entails is a heap plus a flag saying whether the board is currently under an obligation, and the flag is not local: it names which component the obligation is in. So the state a solver stores is a state of the whole board, and the table is over boards rather than over components. That is the exponential cost, and it is the one decomposition exists to avoid.

The held pass is between the two in size and worse in kind. The token is a single bit and can be stored cheaply; what cannot be stored cheaply is the fact that its legality is a predicate over everything else on the board, so the bit cannot be attached to any component and has to travel with the whole position.

The two orderings are not the same, and the disagreement is the useful part. By failure rate the pass is worst and Fibonacci Nim and Top Entails are close together; by state kept, Fibonacci Nim is alone in being cheap and Top Entails is the most expensive of the three, with the pass beside it. So the game whose rate is second-worst is the game whose repair is cheapest, and the game that looks best on the instrument is one of the two that cannot be repaired at all. A rate measures how often a recipe misleads; a state count measures whether anything can be done about it, and no amount of the first predicts the second.

Whether the class has a boundary #

The obvious question is whether carrying something is one property or three, and the honest answer is that this page has not shown it is one.

What the three share is stated negatively — a component cannot say what its own legal moves are — and negative descriptions are cheap. A positive one would name a quantity the component would have to carry instead of a Grundy value, such that the recipe worked again.

For one of the three that quantity exists and is known: a Fibonacci Nim heap with a cap is a well-defined position, so the state $(n, \text{cap})$ is a component and the game over those components is a genuine disjunctive sum. The measurement above is what happens when a reader insists on describing a heap by its size alone.

For the other two it does not. Top Entails’ obligation reaches outside the component by construction, and the pass’s legality is a fact about the whole board. Enlarging the state does not help, because there is nothing local to enlarge it with.

None of this is a question about the operation. The sum here is the ordinary disjunctive one in every row — the same combination values were built for — and it is the components rather than the addition that have stopped being independent.

That split is the most useful thing to take away. Carrying history is repairable by enlarging the state; carrying a fact about the rest of the board is not. The first kind of rule costs a bigger table and keeps the theorem; the second kind costs the theorem, and no amount of bookkeeping inside a component buys it back.

What the counts do not settle #

The pools are small and deliberately so: pairs of heaps up to twelve for Fibonacci Nim, up to six for Top Entails, and every heap list the pass census enumerates. Nothing here says what the failure rates look like at scale, and a rate measured over pairs is not a rate over boards with six components.

Worse than small, the pools are not the same pool, and only one of them answers to the size the table is asked for.

That is a limit of the instrument rather than of the games, and it is worth stating plainly because it is invisible in a table that quotes one rate per row. Three of the four rows were asked one question each; the fourth was asked three, and it gave three answers.

The Fibonacci Nim version is a modelling choice and the essay should not hide it. A sum of Fibonacci Nim heaps needs a decision about whether the cap is per-heap or shared across the board, and this measurement uses per-heap, because a shared cap is not a disjunctive sum at all — a move in one component would change the legal moves in another. The shared-cap game is a different and harder object, and nobody has solved it here.

And the three rates are not directly comparable as numbers, only as an ordering. They are measured over different families of positions, and a family with more easy sums in it will show a lower rate for reasons that have nothing to do with the rule.

The convention, named #

Normal play throughout: the player unable to move loses. Every outcome quoted was obtained by solving the position — the whole sum, not the parts — under that convention, with the state each game carries tracked explicitly through the search.

The held pass is the held version specifically: a player may take the pass at any time, it may be taken only once, and it may not be the move that ends the game. A pass is not a move is where the two versions are separated, and the free version — where the pass may end the game — is exactly a Nim heap of one and breaks nothing.

Where the ladder goes next #

memory opens here with the class named and one instrument pointed at all of it.

The rung above answers the positive question this page could only pose, on the one game where an answer exists. What restores the theorem re-indexes the Fibonacci Nim recursion on the pair of heap size and cap rather than on the heap size alone, and the recipe becomes exact on every pair and every triple — the theorem is not weakened by the rule, it was being applied to the wrong object. The number a heap of nine carries turns out to be five rather than the one this page’s isolation reading gives it, which is the measure of how much the honest-looking per-heap number was throwing away.

That result also sharpens the split this page ends on. Fibonacci Nim’s state is repairable because the cap belongs to the heap; enlarging the component restores everything. Top Entails’ obligation names another component and the pass’s legality is a predicate over the board, so there is nothing local to enlarge, and no re-indexing will do for them what it does here.

Beyond that is the general question, and it is a question about rule tables rather than about positions: which rules let a component state its own legal moves? The three here fail it in two different ways, and stating the condition in general is the kind of result that would let a reader classify a new game by reading its rules.

Two neighbours are worth the trip. The heap is not the position is where the class was named, and where the one-heap theory of Fibonacci Nim is complete and beautiful. And a pass is not a move is the sharpest of the three failures, where two positions with the same Nim value are told apart by a single token.