What a component would have to carry

The first essay on the pass ended with a proposal. A held pass — one token, usable by either player, never as the last move — breaks the rule that a sum of impartial games is worth the nim-sum of its parts, because whether the pass is legal depends on whether the whole board is empty. A Grundy value summarises a component for every question the disjunctive sum can ask, and “is anything else left?” is not one of them. So carry one more bit with each component, saying whether it is empty, and perhaps the held pass becomes a function of the summaries again.

Three heaps and a pass showed that on Nim heaps alone the losing positions have no known formula once there are three of them. That is a statement about Nim. The proposal was about components in general, and it can be tested without solving anything: collect components from several rulesets, put each beside every small company with a held pass on the board, and count how many different behaviours there are.

What “enough” means here #

A summary of a component is enough for the held pass when any two components with the same summary can be swapped in any position without changing who wins with the pass on the board. That is the notion of equality the rest of the subject uses, restricted to one question — the same move equal in this company makes when it replaces “every game” by a smaller set of companies — and it has a finite test. Two components are separated when some company, added to each with the pass still unspent, gives a win on one side and a loss on the other.

The pool is every Nim heap, every Kayles row and every heap of Dawson’s chess from one to eight counters or pins: twenty-four components. The companies are the empty board and every sum of one or two pool members, which is three hundred and twenty-five. Two components are put in one class when all 325 companies agree on them. That gives a count of classes — fifteen — and it is a lower bound, since a larger company can only split classes further and never join them.

Against that count stand the summaries. Twenty-four components take nine Grundy values between them. Every one of them is non-empty, so “Grundy value with an empty bit” also gives nine. And the pair (Grundy value, value with a held pass of its own) takes fourteen distinct values. Fifteen classes, fourteen pairs, nine values: every short summary falls short.

The Grundy value is not enough #

The most striking failure is the first, because it involves two games that are equal in the strongest sense ordinary theory has.

A Nim heap of one counter and a row of eight Kayles pins are both worth $\ast 1$. Without a pass they are interchangeable in every sum there is — that is what the Sprague–Grundy theorem promises, and it is the reason a Grundy value is worth computing. With a held pass beside a Nim heap of two, one sum is lost and the other won.

The Nim side is the two-heap rule of the last essay: heaps of one and two are a pair $(2k-1, 2k)$, so the mover loses. The Kayles side differs because the row of eight has a completely different option structure underneath its value. Its eight options take Grundy values from nought to six, several of them splits into two rows, where the Nim heap has a single option. The Grundy value is a mex over option values and forgets the options themselves; the held pass needs some of what was forgotten.

The empty bit does not help, because both components are non-empty. So the proposal of the first essay fails on its first pair, and it fails with the smallest company there is beyond the empty board.

Two numbers are not enough either #

The natural repair is to carry the component’s own held-pass value alongside its Grundy value — what it is worth with a pass beside it and nothing else. That separates the Nim heap of one (held value 2) from the Kayles row of eight (held value 4), and it is the pair of numbers anybody would try next.

It fails too. Kayles rows of three and six agree on both numbers — each is worth $\ast 3$ without a pass and $0$ with one — and a company of two Nim heaps, six and eight, separates them. The pair of numbers is the fourteenth summary for fifteen classes, and this pair of components is the difference.

The witness is worth reading as a statement about sums. With a pass beside it alone, each row is worth nought: the mover loses, which means every move, including spending the pass, hands the opponent a win. Add two Nim heaps and the pass now has somewhere else to be spent — beside heaps whose nim-sum is fourteen — and the question of when to spend it is decided by how the play in the Kayles row interleaves with the play in the Nim heaps. Rows of three and six interleave differently, and no single number computed from either row on its own records how.

The two witnesses, played #

A separation is a claim that one sum is won and another lost, and a claim like that is only as convincing as the winning move behind it. Both witnesses have short ones.

In the first pair, the Nim heap of one beside a Nim heap of two is the two-heap loss $(1, 2)$, and nothing more needs saying. The Kayles row of eight beside the same heap of two is won by a single move inside the row: knock down the third pin, leaving rows of two and five. That leaves three components and an unspent pass, and every reply loses. The move is available because a row of eight has eight different options, several of them splits into two rows, and one of those splits happens to produce a position the pass cannot rescue. A Nim heap of one has exactly one option, the empty heap, and so has nowhere to go that could do the same.

In the second pair, the row of three wins by becoming a row of two, and the row of six has no winning move at all. Both rows are worth $\ast 3$ and both are worth nought with a pass of their own; the difference is entirely in which positions their moves reach once there are two Nim heaps beside them. Neither winning move spends the pass. In both witnesses the pass matters as a threat — a move the opponent would like to make and cannot use profitably — and never as a move actually made.

That last observation is the clearest way to see why a number per component cannot be enough. A threat is a property of the whole board, because whether spending the pass is good depends on the nim-sum of everything that is left, and every component contributes to that nim-sum through its own later moves. A summary computed from one component alone has to anticipate every way its moves can combine with a pass that some other component’s position will make good or bad to spend.

The gap grows with the pool #

One pair of components is a counterexample. Whether it is an isolated one or the first of many is a question about counts, and the counts can be taken at every pool size.

Up to components of size seven the pair of numbers accounts for every class — twelve classes and twelve pairs over twenty-one components. From size eight the classes pull ahead: fifteen against fourteen, then eighteen against seventeen, twenty-one against eighteen, twenty-four against twenty-one, twenty-seven against twenty-three at size twelve. Every count is taken with companies drawn from the same pool, so a larger pool is also a larger set of companies, and every gap here is a floor rather than a measurement of the true gap.

The Grundy values fall behind much faster, which is expected: Kayles and Dawson’s chess have small, periodic values, so dozens of components share a handful of nimbers. What was not expected, and what the figure is for, is that a second number does not close the distance. It narrows it and then lets it widen again.

Which rulesets need more than two numbers #

The pool mixes three rulesets, and it is fair to ask whether the extra classes come from any one of them or only from mixing.

Three answers, and each says something different.

Nim on its own needs one class per heap — ten heaps, ten classes, ten Grundy values. A Nim heap is its own value, and the held pass reads nothing a heap does not already say. That is the fact the one-heap and two-heap formulas rest on, and it is why the difficulty on three Nim heaps is a difficulty of combination rather than of any component.

Kayles on its own is described exactly by the pair of numbers — seven classes, seven pairs. On its own, then, a Kayles row carries nothing beyond its Grundy value and its held-pass value that the pass can detect among other Kayles rows.

Dawson’s chess on its own already fails: seven classes against six pairs. There are two Dawson heaps with the same Grundy value and the same held-pass value that some company of other Dawson heaps separates. So the failure is not an artefact of mixing rulesets. It happens inside a single octal game, among components that differ only in size.

And every mixture — Nim with Kayles, Nim with Dawson, Kayles with Dawson — needs more classes than pairs. Mixing adds classes beyond what any single ruleset needs, which is what the widening gap in the growth figure was measuring.

Where the extra classes sit #

Read by value, the classes say where the confusion lives. Of the nine Grundy values in the pool of twenty-four, $\ast 1$ and $\ast 3$ each split into three classes and $\ast 2$ and $\ast 4$ into two, while the five others stay whole. The split is concentrated in the small values, and that is where the rulesets overlap: Kayles and Dawson’s chess take the values nought to four over and over, while Nim heaps of five to eight are the only components worth $\ast 5$ to $\ast 8$ and so have nothing to be confused with. A value that stays whole here stays whole only because the pool contains no second component of that value, which is a fact about the pool and not about the value.

That is also why the Nim-only row of the table has no extra classes and says nothing reassuring. Three heaps and a pass is hard not because a Nim heap needs more than its size — it does not — but because three sizes combine in a way no rule has been found for. Here the components themselves are the problem, before any combining happens.

One move down is enough, so far #

If two numbers fail, the obvious question is what does not. The richest summary of a component is the component itself, which trivially suffices and is useless. Between the two there is a natural next step: keep the component’s two numbers, and add the two numbers of each of its options — one level of the game tree, summarised.

On every pool computed, that summary is enough. At components up to twelve, thirty-six components fall into twenty-seven classes, the pair of numbers takes twenty-three values and so must merge at least four classes, and the deeper summary takes thirty values and merges none. Every pair of components that the held pass separates has a different set of option pairs.

Two cautions go with that. First, the deeper summary overshoots: thirty summaries for twenty-seven classes means some components that behave identically under the pass have different option structures one move down, so the summary is sufficient here without being the right one. Second, sufficiency on a pool of thirty-six is not a theorem. The pair of numbers was sufficient on every pool up to size seven and failed at eight; the deeper summary may fail at some larger size in exactly the same way, and a second level of depth would then be the next thing to try. What the measurement establishes is a floor — a held pass needs at least one move of look-ahead into each component — and not a ceiling.

Why this is the misère story again #

The shape of all this is familiar from misère play, and seeing the resemblance explains the result better than the counts do.

Under misère play — the last player to move loses — a Grundy value also stops being enough, and for the same kind of reason: the ending condition asks about the whole board at once. The response the subject eventually found was not a better number but a finite algebra computed for one game’s own positions, the misère quotient, whose size depends on which components are allowed and grows as more are. The classes counted here are exactly that construction applied to a held pass: an equivalence on components relative to a set of companies, finite for each pool and growing with it.

That is the surprising connection. Entailing moves break the sum in a similar way, by making one component’s move constrain the reply elsewhere, and a held pass looks like a small normal-play variation — one token, and a restriction on when it may be used — and the theory it calls for looks like the theory of misère play. Both conventions add a condition that consults the whole position at the moment the game ends, and any condition of that kind turns a local summary into a contextual one. What misère play costs measured that cost for misère play; the counts here are the same measurement for a pass.

The convention named #

Everything above is normal play with one shared pass, which may be spent by either player at any time except when every component is empty. The pool is fixed: sizes one to eight, three rulesets, companies of at most two components. Every count is relative to those choices, and the direction of the dependence is known: larger companies can only split classes, so a larger study could find more classes and never fewer.

What counts as “the same” is outcome under the held pass, which is the coarsest notion that matters for play. Two components in one class may still have different Grundy values with the pass in some company, and a finer relation would count more classes again.

What the counts cannot show #

A class count says how many behaviours there are, not what distinguishes them. The witnesses name one company that separates each failing pair, and nothing here identifies the property of a Kayles row of six that a row of three lacks. The obvious candidates — the number of moves, the longest play, the value after the first move — were not tested, and the result that two numbers fail does not rule out that three well-chosen ones succeed on this pool.

Nor does the growth figure say the classes grow without bound. It says they grow as far as the pool reaches, twenty-seven at size twelve, with the gap to the pairs still widening. Whether some finite set of numbers per component would eventually account for every class — a finite quotient, in misère language — or whether the count is unbounded in the pool is exactly the kind of question the misère theory answers game by game and not in general.

Still open: the classes as an algebra #

The classes are an equivalence on components. For the held pass to be computed from them, they would also have to combine: the class of a sum would have to be a function of the classes of its parts, in some finite multiplication table, as a misère quotient’s classes combine. That is a stronger property than being an equivalence and nothing here tests it.

The test is direct and is the natural next measurement. Take two classes, pick members of each, add them, and check whether every choice of members lands in the same class. If it always does, the held pass has a quotient on this pool and the first essay’s hope survives in a changed form — not one extra bit, but a finite table. If it does not, the held pass is further from the theory than misère play is, because misère play at least has that. The worked separation of three from one and two, repeated below, is the smallest place such a table would have to begin.