The condition the recursion rests on

Every value on this site is defined by the same shape of sentence: the value of a position is built from the values of its options. That is a recursion, and a recursion needs somewhere to stop.

The usual assumption about where is wrong twice over. It is not that a game has finitely many moves left, and it is not that a position has finitely many options. Both of those can fail while the theory holds, and both can hold while it fails.

The condition is: no infinite sequence of moves exists. Nothing else, and nothing less.

Unbounded and still finite #

Poker Nim is the clean counterexample to the first wrong assumption.

Strip the reserves away and the argument is the boring one. Three Nim heaps of three, five and seven hold fifteen counters, every move takes at least one, and the game is over within fifteen moves; the count is the bound and there is nothing more to say.

Put the reserves back and that argument is gone. There is no bound on how long a game of Poker Nim can last that depends only on the heaps: a player with a large reserve can add counters for a long time. There is no bound on the size a heap can reach either. And every game of Poker Nim ends.

The reason is that the reserves are finite and the additions are reversible — a counter put back can be taken off again immediately, returning the position to what it was with one fewer counter in reserve. So a quantity does decrease over any two moves, and the game cannot run for ever.

That is the shape of every termination argument worth having: find a quantity that cannot decrease for ever, and show that play decreases it.

Finitely many options and never ending #

Now the second wrong assumption, and it is the sharper one.

The game called on has exactly one option, for each player: a move back to itself. One option is as few as a position can have while still having a move at all, and no game of on ever ends.

So finite branching is not the condition either. What matters is not how many moves are available but whether an infinite sequence of them exists, and on has one — the same move, for ever.

One node is the smallest graph on which that can happen, and it is worth seeing that nothing changes when there is somewhere to go. A cycle offers a genuine choice of destination at every step and gets the same answer, because the analysis cares about where a chain of moves ends and not about how long it is.

The quantity that falls, game by game #

Every termination argument on this site is the same shape with a different quantity, and collecting them makes the shape visible.

Nim: the total number of counters. Every move removes at least one.

Poker Nim: the counters on the board plus twice the counters in reserve. An addition moves one counter from reserve to board, which lowers that total by one; a removal lowers it by one as well.

A subtraction game: the heap size, which falls by at least the smallest move.

Domineering, Clobber, Col, Snort: the number of empty or unpainted squares, which falls with every move because every move fills something.

Hackenbush: the number of edges, which falls by at least one per cut and often by more.

Toads and Frogs: the total distance the toads have left to travel plus the distance the frogs have. Each move reduces it by one or two, and no move increases it — which is a slightly better argument than “the animals move one way”, because a hop moves two squares and the naive count would have to handle it separately.

Six games, six quantities, one argument. The reason the condition is stated abstractly — no infinite run of moves — rather than concretely is that the concrete quantity is different every time, and a definition that named one of them would exclude the others.

Three ways to fail #

Collecting them, because they are genuinely different failures and only one of them is loopiness.

A cycle. Play returns to a position it has already visited, so a sequence of moves repeats for ever. That is a loopy game, and the replacement machinery is retrograde analysis.

An infinite descent without repetition. No position recurs and the game still never ends — possible when the position space is infinite. A game where a player must name a smaller integer each turn, and the integers are allowed to be negative, is the standard example: every position is new and nothing terminates.

Infinitely many options at one node. Not a failure of termination by itself — a position with infinitely many options can still have every play end after two moves — and it is a failure of this site’s evaluator, which enumerates options. It is the boundary the recursion this site cannot run is about.

The first two put a position outside the theory. The third puts it outside the machinery, which is a different and more embarrassing kind of limit — the day-by-day construction run without stopping reaches objects whose option sets have no last member, which the theory does not mind and this evaluator cannot enumerate.

There is one more thing to say before leaving the list, because the first failure has a case that looks as though it should be fatal and is not. A game can fail the condition outright and still have an outcome.

So the condition is what guarantees an outcome and is not what an outcome requires. Losing it costs the method outright — there is no recursion to run and no value to return — and whether it costs the answer as well depends on the graph. off keeps its answer because the infinite run belongs to the player who was winning anyway; on loses its answer because the same run is available to both.

Six quantities, one object #

The section listing a decreasing quantity per game ends by saying the abstract condition is stated abstractly because the concrete quantity is different every time. There is a name for what all six are instances of, and having it makes the three failures fall into place.

Each of those quantities is a rank: a function from positions to a well-ordered set, strictly decreasing along every move. Nim’s is the counter total, Hackenbush’s is the edge count, Toads and Frogs’ is the remaining displacement — six functions into the natural numbers, one per game.

And the abstract condition is exactly the existence of such a function. No infinite run of moves exists is the statement that the position graph is well-founded, and a well-founded order always admits a rank function into the ordinals. So the six concrete arguments are not six unrelated tricks that happen to work; they are six exhibitions of the same object, in the easy case where the ordinal is finite.

That is also what a birthday is. The birthday of a position is its rank, and the reason the day-by-day construction works is that the rank function orders the positions so that every option is strictly earlier.

Which settles what the third failure is #

With the rank in hand, the three failures stop being a list and become two of one kind and one of another.

A cycle and an infinite descent without repetition are the same failure: there is no rank function, because there is an infinite descending sequence and ordinals do not descend for ever. Cycles are the visible case and the unrepeating descent is the invisible one, and the theory is equally silent about both.

Infinitely many options at one node is not a failure of the condition at all, and the rank says so precisely. A position with infinitely many options can be perfectly well founded: give it rank $\omega$, give its options ranks $0, 1, 2, \ldots$, and every move descends. Ordinals were built to make exactly that arrangement legitimate, and it is the arrangement the number $\omega$ itself has — an option set with no last member, every member finite, and a rank one step above all of them.

So the essay’s own hedge is right and can be made sharp. The third item is a limit of the machinery and demonstrably not a limit of the theory, because the theory has a rank for it and the evaluator has no way to enumerate the options. That is a stronger statement than “more embarrassing”: it says the boundary is in the code, and where the boundary sits is checkable rather than a matter of opinion.

And it says which games need the transfinite #

That reading also gives a test for when the finite arguments run out.

Every game with a bounded number of moves has a finite rank, and the six listed above are all of that kind: the quantity is a count of something on the board, so it is a natural number and the argument never mentions ordinals.

A game whose plays are all finite but not boundedly so needs $\omega$ or more — and this site has one. It ends and nothing says when is about exactly that: every play terminates, no bound on the length exists in advance, and the rank is therefore past every natural number. The essay’s list of six could not have included it, because there is no count of anything on the board that falls.

So the condition’s abstractness is load-bearing rather than fastidious. A definition naming a decreasing count would cover six games and exclude the one that makes the point; a definition naming well-foundedness covers all of them, covers $\omega$, and draws its boundary in the one place a boundary belongs — at an infinite play, which is the only thing that ever actually goes wrong.

What the condition buys #

Given no infinite run of moves, everything else follows, and it is worth listing what “everything else” is.

Induction is available. Every proof in this subject is an induction on the position, and the induction is well founded exactly because no infinite descent exists. Without it, none of the theorems are even statable.

Every position has an outcome. Somebody wins, because play stops and whoever cannot move has lost. With infinite play there is a fifth possibility and the four classes stop being exhaustive.

Values exist. The recursion terminates, so name() returns something, and the canonical form is reachable in finitely many reductions.

And the two players’ fortunes are decided in advance. That is Zermelo’s theorem, which is exactly the statement that backward induction terminates on a finite game — a theorem about labelling rather than about any particular game.

The other way to end a game #

Not every ending argument is about a decreasing count of moves, and the most elegant one on this site is about something else entirely.

That is a termination argument by conservation rather than by descent: a quantity is invariant, another grows, and the two together bound the length. It gives more than termination — it gives the exact length, so the winner of Brussels Sprouts is known before the first curve.

Ordinary Sprouts is the contrast, and it is worth keeping the two apart. Both games end; only one of them ends after a number of moves computable from the starting position, and the difference between them is the difference between a game and a piece of arithmetic wearing a game’s clothes.

What a violation actually costs #

It is tempting to treat the condition as a technicality, and the cost of losing it is severe enough to be worth itemising.

No values. Not “harder to compute” — there is no object for the recursion to return, and the loopy theory replaces values with a different apparatus.

No group. Every game has a negative because the mirror strategy answers every move and the game ends. Without an ending, the mirroring runs for ever and on + off is a draw rather than zero — which is one part that never ends.

No induction, so no theorems. Simplicity, canonical form, the mex rule, Sprague–Grundy: every one of them is proved by induction on the position.

The fifth outcome, and why it is not a draw in the usual sense #

When the condition fails, a fifth answer appears, and the word attached to it is worth pinning down because it does not mean what it means in chess.

A draw here is not an agreement, a repetition rule or a stalemate. It is the verdict neither player can force a win, and it arrives as a residue: the backward analysis settles what it can from the ends inward, and whatever is still unlabelled when nothing more can be deduced is drawn.

That is a definition by exclusion rather than by test, and it is the honest one — there is no property of a position that says “this is a draw” other than the analysis failing to reach it. An outcome with no value behind it is the essay about what that residue is like.

Two consequences follow immediately. There is no value to attach to a drawn position, because values were built by a recursion that has not terminated there. And the four outcome classes stop being exhaustive, so every theorem quantifying over “all positions” has to be re-examined.

Which is why this essay exists as its own rung rather than as a paragraph in the loopy one. The condition is the boundary of everything, and knowing exactly where it sits is the difference between a theory with a domain and a theory with an assumption.

Where the model stops #

Transfinite games satisfy the condition and are not here. A game with infinitely many options at a node can still have no infinite play — every line ends after two moves, say, with the first move choosing from infinitely many. The theory handles those and this site’s evaluator does not, which is a limitation of the code rather than of the subject.

“No infinite run” is not decidable by inspection. For a finite position graph it is a cycle check. For an infinite one it is a proof obligation, and the proof is different for every game — Poker Nim’s needs the reversibility argument, Sprouts’ needs a conserved quantity, and a new game needs a new one.

And a game can end and still be unbounded. Poker Nim has no bound computable from the heaps alone. There is nothing wrong with that: the condition asks for no infinite play, not for a length known in advance.

Why this is the right condition and not a stronger one #

A reader might reasonably ask why the theory does not simply require the position space to be finite, which would be easier to check and would cover every game on this site.

The answer is that the weaker condition costs nothing and buys the transfinite half of the subject.

It costs nothing because every proof uses induction on the position, and induction needs a well-founded order rather than a finite one. Nothing anywhere in the theory counts positions.

It buys the numbers past the finite ones. The construction run without stopping reaches ω, its reciprocal and a third — objects with infinitely many options that are perfectly good games, and every play from them still ends. A theory requiring finiteness would exclude them, and the surreal numbers with them.

That is a general habit worth having: when a condition can be stated as no infinite descent rather than as finitely many things, the first is usually both weaker and enough. It is the same distinction that separates a proof by induction on the natural numbers from one by counting, and it is why the subject’s foundational papers state the condition the way they do.

What the picture cannot show #

Termination is a property of every play from a position, and a figure draws one position.

The loopy figures come closest: a cycle drawn as a cycle is a picture of an infinite play, in the sense that the eye can follow the arrows round for ever. What it cannot show is the absence of such a path in the games that do terminate — the no-cycles graph is drawn as a graph with no cycles, and a reader has to check that by looking, which is exactly what a proof would have to do.

The other invisible thing is Poker Nim’s argument. The figure draws heaps and reserves and reports that the reserves change nothing, verified over every position in range. The reason — that an addition is answered by a removal, so a quantity falls over any two moves — is a sentence rather than a drawing, and no arrangement of counters contains it.

Checking it, in practice #

The condition has to be established for every game before anything else is computed, and it is worth being explicit about how this site does it, because the answer is not uniform.

For a game with a finite position space and a decreasing quantity, the argument is a sentence and the code carries no check at all. Nim, Domineering, Hackenbush, the subtraction games: the memo table is keyed on the position and the recursion is trusted to bottom out.

For a game where that is less obvious, the argument is turned into a test. Poker Nim’s reversibility is checked over 1,125 positions against the nim-sum rule; Sprouts’ termination is checked by playing games out and reporting the range of lengths.

And for a game that does not terminate, the code refuses the recursion and uses retrograde analysis instead — a completely different algorithm whose output includes the positions it could not settle.

The middle case is the one worth watching. A recursion on a game that does not terminate does not return a wrong answer; it fails to return, or it exhausts a stack. This site’s evaluator memoises with a placeholder before recursing precisely so that a cycle produces a diagnosable failure rather than a hang — which is a coding decision that exists entirely because of the condition this essay is about.

The convention, named #

Normal play, and one term worth naming because the literature uses it and this essay has been avoiding it.

The condition has a name: the descending game condition, or the requirement that a game be short when the position space is finite as well. Short games are what this site computes with: finitely many positions, no repetition, and every play ending.

The second convention is that a player who cannot move loses. That is what makes “the game ends” and “somebody has won” the same event. Under misère play the ending is the same and the verdict is reversed; under a scoring convention the game may end with neither player stuck, and counting at the end is the essay about what that does to everything above.