What a wider pool rescues

Two misère outcomes are not enough built a sixteen-cell table — one cell per pair of outcome classes, holding the set of outcomes their sums actually took — and found the misère half of it almost entirely ambiguous. Four cells held two or three outcomes rather than all four, which is the shape a constraint takes, and the essay declined to call them one:

The misère table’s four near-miss cells hold two or three outcomes rather than four. Whether they survive a pool of a hundred positions is a computation this site can run, and the expected answer — that they do not — is a prediction the machinery could refuse.

The computation has been run, on four pools rather than one, with the normal-play table beside it as a control. The prediction is right, and it is right emphatically.

At a hundred and thirteen every cell holds all four outcomes. Nothing survives.

What a cell short of four means #

The table’s construction is worth restating because everything turns on what a cell is.

Take every ordered pair of positions in the pool. Classify each by its misère outcome — P, N, L or R — and classify the sum. The cell at row P, column N holds the set of outcomes that sums of a P-position and an N-position took, over the whole pool.

A cell with one outcome in it is a theorem waiting to be proved: those two classes determine the answer. A cell with four is a completed refutation: the classes say nothing. A cell with two or three is neither, and it is the interesting case — a partial constraint, if it is real, and the only kind of thing a partial theory could be built on.

It is also exactly the case that cannot be read off one table. Widening the pool can only ever add outcomes to a cell, never remove one, so the sequence of tables is monotone and the question is this cell constrained or is the pool small? is answered by watching rather than by arguing.

The ambiguity is what makes the misère theory hard, and the near-ambiguity is what makes it look as though something might be salvageable. A cell reading $\{P, N\}$ says these two classes never sum to L or R — which, if true in general, is a real constraint and something to build on. Nine such cells is still a table with a shape to it, and a reader who stopped here would be entitled to go looking for the theorem behind the shape.

The pools, and what happens to them #

Four pools, each larger than the last, each a superset in spirit if not in membership.

Ten positions — the original: $0$, $\pm 1$, $\ast$, $\uparrow$, $\downarrow$, $\{2 \mid 0\}$, $\{1 \mid -1\}$, $\ast 2$, $\{0 \mid -1\}$. Fifteen of sixteen cells short. One determined: N + N gave nothing but N.

Twenty-two positions — every value born by day two, in full. Nine cells short. The other six have been filled in by positions the ten did not contain.

A hundred positions — the first hundred values born by day three, in the order the enumeration built them. One cell short: N + N, which takes P, N and R and never L.

A hundred and thirteen positions. Nothing short. Every pair of misère outcome classes takes every misère outcome, over 12,769 sums, each one played out under the misère convention rather than read off any value.

The fourth pool is not a round number and that is the point of it: 113 is the shortest prefix of the enumeration whose table is full, found by extending the pool one value at a time. A hundred and twelve leaves the last cell short and a hundred and thirteen does not.

The cost is worth pausing on. Twelve thousand sums is not a large computation by this site’s standards — a census of half a million forms is what exhausts this machine — and it is a large computation for this question, because there is no algebra to shorten it with. Under normal play the outcome of a sum is read off a value computed once per position; under misère every sum is a fresh search over the tree of the whole board, and the interning table this site keeps fills up on a pool twice this size.

The monotonicity is asserted rather than assumed: a wider pool can only add outcomes to a cell, so a cell that lost one between two tables would mean the pools are not nested in the way the argument needs. That check runs whenever the table is drawn, and it has never fired.

The one that nearly survived #

The last cell standing is worth a paragraph, because at a hundred positions it looks exactly like the constraint the rung below hoped for.

$N + N$ takes $P$, $N$ and $R$ — and never $L$. Sixteen cells and one asymmetry, in a table whose whole subject is that misère play has no structure. It would say: a sum of two first-player wins is never a win for Left specifically.

It is an artefact of the pool, and the reason is visible once stated. The hundred values are the first hundred of the day-three enumeration, in construction order, and that order is not symmetric under negation. Take a hundred values and their negatives instead of a hundred values and the cell fills immediately; carry the same construction order on for thirteen more values and it fills as well.

That is a caution worth keeping, and it generalises past this page. A slice of an enumeration is not a sample of a population. An asymmetry in a truncated list is evidence about the truncation before it is evidence about the subject, and the truncation here was chosen for no better reason than that a hundred was the number the rung below named.

Why every cell fills, put positively #

The census answers the question and does not explain it, so the explanation is worth attempting separately.

Under normal play nine of the sixteen cells are determined, and every one of them is a theorem with the same one-line proof: a P-position is worth zero, and adding zero to anything changes nothing. So P + X = X for every class X, which fills a whole row and a whole column with certainty.

Under misère there is no zero. Misère play has no negatives is the other half of the same loss: a position and its mirror image do not cancel, so no position acts as an identity for the sum. Without an identity, the row and column that would have been theorems become the most ambiguous rows in the table — and the census bears that out, since P + L and P + R are among the first cells to reach all four outcomes.

The honest comparison is that outcomes do not add under normal play either — three pairs of first-player wins whose sums are nought, two and ⇑ make the point in one line, and it is a whole essay. The difference is what happens next. Normal-play positions have values, the sum’s value is the sum of them, and the outcome falls out of the value; the seven ambiguous cells are a curiosity because nothing depends on them. Under misère there is nothing to fall out of, and the sixteen ambiguous cells are the whole of what can be said.

So the emptiness of the misère table is not an accident of the pool. What was an accident of the pool is how full it looked at ten positions.

The control: the same widening under normal play #

A census that reports something disappearing has to answer one question first — whether everything disappears when the pool grows, in which case the measurement is about the method and not about misère play.

It does not, and the contrast is the sharpest thing on this page.

The normal-play table does not move at all. Nine cells determined, seven ambiguous, thirteen short of four outcomes — the same numbers on ten positions and on a hundred and thirteen, with a hundred and twenty times the sums going through it. Its constraints are theorems and a theorem is not embarrassed by a larger pool.

The misère table collapses from fifteen short cells to none over the same widening. Every one of its apparent constraints was a shortage of positions.

That is the finding stated at full strength. It is not that misère play is less constrained than normal play; both essays’ tables agree that the outcome class of a sum is not determined in either convention. It is that under normal play what looks like structure is structure, and under misère what looks like structure is a small sample.

Six sums a cell #

The arithmetic of the small pool is worth doing, because it makes the collapse predictable rather than surprising, and it is the reason this page’s method is worth reusing.

Ten positions give a hundred ordered pairs spread over sixteen cells: about six sums a cell. A cell reports determined when the outcomes of its sums are all the same, and six draws are not many — a cell whose sums really can come out any of four ways will look determined a noticeable fraction of the time simply by not having been asked enough. A hundred and thirteen positions give 12,769 pairs, which is eight hundred a cell, and eight hundred draws miss nothing that is there to be found.

So the fifteen short cells at ten positions were never fifteen constraints. They were fifteen cells with six observations each, and the census is the story of what happens when the same cells get a hundred and thirty times as many.

And that is exactly why the control matters more than the result. The normal-play table is built from the same six sums a cell at the small pool, and it does not move: nine determined, seven ambiguous, at six observations and at eight hundred. A sampling explanation would predict it to fill in too, and it does not, because its cells are shut by theorems rather than by shortage — a P-position is worth zero, adding zero changes nothing, and no number of extra sums produces a counterexample to that.

Which gives a test that costs nothing and settles a question that otherwise looks unsettleable. Widen the pool and see what moves. A table whose empty cells survive a hundredfold widening is reporting structure; a table whose empty cells fill in was reporting a sample, and the order they fill in says which of them were closest to being real. Neither reading requires knowing in advance whether a theorem exists, which is the situation anybody building a table over an unfamiliar convention is actually in.

The uncomfortable corollary is that every small table on this site is a candidate for the same treatment, including the ones whose emptiness looks obviously meaningful. The misère table looked obviously meaningful at ten positions. It is the reason the widening was run at all.

Which cells go first, and what that says #

The order the cells fill in is informative, and it points at exactly the missing object.

Between the ten and the twenty-two, six cells fill: P + L, P + R, L + P, R + P, L + R and R + L. Every one of the first four involves a P-position, and P is the class the normal-play theory has a theorem about — a P-position is worth zero and adding zero changes nothing.

So the cells that fall first under widening are precisely the cells that would have been theorems if misère play had a zero. There is no zero — misère play has no negatives is the same loss stated for the other operation — and the census watches the consequences arrive in order of how much they depended on it.

The nine still short at twenty-two are the ones involving N, L + L and R + R, and those go between twenty-two and a hundred. The very last to fall is N + N, which is also the only cell that was ever determined on the smallest pool. The most structured-looking cell in the original table is the last one to admit it has no structure.

What this closes and what it does not #

It closes the question the rung below asked, and closes it in the direction that leaves nothing behind: the outcome class of a misère sum is unconstrained by the outcome classes of its parts, full stop, with no residual cell to build a partial theory on.

That is worth stating as a positive result rather than as an absence. A partial constraint would be something to look for a proof of and something to design around; a complete refutation means that any misère method has to carry more per position than an outcome class, and it fixes the floor for what “more” has to mean.

What carrying more looks like in practice is the misère quotient: a monoid computed per game, which recovers comparison inside one universe and says nothing outside it. Nim over heaps of at most three needs six classes where normal play needs four. The construction exists because the table above is empty, and its cost — one computation per game, with no theory across games — is what the emptiness buys.

What it does not close is anything about restricted universes. The pools here are drawn from the whole population of short games, and a claim about all games is compatible with a strong claim about a restricted class — which is exactly what a misère quotient is, and what a dead-ending universe is. The hundred and thirteen positions above say the general table is empty; they say nothing about the table over a family closed under the right operations.

What the census cannot reach #

The pools are values born by day three, so every position in them has a birthday of at most three. A pool of positions from a real game — Domineering boards, Nim heaps, Toads and Frogs strips — is a different population, and the misère outcome of a sum of those is what a player would want.

That difference matters more than usual here, because misère quotients are computed per game precisely because the game a position comes from is part of the answer. A table over abstract values is the widest possible statement and, for the same reason, the least useful one.

It is worth being clear about which direction the gap runs. A pool of Nim heaps would give a fuller table than the abstract pools do — Nim is tame, its misère behaviour is very nearly its normal-play behaviour, and a table built over it would show constraints that are real inside Nim and false outside it. So a reader who has met misère play through Nim has met the friendliest case in the subject, and the abstract pools above are what the general case looks like when nothing is being restricted.

The third limit is about the shape of the count. Each table above reports how many cells are short of four outcomes, which treats a cell holding three the same as a cell holding two. A finer measurement would weight by how much of the space each cell fails to reach, and would show the collapse as a curve rather than as four integers — but the integers are what the prediction was stated about, and the curve would not change the answer.

The second limit is that the outcome class is the coarsest thing to tabulate. Nothing here says what happens if the cells are indexed by the genus instead — a finer invariant that recovers real information for the games behaving like Nim, and the natural next table to build.

The convention, named #

Misère play throughout the tables that matter: the player unable to move wins. The normal-play table beside it is the control and uses the ordinary convention.

Every outcome above was computed by playing the position out under the stated convention rather than read off a value, because under misère there is no value to read off. That is the whole reason the census is a census: nothing about it can be shortened by an algebra, and each of the 12,769 sums in the largest table was evaluated on its own.

Where the ladder goes next #

The misere anchor has six rungs, running from the convention through the quotients, the missing negatives and the empty outcome table to this — the question of whether the table was ever as full as it looked.

The rung above is the finer table. The outcome class is the coarsest invariant available and its table is empty; the genus is the next one up, it is defined for impartial games, and the question of which pairs of genus symbols determine a sum’s genus is already answered on this site for nine games. Doing the same for partizan misère play is not available, because there is no partizan genus — and that gap is the rung.

Two neighbours are worth the trip. Two misère outcomes are not enough is the rung below, whose prediction this page tested. And nobody comes back is the restriction that makes misère play tractable again, and the reason the emptiness here is a statement about all games rather than about the ones anybody works with.