Chess Has an Answer — but Nobody Knows It

Game Theory, Part 2 of 9

On 24 November, in Geneva, Gukesh and Javokhir Sindarov will play the first game of their World Championship match. Both have spent months preparing with teams of seconds and the strongest chess engines available. And yet neither of them knows the answer to the simplest question about chess: who wins if both sides play perfectly?

Stranger still, mathematicians showed more than a century ago that this answer exists. It is as fixed as the result of 2 + 2. Nobody has ever seen it.

What Zermelo showed

In Part 1 of this series we solved the matchstick game by reasoning from the end back to the start. In a 1913 paper, the German mathematician Ernst Zermelo — better known today for his work on set theory — applied similar reasoning to chess.

Chess is a two-player game of perfect information with no chance at all. The number of positions is finite, and the rules don't let a game go on forever. For games like this, exactly one of three statements is true:

1. White can force a win, however Black defends.
2. Black can force a win, however White plays.
3. Each side can guarantee itself at least a draw.

That is "the answer of chess". Which of the three statements is true, nobody knows.

A short historical note. Zermelo actually asked a narrower question than the one usually credited to him: can a player in a winning position force the win, and within how many moves? The familiar three-way statement, and backward induction spelled out explicitly, came later, in work by the Hungarian mathematicians Dénes Kőnig (1927) and László Kalmár (1928). The historians of game theory Ulrich Schwalbe and Paul Walker untangled this mix-up in detail. So "Zermelo's theorem" is really a joint effort by several people, named after the first of them.

Three levels of "solved"

When people say a game has been "solved", they mean one of three things:

• ultra-weakly solved — we know how the game ends with perfect play, but not how to achieve it;
• weakly solved — we know both the result and a strategy that secures it from the starting position;
• strongly solved — we know the right move in every position that can arise.

The matchstick game from Part 1 is strongly solved: we have a rule for any number of sticks. Here is where some real games stand:

Note the wording on checkers. The result applies to one particular variant: ordinary pieces move only forward, kings move one square in any diagonal direction, and captures are compulsory. It does not carry over to other variants, such as international draughts on a 10×10 board.

Checkers: eighteen years of computing

Jonathan Schaeffer's team at the University of Alberta in Canada began the computation in 1989. At the peak, in 1992, more than 200 processors were working on it. The endgame database alone — every position with ten or fewer pieces — holds about 39 trillion positions. In total, 8×8 checkers has roughly 5 × 10²⁰ possible positions.

In September 2007 the journal Science published the result: with perfect play from both sides, checkers is a draw. Interestingly, the proof did not require checking every position. It was enough to show that neither side can profitably deviate from drawing lines.

Why chess can't be counted out the same way

In 1950 Claude Shannon, the founder of information theory, estimated the number of possible chess positions at about 10⁴³ and the number of possible games at about 10¹²⁰. He calculated that a machine checking one variation per microsecond would need more than 10⁹⁰ years to choose its first move.

A more recent estimate by John Tromp is even larger: about 4.8 × 10⁴⁴ legal positions. Checkers, by comparison, has about 5 × 10²⁰. So chess isn't "twice as hard" as checkers — the gap is something like a trillion trillion times.

Mathematicians don't call solving chess impossible. As with checkers, proving a win or a draw wouldn't require examining every position. But Jonathan Schaeffer, who led the checkers proof, has said that a technological breakthrough, such as quantum computing, would be needed before anyone could even attempt chess.

Where the answer is already known

There is one part of chess where the answer has been found completely: the endgame. Computers have worked through every position with up to seven pieces on the board, kings included. These tables — called tablebases — know the exact result of each position and the shortest way to reach it. Some of these wins take more than five hundred moves, and no human could explain their logic.

Let's see what the tables say about one of the most famous studies in chess history.

The Saavedra position

White: king b6, pawn c6. Black: king a1, rook d5. White to move.

FEN: 8/8/1KP5/3r4/8/8/8/k7 w - - 0 1

The study's story began in 1895, in the chess column of the Glasgow Weekly Citizen. Its editor, Barbier, published a position close to this one and believed that with correct play from Black it was a draw. The solution that made the study famous was found by a reader — Fernando Saavedra, a Spanish priest living in Glasgow.

What almost everyone sees. The pawn is one step from promotion. The black rook keeps giving checks, and the white king runs from them. The natural plan is to escape the checks and make a queen:

1.c7 Rd6+ 2.Kb5 Rd5+ 3.Kb4 Rd4+ 4.Kb3 Rd3+ 5.Kc2 Rd4!

Black can no longer give check, but plays cunningly. Now 6.c8=Q looks like an easy win. But after 6...Rc4+! 7.Qxc4 the black king has no legal move. That is stalemate — a draw. Nor can White decline the rook: after any king retreat, Black takes the queen with ...Rxc8 and suddenly it is Black who is playing for a win.

What gets missed. 6.c8=R!! A rook doesn't cause stalemate, because it doesn't control the diagonal the black king needs. White threatens a check from a8, after which nothing can save Black. The most stubborn defence is 6...Ra4 (only 6...Rd2+ holds out as long), and then 7.Kb3! Now White threatens both to take the rook on a4 and to mate with Rc1. Black can't parry both.

What the tables added. The tablebase confirms the main points: 1.c7 is the only winning first move, and 6.c8=Q really is only a draw. But it also shows something the classical analysis doesn't. On move six, not only 6.c8=R wins — so do 6.Kb3 and 6.Kc3. The road to mate there is roughly three times longer, and nowhere near as beautiful. The underpromotion is the shortest win, but not the only one.

What this means for a player

A tablebase doesn't think in "beautiful" and "bad" moves. It thinks in three categories: win, draw, loss. Any move that keeps the category is, in a sense, correct. 6.Kb3 is correct. 6.c8=Q is a mistake, even though it is the most natural move on the board: it turns a win into a draw.

That suggests a practical principle. Before a move that looks obvious, it helps to ask not "is this the best move?" but "does this change the result?". Stalemate, perpetual check, a dropped pawn — this is how won positions turn into draws.

The principle has a limit, though. In the middlegame nobody knows which category a position belongs to: there are no tables for 32 pieces, and there won't be in the foreseeable future. There, players and programs have to evaluate positions approximately and look for the move that is best against the opponent's strongest reply. That idea — minimax — is the subject of the next part of this series.

And the match in Geneva is interesting precisely because Gukesh and Sindarov don't play perfectly. They are playing a game whose answer nobody knows.

Exercise

1. In the position after 6.c8=R Ra4, find White's winning move and explain why it wins.
2. Why, after 6.c8=Q Rc4+, is White forced to take the rook, even though it's stalemate?
3. Which level of "solved" does rock, paper, scissors from Part 1 belong to? Can you even say who wins it with perfect play?

Answers are at the end.

Questions for discussion

• If it were announced tomorrow that chess is a draw with perfect play, would anything change in how you feel about the game?
• Which is more useful for learning: knowing the perfect move from a table, or understanding why a move works — even if faster moves exist?
• Saavedra found a move the study's author had missed. Have you ever seen a solution that more experienced people overlooked?

Next in the series: "Minimax: How an Opponent Who Wishes You the Worst Thinks", on von Neumann's theorem and how chess programs "think".

Answers. 1) 7.Kb3! — according to the tablebase, the only winning move. White attacks the rook on a4 and threatens mate with Rc1 at the same time. 2) After any king retreat, Black takes the queen with ...Rxc8 and is left with a rook against a bare king. 3) The moves are simultaneous, so there is no single "right move". The perfect strategy is to choose each option at random with probability 1/3. Then, on average, nobody wins, however the opponent plays. Mixed strategies like this will get their own article in the series.