how a game thinks

when building maths warriors, one of the problems i worked on was choosing a move for an ai opponent. a tempting move might lead to a great score, but only if the other player cooperates.

let’s shrink that problem to a tiny game. you have three moves: a, b, and c. after each move, your opponent has three replies. the numbers at the bottom are the final scores for you. higher is better.

look one reply further

your opponent wants your score to be small, so each square takes the lowest score beneath it. you then choose the largest of those three values. that alternating choice is minimax.

the tempting move

with the starting scores, move b offers an 8 and a 9. neither matters if your opponent can choose 2 instead. move a guarantees 3, so it is the better choice.

try it: raise b1 above 3 and choose “show result.” move b now becomes preferable. at exactly 3, a and b tie; the search keeps whichever equally good move it finds first.

knowing when to stop

after checking move a, we already know we can guarantee 3. under move b, the first reply gives 2. the other replies could make b worse, but they cannot make its minimum larger than 2. there is no reason to inspect them.

that is the idea behind alpha-beta pruning: keep bounds on what each player can guarantee, and stop exploring when a branch cannot improve the decision. a “≤” in the diagram means we have a bound, rather than an exact value.

try it: reset, then compare the result with pruning on and off. next, search c → b → a. the starting example needs six inspected outcomes in one order and nine in the other, while keeping the same best score.

from a small tree to a game

real games usually have too many continuations to examine all the way to the end. a depth limit stops the search early, and an evaluation function estimates how good the remaining positions are. minimax then works with those estimates. searching deeper helps only as far as the rules and evaluation are useful.

this demo uses a fixed, two-ply tree with known final scores. it illustrates the search decisions, rather than running the maths warriors rules or measuring its ai strength.

further reading: solving perfect information games, artificial intelligence: foundations of computational agents.