A quotient that identifies nothing

The clause that turns the class off built the matched pair this anchor has wanted since it opened: Toads and Frogs with the jump and without, which are the same game on the same strips except that one is dead-ending and the other is not. It measured the class-specific comparison test against a control on both, and found the class gaining less than the control gained.

It closed by naming what it had measured the wrong object:

Every measurement on this anchor has been about comparison — whether one position is at least another in a universe — and the class’s actual reputation is about quotients, which are a coarser object … A quotient can be small where comparison is hard, and the matched pair is exactly the population on which to ask whether dead-endedness makes it smaller.

Neither quotient is smaller, because neither quotient is anything at all.

The nineteen against twenty-two is not a smaller quotient. It is a smaller ruleset: forbidding the jump removes moves, so fewer distinct positions arise, and every one of the nineteen that does arise is told apart from every other. Reading the smaller number as a smaller quotient would be the whole error this page exists to avoid, and it is an easy one to make — a table of two numbers with the dead-ending ruleset lower in both columns looks exactly like a class doing something.

The step underneath, which had to be checked first #

Before any of that can be read, one thing this anchor has been doing since it opened needs verifying, and nobody had.

Every measurement here reduces a strip to its canonical form before asking anything — that is how 244 strips become 22 positions. Canonical form is the normal-play reduction: delete dominated options, bypass reversible ones. Both operations preserve the normal-play value of a game and neither is guaranteed to preserve its misère outcome, because the misère convention rewards a different thing and a reversible move can be exactly the move that matters when the last player loses.

So collapsing 244 strips to 22 forms before asking a misère question is, in general, a step that can lose the question.

On this population it is sound. Not one of the 22 forms with the jump, and not one of the 19 without, holds two strips whose misère outcomes disagree. That is a fact about these strips rather than a licence for the reduction in general, and it is worth having written down, because four rungs of measurement rest on it and none of them had said so.

Where a quotient starts #

A quotient refines from somewhere, and it is worth seeing the somewhere.

The empty sum sorts the positions into four classes, which are the four misère outcome classes and nothing finer. Two misère outcomes are not enough is where that reading was established as the coarsest invariant available and where its table was found empty — the outcome of a sum is not a function of its parts’ outcomes.

Every addend after the first refines those four. The question a quotient asks is where the refining stops, and the answer here is that it does not stop until every position is on its own.

Why a quotient is the right question and a comparison is not #

It is worth being exact about how the two objects differ, because the rung below’s sentence turns on it and the difference is easy to blur.

A comparison is an order. $G \geq H$ over a universe $U$ means that for every $X$ in $U$, Left does at least as well in $G + X$ as in $H + X$. It fails in two quite different ways: because $H$ is genuinely better somewhere, or because neither is better anywhere and the two are simply incomparable. Most pairs of misère positions are incomparable, which is why comparison is hard and why what the class does not buy found so little to buy.

A quotient is an equality. $G \equiv H$ means that for every $X$, the two sums have the same outcome — not that one is at least the other. Two incomparable positions can be equivalent, and often are: neither dominates and neither is ever told apart. So a quotient can be small on a population where the order is almost empty, and that is precisely the situation the dead-ending literature is about.

That is what made the rung above’s question a good one rather than a restatement. The anchor’s four negative results were all about an order, and an order failing says nothing about whether the equality succeeds. Asking the coarser question was the right move and it is the reason this page exists.

And the coarser question has the same answer, for a reason that has nothing to do with the class. An equality quantified over a rich universe is as demanding as an order quantified over it — more so, in one direction, since it requires agreement rather than dominance in every sum. What makes a quotient small is not its coarseness but its universe, and that is the finding two sections below.

What separating costs #

If dead-endedness does not make the quotient smaller, the remaining form of the question is whether it makes the positions harder to tell apart — whether the dead-ending ruleset needs more company before its positions come unstuck from each other.

Five addends, on both sides. The first two do most of the work on both — four classes to twelve, on each — and the last three finish the job. The dead-ending ruleset is not harder to separate and it is not easier.

The agreement of the first two steps is worth more than the agreement of the total. Two universes of different sizes, over rulesets with different numbers of positions, both go from four classes to twelve on their first chosen addend and then to twenty and sixteen on their second. A shared total could be a coincidence of two small integers; a shared curve is the two populations behaving the same way under the same procedure, which is the strongest form the null takes anywhere on this page.

So the question has now been asked in every form it has. Does the class make the quotient smaller? No: both are trivial. Does it make separation dearer? No: five and five. Does it make the comparison test better? That was the rung below’s question and the answer was less than a control.

Why nothing collapses #

The negative has a mechanism, and the mechanism is more useful than the negative.

A misère quotient is small when its universe is poor. The construction in the literature takes the closure of one game’s own positions under addition and quotients over that, and the smallness of the result — the reason misère quotients are worth building at all — comes from the restriction. Forbid most of the company and positions stop being distinguishable; allow it back and they separate again.

The universe here is not poor. It holds every position of the ruleset, every follower of every position, and every sum of two of them — 276 addends for 22 positions. Against twelve addends apiece, almost nothing stays identified, and no property of the ruleset was ever going to change that.

So the class was never being tested. What was being tested was the universe, and the universe is a choice made by whoever sets the question. That is the same lesson equal in every company draws for normal play — the quantifier is the content — and it arrives here as the reason a well-posed comparison came back empty.

What the anchor has now measured #

The anchor is now finished asking, and the honest summary is uncomfortable and worth stating plainly.

Dead-endedness is a real property and this pair really does turn it on and off. Nobody comes back establishes what it means — a player with no move never regains one — and the jump clause is a clean switch: without it, no player ever gets a move back, over every strip to seven squares; with it, thousands do.

And on this pair it buys nothing measurable. Not in comparison, where a control does better. Not in the quotient, which is trivial on both sides. Not in the cost of separating, which is identical.

That is not a claim that the class is worthless in general, and it is important to say what it is instead. The literature’s results about dead-ending universes are theorems about particular universes chosen to be small — and this page’s last figure is the reason those two things are consistent. A class that helps by making a restricted universe well-behaved will show nothing at all when the universe is unrestricted, because there is nothing left for it to be well-behaved about.

What this anchor has produced is therefore a method rather than a result about Toads and Frogs. A matched pair with one clause switched, a control that knows nothing about the class, and the same measurement on both — and the finding, three times over, that the class-specific gain is inside what the control gets for free. That is what it looks like to hold a named class to the standard this site holds a rule of thumb to.

What a null result of this shape is worth #

Three measurements on one matched pair, all coming back at nothing, is the sort of outcome that reads as a wasted ladder, and it is worth saying why it is not.

The pair itself is the contribution. Before the clause that turns the class off there was no way to measure what a named class buys, because every measurement of a class is confounded: a ruleset that is dead-ending differs from one that is not in every other respect too, so a difference in behaviour could be the class or could be the game. One clause, two rulesets, the same strips and the same evaluator is the design that removes the confound, and it is transferable — the same construction would work on any class with a clause that switches it.

And the control is what makes the nulls readable. A class-specific test gaining 4.9 points looks like evidence until a rule knowing nothing about the class gains 6.3 on the same data. Without the control this anchor would have reported a positive result four rungs ago and been wrong. Wrong in one direction only is where that test’s one-sidedness was established, and it is the property that survives every one of these negatives — the test never accepts a comparison that fails, which is the half of it that is worth keeping.

So what the anchor has is a method that produces falsifiable answers about classes, and one class it has answered on one universe. The next section says what the answer does not cover, and it covers rather a lot.

What the solver computed, and how #

Every strip of at most five squares holding at least one toad and at least one frog — 244 of them — under two rulesets that differ in a single clause: whether a piece may jump over an opposing piece into the empty square beyond.

Each strip is evaluated as a partizan game and reduced to canonical form, which gives 22 distinct positions with the jump and 19 without. Before that reduction is used, every canonical class is checked: the misère outcomes of its strips are computed from the unreduced games and compared, and a class holding two different outcomes would mean the reduction had identified positions the question separates.

The universe is the closure used throughout this anchor: nought, every distinct position, every follower reached by descending through options, and every sum of two of them — 276 members with the jump and 210 without. Each position is given a signature, which is its misère outcome added to each member of the universe in turn, and two positions are in one class exactly when their signatures agree. That is the quotient computed directly rather than by comparing every pair.

The separating set is found greedily: start with the empty sum, and repeatedly add whichever universe member splits the most classes, until every position stands alone. Greedy gives an upper bound on the minimum rather than the minimum itself, and the same bound is computed the same way on both sides — which is what the comparison needs, since the question is whether the two costs differ rather than what either is exactly.

Two things are asserted rather than reported: that neither quotient identifies a pair, and that no canonical class holds two misère outcomes.

Where the model stops #

Five squares. Twenty-two positions is a small population and the quotient’s triviality could in principle be a small-population effect — with more positions there is more chance two of them are indistinguishable. The direction of that objection is against the finding, so it is worth stating: a larger sweep might find a collapse. What it could not do is find one on the dead-ending side and not the other, since the universe grows with the population on both sides at once.

Greedy separation is a bound. Five is an upper bound on the minimum separating set, on both sides, computed identically. The true minimum might be four on one side and five on the other, and nothing here would see it. A minimum separating set is a set-cover problem and exact set cover on 276 candidates is affordable; it was not run, because the comparison is what the page is about and the bound is computed the same way twice.

Misère play throughout, and it is the whole point — every result here is about the convention where the player unable to move wins, and none of it holds under normal play, where the quotient of these positions is their values and the collapse is enormous.

And the figures cannot show a quotient, because there is none to show. Six tables of counts describe an equivalence relation that turned out to be equality, and the drawing a reader would want — positions grouped into classes, with the sums that hold each group together — does not exist on this population. What could be drawn is the four outcome classes and the first addend that breaks them apart, which is one step of a refinement that then runs out of anything to say.

Where the ladder goes next #

The dead-ending anchor has five rungs: nobody comes back, what the class does not buy, the test it was supposed to license, the clause that turns the class off, and now the quotient.

The rung above is the poor universe, and it is the one the three negatives here point straight at. Every measurement on this anchor has used the richest universe available, and the class’s reputation is built on restricted ones — so the experiment that has not been run is the same matched pair with the universe deliberately impoverished: take the closure of a single strip’s own positions rather than of all 244, and ask for the quotient there. That is the construction the literature actually uses, it is smaller and cheaper than anything on this page, and it is the only version of the question in which dead-endedness has room to matter. If the class buys nothing there either, the anchor has a real result; if it buys something, the anchor has found the hypothesis it has been missing for five rungs, which is not dead-ending but dead-ending and alone.

Two neighbours are worth the trip. Misère quotients is where the construction is built and where its smallness is the point, and it is the page whose universe this one should have copied. And the same strip without the jump is where this pair of rulesets is set out under normal play and the clause’s effect on values is measured, which is worth reading beside a page that finds the same clause doing nothing at all one convention over.