Tame and wild

Under normal play a position is worth one number. Every impartial game is a Nim heap, the heap sizes combine by exclusive or, and a whole board collapses to one small integer.

Reverse the ending — the player who cannot move wins — and one number stops being enough. Misère play sets out the damage: the ordering breaks, dominated options cannot be deleted, equal games stop being interchangeable. What it does not do is compute anything.

The genus is the first thing anybody built to fill the gap, and it is a Grundy value with a tail. Write it g^{g₀g₁g₂…}: the base g is the ordinary normal-play Grundy value, and the superscript digits are the misère Grundy values of the same position with 0, 1, 2, … Nim heaps of two added to it. A game is tame when every one of its positions carries a symbol that some Nim heap also carries, and it is wild as soon as one position does not.

The symbol, digit by digit #

Fix a position G. Its base g is the normal-play Grundy value: the mex of its options’ values, with the empty position scoring 0. Its first superscript g₀ is the same recursion with one clause changed — a position with no options scores 1 rather than 0 — which is the misère convention written as arithmetic. The remaining superscripts are g₀ again for G plus one Nim heap of two, then plus two of them, and so on.

The added heaps are ∗2 and nothing else — heaps of one would give a different sequence and a different classification, and nothing in the notation catches the substitution. They are also carried in a separate component and are not heaps of the game being measured. In Kayles a heap of two happens to move exactly as a Nim heap of two does; in Dawson’s chess it does not, and a computation that took the shortcut in both places would be measuring the wrong thing in the second.

The sequence has to be written finitely, so the convention is the one Winning Ways uses: print the shortest prefix whose last two digits repeat for ever. So 0¹²⁰ is 1, 2, 0, 2, 0, 2, 0, …, and 2²⁰ is 2, 0, 2, 0, …. The figures here compute nine superscripts per position and accept a prefix only if the alternation holds across all nine; the generator throws rather than print a symbol when no such prefix exists.

Read down that column and the pattern is n^{n (n⊕2)} — the misère value of ∗n alone is n, adding a ∗2 exclusive-ors it to n⊕2, and the two then alternate. So the tame symbols are that family for every n ≥ 0, plus two a row of single counters reaches: 0¹²⁰ for an even number of ones, including none, and 1⁰³¹ for an odd number.

The reference table stops at 7 because heap 8 of Nim has genus 8^{8·10}, the first symbol whose superscript needs two-digit entries, and a table of digits stops being readable exactly there.

Firm, fickle, and a game that is tame without being Nim #

The two tame families are the two things a tame position can do when the ending is reversed, and the difference shows at the board.

The three rows that flip are exactly the three whose genus is 0¹²⁰ or 1⁰³¹. Those are the fickle symbols, and fickle means what it says: the misère outcome is the opposite of the normal one. The three rows that do not flip carry 2²⁰, 0⁰² and 0⁰² — members of the n^{n (n⊕2)} family, the firm symbols, where reversing the ending changes nothing at all.

That is the whole of what a tame classification buys: a game all of whose positions are tame is played in a misère sum exactly as Nim is played in one. Tameness is not a property of Nim, though, and the cheapest way to see that is a game that is plainly not Nim and tame anyway.

Subtraction games are the tamest corner of the octal codes under normal play and are tame in this technical sense as well, as is the octal game ·007. Four of the seven games computed here have no wild heap in range at all.

The normal-play value gives no warning #

Here is the finding that makes the genus worth computing rather than quoting.

Heaps 3 and 11 of Dawson’s chess are indistinguishable to the entire normal-play theory. Both are worth ∗2, so either may be substituted for the other in any normal-play sum with no effect on any outcome — that is what having equal values means. Under misère play one behaves like a Nim heap of two and the other does not, and the value that certifies their equivalence carries no trace of the difference. The same happens one row up: heaps 5 and 9 are both worth ∗3, and only heap 5 is tame.

This is why the genus has a tail at all. The base is not merely insufficient, it is silent: knowing that a Dawson heap is worth ∗2 excludes nothing about how it behaves when the ending is reversed, and the only way to find out is to run the misère recursion.

Kayles behaves differently. Over heaps 1 to 22 no two Kayles heaps share a normal-play value and disagree about tameness: ∗1, ∗2 and ∗3 are tame throughout that range and ∗4, ∗6 and ∗7 wild throughout it. So there the base does predict the verdict as far as the computation went — a coincidence of that game over that range, not a rule, since Dawson’s chess breaks it twice in fourteen heaps.

Solved under one convention, wild under the other #

Kayles is worth a second look, because two facts sit in the same game and neither touches the other.

Under normal play its Grundy sequence becomes periodic with period twelve from heap 71, and holds that period through every one of the 2,001 values computed — and a period is a proof, covering every heap size there will ever be.

Kayles is therefore solved under normal play in the strongest sense the subject offers: a finite table plus a period, from which the value of a heap of any size follows. Under misère play the same game is wild from heap 5. The two computations run over the same position graph and differ in one clause — what a position with no options scores — so the distance between “settled for ever” and “no general theory” sits entirely inside that clause, which is the sharpest statement this site can make about how much the ending convention is carrying.

What the solver computed, and how #

The evaluator here takes a mixed position — the game’s own heaps together with a bag of loose Nim heaps — under a convention named by a single number: what a position with no options scores. Zero is normal play, one is misère, and both recursions are the same code with that one argument changed.

genusRun walks heaps 1 to 14, computing the base and nine superscripts for each and memoising misère states across the run. Seven games, 5.8 seconds in total:

That is 23,490 memoised misère states across the seven games, and the wild symbols are worth naming. Kayles has 4¹⁴⁶ at heap 5, 4⁰⁴⁶ at 9 and 12, 6⁴⁶ at 11. Dawson’s chess has 3¹⁴³¹ at 9, 2⁰⁵²⁰ at 11, 4¹⁴⁶ at 13. The octal game ·6 has 3¹⁴³¹ at 7, 10 and 13, 4⁰⁵⁶⁴ at 11 and 14, and — the clearest case of the lot — 0²⁰ at heap 12, a symbol with the right Grundy base and the wrong superscript, which is the whole of what wild means.

That last row is worth drawing rather than quoting, because it is the one heap in the whole run whose symbol differs from a tame one in a single digit.

A classifier that only ever says tame would produce the four zero rows in that table and nothing would look wrong. So it is run a second time with its misère base case removed.

The sabotaged run is wrong for a reason that can be stated in advance. With the base case restored to normal play, the Sprague–Grundy theorem applies to the perturbed positions too, so every superscript sequence comes out as g, g⊕2, g, g⊕2, … — precisely the tame pattern. Every game must therefore come out tame, and every game does: 0 wild of 12 for all seven games, including Kayles, which really has 4 in that range, ·6, which really has 4, and Dawson’s chess, which really has 2.

The honest run disagrees with it on 4, 4 and 2 rows respectively, and on 0 rows for Nim, ·007 and the two subtraction games — which is what it should do, since those four really are tame. That second half is what makes the test worth running: the classifier agrees with the broken version exactly where the broken version happens to be right. The same discipline runs the closure test in the coin-turning essay and the sabotaged reduction in the complexity gate — a test that has never rejected anything has not been tested.

The genus is not a complete invariant #

Tame and wild is a verdict about a game. The sharper question is whether the symbol predicts how a position behaves in a sum, and for wild games it does not.

The check is exhaustive. All 220 positions with at most three heaps of at most nine counters were grouped by genus symbol, and each group attacked with every test position of at most two heaps — 55 of them — to see whether a pair sharing a symbol could be told apart by the outcome of a sum.

Nim survives with nothing separated, as a tame game should. Dawson’s chess produces fewer distinct symbols than either of the others while failing far more often, which is what an invariant that has stopped discriminating looks like. The cheapest Kayles witness is small enough to hold. The empty position and the Kayles position of two heaps of five both have genus 0¹²⁰. Add a heap of nine to each: one sum is a second-player win and the other a first-player win. Nineteen counters across the two positions and the test that separates them, and the genus is identical on both sides. The cheapest Dawson witness is the same shape at 22 counters: a heap of 3 and three heaps of 3 both carry 2²⁰, and adding heaps of 1 and 9 gives N in one case and P in the other.

So the genus is an invariant of the position that fails to be an invariant of its behaviour, and that gap is what a value is supposed to close. For tame games it closes it; for wild games no number of extra superscripts repairs it, because the failure is not in the length of the tail.

Where the wildness shows in the quotient #

The construction that does close the gap is the misère quotient: fix a game, restrict attention to sums of its own positions, and quotient by indistinguishability inside that universe. It subsumes the genus and is computable one game at a time.

Computed for Kayles restricted to heaps of at most five — all 126 positions of at most four heaps, sorted into the classes indistinguishable inside that universe — it gives twelve classes under misère play against eight under normal play, the eight being the Nim values 0 to 7.

Twelve against eight is the price of the reversal in that universe. Whether the wildness shows up in the count is the sharper question, and it does — though the honest statement of it is careful rather than dramatic.

The same computation for maxHeap 3 through 9 across five games gives the pattern in full. Nim’s misère count runs 6, 10, 10, 10, 10, 18, 18 against 4, 8, 8, 8, 8, 16, 16 under normal play — it grows, and every jump is one the normal count already explains. The tame ·007 behaves the same way. Kayles jumps unexplained at heap 9, Dawson’s chess at heap 9, and ·6 at heap 7.

The two tame games show no jump the normal-play count does not already explain; each of the three wild games shows one; and none of them shows one before its own first wild heap. For ·6 and for Dawson’s chess the unexplained jump lands exactly on the first wild heap. For Kayles it lands four heaps later, at 9 rather than 5 — a reminder that the quotient is measured over a universe of at most four heaps and the genus over single heaps, and the two are not the same experiment.

Where the model stops, and what the picture cannot show #

The convention first, since everything above depends on it. Normal play is the default on this site and misère play is a different game with the same rules. The genus mixes the two deliberately: the base is a normal-play Grundy value, the superscripts are misère Grundy values, and neither half means anything without the label.

The tail is observed, not proved. Nine superscripts were computed for every heap — up to eight added ∗2s — and the symbol printed is the shortest prefix whose last two digits alternate across all nine. Every heap checked settled, and the longest prefix seen anywhere was four digits: 3¹⁴³¹, 2⁰⁵²⁰ and 4⁰⁵⁶⁴. Nothing here proves that any of those tails continues, and that is exactly what the picture cannot show: a genus table draws a finite string of digits and the object it stands for is infinite. Reading 2⁰⁵²⁰ as 0, 5, 2, 0, 2, 0, … for ever is a claim the drawing does not make and the computation did not check past its ninth digit.

How far it went. Heaps 1 to 14 for all seven games; separately 1 to 22 for Kayles, 1 to 20 for Dawson’s chess and 1 to 16 for ·6. The largest single run memoised 56,475 states, which was Kayles to heap 22, and nothing is claimed beyond it.

The searches are bounded too: 220 positions per game against 55 test positions, so Nim’s zero separated pairs is a statement about that universe and not a theorem; the quotient tables reach heaps of 9, over sums of at most four heaps told apart by sums of at most four. No wild game’s full misère quotient is computed here at all.

Who found it, and when #

Grundy and Smith attacked misère disjunctive games in the mid-1950s and produced the idea of carrying a sequence of misère values alongside the Grundy value. Conway systematised it into the genus and the notation used here; On Numbers and Games and Winning Ways both present it, both with the tame-and-wild vocabulary, and both frank that it does not go far enough.

The frankness was earned by the games in this essay. Dawson’s chess had been a chess problem since 1934 and became the octal game ·137 when Guy and Smith organised the take-and-break games into codes; its misère analysis was the standard hard case, and its wildness is why. Misère Kayles held out until Sibert and Conway solved it in the early 1990s with machinery that was not the genus at all — which reads oddly beside the normal-play fact that Kayles has been finished since its period was found.

Plambeck’s misère quotient construction arrived around 2004, with Siegel building the computational side. The genus survives as the fast test: cheap, complete on the tame games, and on a wild one it says that the cheap answer has run out — a real service, and the whole of what it offers.

Where the ladder goes next #

This is the base rung of the genus, and the rungs above it are all things this machinery could reach.

The genus of a sum. The tame symbols compose, and not by exclusive or on the base alone: firm and fickle combine differently, and the rule is stateable in a line and worth drawing at the numbers.

Why tameness is closed under addition. A sum of tame positions is tame, which is what makes the classification a property of a game rather than of each position separately — and the reason a single wild heap ends the analysis for the whole game.

The games whose genus is periodic in the heap. Kayles’ normal-play values are periodic with period 12 from heap 71, and its genus symbols over heaps 1 to 22 draw from seven distinct values. Whether the symbols are eventually periodic is the kind of question the octal codes leave open.

The misère quotient as the construction that subsumes this one. The rung that is missing is the bridge: which quotients the tame games have, and how a genus symbol is read off an element of one.

And the outcome question underneath all of it. Misère play has no negatives, no zero and no theory of sums from outcomes alone, and the genus measures how much of that loss a particular game actually suffers. For a tame game, almost none. For Dawson’s chess, 203 pairs the genus calls identical and a sum tells apart, which is where the impartial theory stops.