Combinatorial Game Theory
who wins, and by how much
Concept

Determinacy — where it appears

The fact that a finite game with no chance and no hidden information is already decided before anybody moves. It guarantees an answer exists and names neither the winner nor a move, which is the shape of several results here.

Named by 19 essays across 3 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 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 Hex on 3 × 3, with every winning opening found. A rhombic Hex board with each cell marked according to whether taking it first wins. Left joins the top edge to the bottom and Right joins left to right; a filled board is always a win for exactly one of them, so the search needs no draw test. Strategy stealing proves that a winning opening exists without exhibiting one — these are the ones exhaustive search finds, on a board small enough for exhaustive search to finish.

The theorem that names a winner and no move

Strategy stealing proves that the first player wins Hex and wins Chomp, on every board, in about four lines. It exhibits no move, contains nothing a move could be extracted from, and is not going to. The moves have to come from somewhere else, and where they come from runs out almost immediately.

applied · Strategy stealing a path with every link doubled: the criterion and the game. A Shannon switching graph with the two marked vertices in gold. Short secures links and Cut deletes them; Short wins by joining the two marks. Lehman's criterion says Short wins moving second exactly when some subgraph holding both marks splits into two edge-disjoint spanning trees — drawn here in blue and red where one exists. The verdicts beside the graph come from playing the game out, and the criterion is computed without looking at the game at all.

A winning strategy that is a spanning tree

The Shannon switching game was sold in a box in 1960 and solved in 1964, and the solution is not an assertion that somebody wins. It is a property of the graph anybody can check, and the strategy falls straight out of it — whichever link the opponent cuts, take its partner in the other tree.

applied · Switching 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 The same position, two conventions, two winners. Three-player Nim with the last counter winning. The two columns differ only in what a player does when they cannot win themselves, which is a question the rules do not answer — and the answer decides who wins.

Three players and no answer

Every theorem here is about two players, and the reason is not convenience. With two players the game is zero-sum, so 'play well' needs no further explanation. Add a third and the winner of a Nim position becomes a fact about the convention: two reasonable ones disagree on 56 of the 71 positions swept. The one question no convention touches — can a player force a win against the other two together — is answered 'nobody' in 65 of the 71.

limits · Multiplayer What the auction can and cannot see. Values under both conventions. The Richman value is the share of the money the second player needs; a half means the position itself decides nothing and whoever has more money wins. Every infinitesimal on the list, and zero with them, comes out at a half.

Nobody has to move

Every convention here rests on one sentence nobody examines — the players move alternately. Replace it with an auction and a position stops having an outcome class and starts having a number: the share of the money the second player needs. The 22 values born by day two collapse to seven of those numbers, eight of them landing on exactly a half; the new number respects the game order on all 179 comparable pairs, and is not determined by the parts under addition on 14 of 49.

limits · Bidding 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 A shuttle and a loop, judged by what the play returns to. A three-node loopy game drawn as a graph, with Left's moves in blue, Right's in red and position a marked. Beside it, each position-and-mover pair under the backward labelling and under the rule that a never-ending play goes to Left when it returns to a infinitely often. Four pairs are drawn by the labelling; the new rule gives two to Left and two to Right and leaves the decided pairs as they were.

What the play keeps coming back to

A draw is what the backward labelling never reaches, and handing every never-ending play to one player turns the draws into wins wholesale. Judge an infinite play instead by what it keeps returning to, and every draw gets a winner of its own: over the 262,144 three-node games, 15,432 send some of their draws to one player and some to the other, which no wholesale rule can do. Finding those winners takes a fixed point inside a fixed point.

history · Determinacy A hub with two spokes, and the bit of memory it needs. A three-node loopy game in which Left, at a hub, chooses between two spokes and Right must return from either. Left wins a never-ending play that passes through both spokes infinitely often. With one bit of memory recording which spoke is owed, Left wins from the hub; with a strategy that depends only on the position, Left always takes the same spoke and loses. Three position-and-mover pairs change hands.

One bit of memory

Judge an infinite play by whether one position keeps recurring and every winner can play from a table of one move per position, with nothing remembered. Ask for two positions to keep recurring and that stops being true. At a hub with two spokes a player has to alternate, and a table cannot alternate: over every three-node game, 49,487 position-and-mover pairs are won with one bit of memory and lost without it.

history · Determinacy Which conditions make a winner remember. Every condition on which set of three positions a never-ending play keeps returning to, grouped by two properties of the condition alone, against the arenas swept. 32 of 128 conditions have an arena Left wins and cannot win from a table of one move per position; 19 of those are closed under union.

The rule decides who has to remember

Whether a winner needs memory is a property of the winning condition and not of the board, and the property everybody reaches for is the wrong one. Of the 128 conditions on which of three positions a play keeps returning to, 32 demand memory and 19 of those are closed under union. What separates them is measured two independent ways and the two agree on all 128: a condition needs no memory exactly when it can be rewritten as a number on each position.

history · Determinacy The tree of {a and b and c}, and the states it costs. The Zielonka tree of one winning condition on which positions a never-ending play recurs at. The root is the whole set of positions; the children of a node are the largest subsets the condition judges the other way. The number of memory states a winner needs is read back up the tree by adding at accepted nodes and taking the largest at rejected ones, and this condition costs 3.

Two things to hold at once, or three

Whether a condition makes a winner remember has been settled over every condition on three positions; how much it makes them remember has not. A tree built out of the condition alone, with no board in it anywhere, prices all 128: sixty-one cost nothing, fifty-eight cost two states and nine cost three. It also names the property that was nearly right — closure under union of the sets a condition rejects decides it exactly, where being writable as numbers is sufficient and reaches twenty-six.

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 The same number, from a rule that needs no tie-break. The number computed twice: once as the critical share of a pot under the auction, and once as the probability that Left wins when a fair coin decides who moves at each turn. They agree on every position, and only the second derivation survives being played out.

A coin needs no tie-break

The same recursion has a second derivation: a fair coin decides who moves at each turn, a player whose turn it is with no move has lost, and both play to win. Written from those rules it comes out identical on every position — and it needs no rule for equal bids, because there are no bids. The number is a probability, it belongs to Left rather than Right, and the empty position is the one where the coin decides everything.

limits · Bidding A position Left always wins, and not always. Values grouped by the outcome class alternating play assigns them, with the range of probabilities the coin gives Left inside each class. A class that alternating play calls a win for Left every time holds no position the coin makes certain.

Left always wins, and loses more often than not

Alternating play answers with one of four classes and the coin answers with a chance, and the two do not have to agree. Over the twenty-two values born by day two they never disagree and the margin is exactly nothing — the lowest chance on a position Left wins whoever moves is a half. Over the 1,474 born by day three, seven of them sit at seven sixteenths, and seven mirror them on the other side.

limits · Bidding Every chance the coin gives, by day 2. The probabilities the coin produces over all the values born by a given day, drawn on the unit interval. They fall on a grid of dyadic fractions, every interior point of it is reached, and the two ends never are — so no position is ever a certainty under random turns.

Every chance but a certainty

The coin's number lands on a grid of dyadic fractions, and which points of that grid arrive is a count rather than a guess. Over the 1,474 values born by day three it reaches every one of the fifteen interior sixteenths and neither end — no position is ever certain. The groups sharing a chance run 1, 2, 4, 8 on the small pool, which looks like doubling, and 1, 2, 4, 20 on the large one, which is not.

limits · Bidding The coin's move is often a blunder. Positions where Left has a choice and at least one option wins under alternating play, with how often the option maximising Left's chance under random turns is an option that loses the alternating game outright.

The best chance is the wrong move

Maximising a probability and denying an opponent a reply are different objectives, and on 189 of the 904 day-three positions where Left has a choice and a winning move, the option the coin prefers is one that loses the alternating game outright. The smallest case is two options and one line of arithmetic: five eighths beats a half, and a half is the move that wins.

limits · Bidding

Named alongside it

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

Exhaustive searchOutcome classNormal playPosition graphDrawStrategyAlternationCounterexampleLoopyTerminationBackward inductionFixed point

All concepts