Games as trees
When players take turns and can see what happened, a game can be drawn as a tree. The starting position is the root. Each possible move is a branch leading to a new position, from which the other player has their own branches. The ends of the tree are final positions: a win, a loss, a draw, or a score.
Drawing a tree forces you to be concrete. Instead of a vague sense that a move is “aggressive” or “safe”, you list what the opponent can do in reply and what you can do after that. For small games this can be done completely, and for large games it is the idea behind how people and computers look ahead.
The backward induction method
Backward induction solves a tree from its ends toward its root. The steps are:
- Look at the positions where the game ends and note the result for each player.
- Step back to the positions where one move remains. Whoever is choosing there picks the branch that is best for them, so replace that position with the result they would get.
- Step back again, now treating those positions as if they were final with known results.
- Keep going until you reach the root. The branch chosen there is your best opening move, assuming everyone plays well.
The logic is that at each point, a player chooses with full knowledge of what the later choices will be. Because later choices are fixed first, earlier ones can be judged properly. It is the formal version of the instinct to plan from the goal.
A worked example: taking stones
Take a simple game. A pile holds 7 stones. Players alternate turns, and each turn a player removes 1 or 2 stones. The player who takes the last stone wins. You move first.
Work backward by asking whether the player about to move wins (W) or loses (L) with n stones left, assuming both play well.
- With 0 stones, the previous player just took the last one, so the player to move has lost: L.
- With 1 stone, take it and win: W.
- With 2 stones, take both and win: W.
- With 3 stones, taking 1 leaves 2, which is a win for the opponent, and taking 2 leaves 1, also a win for the opponent. Every move loses: L.
- With 4 stones, take 1 to leave 3, which is a loss for the opponent: W.
- With 5 stones, take 2 to leave 3: W.
- With 6 stones, taking 1 leaves 5 and taking 2 leaves 4, both wins for the opponent: L.
- With 7 stones, take 1 to leave 6: W.
So the first player should take 1 stone, leaving 6. From then on, whatever the opponent takes, the first player takes enough to make the total removed in that pair of turns equal 3. If the opponent takes 1, you take 2. If they take 2, you take 1. The pile goes 6, 3, 0, and you take the last stone.
The losing positions are 0, 3 and 6, the multiples of 3. The same reasoning shows that a pile of 9 would be lost for the first player against perfect play, whereas the second player would win. A pile of 8 would be a first-player win by taking 2 to leave 6.
Notice that the structure only appeared once we worked backward. Starting from 7 and guessing was much harder than starting from 0.
Chance nodes
Many games include chance: dice, shuffled cards, random events. A tree can handle this with chance nodes. At a chance node, branches are labelled with probabilities rather than being chosen by a player. When working backward, you replace a chance node with the weighted average of the outcomes below it, which is the same calculation as expected value.
This is a useful extension, but it changes what a “best” move means. A branch with the highest average may not be the one you want if you cannot afford a bad outcome, as risk of ruin discusses. The tree gives you the numbers, and your goals decide how to use them.
Hidden information
Trees are cleanest when everything is visible. When a player cannot see something, such as a rival’s hand, the player does not know exactly which position they are in. Game theorists group positions that look the same to the player into information sets, and a player’s choice must be the same across all positions in the set.
This breaks the simple backward procedure, because you can no longer plan separately for each position. Solving such games usually involves probabilities over rivals’ hidden states, and often mixed strategies. So backward induction is a tool for games of perfect information, such as chess, checkers or the stone game above, and a partial tool beyond them.
Why real games are harder
Even in perfect-information games, the full tree is usually far too large. Chess has far more possible games than anyone could list, so nobody solves it by drawing the whole tree. Instead, players and programs look a few moves ahead and then judge the position by rules of thumb. That is a depth-limited version of the same idea: use the end of your horizon as a pretend final position and evaluate it. Judging positions well is a big part of skill, and opening theory is partly a record of branches that others have already explored.
For large trees, programs sometimes sample random continuations rather than exploring every branch, an idea related to the Monte Carlo method. Sampling gives estimates, not proofs, so the answer carries uncertainty.
Practical lessons for players
- Start from the end. In races and take-away games, find the positions that are bad to be in, then steer toward leaving your opponent in them.
- Check the opponent’s best reply. Many errors come from considering only the opponent’s most obvious move. Backward reasoning asks what their best move is, not what you hope for.
- Look for forcing lines. If a move leaves the opponent only one sensible reply, the tree is narrow and easier to read. Plans built from forcing moves are easier to verify.
- Remember the finite horizon. In multiplayer or long games, you can seldom see to the end. Planning a few steps and revising as the game state changes is realistic, and so is turn-based planning with a clear idea of what the next few turns should achieve.
A caution about perfect play
Backward induction assumes both players are rational and expect rationality from each other. Real opponents make mistakes, and sometimes the move that is best against a perfect opponent is not the move that is best against the one in front of you. In some famous theoretical games, backward induction predicts outcomes that people rarely produce in practice. That does not make the method wrong. It tells you what would happen under its assumptions, and gives you a baseline against which to judge how your opponent is actually behaving.