Minimax: How an Opponent Who Wishes You the Worst Thinks

Game Theory, Part 3 of 9

Manchester, 1952. Alan Turing is playing chess against Alick Glennie, but he isn't choosing his own moves. He is carrying out a program he wrote a few years earlier with David Champernowne. No computer yet exists that can run it, so Turing plays the processor himself: pencil, paper and tens of minutes per move.

The program, later known as Turochamp, lost the game in 29 moves. But the rule Turing was following outlived both him and his era. Today most classical chess programs choose their moves by it, and so does the MindLounge checkers bot. The rule is called minimax.

Judge a move by its worst case

The idea of minimax fits into one sentence: judge your move by your opponent's best reply, not by the reply you are hoping for.

The easiest way to see it is a trap almost everyone meets while learning chess, the Scholar's Mate:

1.e4 e5 2.Bc4 Nc6 3.Qh5

White threatens 4.Qxf7 — checkmate. If Black misses the threat and plays, say, 3...Nf6??, the game is over in one move. Some players set this trap because "what if it works?"

Minimax asks a different question: what happens if Black finds the best reply? Here is roughly how Stockfish 16 rates the two options (depth 28–30, in pawns; plus means White is better):

After 3...g6 the queen has to retreat, and Black gains time for development. The small edge White had from moving first passes to the opponent. It is a modest edge, but it is still a price — and not one worth paying for the hope of someone else's mistake. You can explore the position after 3.Qh5 yourself.

Where does the name come from? In every position, your opponent picks the move that minimises your result. Among your own moves, you pick the one whose minimum is the largest. The maximum of the minimums: minimax.

Why pessimism isn't a weakness here

In everyday life, someone who always expects the worst is rarely called wise. So why is it the right strategy at the board?

The answer came from the Hungarian-born mathematician John von Neumann. In 1928 the journal Mathematische Annalen published his paper "Zur Theorie der Gesellschaftsspiele" — literally, "On the Theory of Parlour Games". Its key idea is the zero-sum game: whatever one player wins, the other loses. Chess, checkers, Go and two-player poker are all zero-sum.

In a game like this, an opponent who wishes you the worst isn't being malicious. They are simply playing for themselves. The worst outcome for you is exactly the best outcome for them.

So assuming your opponent will find the strongest reply isn't pessimism. It is taking their interests seriously.

Von Neumann proved more. Every finite two-player zero-sum game has a number — the value of the game.

The first player can guarantee at least that result, however the opponent plays. The second player can guarantee that the first gets no more. The guarantee "from below" and the guarantee "from above" are the same.

There is an important caveat. In games with hidden information, such as rock-paper-scissors, this equality only holds if players choose their moves at random with certain probabilities. Those mixed strategies will get their own part of the series.

In chess and checkers, where everything is on the board, the value is reached by an ordinary sequence of moves. It is what we called "the answer to chess" in Part 2.

In 1944, von Neumann and the economist Oskar Morgenstern published Theory of Games and Economic Behavior. With that book, game theory moved far beyond the board.

How machines count

The theorem says the value of the game exists. It doesn't say how to find it. As we saw in the previous part, chess can't be searched to the end. So what does a program actually do?

In 1950, Claude Shannon described a recipe that is still in use. The program unfolds a tree of variations a few half-moves ahead and stops there. It scores the final positions approximately, with an evaluation function: material, piece activity, king safety.

Those scores are then passed back up the tree by the minimax rule. Where the program is to move, it takes the maximum; where the opponent is to move, the minimum.

Turing's program did exactly this, only on paper. It looked roughly three half-moves ahead, and kept following captures until there were none left.

The second key discovery was alpha-beta pruning. Several researchers found it independently in the 1950s and 1960s; Donald Knuth and Ronald Moore published a full analysis in 1975. The idea will be familiar to anyone who has spent too long choosing a restaurant.

Suppose you have already found a move that guarantees you an equal position. Now you check another move and see that your opponent has a reply that costs you a piece. You don't need to look at the other replies to that move: it is already worse than the one you have. With an ideal move order, this kind of pruning lets a program search up to roughly twice as deep in the same time.

Today's Stockfish is built the same way: alpha-beta search plus an evaluation function. Only the evaluation has changed. Since 2020 it has used a neural network called NNUE, not just rules written by people.

Minimax on MindLounge

The MindLounge chess bot is Stockfish, deliberately weakened by its skill setting. For checkers there is no engine of that class to plug in, so the checkers bot was written for the site from scratch. It is minimax with alpha-beta pruning in its purest form.

Here is what its code shows:

• the levels differ only in depth: easy looks 2 half-moves ahead, medium 4, hard 6;
• a man is worth 1 point and a king 1.6, with 0.05 added for every row a man has advanced;
• given two equally winning paths, the bot chooses the shorter one.

MindLounge uses Anglo-American rules (English draughts): ordinary kings that move one square, compulsory captures, and multi-jumps must be completed.

What does depth 2 mean in practice? We took a position constructed for this article and ran the bot's code on it. The bot plays Black ("b"); it is Black's move:

8 · · · · 7 · · b b 6 · · · · 5 · · w b 4 · · · · 3 · · · w 2 · w · · 1 · · · · a b c d e f g h

The easy level played e7-f6. It looks active: Black attacks the man on e5. At depth 2 the bot sees its own move and one reply by White. Four moves got the same score, and, as its code prescribes, it took the first.

But White answers g3-h4! Now Black must capture: f6xd4. That capture empties f6, and White takes two men in one move — h4xf6xh8 — and is crowned as well. Black's last man on d4 is lost on the next move.

The medium and hard levels played g5-f4. Depth 4 saw that e7-f6 loses a man. Depth 6 saw more: after e7-f6 the game is lost.

Same rule, same code; the only difference is how far it sees. Programmers call this the horizon effect: anything that happens beyond the search depth simply doesn't exist for minimax.

Where minimax won't help

It is worth knowing the limits of this way of thinking, too.

The horizon. Minimax is exactly as good as it is deep. A human at the board has a horizon as well. Asking "what if my opponent finds the strongest reply?" before every move is a way of pushing it back by at least half a move.

A live opponent. Minimax assumes the opponent plays perfectly. People make mistakes, and experienced players sometimes choose a move that sets more practical problems. But honest calculation first asks whether the move makes the position worse against accurate play. If it does, it is no longer a strategy — it is a bet on a mistake.

Non-zero-sum situations. This is the main limit. Minimax is justified when your gain is your opponent's loss. In negotiations, at work or in friendships, that usually isn't so. Act there as if the other person wishes you the worst, and you may both end up with nothing. That is what the next part of the series is about.

Exercise

1. Here is another position we tested the bot on. The easy level (Black) played a7-b6. Find White's move that wins material.

8 · · · · 7 b b · · 6 · · · · 5 · b w · 4 b · · · 3 w · w · 2 w · · · 1 · · · · a b c d e f g h

1. You are choosing between moves A and B. Against A, your opponent has two replies: one leaves you at +3, the other at −1. Against B, the two replies leave you at +1 and +2. Which move does minimax choose? Which does a player hoping for a mistake choose?
2. Play the MindLounge checkers bot on the easy level and try to set up a "give one, take two" shot. Then try the same on medium.

Answers are at the end.

Questions for discussion

• Have you ever set a trap counting on your opponent's mistake? How did it end?
• Where in your life is it useful to assume your "opponent's" worst move, and where does that assumption do harm?
• On the easy level, the bot doesn't miscalculate — it just doesn't see far. Are your own mistakes at the board like that?

Next in the series: "The Prisoner's Dilemma", a game in which each player acts sensibly for themselves — and both lose.

Answers. 1) e3-d4! Black must capture with c5xe3, and White replies with the double capture a3xc5xa7. In this position the medium and hard levels play c7-b6 and don't allow the shot. 2) Minimax chooses B: its worst case is +1, while A's is −1. A player hoping for a mistake chooses A for the +3. 3) There is no set answer here: this experiment is yours.