Artificial Intelligence · AI Foundations
Alpha-Beta Pruning and Evaluation
In AI because a full minimax tree is usually too big to finish — alpha-beta skips branches that cannot change the decision, and an evaluation function stands in when you must cut…
Minimax already knows the safe move on a finished tree. Real games do not finish: chess branching makes a full backup impossible, so two savings have to be spent together. Alpha-beta pruning walks the same tree and skips a branch the moment it cannot beat a move you already have. An evaluation function invents a number for a position that is not a leaf, so you can stop early. This lesson is those two devices, on a slightly wider club tree than last time, and the horizon mistake an evaluation invites.
- Artificial Intelligence
- Medium level
- 5 concepts
1Minimax already decided — some leaves cannot matter
Minimax's root value is determined by one optimal line. Leaves off that line still get visited, even when a partial look at a branch already proves it cannot beat the line you hold. That extra work does not change the move. Alpha-beta is the bookkeeping that notices the proof and stops generating the rest of the doomed branch.
The club tree this lesson uses has the same two-ply shape with one extra leaf: MAX at the root, MIN L holding 5 and 6, MIN R holding 2 and 7. Minimax would back up \min(5,6)=5, \min(2,7)=2, then \max(5,2)=5 and take left. After MIN R reveals the 2, the 7 cannot raise that MIN above 2, and 2 already loses to the 5 you hold — so the 7 cannot change the root. That is the leaf alpha-beta will refuse to open.
Figure. After left MIN is known to be 5 and right MIN has shown a 2, the dashed 7 cannot lift right MIN above 2, and 2 already loses to 5. Topology; the skip mark is the claim, not a motion.
| Already known | What that forces |
|---|---|
| MIN L = 5 | MAX already has a move worth 5 |
| MIN R has shown 2 | this MIN is at most 2 |
| 2 < 5 | MAX will not switch; 7 is irrelevant |
What enables alpha-beta pruning to skip evaluating entire subtrees without altering the final minimax decision?
- It replaces minimax backup values with random sampling approximations
- It assumes the opponent will make suboptimal random mistakes
- Branches that are already proven worse than a known available choice cannot affect the root decision
- It bounds tree depth to a maximum of two plies regardless of time limit
If a branch cannot possibly change the value of a parent node (because a better choice is already secured), exploring it further is redundant.
2Alpha, beta, and a closed window
Alpha is the best value MAX has already guaranteed along the path from the root to here — a floor. Beta is the best value MIN has already guaranteed — a ceiling. Together they are a window (\alpha, \beta) of values that could still change the decision. If a node can only produce a value outside that window, the remaining siblings are irrelevant.
Walk the club tree left-to-right. After MIN L, MAX has guaranteed 5, so \alpha = 5. At MIN R the first child is 2. MIN's value is then at most 2. That 2 is already below \alpha, so no remaining child of MIN R — however large — can make MAX prefer this branch. The window has closed. The 7 is pruned. The root move is still left, value 5, the same answer minimax would have published after opening every leaf.
The 7 is pruned
Leaves in left-to-right order: 5, 6 under MIN L; 2, 7 under MIN R. Root is MAX. Search left to right.
- MIN L = min(5, 6)5; MAX sets alpha = 5
- MIN R sees 2; MIN value <= 22 < alpha 5
- Remaining child 7 cannot raise MIN R above 2prune 7
- MAX = max(5, 2)5, left — same as full minimax
Pro tip. If the 2 and the 7 were swapped, the first child of MIN R would be 7, the window would stay open, and you would still have to look at 2. The prune is real only in this order.
Coding lab. Alpha-beta pruning on a game tree runs in the app, with checks on your output.
3Move ordering is the prune
Alpha-beta's savings live in the order the children are tried. Best-first ordering — try the move that will turn out best, first — closes windows early and prunes the rest. Worst-first ordering can visit every leaf and still return the same root value. The algorithm is correct either way; only the work changes.
In the limit of perfect ordering, the number of leaves examined is on the order of the square root of a full minimax tree — roughly, you can search twice as deep in the same time. That is an asymptotic reading, not a promise about the club tree of four leaves. The engineering habit it justifies is: spend a cheap guess on move order (a shallow eval, a killer-move table) before you spend another ply of brute force.
Both orders return left at 5. Only the leaf count changes.
| Order under MIN R | Leaves opened | 7 pruned? |
|---|---|---|
| 2 then 7 | 5, 6, 2 | yes |
| 7 then 2 | 5, 6, 7, 2 | no |
4An evaluation is not a utility
A utility is the true outcome of a finished game. An evaluation function e(s) is a number you invent for a position that is not finished, so the search can pretend s is a leaf and stop. Material in chess — queen worth 9, pawn worth 1 — is the classic e. It is a guess about who is winning, not a score the rules will award.
Cutoff search runs minimax or alpha-beta to a fixed depth, then calls e on every frontier position. The backup is the same arithmetic; the inputs are no longer terminals. That is how a chess program moves in a second instead of a century. It is also how a position that looks good at depth 4 and collapses at depth 5 gets a confident wrong number — the horizon effect, next.
| Quantity | Defined on | Who is right |
|---|---|---|
| Utility | A finished position | The rules of the game |
| Evaluation e(s) | A position you chose to stop at | Your function, which can be wrong |
5The horizon and when to stop
The horizon effect is a disaster sitting one ply past the cutoff. A piece is hanging; at depth 4 the evaluation still likes your extra queen; at depth 5 the capture is visible and the score collapses. The program is not stupid — it was never shown the capture. Deeper search, quiescence search (do not stop in the middle of a capture chain), and a better e are the three standard replies. None of them makes e a utility.
Evaluation design is the real remaining work once alpha-beta is in place. Features have to be cheap, correlated with winning, and hard for the opponent to game. A function that just counts pieces will walk into a forced mate it cannot see. The next lessons leave games; the habit to take with you is: a cutoff replaces a true leaf with a guess, and every guarantee from last lesson was about true leaves.
Figure. The horizon effect is a disaster sitting one ply past the cutoff. At depth 4 the evaluation still likes the extra queen; at depth 5 the hanging-piece capture is visible and the score collapses. The program was never shown the capture.
Alpha-beta on the club tree (5, 6 under left; 2, 7 under right) prunes the 7 and returns left at 5. A classmate says the algorithm 'guessed' the 7 was useless. What is wrong?
- Nothing was guessed: after seeing 2, MIN R is at most 2, which already loses to the 5 MAX holds, so the 7 cannot change the root
- They should have used an evaluation function on the 7
- Alpha-beta is only correct when every leaf is opened
- The 7 might be bigger than 5, so it could still win the root
The prune is a proof about bounds, not a heuristic skip. A 7 under MIN cannot lift that MIN above 2, and 2 loses to 5. Evaluation is a different device, used when you stop before a real leaf.
Notes
- Alpha-beta returns the same root move as minimax and skips subtrees that cannot change it.
- Alpha is MAX's current best; beta is MIN's current best. A window that empties is a prune.
- An evaluation function scores a non-terminal so search can cut off; that score is a guess, not a utility.
Formulas
- alpha: the best value MAX has so far along this path
- beta: the best value MIN has so far along this path
- Prune when a remaining sibling cannot produce a value inside (alpha, beta)
Exam traps & shortcuts
- Alpha-beta does not change the answer — it changes how much of the tree you look at.
- Good move ordering (best moves first) is what makes the prune fire early; a reversed order can prune nothing.
- An evaluation is not a utility: it can be wrong, and a shallow cutoff can hide a disaster one ply past the horizon.
Recap
Next: the tic-tac-toe implementation.
- Same answer, less tree
- Alpha-beta publishes the minimax move. It skips a branch only after a bound proves the branch cannot win.
- Window
- Alpha is MAX's floor, beta is MIN's ceiling. On the club tree, 2 < alpha 5 closes the window and prunes 7.
- Order
- Best moves first make prunes fire. Worst-first can visit every leaf and still be correct.
- Evaluation
- e(s) is a guess used as a fake leaf. A cutoff can hide a disaster one ply past the horizon.
Practise Alpha-Beta Pruning and Evaluation
Reading is free and needs no account. Practice, mocks and progress live in the app.
- 2 quick checks with worked explanations
- Timed mocks scored with the real marking scheme
- Readiness tracked per topic, kept on your device