Loopy games

Every definition on this site is a recursion, and every recursion needs a base case. The base case is the position with no moves, and reaching it is guaranteed by an assumption stated so early it is easy to miss: play ends.

Drop it and the theory has no floor.

The assumption, made explicit #

The formal statement is that a game is short: finitely many positions, and no position reachable from itself. Every line of play then terminates, and every recursion over options bottoms out.

That assumption underwrites everything. The value recursion needs it. Canonicalisation needs it — the reduction loop terminates because options are strictly smaller. Comparison needs it. Sprague–Grundy needs it: mex over an infinite descending chain is not defined.

A game with repetition breaks all of them at once, and not by making them harder. It makes them meaningless — there is nothing to compute.

The fifth outcome #

The immediate consequence is a new possibility.

If play can go on forever, then neither player wins. Under the normal-play convention a player loses by being unable to move; a player who is never unable to move never loses, and a game in which both players can move indefinitely ends in nothing.

That is a draw, and it is the fifth outcome. The four classes — L, R, P, N — were derived from two yes-or-no questions, “can Left win moving first” and “can Right win moving first”. With draws available the questions have three answers each: win, lose, or draw. The classification grows accordingly.

Chess and Go both have draw provisions, and both need them precisely because their positions can repeat. The rules that prevent infinite play — threefold repetition, the fifty-move rule, ko rules in Go — are patches on exactly this problem, and every one of them is a rule about the history rather than the position, which is why they sit awkwardly in a theory whose objects are positions.

On, off, and the loopy values #

Conway’s treatment does not abandon values. It extends them.

Define on as the game $\text{on} = \{\text{on} \mid \;\}$: Left can move, and the move returns to the same position. Left can move forever; Right can never move.

So on is a Left win, and it is larger than every number — larger than a million, larger than any integer, because Left simply never runs out. Its mirror, off $= \{\; \mid \text{off}\}$, is a Right win smaller than every number.

Then there is $\text{dud}$ — deathless universal draw — defined as $\{\text{dud} \mid \text{dud}\}$. Both players can move, both moves return to the start, and neither player ever loses. It is the pure draw, and it is confused with everything: not greater than any number, not less, not equal.

That figure is worth reading twice, because it separates two things the word loopy runs together. The recursion fails on off — its value is defined in terms of itself and no unrolling reaches a base case — and the outcome is as clean as any in the subject. What a loop destroys is the definition of a value, and what it may or may not destroy is the answer to who wins.

These definitions are circular, which is the point. They are fixed points rather than constructions: a loopy value is defined as the solution of an equation rather than built up from smaller pieces, and the theory’s task is to show the equations have solutions and that the solutions behave.

A loop, traced #

The smallest loopy position is worth walking round once, because the failure is easier to see than to describe.

Take a position $X$ from which Left has exactly one move, and that move leads back to $X$. Right has no moves.

Evaluate it. The value of $X$ is $\{\,\text{value of } X \mid \;\}$, so computing the value of $X$ requires the value of $X$. The recursion calls itself with the same argument and does not descend.

Now play it. Left moves. The position is $X$. Left moves. The position is $X$. This continues. Right never gets a move and never loses by being unable to move, because being unable to move only matters when it is that player’s turn — and Right’s turn never arrives with a terminal position on the board, since the position is never terminal.

So Left never wins either. The game is infinite, and under the draw convention it is drawn; under the convention that the looping player wins, Left wins; under the convention that the looping player loses, Left loses.

Conway’s $\text{on}$ is exactly this position, and the choice made is that $\text{on}$ is a Left win, larger than every number. That is a stipulation with consequences, not a derivation.

Add a single Right move somewhere and everything changes. If Right can move once, then Left looping forever means Right sits with an unused move and the position is still infinite — so the draw stands, and the extra option changed nothing. If Right’s move ends the loop, the analysis becomes about whether Left wants to loop or to let Right end it, which is where the fixed-point machinery earns its keep.

Put on beside off and the pair makes the point of the whole rung. The two graphs differ by one arrow — Right’s move back to the position, present in the first and absent in the second — and that arrow decides whether the outcome exists. The recursion fails identically in both.

Short games hidden inside loopy ones #

The reason the short-game theory is useful for real games, despite most of them being loopy, is worth spelling out.

A chess or Go position is loopy in principle and short in practice for long stretches. Pieces are captured, stones are placed, liberties are filled, and a position that has consumed something cannot return to the state before it consumed it. Those stretches are short games, and the theory applies to them.

The loopy parts are localised. In Go they are ko fights, and a ko fight is a small loopy component embedded in an otherwise short position. The applied machinery — Berlekamp’s ko treatment inside the temperature framework — handles exactly that shape: a short board with a bounded loopy region.

So the honest picture is not “the theory covers a narrow class of games”. It is that the theory covers the parts of real games where something is being consumed, and needs extensions for the parts where nothing is.

The shape that arrangement makes is worth having on the page, because it is the one a real board is in rather than either extreme.

That is a better position than it first appears, and it is also why the endgame is where every application on this site lives. An endgame is by definition the part of a game where the loops have run out.

Termination and the other limits #

One clean way to see where loopy games sit is to compare the three boundaries directly.

Misère play leaves the game graph exactly as it was and inverts the base case. Every recursion still terminates; the results just stop composing. The damage is to the algebra.

Loops leave the base case exactly as it was and remove the guarantee of reaching it. The algebra would be fine if the recursion ran; it does not run. The damage is to the induction.

Complexity leaves both intact. Every recursion terminates and every value composes; there are simply too many positions. The damage is to the computation.

Three different failures, and they are independent — a game can be misère, loopy and intractable at once, and misère loopy games are worse than the sum of the two difficulties. Distinguishing them matters because the responses differ: misère play needs a new algebra, loops need fixed points, and intractability needs approximation.

Only the third has anything to do with difficulty in the ordinary sense. The first two are failures of the model rather than of the machine.

Why the induction cannot be patched #

A natural hope is that some cleverness recovers the recursion — evaluate the loop once, take a limit, cut the cycle somewhere.

The obstruction is that the value of a loopy position genuinely depends on the loop, not on any finite unrolling. Consider a position from which Left can either take a small immediate gain or return to the start. Whether looping is good for Left depends on what else is on the board — if Left is ahead elsewhere, looping forever is a draw and a draw may be worse than the small gain; if behind, the draw is a rescue.

So the loop’s value is contextual in a way finite positions’ values are not, and the substitution property that makes values worth computing is weakened. Loopy games do have a theory of sums, and it is considerably more delicate than the short-game one.

The replacement machinery works with greatest and least fixed points — the value of a loopy position is defined as an extremal solution of the defining equations, and different extremal choices correspond to different conventions about who benefits from an infinite game. The choice is not forced by the rules; it has to be stipulated, which is another way of saying that the draw convention is an extra piece of input the theory does not derive.

The draw convention has to be chosen #

That last point deserves isolating.

In a short game, the outcome of every line is determined by the rules. In a loopy game, an infinite line has no outcome unless one is assigned, and assigning one is a decision.

A draw is the usual choice, and it is what chess and Go do.

A loss for the player who caused the repetition is another, used in some Chinese chess rules and in some Go rulesets.

A win for the player who can loop is a third, and it is the natural one for pursuit games — a game where one player is trying to catch another and the other is trying to survive, in which surviving forever is winning.

Three conventions, three different theories, all consistent. That is a genuine difference in kind from the short-game case, where normal and misère play are the only two choices and both are about the terminal position rather than about infinity.

The four short-game outcome classes are exhaustive precisely because play stops. A fifth is needed as soon as it need not, and what the fifth means is a convention rather than a consequence — which is why naming it is a separate act from computing it.

What the solver computed #

The site’s evaluator implements short games only. The recursion has no cycle detection, because it does not need any: every position it is given is loop-free by construction.

That is a deliberate limit and the site states it rather than working around it. Nothing here computes a loopy value.

What the loopy figure shows is the structure — a position graph with a cycle in it, drawn so the cycle is visible, with the recursion’s failure marked at the point where it would revisit a position it has already entered. That is a picture of why the computation cannot run, and it is honest in a way that a picture of a loopy value would not be.

The check that the code enforces is the converse: assertValue runs the recursion, and the recursion would not terminate on a loopy input. Every position the site evaluates is short, and the build’s completion is itself the proof that none of them contained a cycle.

Where loops come from #

Loops are not exotic. They are what happens whenever a move can be undone.

Chess. Pieces move back and forth. The rules add repetition and move-count limits to force termination.

Go. The ko rule exists solely to prevent an immediate recapture cycle, and the more complex superko rules exist because the simple ko rule does not prevent longer cycles.

Checkers, Chinese chess, most abstract games with mobile pieces. All the same.

Fox and Geese, a classic loopy game and the standard worked example — one player can circle indefinitely, and whether that is a win, loss or draw is exactly the convention question above.

Which means the assumption this whole site rests on — that play terminates — excludes most of the games people actually play. The theory covers games where moves consume something: counters, edges, empty squares. It does not natively cover games where pieces move around.

That is a large exclusion and it is worth stating plainly rather than leaving in a footnote.

Loopy games are outside the reach of exact analysis in a different way from merely large games. A large game is too big for this recursion; a loopy game is not of a kind this recursion computes at all, and the difference matters because the responses differ — a bigger machine helps with the first and with the second it does not.

The rules that force termination #

Real games make themselves short, and the devices they use are worth cataloguing, because each one is a different answer to the same problem.

Consume something. Nim removes counters, Hackenbush removes edges, Domineering fills cells. Nothing can be put back, so no position recurs and termination is automatic. Every game this site evaluates works this way.

Forbid repetition. Go’s ko rule bans an immediate recapture; superko bans any repetition of a whole-board position. Both are rules about history, which means a Go “position” in the strict sense includes what came before it.

Count moves. Chess’s fifty-move rule ends a game that has gone nowhere. Crude, effective, and entirely outside the position.

Declare a draw. Threefold repetition in chess. This does not force termination so much as define an outcome for the failure to terminate.

The first is the only one internal to the position, and it is the only one the short-game theory handles natively. The other three are all statements about the history of play, which is why they sit so awkwardly with a theory whose objects are positions and whose central operation is substituting one position for another. A position cannot be substituted freely if its legality depends on what preceded it.

That is the shape every game this site evaluates has. Nim removes counters, Hackenbush removes edges, Domineering fills cells; the move destroys something, so no picture can recur, and the recursion has somewhere to stop. The check that says so is the same breadth-first search the other figures run — which is the point of drawing a game with no loops in it at all. A search for cycles that has never come back empty is a search nobody has any reason to believe.

Who found it, and when #

Conway treats loopy games in On Numbers and Games, and on and off are his, with the names. The fuller development is in Winning Ways, which has a chapter on games that go on forever and works through Fox and Geese.

The fixed-point machinery was developed further by Aviezri Fraenkel and others, and by Clark Smith in the 1960s in work on games with cycles that predates the general theory.

The practical importance is largest in Go, where ko fights are loopy sub-games embedded in a short game, and where Berlekamp and others developed specific machinery for handling them within the temperature framework. That is the case where the loopy theory has done real work rather than existing as a completeness exercise.

Where the model stops #

This site computes short games only. No loopy value is claimed anywhere.

The draw convention is input. Different choices give different theories, all valid.

Sums of loopy games are delicate. Additivity holds in a weakened form, with side conditions the short-game theory does not need.

Most played games are loopy. The short-game theory reaches them only through their endgames, and only after the loops have been eliminated by the rules or by the position.

Normal play, still — the misère and loopy complications are independent, and combining them is worse than either.

Three ways a rulebook can deal with a loop #

Every game that can return to a position has to say something about it, and there are exactly three things to say. Setting them out makes clear that a draw is one design choice rather than the natural answer.

Share the residue. Declare the repetition drawn, as chess does with threefold repetition. That keeps the game symmetric and gives up decisiveness: a position can be worth nothing to either player with no way to break the tie. It also makes the rule a condition on the history rather than on the position, so what a player is looking at is no longer the whole state.

Forbid the repetition. Go’s ko rule does this, and it is the only one of the three that keeps the game finite by construction: the loop is removed from the graph rather than labelled, so there is no residue for a convention to name. The price is again a history-dependent legality.

Award infinite play to somebody. Whoever keeps the game going wins it. That keeps both finiteness of the answer and decisiveness, and gives up symmetry — one side has a way of winning that consists of doing nothing in particular, which is why real games rarely adopt it and the theory of infinite games does.

None of the three is more natural than the others and all three are outside the recursion. The propagation computes the same labelling under all of them; what differs is what the unlabelled positions are called. That is the whole content of a draw is not a value, stated as a design question rather than as a limitation.

A rule in a real game, doing this job #

The clearest instance of all of this outside the theory is a Go board.

That is worth knowing before reading the rest of this ladder as a study of pathological objects. The loopy games are not curiosities somebody constructed; they are what a real game looks like before somebody writes a rule to prevent them, and every rule set in use contains such a rule.

The ladder from here #

Nearby: on and off with their arithmetic; dud and the confused values; Fox and Geese worked through; greatest and least fixed points, and what each convention corresponds to; and the ko machinery in Go, which is the applied case.

Then across to the other two boundaries. Misère play breaks the ordering while leaving the induction intact; loops break the induction while leaving the ordering intact; and complexity leaves both intact and puts the answers out of reach. Three independent ways to run out, and a game can suffer all three at once.