A heap that loses under both endings

Under misère play the player who makes the last move loses, and the cost of that one change is that sums stop being computable from their parts. A misère position has to be classified by how it behaves in company, and the classification of Dawson’s chess, the octal game ·137, grows as larger heaps are allowed. A staircase, not a slope ran that count to heap sixteen with a closure forty times cheaper than the full one: every position of up to three heaps, tested against every position of up to two. It found a staircase. There were six classes to heap eight, twelve from nine to twelve, and seventeen from thirteen to sixteen.

Both steps landed somewhere a reader could have pointed to. Heap nine is the first wild heap, the first whose misère behaviour Nim cannot imitate. Heap thirteen is the first heap with a Grundy value of four, a value that opens a third bit and doubles the range of nim-sums. That essay ended on a hypothesis: steps come at first appearances, the first wild behaviour and the first value that opens a new bit, and heaps that only repeat what the game has already done are absorbed into classes that exist. It proposed running the count on to the next first appearance to test it.

The lead needs one correction before it can be tested. Dawson’s Grundy values do reach six and seven further along, but neither opens a new bit, since four, five, six and seven all share the bit that four opened. So the hypothesis, read strictly, predicts no further step at all: Dawson’s normal-play values settle into a period of thirty-four and never exceed seven, so the arithmetic kind of first appearance is used up at heap thirteen. Running the count on is then a test of a sharp prediction, flat for ever after thirteen unless a new kind of wildness turns up.

Flat to nineteen, then twenty-four #

The count holds at seventeen through heaps fourteen to nineteen. Six heaps go by and the classification absorbs every one of them, including heap fifteen, the first with a Grundy value of five, and heaps sixteen and eighteen, which are wild. So far the prediction stands.

Then at heap twenty the count jumps to twenty-four. Seven new classes arrive at once, the largest step on the staircase, on a heap the hypothesis gave no reason to expect anything from. Heap twenty is worth nought under normal play. Its genus is tame: it is one of the patterns Nim produces, not a wild one. It brings no new Grundy value and no new bit. Under both halves of the hypothesis it should have been absorbed, and it brings more new classes than any heap before it.

The normal-play column makes the contrast plain. Normal play classifies the same positions by the nim-sum of their heaps’ Grundy values and reads eight classes from heap thirteen on, unmoved at twenty and unable to move again, since no nim-sum of values below eight can leave the eight values it already reaches. Misère play, which had already added nine classes of its own over the normal count, adds seven more. The gap between the two conventions was eight classes at heap twelve and nine at sixteen, and at twenty it is sixteen.

The checks against larger closures run to heap twelve, as before, and past that the cut closure is trusted alone. That has a precise meaning for the step. Every one of the twenty-four classes is separated from the others by a test actually computed, so the twenty-four are real: there are at least that many distinct misère behaviours among positions of three heaps up to twenty. What the unchecked range cannot rule out is that a larger closure would have found some of the seven earlier, at nineteen or below. The step is a fact about this closure. The classes it reveals are a fact about the game.

A new genus, and only then #

If not first wild heaps and first new bits, what do the steps land on? Each heap’s misère genus, the record tame and wild introduced of how the heap behaves alone and beside heaps of two, answers it.

Read down the column of genera and mark each one the first time it appears. Heap three’s 2²⁰ is new, and the count rises there from two classes to six. Heap nine’s 3¹⁴³¹ is new and the count doubles. Heap thirteen’s 4¹⁴⁶ is new and the count rises by five. Heap twenty’s 0⁰² is new, and the count rises by seven. Every step to heap twenty lands on a genus no smaller heap has. The converse also holds over the same range. Every heap that repeats a genus already seen, heap fourteen repeating eight’s, sixteen repeating eleven’s, seventeen to nineteen repeating twelve’s, nine’s and ten’s, brings nothing.

The rule is not that a new genus brings a step. Heaps four, five, eleven and fifteen all bring a genus seen for the first time, and none of them moves the count. Heap eleven is the case the earlier essay noticed, a wild heap that changes nothing, and fifteen is its twin with a new Grundy value as well. So a new genus is necessary for a step and not sufficient, at least to twenty. That is weaker than the hypothesis it replaces, and it has the advantage of not being refuted. Both of the old hypothesis’s cases sit inside it: the first wild heap and the first value of four were both first appearances of genera, and so were the new genera at eleven and fifteen that did nothing. What the old hypothesis did was pick out two kinds of new genus as the ones that matter. Heap twenty is a new genus of neither kind.

A heap that loses under both endings #

Heap twenty’s genus says what kind of novelty it is.

Four heaps to twenty are worth nought: four, eight, fourteen and twenty. Under normal play a heap worth nought is a loss for whoever has to move. The first three turn into wins for the mover under misère play, with the genus 0¹²⁰. That is the genus of an empty Nim position: the player facing nothing to do under misère play has, by the rule, already won. Heap twenty’s genus is 0⁰². It is the first heap of Dawson’s chess that loses for the mover under both endings. It is also a genus no single Nim heap has. A heap of $n$ counters in Nim has the genus $n^{n,\,n \oplus 2}$ when $n$ is two or more, and the patterns 1⁰³¹ and 0¹²⁰ below that; 0⁰² is none of these. It is the genus of a pair of Nim heaps of two. That pair is the classic position on which misère Nim’s whole strategy turns, since 2 + 2 is a loss for the mover under either convention and the player who can leave it wins. Heap twenty is a single heap of Dawson’s chess that behaves, alone and beside heaps of two, like that pair.

That is why the genus is called tame and why the earlier hypothesis did not see it coming. Tameness asks whether a heap’s genus is one that Nim, sums included, can produce, and 2 + 2 is Nim. But nothing below twenty in Dawson’s chess had produced it, and a heap that plays like a balanced pair is a different object in company from a heap that plays like a single heap of any size.

The step at twenty is a new probe #

A step can be made of two different things, and they can be separated. New classes can be new positions, holding the new heap, that behave like nothing seen before. Or they can be older positions, holding no heap of the new size, that the new heap tells apart when it is added beside them as a test.

The three steps are built differently. At heap thirteen every new class is new positions. The older positions, classified against tests that may now hold a thirteen, still fall into the same twelve classes, so the new heap is a new kind of position and no new kind of probe. At heap nine it is a mixture. The older positions go from six classes to eight once a nine may sit beside them, and four classes consist only of positions holding a nine. At heap twenty the balance tips the other way. The older positions go from seventeen classes to twenty-two once tests may hold a twenty, and only two classes, those of 3 + 13 + 20 and 3 + 15 + 20 with ten members each, are made only of positions with a twenty in them.

So most of what heap twenty adds is not new kinds of position. It is a new test. Positions that every sum of heaps up to nineteen treated identically get different misère outcomes once a heap of twenty is added beside them, a heap that loses for the mover under both endings and plays like a balanced pair.

The probes show which company does it. A heap of twenty on its own splits nothing older, and neither do some of the pairs. The splitting tests are a heap of twenty beside one other heap, and twelve such pairs each split at least one class, two of them two. What heap twenty probes, then, is never a position on its own terms but a position beside one further heap. The differences it exposes were present in the older positions all along. No sum of heaps up to nineteen could reach them, and heap twenty with one companion can.

The game Dawson posed #

All of this is about the convention that makes the counting hard, and that convention is not a variant chosen to be difficult. A chess problem that turned out to be an octal game followed Dawson’s 1934 pawn puzzle to the octal code ·137, and the convention Dawson actually used found that the compact results about ·137, its period of thirty-four and its eventual settling, are results about normal play, while the puzzle as Dawson set it is the misère game. The staircase is therefore a description of the game a chess problemist actually posed, and the compact description everybody quotes belongs to the other ending.

That makes heap twenty a fact about Dawson’s own game in a direct sense. A row of twenty files is an ordinary row of Dawson’s pawns, and under the convention he chose a heap of that size is the first one where whoever must move loses whichever ending is played. Every smaller heap worth nought under normal play was a win for the mover under his. A reader working through his puzzle at larger and larger sizes would meet the first heap where the two endings agree on a loss at twenty, and would meet the classification of positions jumping at the same place.

It also explains why the steps are hard to predict from the heap alone. The genus of a sum found that a single heap’s genus says a great deal about the heap and much less about the sums it will be in. Heap twenty is the sharpest instance yet: its genus is tame, Nim’s own, and most of what it changes is how other positions behave in its company. Twelve classes, seven questions found that seven well-chosen tests separate the twelve classes at heap nine and that tests found at one heap bound do not carry to the next. Heap twenty is a test of exactly that kind. It is the probe that sums of smaller heaps could not supply, and it arrives as a heap. Two heaps of testing are enough set the closure at two-heap tests, and every splitting probe here is a two-heap test, twenty and one other heap, so the cut closure was wide enough to see the step even if not to see it early.

Where the search stops #

The step at twenty is also where this way of counting runs out.

Every outcome in the cut closure is a misère search of a sum of up to five heaps, and the search remembers every position it settles so that none is searched twice. Dawson’s moves split heaps, so a search of five heaps visits a great many smaller multisets of heaps on its way down. The number it has to remember roughly doubles with each heap allowed: 1.1 million at sixteen, 7.3 million at nineteen, 12.1 million at twenty. That is 72 per cent of the 16,777,216 entries one JavaScript table can hold. At twenty-one it passes the limit and the search stops. The closure itself is not the problem, since it computes under half a million outcomes at twenty. What runs out is the memory of positions already searched.

This is the price what misère play costs and a misère sum is searched were measuring from the other direction. Under normal play a sum is a nim-sum of numbers already known, and heap twenty costs one more Grundy value. Under misère play each sum is a search, and the searches of a three-heap position beside a two-heap test, at heap twenty, have to remember twelve million positions to stay affordable at all. The cut closure made the curve forty times cheaper to draw. The search under it doubles every heap, and four heaps past sixteen it has used up the room. Going further is a matter of storing positions more compactly, not of a cleverer closure.

The convention the counts rest on #

Misère play: the player who makes the last move loses. Dawson’s chess is the octal game ·137, in which a move removes a whole heap of one, removes two counters from the end of a heap, or removes three counters and leaves nothing, one heap or two. A class count at heap bound $H$ classifies every position of at most three heaps, each of at most $H$ counters, by its misère outcomes against every sum of at most two such heaps. To $H = 12$ it is confirmed against three-heap tests and four-heap positions, and past that it is a floor. A heap’s genus is its Grundy value with the sequence of its misère values beside zero, one, two and more heaps of two written above it, cut where the sequence settles. It is tame when that sequence is one Nim produces, sums of Nim heaps included, and the table marks a tame genus firm or fickle following Conway’s names.

What the staircase cannot show #

Where the step at twenty first appears under a larger closure. The checks stop at heap twelve. A closure with three-heap tests might separate some of the seven new classes at nineteen or earlier, and then the step would be lower and smaller than it looks here. The twenty-four classes are certainly there at twenty; the heap at which they first become visible is certain only for this closure.

That the rule holds past twenty. A new genus is necessary for every step to heap twenty, a range in which the search finds four steps and nine first appearances of a genus. That is a small sample for a rule about an infinite sequence of heaps. A step on a repeated genus somewhere past twenty-one would refute it, and nothing here can look.

Why some new genera bring a step and others do not. Heaps eleven and fifteen bring genera never seen before and change nothing, while twenty brings one and changes a great deal. The anatomy suggests the difference is in company, whether the new heap separates older positions as a test, but that is a description of what happened at three steps, not an explanation that would have predicted it.

Whether the staircase ends. Dawson’s normal-play values are periodic from heap fifty-two with period thirty-four, so normal play’s classification is finished at thirteen. Whether the misère quotient of Dawson’s chess over every heap size is finite is the question this measurement was always circling. A step at twenty after six flat heaps is evidence that flat stretches are not endings, and no evidence about whether there is an end.

Still open: the next first genus #

The rule that survives makes a concrete prediction. The count can step only at a heap whose genus has not appeared before, so the next step, if there is one, waits for the next heap past twenty with a new genus. Dawson’s genera can be computed heap by heap at almost no cost, with no closure at all, so the candidates can be listed long before the classification can reach them. The measurement is the classification at those heaps. It needs a misère search that stores its positions as packed integers rather than strings, or on disk, so that the wall at twenty-one moves. If the next step lands on the next new genus, the rule becomes an early warning: genera are cheap, classes are expensive, and the cheap computation would say where the expensive one is going to change. If a step lands on a repeated genus, the classification depends on something in company that no single heap’s genus records, and the warning was never there.