Combinatorial Game Theory
who wins, and by how much
How it was found

The gap between two answers

A draw is usually described as what the backward labelling never reached, which makes it sound like a shortfall of the algorithm. Written as one predicate the winning condition is an equation, the equation is monotone, and it has a least solution and a greatest one — and the set the two disagree about is exactly the drawn set, on every game checked.
14 min read 6 figures Assertions that rejectIt has to end

Assumes: The paper was about how long · An outcome with no value behind it

Two rungs below, the drawn positions arrive as a leftover:

A draw is not a third outcome the procedure computes. It is the residue the procedure never reaches.

Every word of that is true of the procedure, and it puts the draw in the wrong place. It makes a drawn position sound like a position the algorithm was not clever enough to settle — as though a better propagation might reach it, or a longer run, or a different order of work.

None of those would. The draw is not a fact about the procedure at all. It is a fact about the equations the procedure is one way of solving, and the way to see that is to solve them a different way.

The winning condition as one predicate

The rung below writes the labelling as two rules and describes them as patient and impatient. Written instead as a single predicate — Left wins from here — indexed by the position and by whose turn it is, they become two clauses of one definition:

leftWins(p, Left to move) when some move of Left’s leads to leftWins.

leftWins(p, Right to move) when every move of Right’s leads to leftWins.

A Right-to-move position with no move at all satisfies the second clause vacuously — every one of no moves leads anywhere one likes — and that is the normal-play convention, and it is the only thing in the definition that is not a quantifier.

Now read that as an equation rather than as a procedure. It says: the set of pairs where Left wins is the set of pairs those two clauses describe, given that set. That is a fixed-point equation, and a fixed-point equation is entitled to have more than one solution.

Two solutions to one set of equations. The winning condition written as a single predicate and solved twice: once as the least solution of its own equations and once as the greatest. The least says Left can force a win; the greatest says Left cannot be forced to lose, which admits the positions where Left can keep the game going for ever. On a graph with no cycle in it the two coincide and the equations determine an answer. Where they differ, the difference is exactly the set the backward propagation never reaches — so a draw is not a leftover of the algorithm, it is the equations failing to have one answer.
Fig. 1 The two solutions on games with and without a cycle in them, with the difference between them set beside what the propagation calls drawn. On a graph with no cycle the equation has one solution and there is nothing to report.

Why there are two

The operator those two clauses define — hand it a candidate set of pairs, get back the set the clauses describe — is monotone. Enlarge the candidate and neither clause can turn from true to false: an existential over a larger set is still satisfied, and a universal over a larger set is satisfied more easily.

A monotone operator on a finite lattice has a least fixed point and a greatest one, and both are found by iterating. That is Knaster and Tarski’s theorem, it is a page of order theory with no games in it, and it is the whole of why a cyclic game has two answers rather than none.

Start from nothing is a win and iterate upward. Each pass adds the pairs the clauses now certify, and the process climbs until it stops. What it reaches is the least solution: nothing is a win unless something forced it to be.

Start from everything is a win and iterate downward. Each pass removes the pairs the clauses can no longer certify, and the process falls until it stops. What it reaches is the greatest solution: a pair stays in unless something drove it out.

Those are two different sets in general, and the difference is the whole of this essay.

What each solution means

The two are not arbitrary mathematical endpoints. Each is a sentence about play, and the sentences are the two things a player might mean by winning.

The least solution is Left can force a win. Every pair in it is there because a chain of forcings reaches a position where Right is stuck, and the chain is finite because the iteration built it in finitely many passes.

The greatest solution is Left cannot be forced to lose. A pair stays in it if Left always has a move to another pair that stays in it, which is satisfied by winning and satisfied equally by keeping the game going for ever. The greatest solution admits the positions where Left survives, and surviving is not the same as winning.

So the two readings differ exactly on the positions where Left can play for ever and cannot win. Which is to say: the drawn ones.

Backward induction on a loop with a way out, one round at a time. Zermelo's argument as it actually runs. Round zero is the positions where the player to move has no move at all, which is the only thing the procedure knows without being told; each later round is what those settle. Anything still unlabelled when nothing more can be deduced has no label and never will — and on a game with a cycle in it, that leftover is exactly the set of drawn positions. The theorem is a statement about this procedure terminating, and it names the winner of nothing.
Fig. 2 The graph the two solutions differ on, drawn as the propagation sees it. One move goes round for ever and one ends the game; two of the six position-and-mover pairs are never settled. Those two are precisely the pairs the least solution excludes and the greatest one admits.

Watching the two iterations run

Both iterations are short enough to follow on a game with three positions, and following them is what makes the two solutions feel like two answers rather than two pieces of notation.

Take the loop with a way out: a position a from which Left may go round to b or step off to a position where the game ends, b from which either player returns to a, and the end itself.

Upward. Start with nothing marked. The first pass marks the end with Right to move, because Right has no move there and the universal clause is vacuous. The second marks a with Left to move, since Left has a move to a pair already marked. The third and fourth push what they can, and then the passes stop changing anything — with a and b under Right to move still unmarked, because nothing forced them.

Downward. Start with everything marked. The first pass unmarks the end with Left to move, since Left has no move there and the existential clause has nothing to satisfy it. Later passes unmark whatever the clauses can no longer certify — and a and b under Right to move survive every pass, because Right always has a move to something still marked.

Two pairs marked in one run and not the other. Those are the two the propagation leaves blank, and neither iteration was told that.

Two solutions to one set of equations. The winning condition written as a single predicate and solved twice: once as the least solution of its own equations and once as the greatest. The least says Left can force a win; the greatest says Left cannot be forced to lose, which admits the positions where Left can keep the game going for ever. On a graph with no cycle in it the two coincide and the equations determine an answer. Where they differ, the difference is exactly the set the backward propagation never reaches — so a draw is not a leftover of the algorithm, it is the equations failing to have one answer.
Fig. 3 Four games chosen to separate the two hypotheses: two with cycles and no way out, one with a cycle and a way out for only one player, and one with no cycle at all. The equation has two solutions on the first two and one on the last two, and having a cycle is not what decides which.

The check, which is the reason to run both

The claim above is a claim about three computations, and it is asserted rather than observed.

The propagation is retrograde: it starts at the positions where somebody is stuck and pushes outward, and it reports what it never reached. The two solutions are iterations over the whole graph, one from below and one from above, and neither knows anything about the propagation.

The claim is that the pairs the two solutions disagree about are exactly the pairs the propagation never reaches. That is checked twice over on every game: the least solution has to agree with the propagation on every pair the propagation settled, and the disagreement set has to be the drawn set and not merely the same size as it. Either failing throws rather than being reported, because the point of running three computations is that none of them is being trusted about the others.

Thirteen games, all of them checked, and the numbers are what the figures print: on differs on both of its two pairs, off differs on none of its two, a loop with a way out differs on two of six, and a game with no cycles differs on none of eight.

The two games with cycles that behave differently

The pair worth sitting with is on against off, because they look alike and the equation treats them oppositely.

on is one position whose only move, for either player, is back to itself. Neither player is ever stuck, so nothing is forced, so the least solution is empty and the greatest solution is everything — the two disagree on both pairs, and both pairs are drawn.

off is one position where only Left may move, and Left’s move is back to the same position. Right is stuck immediately, so the second clause fires vacuously and the equation has one solution: the two iterations meet, nothing is drawn, and the game is a win for Left however long Left goes round.

Both graphs are a single node with a self-loop. One of them has a unique solution and one has two, and what separates them is not the cycle. It is whether the convention’s clause has anywhere to fire.

That is the rung below’s finding restated in the equation’s own terms. The hypothesis Zermelo’s argument needs is not no cycles; it is that round zero is reachable from everywhere, and in this vocabulary that is the condition under which the equation has a unique solution.

The two solutions and the two things a draw is worth

There is a reason the least solution is the one everybody computes, and it is not that it is easier.

The least solution answers can this player force a win, which is the question a competitive game is about. The greatest answers can this player avoid losing, which is the question a defender is about, and the two are different questions that happen to have the same answer whenever the game must end.

In games where they differ, both questions get asked in practice and by different people. A player defending a fortress is asking the second; a player attacking one is asking the first; and the position where the answers disagree is exactly the position both of them call a draw and mean opposite things by. A chess fortress is that situation on a board rather than in a lattice, and the fifty-move rule is the sport’s way of forcing the two questions back together.

So the two solutions are not one right answer and one artefact. They are the winning question and the surviving question, and the equation cannot tell them apart because the definition of winning does not mention how long anything takes.

Which is a better description of a draw

The reframing pays for itself in what it lets a reader say next, and the payment is a sentence the residue account cannot produce.

A draw is the equations failing to determine an answer. Not the algorithm failing, not information missing, not a fifth outcome class waiting to be computed. The winning condition, written down exactly as everybody writes it, admits two consistent readings of a cyclic game, and both readings are correct descriptions of something.

That also settles what a draw is worth, which the residue account cannot address at all. Under the least reading a draw is not a win; under the greatest a draw is not a loss. A tournament scoring a draw at half a point has chosen neither, and the choice is not mathematics — it is a decision about what the game is for.

And it explains why the loopy theory had to be rebuilt on graphs rather than patched onto the recursion. Retrograde analysis is the graph algorithm that replaced it, and what it computes is a labelling rather than a value for exactly this reason. A recursion computes the least fixed point and has no way to express the other one; a graph algorithm can be pointed at either. The subject did not need a bigger recursion, it needed a different question.

Backward induction on on, one round at a time. Zermelo's argument as it actually runs. Round zero is the positions where the player to move has no move at all, which is the only thing the procedure knows without being told; each later round is what those settle. Anything still unlabelled when nothing more can be deduced has no label and never will — and on a game with a cycle in it, that leftover is exactly the set of drawn positions. The theorem is a statement about this procedure terminating, and it names the winner of nothing.
Fig. 4 The smallest game with two solutions. One position, two pairs, and the propagation settles neither — round zero is empty, so both clauses have nothing to fire from. The least solution says nobody wins and the greatest says everybody does, and both are consistent readings of a game that never ends.
Two solutions to one set of equations. The winning condition written as a single predicate and solved twice: once as the least solution of its own equations and once as the greatest. The least says Left can force a win; the greatest says Left cannot be forced to lose, which admits the positions where Left can keep the game going for ever. On a graph with no cycle in it the two coincide and the equations determine an answer. Where they differ, the difference is exactly the set the backward propagation never reaches — so a draw is not a leftover of the algorithm, it is the equations failing to have one answer.
Fig. 5 Four sums, which is where the distinction earns its keep. A drawn component added to a decided one produces a position whose equation may or may not have a unique solution, and the count of disagreeing pairs is what says which — computed from the graph rather than from a rule about which components were drawn.

What this does not rescue

A reader might hope that having two solutions is better than having none, and that one of them could stand in for a value.

Neither can. A value in this site’s sense is an object that survives addition: put two positions side by side and the value of the pair is computed from the two values. Neither solution is such an object. They are sets of pairs — labels — and a label answers one question about one position, which is exactly the complaint the rung two below makes about determinacy in the first place.

So the fixed-point reading buys a better description of a draw and no arithmetic whatever. The positions the two solutions disagree about still cannot be added to anything, still have no canonical form, and still have to be handled by a theory built for them by hand with a small vocabulary of named primitives. Which of those primitives a sum lands on is the question that theory answers, and none of its answers is a number.

That is worth stating because the reframing is genuinely illuminating and illumination is easy to mistake for progress. What changes is where the draw comes from. What does not change is anything a player or a solver could do with one.

What the picture cannot show

The games here are tiny by design. Thirteen graphs, none larger than a dozen nodes, chosen because the whole labelling can be printed and checked by eye. Nothing about the argument depends on size — the two iterations converge on any finite graph — but nothing here demonstrates it at a size where the iterations would cost anything.

And the downward iteration is not a practical algorithm. It touches every pair on every pass and takes as many passes as the graph is deep, where the propagation touches each edge once. It is here because it is the other solution, not because anybody would compute a draw this way; the propagation’s residue is the same set for far less work.

Backward induction on a cycle of three, one round at a time. Zermelo's argument as it actually runs. Round zero is the positions where the player to move has no move at all, which is the only thing the procedure knows without being told; each later round is what those settle. Anything still unlabelled when nothing more can be deduced has no label and never will — and on a game with a cycle in it, that leftover is exactly the set of drawn positions. The theorem is a statement about this procedure terminating, and it names the winner of nothing.
Fig. 6 Three positions in a ring and nowhere to leave. Round zero is empty, so the propagation settles nothing, and all six pairs are drawn. The least solution is empty, the greatest is everything, and the distance between them is the whole game — which is the largest gap the two answers can have.

Nor does the figure draw the iterations. What it reports is where the two solutions ended, and the passes between are where a reader would see the greatest solution shedding pairs one round at a time. That would be a filmstrip rather than a table, and the table is what the argument needs.

The convention, named

Normal play, and it earns a paragraph of its own here because in the fixed-point reading it is not a convention that sits beside the equation — it is a clause inside it.

The second clause reads: Left wins with Right to move when every move of Right’s leads to Left winning. Applied to a position where Right has no move, that is a universal over the empty set, which is true. So the convention is not an extra rule saying what happens when somebody is stuck; it is what the definition already says, once one notices that a for all over nothing is satisfied.

Invert the convention — misère play, where the player who cannot move wins — and the vacuous case has to be excluded by hand, which is an extra clause rather than a consequence. The equation is less tidy under the other convention, and less tidy in a way that turns out to be the first sign of everything else the misère theory loses.

That is worth noticing as a small piece of evidence for why the subject went the way it did. The normal-play convention is the one under which the winning condition is two quantifiers and nothing else.

The surprise: the algorithm was not choosing, and it was

The reading a reader is left with by the rung two below is that the propagation does its best and some positions are out of reach. The fixed-point account says the propagation is doing something more particular: of the two available answers, it computes the least one, always, by construction, because it starts from nothing and only adds what is forced.

That is a choice, and nothing in the algorithm announces it. A procedure that starts from an empty set and grows is committed to the least fixed point of whatever operator it is iterating, and a reader looking at the code sees a queue and a counter rather than a commitment.

The general shape is worth carrying well past games. An algorithm that computes a fixed point has chosen which one, and the choice is usually made by the initial value rather than by anything anybody wrote down. Where the fixed point is unique the choice is invisible and harmless. Where it is not, the algorithm is answering one of two questions and reporting the other as a failure — which is exactly what the propagation never reached these means, and why it sounds like a shortfall when it is a decision.

The way to find out whether a procedure has this property is cheap and is the whole method here: start it from the other end and see whether it lands in the same place.

Where the ladder goes next

determinacy now has the theorem, the length it was scaffolding for, and where a draw comes from.

Every one of those rests on the graph being finite. The rung above takes it away, and takes it away carefully: not by adding a cycle, which the rungs below have already priced, but by adding infinitely many positions to a game every play of which still ends. The rounds then do not run out, nothing is drawn, and the rank the induction needs is the first ordinal past every finite stage.

Part 3 of 8

One argument about Determinacy. The parts either side of it:

How long a win takes, against how long the argument allows. Ordinary impartial games with the size of their position graphs, the number of rounds the backward labelling takes, and the number of moves the longest win actually lasts. The round a position settles in is the length of the play from it, which is computed here a second way so the two must agree. The rounds are a handful and the positions are many, which is the gap Zermelo's 1913 paper is about — his question was how many moves a forced win needs, and the answer he could prove was the size of the whole graph. The paper was about how long Part 2 — Zermelo's 1913 paper is remembered for a theorem it proves in passing. The question it actually asks is how many moves a forced win takes, the answer it can prove is the size of the whole position graph, and the round counter in the procedure is the real answer — a quantity nobody named for another forty years. A game every play of which ends, and no round settles. A game whose first move chooses how long the game will be, cut off at several sizes. Every play of it is finite and no position is drawn, so the fourth outcome class has nothing to do with what goes wrong. What goes wrong is the round counter: the opening is a loss, a loss settles only when the last of its options is known, and there is no last option. Cut the game off larger and the round grows, so no number in the column is the answer for the untruncated game — and the induction that labels it has to run past every finite stage. Every play ends and no round settles Part 4 — Take the finiteness hypothesis away carefully — not by adding a cycle, which has already been priced twice, but by adding infinitely many positions to a game every play of which still ends. Nothing is drawn, every line finishes, and the round the opening settles in grows with every cut: two, four, six, eight, twelve, sixteen, and no number in the column is the answer.

Where this goes next

a cycle of three: what the backward analysis settles. A position graph in which the moves can lead back to where they started. The labels are the order in which a backward analysis settles each position, starting from the ones where a player has already run out of moves. Positions the analysis never reaches are drawn — and there is no test for that; being unreachable is what a draw is. An outcome with no value behind it Retrograde analysis labels positions in rounds, outward from the ones already lost. Whatever is still blank when nothing more can be deduced is a draw — and there is no separate test for a draw, because a draw is exactly the residue the method never reaches. How long a win takes, against how long the argument allows. Ordinary impartial games with the size of their position graphs, the number of rounds the backward labelling takes, and the number of moves the longest win actually lasts. The round a position settles in is the length of the play from it, which is computed here a second way so the two must agree. The rounds are a handful and the positions are many, which is the gap Zermelo's 1913 paper is about — his question was how many moves a forced win needs, and the answer he could prove was the size of the whole graph. The paper was about how long Zermelo's 1913 paper is remembered for a theorem it proves in passing. The question it actually asks is how many moves a forced win takes, the answer it can prove is the size of the whole position graph, and the round counter in the procedure is the real answer — a quantity nobody named for another forty years. a loop with a way out: what the backward analysis settles. A position graph in which the moves can lead back to where they started. The labels are the order in which a backward analysis settles each position, starting from the ones where a player has already run out of moves. Positions the analysis never reaches are drawn — and there is no test for that; being unreachable is what a draw is. Start at the end and work backwards When play can return to where it started there is no bottom for the recursion to stand on. What replaces it begins at the positions where somebody has already lost and propagates outwards — and the positions it never reaches are exactly the draws. There is no test for a draw, and there does not need to be.

What links here

Essays that reach for this one mid-argument — the half of a link its own author cannot write down.

What this makes readable

Essays that declare this one a prerequisite.

The objects named here

The third axis, after the field and the series: the games, values and theorems themselves, and every essay that touches each one.

Backward inductionClosureDeterminacyDrawFixed pointInductionLoopyOutcome classPosition graphTerminationUniqueness