A pawn ending is a sum

There is a class of chess position in which counting the material tells nobody anything. The pieces are level, the pawns are blocked, nothing can be captured, and the entire question is which side runs out of harmless moves first.

Chess calls it zugzwang — compulsion to move — and when it applies to both sides at once, mutual zugzwang: a position where whoever has the move is thereby lost. Noam Elkies wrote about these in Games of No Chance in 1996, and the observation is that a blocked pawn ending is a sum of independent games.

What is modelled here, exactly #

This site does not play chess and the figures say so in their own footers. What is evaluated is a file, and a file here is one thing:

A White pawn and a Black pawn on the same column, with an empty gap between them. Either side may advance one square into the gap. Neither can pass the other. When the gap closes the file is dead and nobody can move in it again.

That is the whole rule set. Every value below is that rule set handed to the ordinary game recursion, and whether a real board reduces to a sum of such files is a claim about chess — Elkies’s, not this site’s.

Star and zero, by parity #

The result is as clean as anything on this site.

A file with a gap of g offers both players exactly one move — advance — and it leads to the file with gap g − 1. So the game is {G(g−1) | G(g−1)}, and that recursion has a two-line solution: G(0) = 0, G(1) = {0 | 0} = ∗, G(2) = {∗ | ∗} = 0, and so on alternately.

A file is worth ∗ when its gap is odd and 0 when it is even. Nothing else. It holds a spare move or it does not.

That is pure tempo, and it is the sharpest example on the site of a value that is entirely about when rather than about how much. There is no material in it, no fraction, no advantage of any size — only the parity of a count.

Two vocabularies, one position. A chess player says mutual zugzwang; this site says a P-position, or a game of value zero; and ∗ + ∗ = 0 is the arithmetic that says it. Neither field was looking at the other.

The equation is worth a moment. ∗ is its own negative — the game is symmetric between the players, so mirroring it changes nothing — and every game plus its negative is zero, which makes ∗ + ∗ = 0 an instance of the most general fact in the subject rather than a curiosity about stars. What a chess player has noticed empirically about two spare moves cancelling is the group law.

Two of the four outcome classes are enough to describe every plain ending here, and they are the two a chess player already has words for. A value of 0 means the second player wins — whoever moves loses — which is exactly mutual zugzwang. A value of ∗ means whoever moves wins, which is a file with a spare move left in it. The other two classes, in which one named side wins whoever starts, do not arise at all while both players have the same move in every file, and the fact that they do arise as soon as one player has an extra option is the whole of the next section.

The rule players use #

Endgame manuals do not say ∗. They say count the spare tempo moves, and the rule that comes out of the counting is: if the number of spare moves is even, it is mutual zugzwang; if odd, whoever moves wins.

For plain files that rule is exactly right, and here is why: a file’s value is ∗ precisely when its gap is odd, a sum of stars is 0 or ∗ according to how many there are, and the count of odd gaps is the count of spare moves. The rule is the arithmetic of nimbers, done in words.

Then give one pawn its double step — the move a pawn has on its starting rank, which is a real rule of chess and not a modelling flourish — and the rule stops working.

Two answers against four #

That last point is worth its own section, because it is the essay’s argument.

The counting rule has two answers: mutual zugzwang, or a win for whoever moves. The game has four outcome classes: those two, plus a win for White whoever moves and a win for Black whoever moves.

Sixty-four of sixty-four, and then 1,018 of 4,032. The collapse is not gradual: it happens as soon as the two sides have different options in a file, and it happens because a file with different options for the two players is no longer a nimber.

Forty-eight distinct values appear across those endings, against the two the rule can express. Some of them are values this site has essays about — ↑, ⇑, ∗2, ∗3 — and some are switches, positions both sides want to move in. A switch is not a number, so a position holding one cannot be summarised by any count of anything, and a manual that offered a rule for it would be offering something that does not exist.

What the double step actually does #

It is worth being slow about the double step, because it is a single extra option and it changes the entire character of the answer.

Without it, both players have the same move in every file — advance one square — so a file is an impartial game, its values are nimbers, and a sum of nimbers is settled by an exclusive-or that reduces here to a parity. The counting rule is the exclusive-or.

With it, White has an option Black has not, so a file is partizan — the two players face different move sets — and the values leave the nimbers immediately. {∗ | 0}, ↑, 2·↑∗ and the rest are not nimbers and do not add by parity, and there is no counting rule of any kind that reproduces them.

The count of values is the sharpest way to see it. Over every plain file there are two values in the whole family, ∗ and 0, and every ending of them is one of those two. Over the same files with a double step allowed, the three-file endings alone produce forty-eight distinct values — and forty-six of those are objects no count of spare moves names, because a count of spare moves has two possible answers and cannot have more.

That is the whole mechanism, and it generalises well past chess. Impartial is where the counting rules live. Every folklore rule in this field that reduces to a parity — the long-chain rule, the tempo count here — is a nim-sum in disguise, and every one of them fails at the exact moment the two players stop having the same options. A reader who wants to know in advance whether a rule of thumb will survive can ask that one question about it.

Where the ups come from #

A file with an unused double step for White is worth ↑ when the gap is two, 2·↑∗ when it is three, 3·↑ when it is four. Those are infinitesimals, and the reason they appear is worth following.

Set that beside the first figure and the change is visible in one line of values. Plain files alternate ∗, 0, ∗, 0 — two values for every gap there will ever be. The same files with a double step give a different value at every gap, growing with the gap rather than cycling, and the growth is in multiples of an object no fraction measures. A chess player counting spare moves is counting the first row; the second row is what a real starting rank puts on the board.

The double step gives White an option Black has not: close the gap by two rather than one. That option is never large — it does not win material, it does not create a passed pawn in this model — but it is never nothing either, because it changes the parity of what is left. A move that changes a parity and nothing else is exactly the description of an infinitesimal advantage.

That is the fact this essay exists to record. The values that look most like mathematical curiosities — ups, stars, multiples of up — are the ones a chess player meets first, under the name tempo, and they are what decides a position where everything else is level.

Why every value here is an infinitesimal #

The ups and stars are presented above as a discovery — the values a chess player meets turn out to be the exotic ones — and there is a reason for it that is visible in the rule set before any recursion is run.

Look at when a player is stuck in a file. White can advance whenever the gap is at least one. Black can advance whenever the gap is at least one. Those are the same condition. So in every file, at every moment, either both players have a move or neither does, and the same is therefore true of any sum of files: the two sides run out together, always.

That is the definition of an all-small game, and every all-small game is smaller in absolute value than every positive number. So no file and no ending of files can be worth $\tfrac12$, or $1$, or any number at all except zero — checked over every file drawn here and every two-file ending built from them, with no exception.

The exotic values are not a surprise, then. They are the only values available. A model in which both sides always run out together is a model with the material question assumed away, and what is left is precisely the part of a position that no material count can see. The essay’s later observation — that the theory earns its place exactly where the material is level — is this fact restated: levelness is not a lucky circumstance in which the theory happens to apply, it is a hypothesis built into the rule set, and everything computed here inherits it.

Which property the counting rule actually needs #

That sharpens the account of where the rule of thumb fails, because all-smallness turns out not to be the thing it depends on.

Plain files are all-small and impartial. Both players have the same single move, so the values are nimbers, a sum is settled by an exclusive or, and on stars an exclusive or is a parity. The counting rule is that parity, and it is exactly right — sixty-four endings out of sixty-four.

Files with a double step are all-small and partizan. All-smallness survives untouched: White’s extra option is still an option, Black still has a move whenever White does, and the sum is still infinitesimal. What goes is impartiality, and with it the nimbers. $\uparrow$ at a gap of two, $2\!\cdot\!\uparrow\!\ast$ at three, $3\!\cdot\!\uparrow$ at four — every one of them infinitesimal, and not one of them a nimber.

So the counting rule is not a rule about small advantages, and it does not fail because the advantages got subtler. It fails at the exact moment the two players stop having the same options, and it fails while staying inside the same class of values it was always describing.

That is a sharper test than the one the essay offers a section later, and it is worth stating in its stronger form. Asking whether a folklore rule survives is not asking whether the position stays simple; it is asking whether the two players’ move lists stay identical. Every counting rule in this subject computes an exclusive or, an exclusive or is what the impartial theory has instead of an ordering, and a partizan position has an ordering and no exclusive or.

It also says what a repaired rule would have to look like. The multiples of up are strictly ordered among themselves, so a sum of them is decided by an addition rather than by a parity — which means the replacement for “count the spare moves modulo two” is “add the atomic weights”, and the reason no manual states it is that its terms are quantities nothing on the board displays.

Why the files can be added at all #

The whole analysis rests on the files being independent, and it is worth saying what that requires.

A move in one file has to change nothing in another. In this model it does not, by construction; on a real board it does not when the pawns are blocked and the kings are elsewhere, which is the condition Elkies’s positions are built to satisfy. When the condition fails — a king that can reach two files, a pawn that can capture — the sum is not a sum, and splitting a position is a claim about the position rather than about the drawing.

The operation being relied on is the one this site shows most often in Hackenbush strings: independent components, each with a value, and a total that is their sum. A blocked pawn ending is that picture with the components standing on different files instead of beside each other, and the sums drawn above are that addition performed. What makes the chess case worth stating separately is that the independence is a reading of a board rather than a property of the drawing — nothing about a chessboard says which squares belong to which component, and the decomposition has to be argued for every position it is claimed of.

What a chess engine does instead #

It is worth saying what the alternative is, since chess is the one game in this field with an overwhelming practical answer already.

An engine handed a mutual zugzwang searches. It does not know the position is a sum, does not compute a value, and reaches the right answer by looking far enough ahead to see somebody run out of moves. On the endings in this essay that is easy — the search is a handful of plies deep, because the game is over in a few moves.

The reason to compute a value anyway is not that it beats the search. It is that the value is a statement about the position rather than about a particular game from it: ↑ is true of the ending whatever is happening elsewhere, and it can be added to whatever else is on the board. A search result cannot be added to anything.

That distinction is the difference between a value and a search and it is the reason the theory exists at all. The engine answers one question about one position; the value answers every question about that position in every context it might appear in, which is a much stronger object and a much smaller one.

What the picture cannot show #

The largest thing not shown is whether any real position reduces to this.

That is Elkies’s claim rather than a computation, and it is the load-bearing step: the values above are exact for the rule set stated, and the rule set is a model. A pawn ending where a king can walk from one file to another is not a sum of these games and nothing here applies to it. Nor does anything here handle captures, passed pawns, promotion or the fifty-move rule.

The second thing not shown: which side is better off overall. The values here are about the ending as a closed system, and a real ending sits inside a game where one side may be a pawn up. Combining a material advantage with a tempo value is exactly the operation the theory does badly, because material is a number and tempo is an infinitesimal, and a number beside an infinitesimal is decided by the number every time. The theory is at its most useful precisely when the material is level, which is a narrow and real class of position rather than a general method.

The surprise: the theory was needed for the level positions #

The natural expectation about applying a theory to chess is that it would help with the hard, unclear, roughly balanced middlegame, and that endings with level material would be the easy part.

It is the other way round. The theory says nothing whatever about a middlegame — there is no decomposition, no independence, and nothing to add up. What it says something exact about is the position where everything else has cancelled: level material, blocked pawns, no captures, no plan. That is the position a strong player finds hardest to assess and a computer finds easy only by searching, and it is the one place a value can be written down.

The reason is the same one that runs through the whole of this field. The theory needs a sum, a sum needs independent components, and independence is rare — it appears late, when the position has fallen apart, and lateness is exactly when everything else has already been decided. So the theory arrives after the material question is settled and answers the question that is left.

That is not a limitation to apologise for. A position with level material and no plan is precisely where a player has nothing to count and needs something to compute, and a value is exactly a thing to compute where counting has run out.

The convention, named #

Chess is not a normal-play game — it ends by checkmate or by a draw rule — and every value in this essay is a normal-play value.

The substitution is legitimate for exactly the positions modelled and for no others. In a blocked pawn ending where neither side can afford to run out of pawn moves, being unable to move is losing, because the alternative is to move a king into a losing square. That is the sense in which a mutual zugzwang is a normal-play position, and it is why the correspondence works at all.

Outside that class the substitution fails immediately. A player in an ordinary chess position who has no good move has plenty of legal ones, and the last-move rule has nothing to attach to.

Where the ladder goes next #

chess opens with the case where the theory says something exact about a real position class.

The rung above it is the one Elkies’s paper spends most of its length on: pawn endings whose values are not infinitesimals — halves, switches, loopy games — and what has to be true of the pawn structure for each to appear. That is a rung about the dictionary between structures and values, and it needs a richer model of a file than the one here.