A win is not a way of winning

The claim that a solved game has been finished with is so natural that it hides an assumption. To solve a game is to label each position won, lost or drawn. On a game that must end, that label is all anyone could want: from a won position there is a move to a position labelled lost for the opponent, and whichever such move is taken, the game gets shorter and the label is preserved, so the win arrives by itself. Holding the table is the same as knowing how to play.

That is not true of chess. It is not even true of the smallest piece of chess anyone would call an ending, and the failure is not subtle. Solve king and rook against king, and hand the table to a player who reads it faithfully and always makes a move the table says keeps the win. That player will never deliver mate against a king that resists. Nothing is wrong with the table, and the player has never made a losing move. The position has been won the whole time and it goes on being won, for ever.

The earlier essays on pawn endings treated chess as a source of sums. This one treats it as a graph, because that is what these endings are: a finite position graph with cycles in it, small enough to label completely, and large enough that the difference between won and how to win is obvious on the page.

Five endings, solved whole #

The model first, since it is a model. A black king stands alone against some white pieces. White wins by forcing mate, with no fifty-move rule and no repetition rule, and a black king that can safely take a piece has saved the game, because what is left on the board cannot force mate. Everything is computed backwards from the mates, by the method Ströhlein first ran on the queen and rook endings in 1970: find the positions where black is mated, then those where white can move into one, then those where every black reply leads to such a position, and so on until nothing changes.

The numbers are the known ones, which is the first thing to check: a queen mates in at most 10 moves, a rook in 16, two bishops in 19, and a bishop and knight in 33. So the program and the published tables agree. Nearly all of the positions are won with white to move, and the queen and rook endings have no exceptions at all, since a piece attacked by the king can simply move away.

The two knights give the column its most instructive entry. Mate with two knights is perfectly possible on the board, and there are positions in the table where it can be delivered in one move. But those positions all have black to have blundered into them: there is no position with black to move from which white can force it, so the depth never rises above one. The material count that chess players use as a rough guide does not say this. Neither does it say why a queen, stronger than a rook, should be worth six fewer moves of depth rather than some number proportional to its strength, or why a bishop and knight should take twice as long as a rook. Depth is a property of the graph and not of the material. It is a feature of how the positions connect, and it can only be read off the table.

The histogram for the rook shows how deep a typical position is. The mass of the distribution is at 8 to 14 moves. Only 6 per cent of positions are within three moves of mate, and those are the positions a player could expect to see through by looking ahead. The rest are beyond any short horizon, and that goes for what a depth-limited search would find as well. There is a small secondary bump at two and three moves, from the mates that a rook delivers quickly when the king is already on the edge.

And nothing about a deep position announces itself. The figure’s position, with the white king in the corner, has three pieces on a single diagonal and no apparent difficulty. It takes sixteen moves against best defence, and a player would probably say that the white king is in the wrong corner and has to walk across the board. That reading may be right. The table does not offer it, and has no concept of walking; it only reports that the shortest forced mate from here has that length.

Nearly every move keeps the win #

Now look at what the table says to a player actually choosing a move.

In the rook ending, white has on average 19.3 legal moves in a won position, and 17.8 of them keep the win: 92 per cent. Only about 2.1 of them bring mate one move nearer, and in 56 per cent of positions exactly one does. The pattern repeats across the endings. So a table of outcomes rejects only about one move in twelve as a mistake, and in this ending those moves are exactly the ones that leave the rook where the king can safely take it or that stalemate the king, since nothing else can lose the win. It says yes to almost anything else. A table of distances, on the other hand, says no to almost everything. Those are two very different instruments with the same name.

On a finite game the two would give the same advice in the end, and this is the heart of the matter. If a game must end, any move keeping the win leads to a position with a shorter game ahead of it, because the game has got one move shorter and it cannot go on indefinitely. Picking arbitrarily among winning moves is safe; the worst that can happen is that it takes a while. The remoteness of a position, how long a win lasts under best play, is a real quantity on finite games, but no player needs it in order to win. It tells only how long the win will take.

The reason this fails on a chess ending is what makes these positions loopy: white can give a check, black can step aside, and white can step back. The position returns, it was won and it is won, and nothing has changed.

Staying won for ever #

That can be made into a precise measurement. Take the set of all won positions with white to move. Delete any position from which white has no move that keeps the win without delivering mate and that leaves black with replies only into the set. Repeat until nothing more is deleted. What remains is the largest set of positions inside which white can stay indefinitely, whatever black does. It is a greatest fixed point, the same kind of calculation as the one that finds a stopper but running on a different question.

The answer is that nothing gets deleted. On the queen and rook endings the process stops after a single pass, with every won position still in the set. There is no won position from which white is forced to mate, or even forced to get closer. On two bishops, 384 of about five million positions are exceptions, which are positions where every move keeping the win happens to be a mate or to allow a reply leading out of the set. For all practical purposes a player can hold any of these wins indefinitely, without any cleverness, and without ever making progress. So the word “won” here does not mean the game will be won. It means the game can be won, and that black cannot do anything about it, should white choose to.

This is what a distinction drawn in the 1913 paper on chess was reaching for. Zermelo’s question was not only who wins but how long the winning side needs, and the answer he and his successors reached was that a win can always be forced inside a bound, because the winner need never let a position repeat. That argument says that a good winner finishes. It carries no information on a winner who is merely keeping the win.

The experiment: playing from the outcome alone #

Fixed-point sets say what is possible. Experiment says what happens. The white in this experiment knows the outcome table and nothing else. On each move it plays uniformly at random among moves that keep the win, except that if mate is available it takes it. It is a fairly competent player in the sense that it never throws the win away, and it has the one piece of tactical sense necessary to finish. Black plays one of two ways: as the table says lasts longest, or at random.

The results are as stark as a measurement gets. From positions at least three fifths of the way to the deepest, where the table’s own mean distance is 12.1 moves in the rook ending, white finishes none of 400 games in 2,000 moves against a king that resists. Nor does it finish any game with two bishops, or with a bishop and knight. With a queen it manages 13 of 400, at around a thousand moves. It is not close. And these are the moves of a player who has been told the exact truth about the position at every turn.

Against a random king things go better, because a random king regularly walks to the edge and stands in front of a mate. The rook still takes a median of 301 moves, and only 37 of 400 games would finish inside a fifty-move limit. With a queen the median is 212 and 51 games finish inside it. With a bishop and knight, only 41 of 400 finish at all within 2,000 moves, and one of them finishes inside fifty moves. If the actual rules of chess were applied here, this white, holding a table proving the position is won, would be held to a draw in nearly every game.

The figure shows the comparison as a single game. The white who reads the distance goes straight down, one move at a time, as a matter of definition, and the mate arrives on move sixteen. The white who reads only the outcome wanders in a band between about 12 and 16 for as long as anyone cares to watch. Its line is the shape of a random walk with a floor effect, with a good king pushing it back from any progress it makes by accident. Both whites are using the same table. The difference is only which column of it they are reading.

The surprising connection: why a finite theory never needed this number #

The result is obvious once stated, and yet it reverses a claim made often in this subject. The theory of finite games is built on the idea that a value is all a player needs. Sprague–Grundy values, canonical forms and outcomes all discard how long anything takes, and the essay on the suspense number measured directly that a time-related quantity adds nothing to who wins. All of that is correct, for finite games, and it is correct precisely because the game’s shortness does the bookkeeping. Each move consumes some of the game, so any choice that preserves the win makes progress automatically. Progress is free.

A loop makes progress cost something. So the theory of loopy games has to add a number, and it did. In the impartial theory, a generalised Sprague–Grundy value on a loopy graph comes with what Fraenkel calls a counter function, a number on positions that must decrease along the winner’s line, and without it the value does not identify a winning strategy. In this light a chess endgame table’s distance-to-mate is a counter function, in an instance built from the board. Retrograde analysis fills in the distance as a by-product of the order in which it works, so that people who build tablebases have it for free, and they have always stored it or something like it. What they might not stress is how little the bare outcome is worth without it. A position with no value showed a fortress escaping the recursion that defines a value. The endings here are the opposite case, with a clean outcome on every position, and the outcome alone still does not tell anybody what to do.

The word solved has been divided three ways in the essay on what solved means, in the usual way: ultra-weak, weak and strong. On a graph that loops there is a further step those categories do not record. Having a strong solution in the sense of an outcome for every position is not the same as having a strategy, and the outcome table falls short of one by an amount measured by the experiment above.

The convention named #

No draw by repetition and no fifty-move rule. Everything here is on the bare graph. Under the actual rules of chess a white player who goes round a cycle gives away the win to a repetition claim or to the fifty-move count, and in that game what is called winning in this essay would be a draw. The rules of chess, in that sense, are exactly what turns the outcome table into something honest, by making every position remember how long it has been since progress was made. The rule that makes Go finite does a similar job in a different way. On the actual game, with those rules, the position graph has no loops, and a winner keeping the win is forced to keep making real progress or to lose it. This is the sense in which a repetition rule is not a technicality: it builds the counter function into the rules themselves.

The sampling is also a convention. Each white chooses uniformly among win-keeping moves, which is a poor model of any actual player and is meant as the plainest possible reading of the outcome table. A white with some sense about driving the king to the edge would do far better. That is exactly the point, since the sense in question is a heuristic stand-in for distance.

What the games cannot show #

Anything about chess with more pieces. These are the smallest endings. With pawns on the board the graph has irreversible moves that cut the loops, and an ending with several pieces each may behave very differently. How far the gap between outcome and distance persists when the position has real progress built in is not measured here.

How much distance a player actually needs. A full table of distances is one extreme, an outcome table is the other, and human technique lies somewhere between. How coarse a distance could be while still winning (whether a three-valued progress measure would be enough, say) is an obvious question, and this experiment does not attempt it.

Whether the exact numbers survive another sampling. Four hundred games from one seeded pool give solid counts when they are 0 of 400 but only rough medians. The qualitative result does not depend on the seed, and the second decimal place of any median here would.

Still open: how much progress must be written down #

Between an outcome table and a distance table there is a large gap, and nothing here measures how much of that gap is needed. A player needs some function that falls along a winning line and that can be computed or stored more cheaply than the exact distance. Rules of thumb for these endings are exactly such functions: shrink the box around the king, or bring the white king closer. For each ending, the measurement would be the smallest number of classes into which won positions can be sorted so that a white moving to any position in a lower class always wins. That number would say how much information progress takes, which is a quantity no outcome table reports. It would also separate the endings in a way depth does not: the bishop and knight’s 33 moves are known to need a specific and hard-to-learn procedure, and how many classes its procedure amounts to is a number this table could produce.