The first theorem, and the winner it declines to name

The subject’s first theorem is about chess, and it does not say who wins at chess.

Ernst Zermelo proved in 1913 that in chess, one of three things is already true: White can force a win, Black can force a win, or both sides can force at least a draw. Not that one of them will happen — that one of them is a fact about the starting position, fixed before a piece is touched, and unaffected by anything either player does or fails to notice.

Which of the three it is has never been established and probably never will be.

What the theorem is a statement about #

The temptation is to read determined as a claim about chess, and it is not. It is a claim about a class of graphs, and chess is a member of the class.

A position of a finite game with no chance and no hidden information is a node. The moves are edges. A player to move with no edge available has lost, by the normal-play convention this site uses throughout. Everything else follows from those three sentences, and none of them mentions bishops.

So the theorem transfers, unchanged, to every position drawn anywhere on this site: to a Domineering board, to a row of Nim heaps, to a Hackenbush sprig. The reason it is remembered as being about chess is that chess is where the claim sounds surprising. Nobody is startled to hear that Nim is decided in advance, because Bouton had told them which side and how.

The procedure, and why it terminates #

The labelling has exactly two rules, and it is worth stating them in the order the algorithm uses them rather than the order a textbook does.

A position is a loss for the mover when every move leads to a win for the opponent. This can only be settled once all the moves are known, so it is the patient rule.

A position is a win for the mover as soon as one move leads to a loss for the opponent. One is enough, so this is the impatient rule.

The procedure keeps, for each position, a count of how many of its moves are still unlabelled. A win is settled the moment a single option comes back a loss. A loss is settled when the counter reaches zero.

Round zero is the base case and it is thin: the positions where the mover has no move at all. Those are losses, by the convention, and they are the only positions the procedure can label without being told anything. Everything else is deduced.

Thin is not the same as small, and the cheapest way to see how much weight round zero carries is to take it away entirely. on is the smallest game there is with that property: one position, and the only move — for either player — is back to the same position. Nobody is ever stuck, so no pair qualifies for round zero, and the two rules of propagation have nothing to propagate from.

That is the whole engine exposed. Both rules are conditional on something already labelled, and the only unconditional statement in the procedure is the convention that a player with no move has lost. Remove the positions the convention applies to and the argument has no premise, which is a stronger dependence than the word base case usually implies.

A game can also be half in that condition, which is the more instructive picture, because it shows the propagation stopping at a boundary rather than never starting.

Termination is the whole content. Each round settles at least one position or the procedure stops; there are finitely many positions; so it stops, and when it stops every position that can be labelled has been. On a finite acyclic graph that is all of them.

The hypothesis is doing more work than it looks #

Finite appears in the statement and reads like a technicality. It is not. It is the entire load-bearing member, and the way to see that is to take it away.

Add a cycle — a position from which a move leads back to a position already visited — and the procedure still runs, still settles everything it can, and may stop with positions left over. Those positions are not unlabelled because the algorithm was not clever enough. They are unlabelled because there is nothing to label them with: neither player can force a win, and play can go on for ever.

That is the finding the loopy games essay is built on, and it belongs here too, because it is the sharpest available statement of what Zermelo assumed. A draw is not a third outcome the procedure computes. It is the residue the procedure never reaches.

The word may in the paragraph above is load-bearing, and it is worth spending a figure on rather than a clause, because the obvious reading of everything so far is that a cycle is what produces a draw. It is not. off is a single position at which only Left may move, and Left’s move is back to where it was — a cycle by any definition, since play can return to a position it has already been at, for ever.

So the hypothesis Zermelo needs is not no cycles. It is that round zero is reachable from everywhere: every position must have some route to a place where somebody is stuck, or the deduction has no way in. A cycle is the usual way of cutting that route, which is why the two conditions are so easily confused, and off is the case where the cycle is present and the route survives it. Right is stuck at the first position and stuck for ever, and that one dead end is enough to label the whole game.

Read that way, the three pictures above are one statement at three settings. on has no dead end at all and settles nothing; off has a dead end and settles everything despite its cycle; a loop with a way out has a dead end that some positions can reach and others cannot, and settles exactly those that can.

Chess has a cycle in it — pieces can shuffle back and forth — which is why Zermelo’s statement about chess has three cases rather than two, and why the tournament rules about repetition exist at all. The threefold-repetition rule is not a courtesy to bored spectators; it is the device that turns a game with cycles into a finite one, so that a theorem like this one applies.

What the procedure costs, which is the whole modern subject #

Here is the sentence that separates 1913 from everything after it.

The procedure needs the whole position graph.

Not a clever traversal of it, not a sample: every node, labelled. For the games drawn on this site that is fine — a 4×4 Domineering board has 562 positions in its graph and the labelling is instant. For chess the graph is somewhere past $10^{40}$ nodes, and no arrangement of matter is going to hold it.

So Zermelo’s theorem is true of chess and useless about chess, and the gap between those two is not a gap in the theorem. It is the entire complexity field of this site, which exists because the answer exists and the answer is reachable are different claims that a single word — solved — is routinely used for both of.

The gap between those two numbers is itself worth a sentence, because it is the first place a reader meets it. A solver with no memory walks every route through the graph; a solver with memory visits every position. Zermelo’s argument is indifferent to which, since it only needs each position to have a label; anybody performing the labelling is not, and how hard it actually is is a question about the second number that the theorem never asks.

The distinction has a name here — what “solved” means — and Zermelo’s result is the weakest of the three senses in it. It is an ultra-weak solution of nothing in particular: a proof that an answer exists, with no method for finding it and no claim about which answer it is.

The rounds are quantifier alternations #

The two rules are described above as the patient one and the impatient one, and they have older names: the patient rule is a for all and the impatient one is a there exists. Saying so turns the round counter into something the rest of this site has a field about.

Unfold what the mover wins means at a position settled in round three. There is a move such that, for every reply, there is a move such that the opponent is stuck — one existential, one universal, one existential. A position settled in round $r$ is a statement with $r$ alternating quantifiers in front of it, and the round the procedure settles a position in is exactly the depth of that prefix.

So the rounds are not an implementation detail of the labelling. They are the alternation count, and Zermelo’s procedure is a bottom-up evaluation of an alternating quantifier prefix — which is precisely the object the complexity field measures difficulty by.

Which explains the shape of the cost #

That reading accounts for the essay’s own two observations about what the procedure costs, and it accounts for both at once.

The rounds are few. A game lasting $d$ plies has a prefix of $d$ quantifiers, so the labelling finishes in $d$ rounds — a Domineering board of sixteen squares in at most eight, a chess game in a few hundred. Depth is never the problem.

The nodes are many. Each round has to touch every position at that depth, and the number of positions at depth $d$ grows with the branching. So the expense is entirely in the breadth of each round, not in how many rounds there are.

And that is why the answer exists and is unreachable. A short alternating prefix is what makes the question well posed; an enormous set of positions to evaluate it over is what makes it uncomputable in practice. Zermelo proved the prefix has an answer; nobody can evaluate it.

It also says why one alternation would be easy and $d$ of them are not. A single existential — is there a move that wins outright? — is a search with a checkable witness, and a witness is something a person can be handed. A prefix alternating $d$ times has no witness shorter than a strategy, and a strategy is not a certificate: it is a subtree, and subtrees are the size of the thing being avoided.

So the first theorem and the hardest open questions in the subject are about the same object. Zermelo’s contribution was to show the prefix is well defined and evaluates; everything since has been about what evaluating it costs, and the cost is a function of how many times the two quantifiers swap.

The surprise: it is not a theorem about games #

The argument uses nothing about games except the shape of the graph, and this is where it turns out to be sharper than its reputation.

Run the same labelling on a position graph where the two players have different moves — a partizan game, which is most of this site — and it works identically. Left to move and Right to move are simply different nodes. The procedure does not know or care whether the moves available depend on whose turn it is.

That is why the outcome classes on this site are four rather than two. A position is labelled twice, once for each player to move first, and the pair of labels is the outcome:

Zermelo did not draw this, and would have had no reason to: chess is partizan in the strong sense — the players control different pieces — but the question he asked has one answer per starting position, so the doubling never arises. The doubling arises the moment positions are added together, which is Conway’s subject and not his.

A use for a theorem that names nothing #

Here is the surprising part, and it is surprising because it takes a theorem whose whole complaint is that it names no winner and extracts a named winner from it.

Chomp is played on a rectangular bar of chocolate. A move picks a square and eats everything above and to the right of it. The bottom-left square is poisoned, and whoever is forced to eat it loses.

The first player wins on every rectangle bigger than a single square. The argument is two sentences and involves no search whatever.

Suppose, for contradiction, that the second player has a winning strategy. Then let the first player begin by eating the single top-right square. The second player, by assumption, has a winning reply. But that reply is a move the first player could have made as an opening — eating the top-right square removed nothing any later move needed, so every position available after it was available before it. So the first player could have played that reply immediately and been in the winning position instead. The second player’s strategy has been stolen, and the assumption that it existed is refuted.

Determinacy is what makes the refutation into a result. Zermelo says one of the two players has a winning strategy; strategy stealing says it is not the second; therefore it is the first.

This is the cleanest demonstration available of what the theorem is worth. Strategy stealing is a complete proof of who wins, it costs nothing, and there is no known way to get a move out of it — for general rectangles, the winning opening move of Chomp is not known in closed form to this day. A player who has read and understood the proof still has to search.

That gap is not an artefact of Chomp being awkward. It is the gap the theorem has by construction, because the theorem’s content is that a labelling exists and terminates, and a labelling that exists is not a labelling anybody has.

Where the model stops #

Two limits, and the second is the one worth carrying.

The theorem says nothing about how long. A position labelled win for Left may take four moves to collect or four hundred; the label is the same. That is not a defect of the labelling, it is a fact about what a label is, and what a value leaves out makes the same point one level up.

There is a sharper way to put it. The labelling answers who, and the entire apparatus this site is built from exists to answer by how much — and the second question is not a refinement of the first, because two positions can share an answer to the first and behave completely differently in a sum. A label is not a small value; it is a different kind of object, and no amount of labelling produces one.

And the procedure does not survive infinity in a second way. Everything above assumes the game is finite in positions. A game may have finitely many positions and unboundedly long plays only if it has cycles, which is the case already covered. But a game with infinitely many positions — a Nim heap of unbounded size, say — needs an induction rather than a count, and the induction is available only when the positions are well-ordered by something. Zermelo’s own later work is about exactly that, and the well-ordering it needs is a considerably heavier assumption than anything in this essay.

The convention the whole thing rests on #

One assumption has been used throughout and deserves saying out loud, because every result on this site depends on it and it is a choice rather than a fact.

A player who cannot move loses. That is the normal-play convention. It is what makes round zero of the labelling non-empty, and without a non-empty round zero the procedure has nothing to start from and settles nothing at all.

The alternative — misère play, where the player who cannot move wins — changes only that base case. The two rules of propagation are untouched. And the theorem survives the change completely: run the labelling with round zero inverted and it still terminates, still labels everything, still says the game is determined.

What does not survive is everything built on top. Under normal play a sum of games has a value computed from the parts; under misère play it does not, and the reasons are severe. So the convention is invisible to Zermelo’s theorem and decisive for the subject that followed it, which is a good measure of how little the theorem constrains.

What did not happen for twenty years #

Zermelo’s paper is from 1913 and it is three pages. It contains an error about the length of the winning play, corrected by Dénes König and László Kalmár over the following two decades — the correction is real mathematics and does not touch the determinacy claim.

What is more interesting is what did not happen next. The theorem sat for two decades without producing a theory, and the reason is visible in the argument itself: it is a procedure with no algebra in it. Two positions, both labelled win for Left, are given the same label and nothing else in common. Nothing in the labelling suggests that positions could be added, that the label of a sum could be computed from the parts, or that a position could have a value finer than its label.

That was the missing idea, and finding it took another sixty years. The first step toward it was already in print when Zermelo wrote — Bouton had solved Nim in 1901 with an argument that names the winner, which is exactly what Zermelo’s declines to do — and the second step was Sprague and Grundy noticing that impartial positions carry a number rather than a label.

The ladder from here goes in that direction: a label, then a number, then a value that adds.

It is worth being precise about what each step buys, because the three are often run together.

A label answers one question about one position, and two positions with the same label have nothing else in common. A Grundy value answers the same question and also survives addition: put two impartial positions side by side and the value of the pair is computed from the two values, which is a claim no label can make. A game value in Conway’s sense does that for partizan positions as well, and carries how much is at stake into the bargain.

Zermelo has the first of the three and shows no sign of expecting the others. The gap is not a failure of imagination; it is that nothing in a labelling procedure hints that positions are the sort of object that could be added at all. That idea arrives, as far as the record shows, when somebody looks hard at a game that is already several games at once — a row of Nim heaps — and notices that the answer factorises.