Two heaps of testing are enough

A misère quotient is found by the signature method. Take a universe of positions, take a set of test positions, add every test to every position, and record who wins each sum. Two positions whose rows of outcomes agree are put in one class. The cost is in the closure did this for Dawson’s chess with every position of up to four heaps, each of at most nine counters, tested against the same 715 positions — half a million misère outcomes — and found twelve classes. A misère sum is searched then set that half million against the price of searching sums one at a time, and ended by asking whether it was the price of the answer or only the price of the method.

A universe of that kind has two sizes in it, and they play different roles. One is the size of the positions being classified: a class can only be counted if some position in the universe belongs to it. The other is the size of the tests they are classified against: two positions can only be told apart if some test separates them. The earlier essays varied the two together. Varied separately, they tell a much simpler story.

Reading the grid #

Each cell is a class count. Read along a row and the tests grow; read down a column and the positions grow.

Along every row the count stops at tests of two heaps. Positions of at most three heaps, tested against nothing, fall into two classes — wins and losses. Tested against single heaps they fall into seven; against sums of two heaps, twelve; against sums of three, four and five heaps, still twelve. Nothing a larger test can see is invisible to a two-heap test, at least among these positions.

Down every column the count stops at positions of three heaps. Against two-heap tests, single heaps fall into five classes, positions of two heaps into ten, positions of three into twelve, and positions of four into twelve again. Every class the four-heap universe contains already has a member with at most three heaps.

So the corner that decides everything is small: positions of three heaps against tests of two. It finds all twelve classes, and every cell beyond it finds the same twelve.

The same for three games #

One game might be a coincidence, so the grid was computed for Kayles and Nim as well.

The pattern holds in all three. Kayles’s count stops at eighteen classes, reached with three-heap positions and two-heap tests. Nim’s stops at eighteen as well, and needs only two-heap positions: every class of misère Nim with heaps up to nine has a member of at most two heaps. The single-game grid for Dawson’s chess runs its tests to five heaps and nothing moves past two, and for all three games the three-heap tests are shown to confirm that the second column of tests adds nothing to the first.

What the narrower universe did #

This changes the reading of a figure in the first essay of this series, and the correction should be stated plainly.

That essay drew the class count of Dawson’s chess over a universe of two-heap sums, beside the count over four-heap sums, and explained the gap by saying that a narrower universe “has fewer sums to try, so two positions it cannot tell apart go into one class”. The grid says otherwise. The narrower universe used two-heap positions and two-heap tests — the cell in the second row and third column — and two-heap tests tell apart every pair of positions that any test tells apart. It found ten classes instead of twelve not because it merged positions, but because it did not contain the positions that belong to the other two classes: those need three heaps.

The distinction matters because the two explanations predict different things. If a narrow universe merged classes, substituting one member of a narrow class for another would sometimes change an outcome in a wider company. If it only contains fewer classes, substitution within its classes is always safe. The second is what happens, and it can be tested directly.

What a test set that is too small does #

Merging does happen, one size down.

Classify positions of at most two heaps against single heaps only, and Dawson’s chess shows six classes where there are ten: three true classes have been merged. The merging is visible as wrong answers. Replace each position by the first member of its class and search every company of up to four heaps: 832 of the 35,035 substitutions change who wins. The first one is $3 + 5$ filed with the empty position, which a company of three heaps of one and a nine separates. Kayles is worse, 1,521 wrong substitutions.

With two-heap tests the same experiment finds ten classes — the true number — and not one of the 32,175 substitutions changes an outcome. So the line between too little testing and enough is exactly between one heap and two, for these games at this size, and it is sharp.

One merge, played out #

The first wrong substitution is small enough to follow by hand, and it shows something about misère testing that the counts do not.

The two positions are $3 + 5$ — a heap of three and a heap of five — and the empty position. Under misère play the empty position is a win for the player to move, who has no move and so cannot make the last one. $3 + 5$ is also a win for the player to move. Against every single heap the two agree too: beside a heap of one both sums are losses for the mover, beside a heap of two both are losses, beside a heap of nine both are wins, and so on through every heap up to nine. A classification that only ever adds one heap files them together.

They are not the same. Add the two heaps $1 + 9$: the sum $1 + 9$ on its own is a loss for the player to move, and $3 + 5 + 1 + 9$ is a win. Among the two-heap tests, eight separate the pair — $1 + 9$, $2 + 9$, $3 + 3$, $3 + 5$, $3 + 9$, $5 + 5$, $6 + 9$ and $7 + 9$ — and six of the eight contain a heap of nine. Nine is the first heap of Dawson’s chess whose misère behaviour is wild, not reducible to Nim’s pattern, and it is the heap at which the growth curve of the earlier essay jumped from six classes to twelve. The distinction the one-heap tests missed is one the wild heap exposes.

There is a sharper point in the same pair. Under normal play $3 + 5$ is worth $\ast 2 \oplus \ast 3 = \ast 1$ and the empty position is worth $0$: normal play tells them apart with no test at all. So a misère classification with too little testing is not merely coarser than the true misère one; here it is coarser than normal play, putting together two positions that the simpler convention already separates. The extra classes misère play is supposed to cost are only found if the tests can reach them.

The price of the corner #

The corner is much cheaper than the universe it replaces.

Positions of up to four heaps against tests of up to four heaps is 715 times 715, or 511,225 outcomes. Positions of up to three heaps against tests of up to two is 220 times 55, or 12,100. For Nim, whose classes are all found among two-heap positions, it is 55 times 55: 3,025. The earlier essay’s measure of misère cost — outcomes computed, growing as the square of the universe — was the cost of a method rather than of the answer. The answer costs a small fraction of it.

That does not make the square law wrong. The corner’s size still grows as a product of two universes that each grow with the heap limit, and so the cost still grows much faster than normal play’s single table of values. What changes is the exponent’s base: a closure over three-heap positions and two-heap tests grows like the fifth power of the heap limit, where the full closure grows like the eighth.

What this does to the trade #

A misère sum is searched set two prices against each other: search every sum as it comes, or build the quotient once and multiply classes. With the quotient priced at half a million outcomes, searching looked competitive — a complete table of eight-heap sums of Dawson’s chess cost about a hundred thousand positions searched.

With the quotient priced at 12,100 outcomes the comparison turns over. The corner costs less than the complete table of six-heap sums, which is 18,361 positions, and a ninth of the eight-heap one; and once built it is not tied to one length of sum, because substitution within its classes is exact in every company of up to four heaps that was tried. So for Dawson’s chess with heaps up to nine, the quotient is the cheaper route for almost any workload, and the earlier essay’s framing — misère play costs the square of a large universe — overstated the price by a factor of forty.

That is still far more than normal play charges, and it still grows faster with the heap limit. But it is a different kind of statement: misère play is expensive by a large constant factor and a moderately faster growth, not by the whole of an eight-dimensional square.

The corner moves #

A corner found at heap nine is a fact about heap nine. Whether it stays put as heaps grow is a separate question, and the answer is that it does not, quite.

For Kayles the small closure agrees with both larger closures at heaps nine, ten and eleven. At heap twelve it finds twenty-two classes where three-heap tests and four-heap positions both find twenty-three. Two heaps of testing, enough at heap nine, are not enough at heap twelve. The corner has moved one step along at least one of its two sides.

That is the honest shape of the result, and it is the same shape the earlier essays’ growth curves had: a count that is flat for a stretch of heap limits and then steps. The small closure is flat across a stretch too, and then it has to be enlarged. The closure that is enough is much smaller than the one the earlier essays used, and it grows with the heaps much more slowly than the universe does — but it grows, and the only way to know where it is at a given heap limit is to check it against a larger one. Every use of the small closure in this series is checked that way wherever it is used, and the check is what found heap twelve.

Why two heaps of testing, and not one #

There is a reason the line falls between one and two, and it says something about misère play generally.

A single-heap test asks how a position behaves when one heap is added. Under misère play the characteristic distinctions — the ones normal play does not make — are about what happens near the end of the game, when few heaps remain and the question is who is forced to make the last move. A single added heap can only probe a position’s endgame along one line. Two added heaps can change the parity of what is left in two independent ways, and misère Nim’s own exception clause — play as usual unless every heap has one counter — is exactly a statement about how many small heaps remain. Two heaps of testing are the smallest company that can arrange for a position to be the last non-trivial heap standing in two different ways, and at these heap sizes that is all the distinctions there are.

This is a reading of the result, not a proof of it, and the Kayles case at heap twelve shows its limits: somewhere past heap eleven, a distinction appears that two added heaps cannot probe.

Where this sits among the ways of cutting a company down #

Restricting the company a comparison is made in is an old move, and this is one more instance of it with an unusual result.

Equal in this company restricted normal-play equality to small companies and found that four games — nought, one, minus one and star — already separate every value born by day two, and the company that is closed found that such restricted equalities only license substitution inside a company closed under addition. The misère quotient is the same construction taken seriously, since under misère play there is no unrestricted equality to fall back on, and misère quotients is where it is set up.

What is unusual here is how small the separating company is compared with the positions it classifies. Tests of two heaps are a tiny company — fifty-five positions — and yet substitution inside the classes they define is exact in every company of up to four heaps, not only inside the tests themselves. The two-heap company is not closed under addition, and it still licenses substitution far outside itself on these games. That is a stronger property than the normal-play restrictions showed, and it holds only up to the heap limit where the Kayles corner moves.

The convention named #

Misère play: the player who makes the last move loses. The signature method classifies positions by their outcomes against a set of tests, and two positions are in one class when every test gives the same outcome for both. That relation is equality in a company, with the company being the tests; it can only be coarser than true misère equality, and every class count here is a count relative to its company. Positions and tests are sorted lists of heap sizes, every heap at most the stated limit.

What the grid cannot show #

The grid shows where counts stop changing inside the range computed. It cannot show that they would not change again further out — the Kayles result is exactly a count that looked settled and was not. A column that stops at two-heap tests up to five-heap tests is strong evidence, and not a proof, that no larger test separates anything more.

Nor does the grid show which positions fall into which class, or what the classes are as an algebra. It counts them. The quotient’s multiplication table is a further computation on top of the classes, and its cost is not measured here. Nor, finally, does it say anything about games other than these three. Dawson’s chess, Kayles and Nim are all octal games with small moves, and a game whose moves reach further — a heap that can be split into three, or a move that takes any number of counters and splits the rest — may need larger tests from the start. The grid is a method for finding out, and the three rows of results are what it found on the games it was pointed at.

Still open: how few tests, rather than how small #

The grid bounds the size of the tests needed. It says nothing about their number. Two-heap tests with heaps up to nine are fifty-five positions, and there is no reason to think all fifty-five are needed to separate twelve classes; a single test answers a single yes-or-no question, so twelve classes could in principle be separated by four. How many tests a classification actually needs — and whether the tests found for one heap limit still work at the next — is the question that decides how cheaply a quotient can be checked once it has been found, and it is where the price of misère play is lowest.