A misère sum is searched, not added

The cost is in the closure, not in the positions measured what misère play costs by counting classes: under normal play Dawson’s chess needs four kinds of position however large the heaps, and under misère play it needs six, then twelve, and more as the universe widens. That is a cost in the size of the answer. It says nothing about what it costs to answer one question — who wins this particular sum? — and that is the question a player at the board actually has.

The answer to that question has a very different price under the two conventions, and the difference is not a constant factor.

Normal play pays once #

Under normal play the outcome of a sum is decided by numbers computed one heap at a time. Each heap of Dawson’s chess has a Grundy value; the values are computed by a recursion over heap sizes, and computing them for every heap up to nine touches twenty positions in all — the heaps themselves and the few small sums their moves produce. After that, the outcome of any sum of those heaps is a nim-sum of the heaps’ values: zero means the player to move loses, anything else means they win. A sum of two heaps and a sum of eight cost the same, and the twenty positions are paid for once and reused by every sum there is.

That is what the Sprague–Grundy theorem buys, and it is worth being specific about which part of it does the work. It is not that Grundy values are easy to compute; for some games they are expensive. It is that they are local: a heap’s value is computed from the heap alone, and the sum’s outcome is a function of the values. Nothing about a sum has to be searched as a whole.

Misère play pays per sum #

Under misère play — the player who makes the last move loses — no such summary exists, which is what misère play is about. A sum’s outcome is not a function of its parts’ outcomes, nor of any numbers computed from its parts one at a time. So to decide a sum it has to be searched as one position: every move in every heap, every resulting sum, recursively, until the positions are small enough to settle.

The figure at the top is what that costs. A search is counted by the distinct positions it visits — each a sorted list of heap sizes — since a memoised search visits each position once. For a single heap the average is six positions. For two heaps it is twenty-three; for four, about two hundred; for six, about thirteen hundred; for eight, over five thousand. The worst single sum of eight heaps visits more than thirty-two thousand.

The growth is roughly tenfold every three heaps. A sum of $k$ heaps reaches positions made of smaller heaps, and more of them than it started with: a move in Dawson’s chess can remove one counter and split what is left of the heap in two, so a search that starts from eight heaps passes through positions of nine, ten and more. The number of positions reachable grows with $k$ like the number of ways of writing down a multiset of small numbers — polynomially for a fixed heap limit, but with a degree that rises with $k$ — and the splitting moves raise it further.

The worst sums say the same thing from the other side. For each number of heaps, the sum that costs most to search is the one with the largest heaps in it: nine alone, then nine and nine, then seven, eight and nine, then eight, eight, nine and nine, and so on up to five, five, six, seven, seven, nine, nine and nine for eight heaps. Large heaps have the most moves and split into the most sub-positions, and a sum of them is the most expensive thing a search can be asked. Under normal play the same sums cost exactly what the smallest ones do.

Why nothing smaller than the sum will do #

It is natural to ask whether the misère search really has to treat the sum as a whole, or whether some cleverer bookkeeping — values for the heaps, with a correction — would let it split the work. The classical answer is that in general it cannot, and the reason is worth putting in terms of this measurement.

Suppose a search could decide a sum from some finite description of each heap. Then two heaps with the same description would be interchangeable in every sum, and the descriptions would be the classes of a misère quotient. A finite description exists exactly when the quotient over the family of positions being considered is finite and known. For Dawson’s chess with heaps up to nine it is finite — twelve classes over sums of up to four heaps — and knowing it is precisely the cheaper way to decide sums. What does not exist is a description computed from each heap alone, without reference to the family, because the class a heap belongs to is decided by which sums it can be told apart in. What counts as the same position is the long form of that argument; the search table is its price.

A table of every sum #

A player facing many sums, or a program that must evaluate a position’s options, can share one search memory across all of them. The last column of the table is that: the total number of positions visited in deciding every sum of $k$ heaps with one shared memory. For eight heaps it is 107,685 — a hundred thousand misère outcomes to fill in a table that normal play fills with twenty Grundy values and a nim-sum per entry.

That is the fairest comparison, because it prices the same deliverable: a complete table of outcomes for every sum of a given size. Normal play delivers it at a fixed price; misère play at a price that grows without bound as the sums get longer. And the misère table is not reusable in the way the Grundy table is. It answers sums of exactly eight heaps of at most nine, and a sum of nine heaps, or a sum with a heap of ten, needs new searching.

What the quotient buys back #

The one construction that reverses this is the misère quotient: a finite set of classes, each position assigned to one, and a multiplication table saying which class a sum of two classes falls in. If the quotient is known, the outcome of a sum is found by multiplying the classes of its parts — $k - 1$ table lookups for $k$ heaps — and reading off whether the product class is a win or a loss.

That is exactly the shape of the normal-play solution, with a finite table in place of exclusive-or. The price is paid up front, in constructing the quotient, and the essay before this one measured that price: one misère outcome for every pair of a position and a test position, a number that grows as the square of the universe. So the two costs trade against each other. A solver can search each sum it meets, paying per question, or build the quotient once and answer every later question for almost nothing. Which is cheaper depends on how many questions there will be.

The break-even is easy to see from the figures. The full quotient over sums of up to four heaps each at most nine costs half a million outcomes; the table of all eight-heap sums costs a hundred thousand positions searched. A solver that only ever needs eight-heap sums should search. A solver that needs sums of every size up to eight, or sums it cannot predict, should build the quotient — provided the quotient built on four-heap sums is right about eight-heap ones, which is a separate question.

The quotient built small is right about sums built large #

That separate question has a direct test. Build the classes from positions and sums of a bounded size, then take a larger sum, replace each part by the first member of its class, and search the smaller result. If the answer always agrees with a search of the original, the classes carry information about sums larger than the ones they were built from, and the quotient’s price is paid once for sums of every size.

The test was run on Dawson’s chess and Kayles with heaps up to nine. Positions of at most two heaps were classified against tests of a given size; then every position was replaced by the first member of its class, beside every company of up to four heaps, and the outcome searched both ways. With tests of two heaps, not one substitution among roughly thirty thousand changed an outcome: classes built from two-heap sums are right in four-heap company. With tests of a single heap, 832 substitutions for Dawson’s chess and 1,521 for Kayles changed an outcome. So a quotient built too small is wrong, and one built only slightly larger is right well beyond its own size. The next essay measures exactly where that line sits — but it already says the trade is real: the quotient’s price, once paid, covers sums longer than the ones it was built from.

Where the price is paid #

There is a way of stating all this that makes the difference between the conventions precise.

Under normal play, the cost of a question is independent of the question. Grundy values are computed from heaps; the sum’s answer is arithmetic on them. The expensive part is local and reusable.

Under misère play, the cost of a question depends on the question. Every new sum is a new search unless a quotient has been built, and a quotient is a classification whose correctness depends on the family of sums it was built from — the cost is in the closure, and the closure is a property of a universe, not of a heap.

That is the same distinction the earlier essay drew between local and contextual classifications, seen from the side of a single query. It explains why misère play feels hard in practice even when the positions are small. A player cannot compute something about each heap and combine; they have to consider the whole board at once, and the whole board is bigger than any of its parts by a factor that grows with the number of parts.

The split pair is the reason no shortcut can exist in general. A heap of three and three heaps of three are both worth $\ast 2$; under normal play they are interchangeable everywhere. Under misère play they behave identically on their own and differently beside the heaps $\{1, 9\}$. Any per-heap summary that assigned them the same code would get that sum wrong; any summary that told them apart would have to look beyond the positions themselves. The search is not an artefact of a naive algorithm. It is what the question requires, until something about the family has been computed in advance.

The size of the thing that would save the search #

The quotient’s price is not fixed either, and that is the other half of the trade.

The quotient that would let a solver skip every search has more classes the larger the heaps it must cover, and each class costs outcomes to discover. Under normal play the table of Grundy values stops growing once the values stop growing — four values, whatever the heap limit. Under misère play the table grows in steps as the heap limit rises, so a solver that builds a quotient for heaps up to nine and then meets a heap of ten has to build again. The search is paid per question; the quotient is paid per universe; and both prices rise, one with the length of the sums and the other with the size of the heaps.

That is the precise sense in which misère play is more expensive, and it is more useful than the vaguer claim that it is harder. Every question has a price that normal play does not charge, and the only way to stop paying it is to pay a larger price once, for a table whose size depends on how much of the game is going to be asked about.

The convention named #

Misère play: the player who makes the last move loses, equivalently a player with no move wins. The game is Dawson’s chess, the octal game ·137, with heaps at most nine; a position is a sorted list of heap sizes. Search cost is the number of distinct positions a memoised search visits, which is the natural measure because each visit is one evaluation of a position’s options; time depends on a machine and positions do not. “Normal play needs twenty” counts the positions a memoised Grundy computation for heaps one to nine visits, including the small sums that splitting moves produce.

How the game became a test case #

Dawson’s chess is a good game to price because it is small and completely understood under normal play. A chess problem that turned out to be an octal game tells that story: a pawn puzzle from 1934 that is the octal game ·137, with Grundy values that never exceed three and settle into a period of thirty-four. Under normal play nothing about it is expensive. Every figure on this page is therefore a price paid for the convention alone, on a game where the normal-play price is as low as it gets, and the ratio between the two columns is as clean a measurement of the convention as one game can give.

The practical treatments of misère games take the quotient route rather than the search route, building the quotient one heap size at a time so that each new heap adds only the classes it creates. That is the incremental form of the trade described here: pay for the table as the universe grows, and never search a sum at all. Whether that is cheaper depends, again, on how large a universe the questions will come from.

What the counts cannot show #

The counts are for one game at one heap limit. Dawson’s chess has small Grundy values and a short period, and its misère searches are correspondingly modest; Kayles’s are larger at the same size. The shape — roughly tenfold every three heaps — is what any take-and-break game should show, but the constant is specific.

Nor do the counts say that misère play is intractable. A table of a hundred thousand positions is small, and a better algorithm — one that uses the structure of the quotient while searching, as practical misère solvers do — would visit far fewer. What the counts establish is the comparison: at the same size, the normal-play answer is a fixed cost paid once and the misère answer is a growing cost paid again for every new kind of question.

Still open: how small a quotient can be built #

The quotient’s price was quoted as half a million outcomes, which is what the signature method costs when every position of up to four heaps is tested against every position of up to four heaps. That is the universe the earlier essay used, and it was chosen for being wide, not for being necessary. A universe has two sizes in it — the positions classified and the tests they are classified against — and nothing so far says which of them the class count actually depends on. If most of the half million outcomes are redundant, the break-even with searching moves a long way, and the claim that misère play costs the square of the universe needs a smaller square.