The paper was about how long

The rung below is about the theorem everybody quotes: a finite game with no chance and no hidden information is decided before anybody sits down. It draws the labelling that proves it, shows what the finiteness hypothesis is doing, and ends by noting that the paper is three pages long and 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.

That sentence is the wrong way round. The error is not a blemish on a paper about determinacy. The length is what the paper is about, and determinacy is what it establishes on the way.

The question Zermelo asked #

The 1913 paper’s title is about an application of set theory to chess, and the question it puts is: given that White can force a win, in how many moves?

That is not the question the theorem is quoted for and it is a better question. A proof that a winning strategy exists is worth something only if the win can be collected, and a strategy that wins after some unbounded number of moves is not a strategy anybody can use — chess would not be a finite game if it were available.

So Zermelo considers the set of positions from which White can win within q moves, watches it grow as q does, and argues that it stops growing: there is a bound, and the bound is the number of positions. If White can win at all, White can win within that many moves.

The claim is right. The argument for it in the paper is not, and König and Kalmár are where the correct one comes from.

The round counter is the answer #

The procedure the rung below draws has a round counter in it, and the counter is usually read as bookkeeping — how many passes the propagation makes before it runs out of work.

It is not bookkeeping. It is the number of moves the game lasts under best play, and the reason is in the two rules.

A win settles as soon as one option comes back a loss. So its round is one more than the smallest round among its losing options: the winner takes the quickest route to a settled loss.

A loss settles only when the last of its options is known. So its round is one more than the largest round among its options: the loser drags it out as long as possible, and the position is not settled until the slowest escape has been closed off.

Take the quickest win and the slowest loss, alternately, and that is exactly what optimal play looks like when one side is winning and wants it over and the other is losing and wants it postponed.

So the round in which a position settles is the length of the game from it under best play. That is not read off the counter and asserted; it is computed a second time, by the min-and-max recursion a reader would write, and the two are compared position by position. The figure refuses to draw if they disagree anywhere.

And it has a name, forty years later #

The quantity that counts moves to the end, with the winner minimising and the loser maximising, is remoteness. Steinhaus introduced it in the 1920s and the modern account of it is about compound games — how long a component can be made to last, and which of several compounds a number governs.

It is the same quantity, and it is sitting in Zermelo’s procedure a decade or more earlier, unnamed and doing exactly the job the paper wanted.

That is worth stating carefully, because it is the kind of claim that reads as a priority dispute and is not one. Zermelo did not define remoteness; he did not treat the round as an object; he did not notice that it composes, which is the whole content of the later theory. What he had was a procedure whose termination he needed, and a counter he needed to be bounded, and the counter happens to be the thing.

A quantity that appears inside a proof and is not given a name is a quantity nobody can use. That is exactly the pattern the anchor at the bottom of this field records about Bouton, whose nim-sum appears in his paper as a test to apply rather than as a value a position has, and took thirty-four years to be recognised as an object. Zermelo’s round counter is the same shape, on the same site, in the same decade.

What the numbers say #

Take ordinary impartial games and put the three quantities side by side: the number of positions the procedure has to touch, the number of rounds it takes, and the number of moves the longest win lasts.

Nim with two heaps of four has fifteen positions, thirty position-and-mover pairs, and settles in nine rounds with a longest win of eight moves. Three heaps of three has twenty positions, forty pairs, eight rounds. The subtraction game {1, 2, 3} on two heaps of six has twenty-eight positions and settles in nine.

In every case the rounds are a small fraction of the pairs. That is the shape Zermelo needed and could not prove tightly: the bound he could argue for is the number of positions, and the actual number is the depth of the game.

And the bound is not merely loose; it is loose in a way that matters. A bound of “the number of positions” for chess is a bound of something past 10⁴⁰, which is a statement with no content — it does not distinguish chess from a game that never ends. A bound of “the length of the longest game” is a few hundred, which is a statement a person could act on. The two quantities differ by every order of magnitude there is, and the paper needed the second and could reach the first.

Reading one game’s rounds off the graph #

The table is a set of totals and the mechanism is easier to see on one game, so it is worth walking a small one.

Take the four-position game the rung below opens with. Round zero holds the pairs where the mover has no move at all, which is the only thing the procedure knows without being told. Round one holds every pair with a move into one of those — those are wins, in one move, and the count of moves is the count of rounds. Round two holds the pairs all of whose moves lead into round one, which are losses, and a loss in two moves is a loss that lasts two moves however it is played.

Now run the second computation. From each pair, ask directly: if the mover wins, what is the smallest number of moves in which the win can be collected against best defence? If the mover loses, what is the largest number the loss can be spun out to? That recursion mentions no rounds and no propagation, and it returns the same number on every pair.

Two computations, two vocabularies, one number. That is what makes the identity a finding rather than a definition — a definition cannot be checked, and this one throws if any pair disagrees.

Why the bound needs an argument at all #

A reader may wonder why boundedness needs proving. If a win exists, surely it takes some number of moves, and that number is the bound.

The trap is a quantifier. For each position, the win takes some number of moves is easy. There is a number that works for every position is what a bound is, and on a finite graph it follows — but the reason it follows is that there are finitely many positions to take a maximum over, and taking that maximum is where Zermelo’s paper is thin.

The distinction is sharpest where it fails. On a game with infinitely many positions the first statement can hold and the second fail: every position has a finite win and no single number covers them all. That is the rung above this one, and it is why the finiteness hypothesis is not a technicality.

König’s contribution is the tool that handles the infinite case correctly — the lemma that an infinite tree with finite branching has an infinite path — and it is what turns no unbounded win exists into a proof rather than an appeal to obviousness. Kalmár’s is the extension to games where the induction has to run past every finite stage.

The two numbers a solver actually pays #

There is a practical reading of the gap between rounds and positions, and it is the one the complexity field spends its time on.

The rounds say how deep the labelling goes. The pairs say how wide each round has to be, since every round touches every position at its own depth. A solver’s cost is the second, and its memory is the second, and the first is almost never the problem.

That is why the rung below can say that Zermelo’s theorem is true of chess and useless about chess without the sentence being about depth at all. A chess game lasts a few hundred moves, so the labelling would finish in a few hundred rounds — a number that is nothing. What it cannot do is touch 10⁴⁰ positions in each of them.

So the three columns of the table are three different kinds of quantity. The rounds are a fact about the game, the positions are a fact about the encoding, and only the second is the reason the answer is out of reach. How a position is written down is where that distinction is developed, and it is the reason Nim is easy and chess is not, despite both having short games.

What the rounds are, in the complexity field’s vocabulary #

The rung below reads the two rules as quantifiers — the patient rule is a for all and the impatient one a there exists — and concludes that the round a position settles in is the depth of its alternating quantifier prefix.

That is the same identity a third time, and the three readings are worth holding together because each says something the others do not.

As a round, the number says when the propagation gets there, which is a fact about the algorithm.

As a length, it says how many moves the game lasts, which is a fact about play.

As a quantifier depth, it says how many times the two quantifiers swap in the statement the mover wins, which is a fact about the logic and is what the complexity field measures difficulty by.

One number, three descriptions, and the reason the paper could not reach the second is that it did not have the first as an object. A counter that gets incremented is not a quantity anybody can prove a theorem about.

The theorem the paper is remembered for is the cheap half #

Here is the reordering this rung exists for.

Determinacy is a corollary. The procedure labels every position, so every position has a label, so the game is decided. That takes one line once the procedure is stated, and Zermelo’s three pages do not linger on it. In the vocabulary what “solved” means supplies, it is an ultra-weak solution of nothing in particular — a proof that an answer exists, with no method and no claim about which answer it is.

The bound is the substance, it is what the paper argues at length, and it is where the mathematics is hard enough to get wrong. Twenty years of correction went into the half nobody quotes.

That inversion is not unusual and it is worth naming as a pattern. A result is remembered for the claim that is easiest to state, and the claim that is easiest to state is very often the one that cost its author the least. Chess is determined is a sentence anybody can repeat; a forced win is achievable within a bounded number of moves needs a definition of bounded and a reason, and is the sentence a chess player would actually want. It is also the sentence the modern game encodes in a rule: chess’s fifty-move counter is a bound on the length of a win, imposed rather than proved, and it is wrong on the endings whose forced wins are longer than it allows.

What the picture cannot show #

The games measured here are not chess. Nim heaps and subtraction games are chosen because their position graphs fit in a figure, and every number in the table is about a graph with tens of positions in it. What the table demonstrates is the relation between the three quantities, and the relation is what the argument is about.

And the round counter is only the length under best play. A position labelled a win in round eight is a win that takes eight moves if the loser defends as long as possible and the winner collects as fast as possible. Against any other play it takes some other number, and the value says nothing about which — which is what a value leaves out, one field over, and is the same complaint in a different vocabulary.

Nor does anything here compute a strategy. The rounds say how long a win takes and not what to play, and a strategy is not a certificate: extracting the moves is a subtree, and subtrees are the size of the thing everybody is trying to avoid.

The convention, named #

Normal play, as in the rung below: a player with no move loses. That is what makes round zero non-empty, and without a non-empty round zero the procedure has nothing to start from and the length question has no base case either.

Two things about the convention are worth separating here, because the length question is more sensitive to it than the determinacy question is.

Determinacy survives inverting the base case. Run the labelling with round zero saying the player with no move wins — which is misère play — and it still terminates, still labels everything, still says the game is decided.

The lengths change. A misère game and its normal-play twin have the same positions and the same moves, and a player who wants to lose collects a loss on a different schedule from a player who wants to win. So every number in the table is convention-dependent in a way the theorem is not, and a bound proved for one convention is not a bound for the other.

The surprise: the famous half was free and the forgotten half was the work #

The natural way to read the rung below is that Zermelo proved something big and made a small slip about a detail. The right way round is that he set out to bound the length of a win, needed determinacy as scaffolding, got the scaffolding exactly right in a line, and got the thing he was building wrong.

That has a general moral about what survives of a result. What gets quoted is what fits in a sentence, and what fits in a sentence is usually the part that needed the least. The bound is harder to state, harder to prove, was got wrong, needed two more mathematicians and twenty years — and it is the part a chess player would have asked for.

It also says something about the round counter that is worth carrying into any procedure of this kind. The counter was already the answer. It is exactly the number the paper wanted, it is computed for free by the labelling the paper describes, and it went unnamed because it looked like an artefact of the algorithm rather than a quantity of the game. The interesting thing in a procedure is often the thing being incremented, and the way to find out is to ask whether it means anything about the object rather than about the run.

Where the ladder goes next #

determinacy now has the theorem and the question the theorem was scaffolding for.

The rung above is about the other half of what the procedure produces: the positions it never reaches. The rung below reports those as drawn and calls the draw a residue, which is true of the procedure and makes it sound like an algorithmic shortfall. It is not. Written as a single predicate, the winning condition is an equation, the equation is monotone, and it has a least solution and a greatest one — and the drawn set is exactly the distance between them.