Nobody comes back

Under normal play, a player with no move has lost and there is nothing more to ask. Under misère play they have won — and that single reversal is why the misère theory is a catalogue of losses rather than a theory.

The difficulty is specific and it is worth naming before the class that avoids it. Under misère play a component that has finished still matters, because it decides the parity of everything else on the board. So a player has to know not only what each component is worth but whether it is over, and over is not a stable notion: in some games a player who has run out of moves can be handed one back.

The games where that cannot happen are called dead-ending, and it turns out to be the hypothesis under which the modern misère results are stated.

Nine of the eleven are dead-ending. Two are not.

The definition, precisely #

An end for a player is a position from which that player has no move at all. A ruleset is dead-ending when every end is dead: once a player has no move, nothing either player does gives them one again.

Two things about that are easy to get wrong, and the second one is the reason this page exists as a measurement rather than a paragraph.

It is a property of the whole position graph, not of the position in front of the reader. A ruleset with one board in a thousand carrying a resurrection is not dead-ending; the class is a claim about the rules. So the check has to ask the question at every position reachable from a start, not at the start.

And it is a property of the rules rather than of the values. A position where Left has no move can be worth a game whose canonical form has Left options, because a value is a class of positions and the canonical form is only one member of it. Running the test over canonical forms therefore replaces the fact under test with an equal game that need not have it, and every ruleset comes out dead-ending. That is not a hypothetical: it is what the first version of the machinery here did, and it reported eleven of eleven with a straight face.

So the walk is over board states. Nothing on this page evaluates anything.

The two that fail, and why #

Toads and Frogs fails, and the culprit is the hop.

On the strip $.\,\mathrm{T}\,\mathrm{F}$ the toad is against a frog with nothing past it, so Left cannot move. Right’s frog hops the toad and lands on the empty square: $\mathrm{F}\,\mathrm{T}\,.$ — and now the toad has an empty square in front of it. A player with no move has been given one, by their opponent, in one move, on a board of three squares.

Amazons fails for a different reason and a more obvious one. An amazon that moves away frees the square it was standing on, and a Left amazon walled in by a Right amazon becomes mobile the moment the Right amazon leaves. The witness turns up on a strip of five: Left’s amazon at one end, Right’s beside it, an arrow past them, and Left with nowhere to go — until Right steps aside.

The two failures are worth contrasting because they are not the same phenomenon. The Amazons one is a vacancy: a square that was occupied stops being occupied, and the game has an explicit move that does it. The Toads and Frogs one is a reordering: no square is freed that was not freed before, and what changes is which piece is in front of which. The second is far easier to miss, which is why the smallest witness for it is three squares and the smallest for Amazons is five.

Everything else on the table survives, and the reasons are all of the same shape: a move only ever removes possibilities. A domino covers squares. A topple deletes dominoes. A shove pushes a coin over the cliff. Colouring a vertex forbids more colouring and permits none. A NoGo stone fills a point and never vacates one. In each case the set of legal moves for the player who is stuck can only shrink.

The clause, isolated #

The sharpest thing on this page is the ninth row of the table.

The same strip without the jump is the essay about the game Toads and Frogs becomes when the hop is deleted — pieces shuffle forward into an empty square and can never pass each other. That one clause is worth a great deal: it removes every fraction from the game’s values, as the strip where every number is a whole one measured over 7,746 numbers.

It also decides dead-ending. Without the hop, a frog can never end up behind a toad, so it can never vacate a square in front of one, so a stuck toad stays stuck. The jumpless game is dead-ending and the game with the hop is not, on the same boards, with one line of the rule different.

The claim that the clause is the whole mechanism is checkable, and it is worth checking rather than repeating, because a clause that merely correlates with a property looks exactly like one that causes it.

Four hundred and ninety-eight to nought is a clean switch, and a clean switch still leaves open how the recoveries happen — a clause can be responsible for a property by several routes, or by one. Looking at the recoveries themselves settles that too.

That is the whole mechanism, and it explains the other ten rows at once. A ruleset is dead-ending when no move reverses the relative position of two pieces. Toads and Frogs has one that does; Amazons has one that does; nothing else here has one at all.

What the class buys #

The reason to care is that a dead-ending universe is where misère play becomes tractable, and the argument is short enough to give.

Two misère outcomes are not enough establishes the disaster: under misère play the outcome class of a sum is not a function of the outcome classes of its parts, so nothing composes. The repair everybody reaches for is the misère quotient, which restricts attention to sums of positions from one game and recovers a workable algebra there — and pays for it by having to be recomputed per game.

A dead-ending universe is a much larger restriction to sit inside, and the property is what makes the induction work. When a component is finished for a player it is finished for good, so the parity contribution of that component is settled and can be carried forward. When it is not — when a frog can hop back and give a toad a move — the contribution is not settled and the induction has nothing to stand on.

The trade between the two constructions is what makes the class worth identifying at all. A misère quotient is computed per game: it recovers comparison inside one ruleset and has to be built again for the next one, and for many rulesets it is infinite. A universe is a hypothesis stated once that a whole family of games satisfies, so a theorem proved over it applies to every ruleset in the family without further computation. One is a machine run per game; the other is a condition checked per game and then never mentioned again.

So the table above is a list of which of this site’s games the modern misère literature has anything to say about. Nine yes, two no — and the two are the two whose values under normal play are already the awkward ones.

The nine, and what they have in common #

Reading down the nine that pass, one description covers all of them and it is not the one the definition suggests.

The definition is about a player’s move supply. What the nine share is something about the board: every move consumes a resource that is never replaced. A domino consumes two squares. A topple consumes dominoes. A shove consumes a coin’s distance from the cliff. A colouring consumes a vertex. A Clobber move consumes an enemy stone. A NoGo stone consumes an empty point. In every case the sentence is about the board’s furniture rather than about anybody’s options, and the step from one to the other is taken silently — which turns out to matter, and is what the section after next is about.

The two that fail consume nothing. A Toads and Frogs move rearranges pieces on a fixed strip; an Amazons move rearranges an amazon and burns one square, and the rearrangement is the part that matters. Both games terminate — Toads and Frogs by a bound on total displacement, Amazons by the burnt squares — but the quantity that goes down is not the quantity a player’s move supply depends on.

That is the transferable rule. A ruleset is dead-ending when the resource each player’s moves need is monotone, and a ruleset whose moves rearrange rather than consume is one to check by hand.

The clearest instance is a game that is not on the table at all. In Cram both players place dominoes on a grid, every move covers two squares, and no move uncovers any — so a player who cannot fit a piece anywhere will never fit one again, and the argument needs no walk. The same sentence with “domino” replaced covers seven of the nine rows above, which is exactly why the pattern is worth naming and exactly why it deserves the scrutiny the next two sections give it.

What the walk does and does not prove #

The asymmetry between the two answers is worth stating plainly, because the table does not carry it.

A “no” is certain. It is exhibited by two actual boards, one where a player has no move and one reached from it where they do. Nothing about the size of the board or the reach of the search qualifies it.

A “yes” is evidence. It says that across the positions reachable from three small starts — 5,334 of them in all, containing 2,286 ends — no resurrection occurs. For Domineering, Toppling Dominoes, Shove, Push, Col, Snort and Clobber there is also a one-line argument for why none can, and the walk agrees with the argument. For NoGo there is not, and the “yes” there is the one to be careful about: NoGo’s legality condition is about liberties rather than about occupancy, and a stone placed next to a friendly group gives that group more of them, so “a stone fills a point and never vacates one” is not obviously the end of the matter.

That is the honest shape of the finding: seven arguments confirmed by a walk, one walk without an argument, two refutations with witnesses, and one clause that moves a game from one side to the other.

Two properties, and the essay has been proving the stronger one #

The rule the last section extracts — a move consumes a resource and never replaces one — is a good rule and it is not the definition. It proves something stronger than dead-ending, and separating the two says exactly what the NoGo row is missing.

Monotone move supply: a player’s set of legal moves never grows, at any position, ever.

Dead-ending: a player whose set of legal moves is empty never sees it become non-empty.

The first implies the second — a set that never grows certainly never grows from nothing — and the second does not imply the first. A game in which one player’s options go from one to two, and never from nought to anything, is dead-ending and is not monotone, and nothing in the definition forbids it.

That is easy to say and it invites the reply that no real ruleset behaves that way. So the same walk is run again with the counts taken rather than the ends: every move on every reachable board applied, and both players’ number of options measured before and after.

The Toppling Dominoes case is worth following, because the argument that fails is a good argument about the wrong quantity. Toppling removes dominoes and adds none is exactly true. What it does not control is the number of distinct results: on the row LRL, Right’s two available topples both leave L, so Right has one option. Left topples to RL, and now Right’s two topples leave L and the empty row — two options where there was one. Nothing was added to the board. Two moves that had been the same move stopped being the same move.

So the one-line arguments the previous section offers are arguments for monotonicity, they establish dead-ending as a corollary, and on one of the seven rows the argument is false while the conclusion is true. That row is in the class, and it is in the class for a reason the sentence beside it does not give.

Which sharpens the NoGo row rather than the essay’s worry about it #

The same measurement re-reads the row the previous section said to be careful about.

The worry about NoGo is that its legality condition is about liberties rather than occupancy, so a stone placed beside a friendly group changes that group’s liberties and might make a previously illegal move legal. That is a worry about monotonicity, and dead-ending does not need monotonicity — a NoGo player whose legal moves went from two to three would break the monotone rule and would leave the class untouched. What would break the class is a player with nowhere legal to play at all acquiring a point, which is a much narrower event.

The narrowing is substantial. A player with no legal move in NoGo is one for whom every empty point is either self-capturing or captures an enemy group — a global condition on the whole board, not a fact about one group’s liberties. For a later stone to undo that, it would have to relieve every one of those points at once, and a stone placed by either player occupies a point and gives no player a point back.

And the stronger statement holds over the walk as well. No NoGo move anywhere in the 4,169 positions raises either player’s option count, by one, from any number — so the liberty worry, which is a real feature of the rules, does not turn into a growing move supply on any board reached here. That is more than the class asks for and it is what the figure above measures.

None of which turns the NoGo “yes” into a theorem — it is still a walk over three small boards, and this site does not promote a walk. What it does is say what a proof would have to do, and the target is smaller than the essay had been aiming at: not the liberties never help, but a player with nothing at all never acquires something.

And it re-reads the two failures #

The distinction also sharpens the contrast between the two games that fail, which the essay draws as vacancy against reordering.

Both failures are failures of dead-ending, not merely of monotonicity, and the witnesses say so: in each, a player with no move at all is handed one. That is the strong form, and it is what makes the two refutations certain rather than suggestive. Had either witness merely shown a player’s options growing from two to three, it would have refuted the monotone rule and left the class intact — and the table would have been wrong.

So the asymmetry the essay reports between a certain “no” and an evidential “yes” is even sharper than stated. The refutations are refutations of the property itself, exhibited on three squares and on five; the confirmations are walks whose accompanying arguments prove a different and stronger thing. Both halves of the table are honest, and they are honest about two different claims.

What a stuck player is worth #

There is a second reason the class matters, and it is about normal play rather than misère play — which makes it the reason a reader of this site should care even if the misère theory is not their subject.

A component in which Left has no move and Right does is worth a negative integer under normal play: Right can take moves out of it at leisure, and Left can only watch. That is what an integer is in this subject — a supply of free moves for one player — and it is why Cutcake and Shove produce nothing but numbers.

In a dead-ending game that reading is stable. Once Left is out of a component, the component is a bank of Right’s moves and will stay one, so it can be counted and set aside. In Toads and Frogs it is not: a component where Left is stuck may become a component where Left is not, and its contribution has to be re-derived.

That is a smaller claim than the misère one and a more everyday one. It is the reason a Domineering player can look at a walled-off region and stop thinking about it, and the reason a Toads and Frogs player cannot.

The other end of the same question #

There is a converse worth naming because a reader will supply it wrongly.

Dead-ending is not the same as “the game gets smaller”. Every game on this site terminates, and every one of them has some quantity that decreases — that is the condition the recursion rests on, and without it nothing here would have a value at all. Toads and Frogs terminates perfectly well; its pieces cannot go backwards and the total displacement is bounded.

What dead-ending asks is finer: not whether the game is running down but whether a particular player’s supply of moves is monotone. Toads and Frogs runs down while Left’s move count goes up and down, and that is exactly the situation the property forbids.

The extreme case makes the independence plain. A hydra game must end — every play of it terminates, provably — with nothing whatever bounding when, and a game of that kind can still hand a stuck player a move at any point before it does. Termination is a statement about the whole play running down; dead-ending is a statement about one player’s supply never coming back. The two conditions are independent, and Toads and Frogs is the instance this site has of one holding without the other: it terminates perfectly well, by a bound on the total displacement of its pieces, and it is not dead-ending.

The convention, named #

Everything measured here is measured on the rules, so the normal-play and misère conventions do not enter the walk at all — a position where a player has no move is the same position under either, and only the verdict attached to it changes.

That is what makes the property worth having. It is a hypothesis a ruleset either satisfies or does not, checkable once, and then available to any theorem stated over the class. Values quoted in this essay for the boards walked are normal-play values, computed by the site’s evaluator, and none of the classification depends on them.

Where the ladder goes next #

dead-ending opens here with the class identified and this site’s games sorted into it.

The rungs above are the ones the class exists for. 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. Which sub-universes are closed under addition is the second, and it is the same closure question equal in this company asks of a company of games, asked of a family of rulesets instead.

And the third is a classification rather than a check: which move rules can hand a stuck player a move? The answer here is “the ones that reverse the order of two pieces”, on eleven rulesets. Stating it in general, for an arbitrary rule table, is a question about rules rather than about positions and nothing on this site has asked one of those.

Two neighbours are worth the trip. Equal in this company is where restricted equality is made computable, and this class is the restriction the misère literature actually uses. And the same strip without the jump is the essay about the deleted clause, where the same one line is shown to be responsible for every fraction in the game’s values.