The convention Dawson actually used

The rung two below opens with what Dawson published:

Thomas Rayner Dawson was a chess problemist, and in 1934 he published a puzzle in Caissa’s Wild Roses: white pawns and black pawns on a board three ranks deep, each side obliged to capture when a capture is available, and whoever runs out of moves loses.

That is the modern reading and it is not the one Dawson set. His problem was a loser-wins problem, of the kind chess problemists have always posed: the player left without a move is the winner, not the loser.

Every compact statement on this ladder — nine distinct values, a period of thirty-four, five exceptions, a certificate a hundred and twenty-four values long, a bill of 7,919 operations — is a statement about the convention Dawson did not use. Under his own the objects are of a different kind, and the difference is not a sign flip.

What changes, and it is one clause #

Misère play inverts exactly one thing: a position with no move is a win for the player to move rather than a loss. The moves are identical, the positions are identical, the game is the same object drawn the same way.

Under normal play that single clause is the base case of the recursion, and everything above it — the Grundy value, the periodicity, the nim-sum over components — is built on it. Invert it and the recursion still runs and still produces a number for every heap, and the number stops composing.

That is the whole of the difference and the whole of the difficulty. In normal play a heap of n is worth some nimber and a position built from several heaps is worth their exclusive-or, so one number per heap is enough for everything. Under misère play two heaps with the same number can behave differently once something else is beside them, so a number per heap is not enough for anything.

The genus, and where ·137 goes wild #

The object that replaces a value under misère play is a genus: a normal-play Grundy value with a superscript recording how the position behaves when nimbers are added to it. Tame and wild is where the classification is built; what matters here is that a tame heap behaves like a Nim heap under misère play and a wild one does not.

Run it on ·137 and the first eight heaps are tame. Heap nine is the first wild one.

That number is worth having because it separates two things a reader might conflate. The convention changes the answer immediately — heap one is worth a win to the mover under one convention and a loss under the other — but for eight heaps the structure survives: the positions still behave like Nim heaps, the exclusive-or still works with a known correction, and a reader could get by with the normal-play table and one rule.

At heap nine that stops. From there the classification is doing something the nimbers cannot express, and the genus symbols get longer to say so.

Reading a genus #

The symbols beneath the heaps are worth reading rather than glancing at, because the notation carries the whole distinction.

A genus is written as a Grundy value with a superscript string. The value is the ordinary normal-play one. The string records what happens to the position when nimbers are added to it — the first character is the misère outcome of the position alone, the second what it becomes with a star beside it, the third with a star-two, and so on.

For a tame position the string settles into a repeating pair, because adding nimbers to something that behaves like a Nim heap has an answer that alternates. That repetition is what tameness is in this notation, and it is why the symbols for the first heaps are short.

For a wild one it does not, and the symbol lengthens to say so. Heap nine’s is longer than heap eight’s for that reason and not because heap nine is bigger.

So the strip of symbols is not a table of values with some anomalies in it. It is a table of behaviours, and the length of a symbol is how much of the behaviour could not be predicted from the beginning of it.

The classification doubles at exactly the heap that admits it #

The sharpest measurement is the count of classes, and it is worth stating what the count is a count of.

Fix a limit on the size of a heap. Consider every position built from heaps up to that limit, and call two of them the same when no other position in the universe tells them apart — when adding any third thing to each gives the same winner. The number of classes that survives is how many distinct kinds of thing the theory has to carry.

Under normal play the answer is four, at every limit, and it stays four for ever. Four nimbers appear in ·137’s sequence within the range, and the Sprague–Grundy theorem says a position is exactly its exclusive-or, so four numbers is the whole classification however large the heaps get.

Under misère play the answer is six up to a heap limit of eight, and twelve from a limit of ten.

The step is at the heap limit that first admits heap nine, which is the first wild heap. Two independent computations — a genus run on single heaps and a class count over whole universes — locating the same number.

That coincidence is the finding rather than a decoration on it. The genus is a classification of heaps; the class count is a classification of positions; and the fact that the second doubles exactly when the first goes wild is what says the genus is measuring something real rather than recording an artefact of its own notation.

Why the count can only rise #

The class count has a property worth asserting rather than observing, and the figures assert it.

Widening the universe — allowing larger heaps — can only ever separate positions that were previously indistinguishable, never merge positions that were previously told apart. A wider universe has more tests in it, and a pair separated by one test stays separated when more tests are added.

So the misère class count is non-decreasing in the heap limit, and a run that reported a fall would be a run that had lost a distinction it had already found. That is a check on the computation rather than a fact about the game, and it is the sort of check that matters because the alternative — a subtle bug in an indistinguishability sweep — produces plausible numbers.

The second assertion is that the misère count is never below the normal one. Every pair of positions the misère theory tells apart, the normal theory either tells apart too or has merged for purposes that are not these — there is no direction in which inverting the ending can identify positions the Grundy values separate.

Where a heap stops being a heap #

There is a way of saying what misère play takes away that is more concrete than “a value that does not compose”, and Dawson’s chess supplies it.

Under normal play a heap of nine is interchangeable with a Nim heap of whatever its Grundy value is. Not similar to it, not usually equivalent to it: the same object, in the strict sense that swapping one for the other inside any position whatsoever changes nothing about who wins. That is what a Grundy value asserts and it is why one number is enough.

Under misère play a heap of nine is interchangeable with nothing. There is no Nim heap it can be swapped for, no smaller position that stands in for it, and no number that summarises it. What it has instead is a class, and a class is defined by what it does against everything else in view — so the answer to what is this heap is a list of comparisons rather than a value.

That is the practical content of the class count. Six classes means the theory has six kinds of thing to carry; twelve means twelve; and neither is a number that lets a player look at a heap and know what it is worth. Two misère outcomes are not enough to settle a sum, which is the same statement one level coarser, and the quotient is what is built when the outcome table turns out to be too small.

What Dawson would have had to do #

There is a temptation to read the last two sections as Dawson’s convention is harder and stop. It is worth being exact about what harder means, because the two conventions differ in kind rather than in degree.

Under normal play a reader who wants to solve Dawson’s chess computes one sequence, finds a period, checks a window, and is done for ever. The answer is a table of thirty-four numbers, the position is a nim-sum, and a heap of a million is a division.

Under misère play there is no sequence to find a period in. A heap does not have a value; a position has a class; the classes depend on which other positions are in view; and enlarging the view can add more of them. What replaces the table is a misère quotient — a monoid of classes with a multiplication table — and its size is a function of the universe rather than a constant of the game.

So the question what is Dawson’s chess worth under misère play does not have the shape the normal-play question has. It is not a harder computation of the same object. It is a different object, and the honest answer is a description of how the object grows.

What the puzzle Dawson set actually asked #

There is a smaller point underneath the machinery and it is the one that gives this rung its title.

Dawson set a position. A problemist’s puzzle names a diagram and asks who wins, and the answer to such a puzzle is a line of play. That is what he supplied.

The modern subject asks about the family — every row length at once — and the family is what has a Grundy sequence. The rung two below records that this is the usual direction, and records the cost: nobody now cites Dawson’s puzzle for the position he was asking about.

What this rung adds is that the translation also changed the convention, and that the change is the larger of the two losses. Asking about a family instead of a position is a generalisation, and the original question is recoverable from the general answer. Changing the convention is not a generalisation; it is a substitution, and the general answer says nothing whatever about the original question.

So the object that carries Dawson’s name answers neither half of what he asked. Not the position, because the subject moved to the family; and not the convention, because the family is tractable under the other one.

Why the subject went the other way, and was right to #

None of that is a complaint. The reason the normal-play reading won is that it is the one with a theory in it, and the theory is not a convenience.

The rung two below prices what normal play buys: a certificate of 7,919 operations that turns every future question about the game into a lookup. Under misère play there is no such purchase available at any price, because there is nothing of fixed size to buy.

And the failure is not particular to ·137. Misère analysis was declared intractable in the 1970s and the verdict was correct about what was being attempted; quotients did not refute it thirty years later so much as change the question, from a value per position to a monoid per game. That is a smaller ambition honestly stated, and it is what makes numbers like six and twelve reportable at all.

So the sensible reading of the whole ladder is: Dawson posed a problem, the subject took the half of it that had a theory, and the half it took is the half everybody quotes. That is not a failure of anybody’s, and it is worth recording that a swap happened, because a reader told that ·137 is Dawson’s chess has been told something with a clause missing.

What the picture cannot show #

The class counts are bounded by their universes. Six and twelve are counts over positions built from heaps up to a stated limit, with a stated number of heaps in a position and a stated number in the tests. A wider universe may find more classes, and the count is a lower bound on whatever the full quotient turns out to be.

And the genus is a finite prefix of an infinite object. The symbols printed are computed with a stated tail length; a longer tail can distinguish heaps a shorter one merges. The tame verdicts are therefore tame as far as checked, and the wild ones are permanent — wildness is a positive finding and tameness is an absence of one.

Nor is Dawson’s own diagram anywhere on this page. What is computed is the octal game the modern subject calls Dawson’s chess, under the convention Dawson used, and the step from a three-rank pawn diagram to a row of counters is a reduction this site takes on trust from the survey literature rather than performs.

The convention, named #

Both of them, and the essay is the comparison.

Normal play: the player who cannot move loses. Every result on the two rungs below is stated under it, and none of them is stated as being under it, which is the usual and slightly careless practice.

Misère play: the player who cannot move wins. That is Dawson’s, and it is the older convention in the problem literature — chess problemists were setting loser-wins puzzles long before anybody wrote down a theory that preferred the other one.

The thing worth carrying is that the choice is invisible in the rules of the game. Dawson’s pawns move the same way under both; the position graph is identical; the only difference is a sentence about what happens at the leaves. A convention is not part of the game and decides everything about the theory of it, which is a sentence this site has now made in three fields and on four games — Kōnane arrives at the normal-play convention by accident and gets a theory for it, and Go arrives at a scoring one and does not.

The surprise: eight heaps of agreement, then a cliff #

The expected shape, before the genus was run, was gradual: the two conventions agree on the smallest positions where nothing much can happen, and diverge more and more as the heaps grow.

What happens is a cliff. Heaps one to eight are tame — they behave like Nim heaps, the classification is six classes, and a reader could work with the normal-play table plus one correction. Heap nine is wild, and the class count doubles at the first heap limit that includes it.

Eight heaps of good behaviour is exactly enough to be misleading. A person checking a new octal game by hand, on the heaps small enough to check by hand, would find every one of them tame and would conclude the game is tame — and would be wrong at the first heap past where they stopped.

That is a general hazard in this subject and it has a name in the anchor next door: a pattern that has not started yet is the same trap in the periodicity family, where a sequence’s regularity begins past where anybody looked. Here the trap runs the other way — the irregularity begins past where anybody looked — and both are instances of one thing, which is that the interesting behaviour of these games is reliably just beyond the range a person can reach.

Where the ladder goes next #

dawson has three rungs: the game and the exceptions its quoted result hides, the price of the certificate nobody quotes, and the convention its author used.

The rung above is the one the misère machinery makes possible and nothing here attempts. The quotient of ·137 is computed here only up to a heap limit of twelve and it doubles once in that range; whether it keeps doubling — whether the classification grows without bound as the heaps do, or settles at some size the way a Grundy sequence settles at a period — is the question that decides whether Dawson’s own convention has a finite answer at all. That is a computation rather than an argument, and it is a large one.