What a tame heap may be replaced by

The genus is a Grundy value with a tail: the misère values of a position with 0, 1, 2, … heaps of $\ast 2$ added to it. A game is tame when the symbol that comes out is one a Nim position has, and wild when it is not — and the rung below computes the classification for seven games and finds where each first goes wild.

A classification is only worth having for what it licenses. What tameness licenses is a substitution: a tame position may be replaced, inside any misère sum, by a Nim position with the same genus, and the answer does not change.

Why a substitution is the thing to want #

Under normal play the substitution is total and nobody thinks about it. Every impartial position equals a Nim heap, the heap is found by the mex rule, and a sum is read by adding heap sizes with exclusive or. The whole theory is one substitution theorem, and its consequence is that a position can be replaced by a number and then forgotten.

Misère play takes that away. There is no zero — a position and its copy do not cancel — so nothing can be replaced by anything on the strength of a value, and a sum has to be solved as itself. The genus is the attempt to recover part of the licence: not “every position is a Nim heap” but “these positions are, and here is the one each of them is”.

That is why the classification is only interesting as a permission slip. “Kayles’ heap of eight is tame” is a fact about a symbol; “Kayles’ heap of eight may be replaced by two Nim heaps of two and three, in any misère sum” is a fact a player can use, and the second is what the census tests.

The substitution nobody would guess #

Kayles’ heap of eight is worth $\ast$ under normal play. Two heaps of eight therefore cancel: $\ast + \ast = 0$, second player wins, and under normal play that is exactly right.

Under misère it is a second-player win as well — but not for the reason the substitution suggests. Two heaps of one are a first-player win under misère, so if the heap of eight really behaved like a heap of one, two of them would be a first-player win too. They are not.

$2 + 3$ explains it. Two Nim heaps of two and three have nim-sum $1$, so they behave like $\ast$ in normal play; under misère, a position with a heap of two or more follows the ordinary rule rather than the reversed one, and two copies of $2 + 3$ come out a second-player win. The genus records exactly the distinction the Grundy value throws away.

The tail, read slowly #

The genus symbol is a head and a tail, written $g^{g_0 g_1 g_2 \ldots}$, and the tail is where the misère information lives.

The head $g$ is the ordinary normal-play Grundy value. The tail entries are the misère Grundy values of the position with $0, 1, 2, \ldots$ copies of $\ast 2$ added — each of them a separate exhaustive search, each of them an answer about a different board. The sequence settles into a period, the symbol prints the prefix before it settles, and the whole thing is a finite description of an infinite family of answers.

Why $\ast 2$ and not $\ast$ or $\ast 3$? Because adding $\ast 2$ is the smallest perturbation that changes the misère regime: it puts a heap of two or more on the board, which is the condition the misère Nim rule turns on. Adding heaps of one would produce a different classification and, as the rung below records, the site’s own prose once described the tail that way and was wrong.

A Nim heap of one has genus $1^{031}$: worth $\ast$ in normal play, worth nothing in misère play by itself, and worth $\ast 3$ once a $\ast 2$ is present. Kayles’ heap of eight has genus $1^{13}$: worth $\ast$ in normal play and worth $\ast$ under misère as well. Those two first tail entries are the entire difference, and they are what the three failing Kayles pairs turn on.

Checked as a substitution, not as a label #

The test is not whether the symbols match. It is whether replacing the heaps by their Nim positions gives the right answer for a sum, which is the only thing a misère theory is for.

Every pair of tame heaps was solved twice: once as the real game, by full search over the misère recursion, and once as the Nim position obtained by substituting both heaps. The Nim answer comes from the misère Nim rule — with a heap of two or more, the second player wins when the nim-sum is zero; with every heap at one, the rule reverses.

Kayles: 28 of 28 correct. Dawson’s chess: 36 of 36. The octal game $\cdot 6$: 36 of 36. The subtraction game $\{1, 2\}$: 45 of 45. Against that, substituting the Nim heap of the same normal-play value is right on 25 of Kayles’ 28, and on every pair of the other three — because none of those three has a heap whose genus belongs to no single Nim heap in this range.

Two games agreeing is not much of a test, and it is worth knowing whether the census contains a game on which the naive rule could not possibly go wrong. It does, and saying so is what keeps the Kayles result from being read as a general defect.

What the three failures look like from the board #

The three Kayles pairs the naive substitution gets wrong are $1 + 8$, $4 + 8$ and $8 + 8$, and they are worth walking rather than counting.

Kayles is the octal game $\cdot 77$, whose Grundy sequence is periodic with period twelve from heap 72 onwards: a row of skittles, and a move knocks down one skittle or two adjacent ones, splitting the row. A heap of eight is a row of eight skittles, and its normal-play value is $\ast$ — one Nim heap of one, as far as normal play is concerned.

Under misère, $8 + 8$ is a second-player win. If the heap of eight really behaved like a Nim heap of one, then $8 + 8$ would behave like $1 + 1$ in Nim, which under misère is a first-player win — take one heap and hand the opponent the last move. The prediction and the answer differ, and they differ on the position a player is most likely to reason about by cancelling.

Substitute $2 + 3$ instead and the arithmetic works out: $8 + 8$ becomes $2 + 3 + 2 + 3$, a Nim position with heaps of two or more and nim-sum zero, which under misère is a second-player win. Same answer as the search, by a rule instead of a search.

The lesson generalises past Kayles. Cancellation is the operation misère play is worst at, because a position and its copy cancelling is exactly the fact misère play removes — and it is the operation a player reaches for first.

What the wild heaps stand for #

Nothing, and that is the content of the word.

A wild heap’s genus is a symbol no Nim position carries, so there is no Nim position to substitute. Kayles’ heap of five has genus $4^{146}$; heap nine has $4^{046}$; Dawson’s heap of nine has $3^{1431}$. In each case the tail is not the tail of any Nim position, and every pair containing such a heap has to be solved as itself.

That is what the whole apparatus is for. Under normal play a position may be replaced by an equal one inside any sum, and the replacement never has to be justified twice; under the reversed convention that licence is withdrawn wholesale, and every sum has to be computed as itself. The genus is what is left of the licence once it is restricted to the positions it still works for — which is what makes tame a useful word rather than a compliment, and what makes wild a statement about an empty column rather than about a difficult game.

What the census cannot see #

Two heaps is where the check stops and it is worth saying what a three-heap check would add.

The substitution claim is about every misère sum, so a genuine test would substitute inside sums of three, four and more heaps. Each additional heap multiplies the search, and the misère recursion has no shortcut — that is the whole problem — so the census stops where it can still be exhaustive rather than sampled.

What that leaves untested is the composition. Substituting one tame heap in a two-heap sum is checked here 100 times over; substituting both heaps at once is what the census actually does, and substituting three at once is not. A theorem is a theorem and this is not evidence against it, but the site’s habit is to say which instances were run.

Why a substitution is licensed at all #

The census checks that the substitution works and does not say why it should, and the reason is worth having because it locates the failure precisely.

Two things have to be true before a position may be swapped for another carrying the same symbol.

The symbol has to compose. The genus of a sum must be determined by the genera of its parts — otherwise replacing a part changes the whole in a way no bookkeeping can track, and carrying one symbol per heap is useless. This site tests that directly, over pairs of positions drawn from nine different games at once, which is the arrangement that makes the test sharp: inside a single octal game the same pair of symbols may never occur twice, and across nine of them it occurs constantly. Two positions from different games carrying the same symbol are exactly the case the claim is about, and the sums’ genera agree.

And the symbol has to decide the outcome. Composition alone gives a bookkeeping system; what makes it a substitution is that the symbol at the end of the sum says who wins. For tame positions it does, because a Nim position with that symbol exists and the misère Nim rule reads it off.

Put together, those two are the whole licence, and they say what wildness actually breaks. A wild position’s genus composes exactly as well as a tame one’s. Nothing about the arithmetic fails. What fails is the second clause: there is no Nim position carrying that symbol, so the sum’s genus is computed correctly and there is nothing to hand it to. The obstruction is an empty target, not a broken rule — which is a considerably more specific diagnosis than “misère play is hard”, and it is why the search for the substitute in the census’s third column is a search rather than a formula.

The naive substitution is a coarser invariant #

That framing also explains the three Kayles failures, and turns them from a curiosity into an instance of something general.

Substituting the Nim heap of the same normal-play value is substituting along the head of the genus and throwing the tail away. The head is a Grundy value and the tail is the misère information, and the question is whether the first determines the second.

It does not, and the heap of eight is the counterexample. Kayles’ heap of eight and a Nim heap of one both have head $1$; their tails are $13$ and $031$. Same head, different tail, and — by the split named below — one firm and the other fickle, which is the sharpest possible way for two positions to differ under misère play while agreeing under normal play.

So the naive rule is not a rough version of the right rule. It is the right rule applied to the wrong invariant: it substitutes positions that agree on a function of the genus rather than on the genus, and the function is exactly the one that discards everything misère play depends on. A substitution along a coarser invariant is unsound whenever the coarsening merges two classes, and here it merges precisely two — firm and fickle at the same head.

That predicts where the failures will be, and the census confirms the prediction rather than merely counting: all three failing Kayles pairs contain the heap of eight, and Dawson’s chess and $\cdot 6$ have no failures in range because neither has a heap in range whose head is shared with a Nim heap on the other side of the split. The naive substitution is not unreliable in general; it is exactly reliable, and exactly unreliable, on a set the genus can name in advance.

Where the model stops #

The genus is not a complete invariant. Two positions with the same genus need not be interchangeable in every misère sum — the genus records a tail of $\ast 2$-additions and nothing else, and there are wild positions it cannot tell apart. The complete invariant is the misère quotient, which is a monoid computed for one game at a time and is larger than the genus for every game this site has computed one for.

The check is over pairs. Substitution is claimed for every sum, and what is verified here is every sum of two heaps up to nine, with both tame. Three-heap sums are affordable and were not run; the claim is a theorem in the literature and this essay tests an instance of it rather than proving it.

Nothing here is about who wins one board. Every claim is about substitution inside sums, which is a strictly stronger property than agreeing on outcomes: two positions can share an outcome and be separated by a third position added to both, and that separation is what equality means wherever this site uses the word.

And the substitution is a misère statement. Under normal play every one of these heaps is exactly its Grundy value, and the heap of eight really is $\ast$ — there is no sense in which the normal-play answer is wrong. Two theories, two invariants, and the whole difference is what happens at the end.

Where the word “tame” comes from #

The vocabulary is Conway’s and it is more precise than it sounds. A tame game is one whose genus is a genus some Nim position has; a wild one is anything else. Inside tame there is a further split — firm and fickle — and it is exactly the split that produced the surprise above.

A fickle position has one of the two special genera, $0^{120}$ or $1^{031}$: the genera of the empty position and of a single Nim heap of one. Those are the positions whose misère behaviour reverses the normal-play answer, and they are the ones the classical misère Nim rule is about.

A firm position has genus $g^{g,g+2}$ for some $g$ — the genus of a Nim heap of two or more. Kayles’ heap of eight is firm with head 1, and $\ast$ itself is fickle with head 1. Two positions of the same normal-play value on opposite sides of the split, which is why the naive substitution fails on exactly those pairs and nowhere else in this census.

So “tame” is not a compliment about simplicity. It is the statement that a Nim position with this genus exists — and the census’s third column is the search for it, performed rather than assumed.

What the solver computed, and how #

The genus of a position is a sequence: the misère Grundy value of the position with $i$ copies of $\ast 2$ added, for $i$ from 0 up to the tail length, each entry a separate exhaustive search over the misère recursion. The symbol is that sequence with its eventual period folded up, and the classification is a comparison of the folded symbol against the shapes Nim positions have.

Every heap’s own value comes from the mex rule applied to the game’s move list, so the head of a genus is the same number the normal-play theory would produce and no separate machinery computes it.

The Nim table is built rather than quoted: every Nim position with up to three heaps of up to four counters is given a genus by the same routine, and the first position found for each symbol is the substitution. That is why Kayles’ heap of eight comes out as $2 + 3$ — nothing selected it, it is simply the smallest Nim position whose genus matches.

The prediction test is then one comparison per pair: solve the real sum, solve the substituted Nim position by the misère Nim rule, and record whether they agree. Both halves are computed; neither is quoted.

Where the ladder goes next #

The rung above this one is the quotient, which this site already computes for several games, and the question that joins them: how much of a quotient the genus recovers, game by game, and whether the gap has a pattern. The other direction is the one the wild heaps point at — a wild heap stands for no Nim position, so what does it stand for, and is there a larger family of positions to substitute into?