Backward Induction in Finite Sequential Games Like Chess
This article explores how the mathematical method of backward induction solves finite sequential games of perfect information, such as chess, within the framework of combinatorial game theory. By starting at the final possible outcomes of a game and working backward to the initial move, this technique determines the optimal strategy for every player. While theoretically guaranteeing a solution for chess, the article also explains why the sheer scale of the game makes complete practical computation currently impossible, restricting its real-world application to endgame scenarios.
Defining the Game Environment
To understand how backward induction works, one must first define the parameters of the game it is solving. In combinatorial game mathematics, chess is classified as a finite, sequential game of perfect information.
- Sequential: Players take turns making moves one after another, rather than acting simultaneously.
- Perfect Information: Both players see the entire board, know all historical and possible future moves, and there is no element of chance, such as dice rolls or hidden cards.
- Finite: The game cannot go on forever. In chess, this is mathematically enforced by the fifty-move rule and the threefold repetition rule, which prevent infinite loops.
The Mechanics of Backward Induction
Backward induction solves these games by mapping every possible sequence of moves as a massive decision structure called a game tree. The single node at the top of the tree represents the starting position of the game. The branches extending downward represent legal moves, and the "leaves" at the very bottom are the terminal nodes. Terminal nodes are positions where the game has officially ended, resulting in a win for White, a win for Black, or a draw.
Instead of trying to calculate from the first move downward, backward induction ignores the beginning of the game. It starts at the bottom of the tree, specifically at the positions just one move away from the terminal nodes. At these penultimate positions, the outcome of every possible move is already known. The method assumes rational play, meaning the player whose turn it is will always choose the branch that leads to their best possible outcome.
Propagating Values Up the Tree
Once the optimal choices just before the end of the game are identified, the outcomes of those choices are assigned directly to those penultimate positions. Effectively, the bottom layer of the tree is shaved off, and the penultimate positions become the new terminal nodes with guaranteed values.
The process is then repeated one step higher up the tree. If it is White's turn at a given node, White will select the move leading to a position valued as a White win; if none exist, a draw; and only if forced, a Black win. On the next level up, Black will do the exact opposite. This alternating process—often executed in computer science as the Minimax algorithm—continues step-by-step up the game tree. Eventually, the values propagate all the way back to the root node (the first move of the game), revealing the exact optimal path from start to finish and determining who should win if both sides play perfectly.
Zermelo’s Theorem
In 1913, mathematician Ernst Zermelo applied this exact logic to chess, formulating what is now known as Zermelo's Theorem. The theorem states that in any finite, two-person game of perfect information where the outcomes are win, lose, or draw, one of three realities must exist:
- White has a strategy that guarantees a win.
- Black has a strategy that guarantees a win.
- Both players have strategies that guarantee at least a draw.
Backward induction serves as the constructive proof for Zermelo’s Theorem. Because the game tree of chess has a finite number of nodes, backward induction mathematically guarantees that chess is solvable and that one of those three outcomes is the predetermined fate of the game before the first pawn is even pushed.
The Computational Bottleneck
While backward induction solves chess in mathematical theory, it fails to solve the whole game in practice due to a phenomenon called combinatorial explosion. To execute backward induction from the beginning of the game, you must first map out all the terminal nodes.
In 1950, mathematician Claude Shannon estimated the game-tree complexity of chess to be roughly \(10^{120}\) possible games, a figure known as the Shannon Number. Because there are more possible chess games than there are atoms in the observable universe (estimated at around \(10^{80}\)), no computer can generate the full game tree to begin the backward induction process. Therefore, the true theoretical value of the starting position in chess remains unknown.
Practical Application: Endgame Tablebases
Despite the impossibility of applying backward induction to the entirety of chess, computer scientists successfully use a localized version of it, called retrograde analysis, to solve the end of the game.
Instead of starting from move one, programmers place a limited number of pieces on the board in every possible checkmate configuration (terminal nodes). They then use backward induction to work in reverse, generating every legal un-move to find all positions that lead to those checkmates. By doing this, they have created massive databases known as Endgame Tablebases. Currently, chess has been completely solved via backward induction for any board state containing seven or fewer pieces (including the kings). When a modern chess engine reaches a seven-piece endgame, it stops calculating forward and simply looks up the mathematically perfect backward-inducted solution.