What the class does not buy

A ruleset is dead-ending when a player who has run out of moves can never be given one back. Nobody comes back identifies the class, sorts this site’s games into it — Domineering, Shove and Toppling Dominoes are in it, Toads and Frogs is not — and closes by naming the rung above:

What misère comparison looks like inside it is the first: the literature’s claim is that comparison behaves in a dead-ending universe in a way it does not behave in general, and the nine rulesets above are a supply of test cases nobody here has run it on.

Running it produces a measurement, a null result, and one number that points the wrong way.

What comparison in a universe is #

Under normal play, $G \ge H$ means Left wins $G - H$ moving second, and that is a test on two positions. Under misère play there is no such test, because misère play has no negatives — $G + (-G)$ is not nought — so the definition falls back to the quantifier it was hiding.

$G \ge H$ in a universe $\mathcal{U}$ means: for every $X$ in $\mathcal{U}$, the misère outcome of $G + X$ is at least the misère outcome of $H + X$, in the partial order where L beats everything, R loses to everything and N and P are incomparable.

Restricting $\mathcal{U}$ is what makes that testable, and it is what restricted equality is for. Here a universe is a ruleset’s own positions, their followers, and every sum of two of them — 45 to 210 games depending on the ruleset, and a comparison has to hold against all of it.

Restricting the company buys a great deal #

Between a quarter and a half of ordered pairs compare.

Shove: 93 of 182. Domineering: 75 of 182. Toads and Frogs: 26 of 72. Toppling Dominoes: 14 of 56. Every one of those is an ordered pair of distinct positions, so a pair contributes twice and a comparable pair in both directions is two of the count.

Those are large numbers by the standards of misère play, where the ordinary situation is that two positions are incomparable unless they are identical.

That is the finding worth having and it is about restriction rather than about dead-ending. In the general misère setting comparison is nearly trivial; confining the company to one game’s own positions turns it into a relation that holds on a quarter to a half of pairs, which is enough structure to do something with.

And dead-ending is not what buys it #

Three of the four rulesets are dead-ending and one is not, and the one that is not is in the middle of the range — 36 per cent against 25, 41 and 51.

The census asserts that. If every dead-ending ruleset compared more often than the one that does not, the class would separate the counts and this page would be reporting the hypothesis working.

It does not, and the reason to be careful here is that the literature is not being contradicted. The theorems stated over dead-ending universes are about a simplified test for comparison — they say the quantifier over $\mathcal{U}$ can be replaced by a condition on options — and not about how many comparisons hold. A census of counts cannot refute a theorem about a test.

What the census does establish is that the count is not the thing the hypothesis controls, which is what a reader meeting the class for the first time would most naturally assume it was for. That assumption is the one worth removing.

The universes, and why their sizes matter #

The four universes are of very different sizes — 45, 66, 66 and 210 — and that is not a nuisance to be normalised away.

A larger universe is a harder test: a comparison has to hold against more games, so a ruleset with a big universe should compare less often, all else equal. Shove has the largest universe by a factor of three and compares the most, which says that all else is not equal by a wide margin.

So the counts cannot be read as a ranking of the rulesets. What they can be read as is a demonstration that the spread between them is large, and that the class does not predict where in it a ruleset lands — which is a weaker claim and is the one the census supports.

The company that breaks a comparison #

The sharper measurement is what happens when a universe is enlarged. A comparison found in one ruleset’s universe is re-tested against that universe with another ruleset’s added — 624 tests in all.

Six hundred and fourteen of the 624 survive. Ten do not.

And every one of the ten is lost to a dead-ending company. Domineering’s comparisons lose six when Toppling Dominoes is added; Toads and Frogs’ lose four to the same. Adding Toads and Frogs — the ruleset that is not dead-ending — costs nothing at all, in any of the three tests where it is the company added.

That is the opposite of what the hypothesis would predict if it controlled stability, and it is worth stating plainly rather than explaining away. The one company in this census that never breaks a comparison is the one outside the class.

What the ten losses are #

They are not a subtle effect and they have an ordinary cause.

Toppling Dominoes supplies positions of a shape the other rulesets do not: rows whose ends are single dominoes of one colour, which under misère play behave as very sharp ends. A comparison that held because no position in the original universe could exploit a particular difference stops holding when a position that can is added.

The six Domineering losses and the four from Toads and Frogs are the same shape: a pair whose difference is invisible to every position of the original universe and visible to something Toppling supplies. Nothing about those pairs is exotic — they are ordinary comparisons that were true against a smaller company.

That is a fact about what Toppling Dominoes contains, not about what class it is in. Toads and Frogs breaks nothing because the positions it supplies are, in this small sweep, not sharp enough to separate anything the other universes could not already separate.

So the honest reading of the ten is that the enlargement test measures what a ruleset supplies and the class does not predict it. A larger sweep with more rulesets would be the way to see whether the class predicts it on average, and four rulesets cannot.

Against a company of anything at all #

The third test widens the universe not by another game but by 276 arbitrary short games — every value born by day two, their followers and their pairwise sums, which is emphatically not a dead-ending universe.

Shove keeps all 93. Domineering keeps 67 of 75, Toppling 12 of 14, and Toads and Frogs 22 of 26 — 86, 89 and 100 per cent against 85, which is not a separation.

That is the same null result at the other extreme of company size, and together the two say the same thing: on this site’s games, at these sizes, being dead-ending does not visibly protect a misère comparison.

The one that never loses anything #

Shove is the outlier in every column and it is worth a paragraph, because the reason is visible in the rules.

Shove compares most often — 93 of 182 — and keeps every one of its comparisons against every company it is tested against, including the 276 arbitrary games. Nothing else in the census keeps everything.

The reason is that Shove is cold everywhere: every position is a number, decided by one coin, and its universe is therefore a set of numbers and sums of numbers. A universe with no fights in it has very little power to separate two positions, so comparisons made against it are easy to make and hard to break.

That is a caution about the whole census rather than a fact about Shove. The four rulesets differ in how discriminating their universes are, and that difference is larger than anything the dead-ending property contributes. A ruleset whose positions are all numbers will always compare more often than one whose positions fight, and no classification of the rules is going to change that.

Why a null result is worth a page #

Three reasons, and the first is the general one.

A hypothesis that is doing nothing measurable should be known to be doing nothing measurable. The class is cited in the misère literature and it is easy for a reader — and for a site — to carry it as though it explained why some games are tractable. On this evidence it does not explain the counts, the stability, or the survival.

The thing it does explain is the definition. A dead-ending universe is one in which a finished component stays finished, so a component that has ended contributes a fixed parity to the rest of the board rather than a moving one. That is exactly the hypothesis the simplified comparison tests need, and it is a statement about how a proof goes rather than about how many comparisons there are.

And the measurement that would show it is a different one. Implementing the simplified test and checking that it agrees with the quantifier — on the dead-ending rulesets, where it should, and on Toads and Frogs, where it should not — is the census that would put the hypothesis to work. That is the rung above and it needs the test written, which is a piece of machinery this site does not have.

What the census does not say #

Four limits.

The ten losses are one company’s doing. Every loss in the cross test is to Toppling Dominoes, so the finding rests on one ruleset being unusually discriminating rather than on a pattern across several. With four rulesets there is no way to tell those apart, and the honest statement is that the class did not predict which company would break anything.

Four rulesets, and small ones. Fourteen positions each at most, with universes of 45 to 210. Misère comparison over a universe is quadratic in the universe and the universe is quadratic in the ruleset, so the sweep is bounded hard.

Three dead-ending against one that is not. The rung below found nine rulesets and eight of them dead-ending, which is the population available — and a null result comparing three against one is weak by construction. A game family with a tunable rule, where a clause can be switched on and off, would be the right instrument and this site’s nearest is the same strip without the jump.

The universe is sums of two. A proper misère universe is closed under all sums, and this one stops at pairs. That makes comparison easier than it should be — a comparison failing only against a three-part sum is counted as holding here — so all four shares are upper bounds.

And the outcome order is the coarse one. N and P are treated as incomparable, which is right, and it means a comparison can fail for the weakest possible reason. A finer invariant — the genus, where one exists — would give a different and probably smaller count.

What a class of games is supposed to be for #

A named class earns its place by supporting a theorem that is false outside it, and it is worth setting out the three jobs such a class can do, because this one does fewer of them than its name suggests.

Restore an operation. The strongest job: a class in which something the general theory lacks becomes available again. Under misère play the missing operations are the negative and the comparison, so a class that restored either would be worth having for that alone.

Bound a computation. A weaker job and often more useful: the class may not restore anything, but the object that has to be computed for it is smaller, or finite, or shared between its members.

Or merely collect. The weakest: the class is a set of games with a property in common, the property is checkable, and nothing follows from membership that did not follow from the definition.

The distinction matters because a definition that is easy to check invites the third and is usually presented as the first. A reader who learns that a game is in some class reasonably expects a theorem to become available, and what is often available is a smaller search.

Which is the honest reading of what a restriction buys anywhere in misère theory. The quotient is a computation per universe, and a class is a way of choosing the universe — so a well-chosen class makes the computation finite and does not make it unnecessary. That is a real service and it is not the service the word class advertises.

What a reader should do with the class #

Three sentences, and the middle one is the correction.

Take it as a hypothesis about proofs. A dead-ending universe is one in which a component that has finished contributes a fixed parity, and that is what a simplified comparison test needs to be provable. It is a condition on an argument.

Do not take it as a prediction about a game’s tractability. Nothing measured here — how often positions compare, whether comparisons survive company, whether they survive arbitrary company — is separated by the class, and the one number that separates anything separates it the wrong way.

And notice which property does predict. Whether a ruleset’s positions are numbers or fights explains the whole spread in this census, and it is a property of values rather than of rules. Nothing worth fighting over is the extreme case at one end and the strip nobody has a formula for is nearer the other, and the census’s four rows are ordered by it rather than by the class.

The convention, named #

Misère play throughout: the player who cannot move wins. Every outcome is computed by the recursion rather than looked up.

A universe here is a ruleset’s positions, every position reachable from them, and every sum of two of those, together with nought. It is closed under options and not under all sums, which is stated because it makes the comparisons reported here a little easier than the literature’s.

$G \ge H$ in $\mathcal{U}$ means the misère outcome of $G + X$ is at least that of $H + X$ for every $X$ in $\mathcal{U}$, in the order where L is above N and P, both of which are above R, and N and P are incomparable to each other.

Dead-ending is a property of the rules: no position reachable in the game gives a move back to a player who had none. It is decided by walking the reachable states and never by evaluating anything.

Where the ladder goes next #

The dead-ending anchor has two rungs: the class identified and this site’s games sorted into it, and now what it does and does not control under misère comparison.

The rung above is the simplified test itself. The literature’s results say that in a dead-ending universe the quantifier over the whole company can be replaced by a condition on options, and this page has not implemented that condition — so the one claim the hypothesis genuinely makes is the one still unchecked here. Writing it and running it on these four rulesets would be decisive in a way none of the three censuses above is: it should agree with the quantifier on the three dead-ending games and disagree on Toads and Frogs, and if it agrees on all four the class is doing even less than this page found.

Two neighbours are worth the trip. Equal in this company is where restricted equality is made computable, and this page is the same machinery pointed at the misère convention, where the restriction is not a convenience but the only thing that makes the question askable. And misère quotients is the construction that takes one game’s own positions as the company and quotients by equality in it — the place where restricting the universe is not an approximation to a theory but is the theory.