Twelve classes, seven questions

Two heaps of testing are enough found how large the tests of a misère classification need to be: for Dawson’s chess with heaps up to nine, sums of two heaps separate everything that sums of five do. It said nothing about how many tests are needed. Every one of the fifty-five two-heap sums was used, and every one of 715 positions in the earlier, larger closures. A classification into twelve classes is twelve answers, and twelve answers need far fewer than fifty-five questions.

The question here is the number. What is the smallest set of test positions such that no two classes give the same outcomes against all of them? That number is the cost of checking a position’s class once the classes are known, and it is where the price of misère play is lowest.

Tests as questions #

A test is a position added to whatever is being classified. The outcome of the sum — does the player to move win? — is one bit. A set of $t$ tests gives each position a row of $t$ bits, and two positions are told apart when their rows differ. So a set of tests separates $c$ classes only if $c$ different rows of $t$ bits exist among them, which needs $2^t \ge c$. For twelve classes, $t$ must be at least four.

That is the floor, and it is almost never attainable, because the rows are not free to be anything. They are determined by the game: a test’s column of outcomes is whatever the game makes it, and the question is only which columns to pick.

Seven for twelve #

The figure at the top is a greedy choice. Starting from nothing, it takes the test that splits the most pairs of classes still undistinguished, then the test that splits the most of what remains, and so on until every pair is split. For Dawson’s chess it stops after seven tests.

The first two are the obvious ones: the empty position, which just asks whether the class is a win or a loss on its own, and a single heap of one, which asks what happens when a spare move is added. Between them they sort the twelve classes into four groups, one for each pair of answers, which is as much as two bits can do. The remaining five tests are sums of three and four heaps: $1 + 3 + 3 + 3$, $1 + 1 + 3 + 3$, $1 + 1 + 3 + 5$, $1 + 1 + 1 + 9$ and $1 + 1 + 4 + 9$. Heaps of one keep appearing, as they do throughout misère play, because a heap of one is a single move that changes the parity of what is left without changing anything else; and heaps of nine appear because nine is the first heap whose misère behaviour is wild.

Seven is three more than the floor, and greedy selection is not optimal, so the true minimum lies somewhere from four to seven. The gap is the price of not searching all subsets of 715 tests, which would be the only way to close it.

Reading the rows #

Named by their shortest members, the twelve classes are more familiar than a matrix of outcomes makes them look. Five of them contain a single heap: the class of the empty position, which also holds heaps of four and eight; the class of a heap of one, which also holds two, six and seven; and the classes of three, of five and of nine alone. The other seven need two heaps or three to name: $3 + 3$, $3 + 5$, $1 + 9$, $3 + 9$, $5 + 9$, $3 + 3 + 3$ and $3 + 3 + 5$.

Set the single heaps beside their Grundy values and one difference stands out. Under normal play heaps of four and eight are worth nought, heaps of one, two, six and seven are worth $\ast 1$, three is worth $\ast 2$, and five and nine are both worth $\ast 3$. The misère classes of single heaps follow that grouping exactly — with one exception. Five and nine are equal under normal play and different under misère play. Among single heaps, the whole extra cost of the misère convention at this size is one split, and it falls on the first heap whose misère behaviour is wild.

The seven multi-heap classes are where the rest of the cost lives. They are all built from heaps of three, five and nine — the odd-valued heaps — together with heaps of one, and none of their shortest members needs a heap from the classes of nought or one. That is the characteristic misère effect in miniature: positions whose normal-play values nim-add to the same thing, but which differ in how many odd-valued heaps they contain and so in who is forced to make the last move.

The tests read the same story from the other side. A heap of one flips which player must move last; the sums of three and four heaps, each containing heaps of one and odd-valued heaps, set up endgames in which exactly that flip decides the outcome. Misère quotients is the general account of why the same few kinds of position keep appearing in these tables, and the matrix is what it looks like when the account is reduced to twelve rows.

Why seven and not four #

The floor of four assumes each question can split the remaining classes in half. These questions cannot, and the matrix shows exactly how far they fall short.

Count the losses in each column. Every one of the seven tests calls exactly three of the twelve classes a loss for the player to move and the other nine a win. That is not a property of the greedy choice; it is a property of misère outcomes, which are losses much less often than wins, and it limits what any single question can tell. A question answered “loss” a quarter of the time carries about 0.81 bits of information rather than one, and twelve classes need $\log_2 12 \approx 3.58$ bits to distinguish. So at least five questions of that kind are needed, not four, and the honest floor for these tests is five.

The gap from five to seven is then the cost of the greedy choice and of the columns not being independent: two tests that call the same three classes losses tell nothing new, and tests that overlap partly tell less than they appear to. One class, the class of a single heap of three, is a win against every one of the seven tests — it is identified by having no losses at all, which is a legitimate row but one that wastes nothing only if every other class has a loss somewhere.

Three games #

Kayles has eighteen classes, a floor of five, and a greedy set of nine. Nim also has eighteen classes and a floor of five, and needs sixteen tests — nine more than Dawson’s chess for only six more classes, and over three times its own floor.

Nim’s excess is informative. Its tests are dominated by sums like $1 + 1 + 1 + 2$, $1 + 1 + 1 + 3$ and so on up to $1 + 1 + 1 + 9$: three heaps of one and one other heap. Those are the positions where misère Nim’s exception bites — play as usual unless every heap is small — and each of them separates only a few pairs of classes that nothing else in the set separates. Nim’s classes differ from one another only in rare companies, one company per difference, and so the witness set cannot be compressed. Dawson’s chess and Kayles, whose misère behaviour departs from Nim’s in more places, have classes that differ in many companies at once, and a few well-chosen tests catch many differences each.

That reverses a natural expectation. Nim is the tame game, the one misère play treats most gently, and it is the one whose classification is hardest to check with few questions. Tameness means its classes are nearly the same as each other, and nearly-the-same is what takes many questions to separate.

The witnesses are not found for free #

The seven tests are cheap to use: to find a position’s class, add each of the seven to it and search seven sums. That is far less than testing against all 715, and far less than the 12,100-outcome closure of the previous essay.

But they cannot be found without that closure, or something like it. The greedy choice needs every class’s full row of outcomes against every candidate test — the entire signature matrix — before it can pick the first test. So the small witness set does not lower the cost of finding the classes; it lowers the cost of using them afterwards. That is a familiar shape for a certificate: expensive to produce, cheap to check, and useful exactly when the same classification will be consulted many times.

The comparison with position keys is exact enough to be useful. A key shorter than the position is about storing a position under a short code so that a solver recognises it when it comes round again, and it found that a key can be much shorter than the position it names because only the distinctions that matter need to be kept. A witness set is a key of the same kind for misère classes: seven bits that name a position’s class, much shorter than the position, and correct for every position in the universe. The difference is where the key comes from. A position key is computed from the position alone. A witness key is seven searches of the position in seven companies, and the companies had to be found by looking at everything first.

They do not carry #

A certificate is most useful if it keeps working as the problem grows, so the natural test is to take the witnesses found at one heap bound and use them at the next.

They do not. For Dawson’s chess with heaps up to seven there are six classes, and four tests separate them. With heaps up to nine there are twelve, and those same four tests separate only seven: five of the new classes are invisible to them. For Kayles the nine tests found at heap seven separate fourteen of the eighteen classes at heap nine.

The reason is the one the growth curve already showed. The classes that appear at heap nine are about the wild heap of nine, and a test chosen before nine was allowed cannot contain it. Two of the seven tests in the heap-nine set contain a heap of nine; none of the heap-seven tests could. A witness set is a fact about a universe, and the universe it certifies is fixed when the witnesses are chosen.

That is the misère version of a statement what counts as the same position makes in general: identification is relative to what is being compared against. Under normal play a single number, the Grundy value, identifies a position against everything at once — the substance of the Sprague–Grundy theorem — and so it never needs to be recomputed as the family grows. Under misère play identification is always against a company, and a larger company needs new questions.

What one position costs to classify #

Put in cost terms, the three measurements so far give a clear scale of prices for Dawson’s chess with heaps up to nine.

Searching one sum of eight heaps from nothing visits about five thousand positions — how hard it is to answer one question, in the plainest currency there is. Building the quotient over the smallest sufficient closure costs 12,100 outcomes. Classifying one new position against a known quotient costs seven searched sums — seven outcomes, each a sum of the position with a small test. And deciding a sum once every part’s class is known costs a lookup per part.

The first two are costs of discovery, the last two costs of use, and the gap between them is where misère play becomes practical. The comparison with normal play is then between seven searched sums per position and one Grundy value per position — still a factor of seven and more, but a constant factor on a fixed family, not a cost that grows with every question.

A test set that is too small #

It is worth setting the seven questions beside a set of questions that fails, because the failure is what makes the seven meaningful.

The tests of at most one heap are a witness set too — ten questions, counting the empty one — and they are not enough: they merge three pairs of true classes among two-heap positions. The greedy set of seven is smaller than ten and separates everything. The difference is not the number of questions but which questions: the single heaps ask ten variations of one question, “what happens when one more heap is added”, and the greedy set asks seven genuinely different ones, most of them about sums of several small heaps. Choosing tests is choosing which companies to look at, and a small, well-chosen company sees more than a larger, uniform one.

That is the practical content of equal in this company carried into misère play. A company that separates everything can be tiny, but it has to be the right company, and finding the right one is itself a computation over the whole of what might be compared.

The convention named #

Misère play, the player who makes the last move losing; Dawson’s chess, Kayles and Nim with every heap at most nine; positions and tests of at most four heaps. A test separates two positions when the misère outcomes of the two sums with it differ. The greedy set is found over the full 715-by-715 signature matrix so that the tests are not restricted in advance to the two-heap corner, which lets the choice show which sizes of test the game actually prefers.

What the matrix cannot show #

The matrix shows that seven questions suffice for these twelve classes. It cannot show that fewer do not; the greedy choice gives an upper bound and the floor of four a lower one, and closing the gap needs a search over sets of tests, which is expensive in its own right.

Nor does the matrix show that the classes it separates are the true misère classes of Dawson’s chess. They are the classes of a bounded universe, found by a bounded closure, and a wider universe may split them further — as the step from heap seven to heap nine did, and as the step at heap twelve does for Kayles. A witness set certifies a classification relative to its universe and cannot certify more. And the greedy procedure has no view of which tests will stay useful: it picks the test that splits the most pairs now, which at heap seven meant tests that could not contain a heap of nine, and so it produced a set that was optimal for its universe and brittle beyond it. A procedure that preferred tests with larger heaps, at some cost in the number of tests, might produce sets that survive a step in the heap bound — a trade between the size of a certificate and its lifetime that none of these measurements explores.

Still open: how far the staircase goes #

Every measurement in this series has been at heaps up to nine, because the full closure became too expensive beyond that. The previous essay made the closure forty times cheaper, and that changes what can be measured. The growth curve that stepped from six classes to twelve at heap nine can now be run much further for Dawson’s chess, checked at each bound against larger closures, and set beside the heaps’ own misère genera to see whether the steps land anywhere a reader could have predicted.