A staircase, not a slope

The cost is in the closure drew the misère class count of Dawson’s chess against the heap limit and stopped at nine, because the closure it used — every position of up to four heaps tested against every other — costs half a million outcomes at heap nine and grows like the eighth power of the heap limit. Six classes to heap eight, twelve at heap nine: two points of a curve, with the rise between them unexplained.

Two heaps of testing are enough found a closure forty times cheaper that finds the same classes — positions of three heaps against tests of two — and twelve classes, seven questions found how few tests the classes need once they are known. The cheaper closure makes the curve affordable to extend. This essay extends it to heap sixteen and asks what the shape is.

The count is flat, then it jumps #

From heap three to heap eight there are six classes. At heap nine there are twelve, and still twelve at ten, eleven and twelve. At heap thirteen there are seventeen, and still seventeen at fourteen, fifteen and sixteen.

That is a staircase, not a slope, and the difference matters for what “the cost of misère play grows with the universe” means. A slope would say that every heap size added brings new distinctions, a steady expense. A staircase says that most heap sizes bring nothing — a heap of ten behaves, in every sum of up to three heaps, like some heap already present — and occasionally one brings several classes at once. The expense is lumpy, concentrated at particular heaps, and between those heaps a wider universe is free.

The staircase also says why the earlier curve looked the way it did. Its two points, six and twelve, sat on either side of the first step. A reader seeing only those two would reasonably guess the count doubles every few heaps; the extended curve shows it rising by five at the next step, not six, and then not rising at all for four heaps.

Checking the cheap closure #

The count past heap nine rests on the cut closure, and the cut closure has been shown to fail once — for Kayles at heap twelve — so it is checked here wherever it can be.

At every bound from three to twelve, the cut closure’s count is compared with two larger closures: the same positions against three-heap tests, and four-heap positions against the same tests. All three agree at every bound. Past twelve the larger closures become expensive and the cut closure is trusted alone — which, given the Kayles result, means the seventeen classes from heap thirteen on are a floor. The step at thirteen is certain; its height might be larger than five.

The table also carries the normal-play count, which classifies the same positions by the nim-sum of their heaps’ Grundy values. It is four through heap twelve and eight from thirteen. The difference between the two columns is the extra misère cost at each bound: two classes at heap eight, eight at heap twelve, nine at heap sixteen.

Where the steps land #

A step is a heap that brings new distinctions, and the natural place to look for its cause is the heap itself.

Each heap has a normal-play Grundy value and a misère genus: the Grundy value with a superscript sequence recording how the heap behaves under misère play when heaps of two are added. A genus that follows Nim’s pattern is tame, and a tame heap behaves in misère sums the way a Nim heap would; anything else is wild. Tame and wild sets this up, and the table lists every heap to sixteen.

The first step, at heap nine, lands on the first wild heap. Every heap from one to eight is tame — its genus is one Nim has — and heap nine’s genus, $3^{1431}$, is not. Its Grundy value is three, the same as heap five’s, which is why normal play does not move at heap nine: no new value, no new class. Misère play sees the wildness and doubles.

The second step, at heap thirteen, lands on the first heap with a Grundy value of four, and heap thirteen is wild too. Normal play steps here as well: a value of four doubles the range of nim-sums a sum of heaps can reach, from four values to eight. Misère play rises by five.

That second step also corrects a sentence in the first essay of this series, which said that Dawson’s chess needs four normal-play classes however large the heaps get, because its Grundy values stop at three. They do not stop at three. They stay at three or below through heap twelve, which covers every universe that essay drew, and then heap thirteen is worth $\ast 4$, heap fifteen $\ast 5$, and by heap thirty-three the sequence has reached $\ast 7$. The normal-play count is four through heap twelve and eight from thirteen. The first essay’s statement has been corrected to say what its range supported.

And where they do not #

It would be tidy if either property predicted a step. Neither does.

Heap eleven is wild — its genus is $2^{0520}$ — and the count does not move at eleven. Heap fifteen is wild and brings the first Grundy value of five, and the count does not move at fifteen either, in either convention: a value of five does not widen the range of nim-sums beyond the eight that four already opened. Heap sixteen is wild and moves nothing.

So the first wild heap brings a step and later wild heaps need not; a new Grundy value brings a step when it widens the range of nim-sums and not otherwise. The two kinds of step are also different in size. The wild step at nine doubles the misère count while leaving the normal one untouched; the arithmetic step at thirteen doubles the normal count while raising the misère one by less than half. A wild heap multiplies distinctions that only misère play makes, and a new bit of Grundy value multiplies distinctions that both conventions make — and misère play, having already made many of them, has fewer left to multiply. Both observations are about first appearances. The first time the game does something new — the first wild behaviour, the first value that opens a new bit — the classification has to grow to accommodate it. After that, a heap that does the same new thing again can apparently be absorbed into classes that already exist.

That is a reasonable hypothesis about the shape of misère quotients, and these sixteen heaps are consistent with it. They are not evidence enough to state it as a rule, and the cut closure’s reliability past heap twelve is exactly what a test of it would need to be sure of.

A cheap warning for an expensive step #

There is a practical reading of the first step, and it is the most useful thing the genus column offers.

A heap’s genus is cheap to compute. It needs the heap on its own and the heap beside a few heaps of two — a handful of small misère searches, one heap at a time, with no closure at all. The class count needs the closure. So if the first step always lands on the first wild heap, the genus is an early warning for the expensive computation: compute the genera heap by heap, and the first heap whose genus is not one Nim has is the first heap at which the quotient has to be rebuilt.

For Dawson’s chess to heap sixteen that warning is exact for the first step and silent about the second, which lands on a new Grundy value rather than on a first wild heap. And it overstates the later steps — heaps eleven, fifteen and sixteen are wild and bring nothing. So the genus predicts where the quotient first stops being tame and nothing after. That is the same limit the genus of a sum found from the other side: the genus of a single heap says a great deal about the heap and much less about the sums it will be in, and the classes are about sums.

The classes themselves #

A count says how many; it is worth seeing which.

Up to heap eight the six classes are named $0$, $1$, $3$, $5$, $3 + 3$ and $3 + 5$ — the empty position, three single heaps, and two pairs of odd-valued heaps. At heap nine six more arrive: $9$, $1 + 9$, $3 + 9$, $5 + 9$, and then $3 + 3 + 3$ and $3 + 3 + 5$. The last two contain no nine at all. They were present before heap nine was allowed, sitting in older classes, and what heap nine brought was a test that tells them apart from the positions they had been classed with. A new heap adds distinctions in two ways: as a position to be classified, and as a company to classify others in, and the second is invisible in a count of positions.

At heap twelve the count is still twelve and two of the names change. The class that was named $1 + 9$ is now named $11$: a single heap of eleven belongs to it, and is shorter. The class of $5 + 9$ is now named $3 + 11$. So the wild heap of eleven, which brought no new class, behaves in every company of up to two heaps exactly like the pair of a one and a nine. That is the concrete content of “a later wild heap can be absorbed”: heap eleven is not a new kind of thing, it is an old kind of thing in a new form, and the classification finds that out without being told.

At heap thirteen every new class contains a thirteen: $3 + 13$, $5 + 13$, $3 + 3 + 13$, $3 + 5 + 13$ and $3 + 9 + 13$. There is no class named by thirteen alone — a single heap of thirteen falls into an existing class — and the new distinctions appear only when thirteen is combined with the odd-valued heaps that carried the previous ones.

Normal and misère, side by side #

The normal-play staircase has one step in this range; the misère staircase has two, and the misère steps are larger.

Normal play’s step at thirteen is a doubling, from four classes to eight, and it is fully explained by arithmetic: the classes are nim-sums, and a new bit of Grundy value doubles the number of nim-sums available. Misère play’s step at thirteen is from twelve to seventeen — not a doubling. Some of the classes that the new bit would create in normal play are identified with one another in misère play, or were already separated by the misère distinctions that arrived at heap nine.

Misère play’s step at nine has no normal counterpart at all. It is the pure cost of the convention: six new classes that exist only because the last move loses. After heap nine, that cost persists — the misère count stays well above the normal one — and at thirteen the two costs, the arithmetic one of a new Grundy bit and the misère one, compound but do not multiply.

What the extension cost #

The staircase to heap sixteen needed, at its last point, 148,257 misère outcomes: 969 positions of up to three heaps against 153 tests of up to two. The full closure at heap sixteen would be 4,845 positions against 4,845 tests, over twenty-three million outcomes. The extension is affordable only because the cut closure is enough, and it is trustworthy only as far as the cut closure has been checked, which is to heap twelve.

That is the practical lesson of the last three essays taken together. The first measured the price of misère play in the most expensive currency available and found it steep. The second found most of that price was the method. The third found how little it costs to use a classification once it exists. And the curve that was too expensive to draw past heap nine can now be drawn to sixteen with most of its points checked — which is how the staircase became visible at all.

What the extension is worth #

The price ratio grows with the heap limit because the two closures grow at different rates — the full one like the eighth power of the limit, the cut one like the fifth. At heap nine the cut closure is forty-two times cheaper; at heap sixteen it is a hundred and fifty-eight times cheaper. Every point of the staircase past nine exists because of that ratio, and every point past twelve rests on it without the check.

That is a fair summary of what this series of measurements has done to the question it started with. What misère play costs was answered first in the most expensive currency available, and the answer — a cost growing as the square of a universe that grows exponentially — was true of the method. The cost of the answer is a smaller closure, a handful of tests, and a classification that grows in steps rather than continuously. It is still far more than normal play charges, and a misère sum is searched is the reminder of what that difference feels like to a player; but it is a cost that can be measured to heap sixteen instead of heap nine, and the measurement shows a shape the smaller one could not.

The convention named #

Misère play: the player who makes the last move loses. Dawson’s chess is the octal game ·137. A class count at heap bound $H$ is the number of classes of positions of at most three heaps, each of at most $H$ counters, when classified by their misère outcomes against every sum of at most two such heaps; up to $H = 12$ it is confirmed against three-heap tests and four-heap positions. The genus of a heap is its Grundy value with the sequence of its misère Grundy values in sums with heaps of two, written as a superscript, and it is tame when that sequence is one a Nim heap has.

What the staircase cannot show #

The staircase counts classes; it does not say what the new classes are at each step, which positions first need them, or what the quotient’s multiplication looks like after each jump. Twelve classes, seven questions named the twelve classes at heap nine; naming the seventeen at heap thirteen is the same computation one step further and is not done here.

Nor can sixteen heaps say whether the staircase keeps climbing. Dawson’s chess has a normal-play Grundy sequence that settles into a period of thirty-four with values never above seven, so normal play’s count stops growing once a value of four has appeared — no later value opens a fourth bit — and stays at eight. Whether the misère count stops too — whether the misère quotient of Dawson’s chess, over all heap sizes, is finite — is a question these computations cannot answer, and a staircase with two steps in sixteen heaps is no evidence either way.

Still open: the next steps #

The two hypotheses this essay raises are testable with the same computation. If steps come at first appearances — the first wild heap, the first Grundy value that opens a new bit — then the next step for Dawson’s chess should come no earlier than the next such first appearance, and heaps between should be free. Dawson’s Grundy values reach six and seven further along its sequence, and each first appearance of a value that opens a new bit is a predicted step. Running the cut closure out to those heaps, with the larger closures checking it where they still can, would test the prediction and would either make the staircase a rule or find the step it does not explain.