Combinatorial Game Theory
who wins, and by how much
Concept

Termination — where it appears

The requirement that no infinite run of moves exists, which is what every value, theorem and induction on this site rests on. Sometimes it is obvious, sometimes it is a theorem, and sometimes the game ends with nothing at all bounding when.

Named by 24 essays across 5 fields — each of them below, with the objects they name alongside it.

Backward induction on a game that ends, 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.

The first theorem, and the winner it declines to name

Zermelo proved in 1913 that a finite game with no chance and no hidden information is decided before anybody sits down — every position is a win for one side or a draw, and which one is settled already. The proof is a labelling procedure, and watching it run shows exactly how little it says.

history · Determinacy A position that comes back. Three positions whose moves lead round in a circle. Every value in this subject is defined by recursion on the options, and that recursion assumes play ends — here it need not, so the definition has nothing to stand on and the outcome may be a draw, which normal-play theory has no name for.

Loopy games

The whole theory assumes play stops. Allow a position to recur and the induction that every value rests on has nothing to stand on — and a fifth outcome appears that normal-play theory has no name for.

limits · Loopy 1 ko point, no ko rule. A ko fight drawn as a position graph and labelled by retrograde analysis: blue edges are Black's captures, red are White's, and each position carries the verdict for whichever side is to move. Positions the propagation never reaches are drawn — neither player can force a win and the game does not end — and they appear only where the rules permit a repetition.

The rule that makes Go a finite game

A ko is a point in Go where a capture can be recaptured for ever, and every set of rules forbids it. That prohibition is not etiquette or tidiness — it is the hypothesis that puts Go inside the class of games every theorem on this site is about, and removing it removes the values.

applied · Go 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.

limits · Loopy Poker Nim from 3, 5, 7, with reserves of 4 and 4. Nim with one extra kind of move: a player may put any number of counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. They cannot, and the winner is decided by exactly the same nim-sum as ordinary Nim — checked here over every position within a stated range rather than argued.

The move that gives counters back

Poker Nim adds one rule to Nim — a player may put counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. The winner is decided by exactly the same nim-sum, and the reason is the single most useful idea in the whole reduction apparatus.

impartial · Nim Poker Nim from 3, 5, 7, with reserves of 4 and 4. Nim with one extra kind of move: a player may put any number of counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. They cannot, and the winner is decided by exactly the same nim-sum as ordinary Nim — checked here over every position within a stated range rather than argued.

The condition the recursion rests on

Not that the moves run out, and not that the options are few. Poker Nim's heaps can grow without bound and it ends; the game called `on` has one option and never does. What every value on this site needs is that no infinite run of moves exists — and there are three separate ways to fail it.

limits · Termination on + off: 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.

One part that never ends

The game called `on` has one move and it is back to itself. Add anything to it — a star, a point, its own mirror image — and the whole board is drawn. So `off` is exactly the negative of `on` and their sum is not zero, which is the group law failing for a reason that has nothing to do with who is winning.

limits · Loopy The gaps of ⟨5, 7⟩, which are the moves. A Sylver Coinage position drawn as the numerical semigroup it is. Gold squares are the numbers already named; plain squares are sums of them, and so cannot be named again; magenta squares are the gaps, which are exactly the legal moves. The largest gap is the Frobenius number, marked F — past it every integer is reachable, which is why the game has finitely many moves left and must end.

The game that is a number system

In Sylver Coinage two players name integers and nobody may name a sum of what has already been named. Its positions are not boards — they are numerical semigroups, its termination is a theorem of Sylvester's from 1884, and the question of who wins after the opening move 16 has been worth a thousand dollars since 2017.

applied · Sylver Turning Turtles: a row of 12 coins. A row of coins, some heads and some tails. A move turns some of them over, and the rightmost coin turned must go from heads to tails — which is what makes the game end. The number under each place is what a lone head there is worth, and the row is worth the exclusive or of the places showing heads.

A row of coins is already a sum

Everywhere else on this site a sum is several positions side by side. In a coin-turning game it is one row — each coin showing heads is a game in its own right, and the row is worth the exclusive or of them. The decomposition is inside a single picture.

impartial · Sprague–Grundy One Sprouts game from 3 spots, counted. One randomly played Sprouts game, with the map counted after every move. A move spends two lives and the new spot brings one, so the lives fall by exactly one every time — and unlike the arms of a Brussels cross they are not replaced. Every move either cuts a face in two or joins two separate pieces of the drawing, and how many of each a game contains is up to the players, which is why the length is not fixed.

A conjecture from hand play

Sprouts was invented over tea and its outcome pattern was guessed from games played with a pencil. Computers have checked it far past where a person could go, and this site's own solver gives out at three spots — so the honest figure states the frontier it reaches rather than the number somebody else published.

history · Sprouts The days this site can compute, and the ones it cannot. Zero on the first day, ±1 on the second, and thereafter the simplest number in every remaining gap — the construction run by the game recursion, which produces only fractions with a power of two underneath however long it goes on. Below it, three objects the same recursion reaches when the stopping rule is removed, each written with its option set and the exact reason this site's machinery cannot hold it. They are named rather than drawn, which is the honest half of a figure-first collection.

The recursion this site cannot run

Remove the stopping condition from the construction and it reaches ω, its reciprocal, and one third — none of which this site's evaluator can represent, because it interns a position from a finite list of options. The figure draws what it computes and names what it cannot, which is where the boundary belongs.

values · Numbers 7 positions of the same value, and how long each of them lasts. Nim positions whose heap sizes all nim-sum to zero. As games they are the same object: each is worth zero, each is a loss for the player to move, and each may be substituted for any other inside any sum without changing a single outcome. The bars are how many moves each one takes, from the shortest legal play to the longest. The value determines everything about who wins and nothing at all about when.

What a value leaves out

A value settles who wins, by how much, and what happens in every sum the position appears in. It says nothing about when. Seven positions here are worth exactly zero and interchangeable everywhere, and they run from two moves long to eighteen.

values · Tempo a loop with a way out under three rules for never ending. One graph, one labelling, and three ways of reading the residue the labelling never reaches. A draw is not a computed outcome here — it is what is left over — so declaring infinite play a win for one side is a legal alternative that costs no extra search and changes who wins.

When never ending is a win

Retrograde analysis labels a position a win when somebody can force the opponent to be stuck, and leaves everything else blank. Calling the blanks draws is a rule from outside the game — and two other rules are available. The labelling does not change under any of them; only the residue does, and on a three-cycle that residue is every position on the board.

limits · Loopy What the outcome of a loopy sum can be. One row and one column per loopy outcome class, and each cell lists every outcome a sum of two such positions was found to have. Most cells hold several. The cell where both parts are drawn holds one.

The one outcome that adds

Finite outcomes do not add: two first-player wins can sum to anything. Loopy play has seven outcome classes instead of four and adds even less — of the 28 cells in the table, eleven hold several answers. Two do not, and they are the two worth having: a second-player win added to anything leaves the outcome alone, and a draw added to a draw is a draw. A draw added to anything else is not.

limits · Loopy Hydras, and how long each takes to kill. Six small hydras with the ordinal the termination proof assigns to each and the exact number of chops it takes to finish it. Two of them are not finished here: the fight is guaranteed to end and the machine runs out of memory long before it does, which is the gap between a termination proof and a bound.

It ends, and nothing says when

The recursion this site runs needs every line of play to reach a position with no moves, and the condition is usually met by an obvious decreasing quantity. The hydra meets it with no such quantity anywhere: the tree grows at nearly every step and the fight ends regardless, because the only thing that decreases is an ordinal. A four-node hydra dies in twenty chops; one level deeper and 279 chops reach forty thousand nodes with no end in sight.

limits · Termination Two ways to be certain and ignorant at once. Ten positions from two games that both terminate for reasons no bound comes out of. Sylver Coinage's proof counts something that goes down and can be counted; the hydra's counts an ordinal, which cannot, and the last column shows what that difference is worth.

Two ways to end with no bound

Sylver Coinage and the hydra are both guaranteed to finish and neither will say when. The difference is that one of them carries its own bound: every move in Sylver removes at least one gap, the gaps can be counted in a moment, and over ten openings the longest play uses every single one. The hydra has no decreasing quantity a solver can hold — three hydras of five nodes each take seven chops, twenty-one, and a number past two hundred and seventy-nine that this machine never reaches.

limits · Termination on: which positions play can return to. A position graph with the moves of both players drawn, and beside it the shortest sequence of moves that gets back to each position. A position play can return to is a position whose value is defined in terms of itself, so the recursion every value in this subject is built from has no base case there. A position with no way back is one the ordinary recursion terminates on.

A stopper and how to find one

The class a value theory for loopy games would need is the ones with no infinite alternating run, and the qualifier does the work: seventy-nine of the two hundred and fifty-six two-node loopy games qualify and seventy-two of them have a cycle. Every one has a decided outcome, and under eight tests the seventy-nine collapse to six.

limits · Loopy Two ways to be certain and ignorant at once. Ten positions from two games that both terminate for reasons no bound comes out of. Sylver Coinage's proof counts something that goes down and can be counted; the hydra's counts an ordinal, which cannot, and the last column shows what that difference is worth.

Which games end at which level

Between a game that ends within a computable bound and one that ends with no bound at all there are levels, each corresponding to a strength of induction. This site's games sit at three of them, and which level a game is at is decided by exhibiting its termination measure and checking that every move lowers it.

limits · Termination A fortress, and the counter that gives it a label. A pawn ending where the defender's king shuffles for ever and the attacker needs time. Down the rows, how many moves of preparation the breakthrough needs; across the columns, how many moves the rule allows before declaring a draw. With no breakthrough the position is drawn whatever the rule says, and drawn as a residue the backward induction never reaches. With a breakthrough and no rule the attacker wins despite the cycle. Where the march is longer than the counter allows, the rule turns a won position into a drawn one.

A position with no value, and the rule that gives it one

A fortress is a cycle in the position graph, so the recursion defining a value has nowhere to bottom out and the propagation never reaches it. Chess has a rule for that — count fifty moves and call it drawn — and the rule does not merely tidy the theory up. On eleven cells of the sweep it takes away a win.

applied · Chess A ko fight decided somewhere else on the board. A ko fight against the number of ko threats each side holds. A threat is a play elsewhere that the opponent must answer, and it lifts the prohibition on recapturing, so a player short of threats runs out of ways to come back. Every cell is a full retrograde labelling and the pattern in them is read off afterwards: the fight goes to whoever is ahead on a quantity that is not on this part of the board at all. Where the labelling never settles, the fight is a no-result whatever anybody holds.

A ko is won somewhere else

The rung below shows the ko rule buying finiteness by deleting one edge. What it buys with the same edge is a fight nobody can settle by looking at it — the prohibition forces a player to spend a threat, threats are counted on the rest of the board, and every decided cell of the sweep goes to whoever is ahead on a quantity that is not in the picture.

applied · Go 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.

history · Determinacy 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.

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.

history · Determinacy 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

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.

history · Determinacy The money played out, and it never mattered. The bidding rule played move by move with a countable pool of chips, at every way of splitting it. The verdict is constant across the splits and opposite under the two ways of resolving equal bids, so what settles these positions is the tie-break rather than the money.

The auction never gets to the money

The critical fraction is computed and never played. Played out with a countable pool of chips — twelve positions, four pool sizes, every split of the chips, every bid answered — the verdict does not move with the money on a single one of the forty-eight sweeps, and the rule for equal bids settles all forty-eight. The reason is one line long: declining every auction wins, and bidding nothing declines.

limits · Bidding

Named alongside it

The objects these essays reach for when they reach for this one.

Outcome classDrawExhaustive searchLoopyPosition graphNormal playRetrograde analysisBackward inductionDeterminacyInductionDisjunctive sumNim

All concepts