Step by Step
M
MAX player — you, maximizing your own score
At MAX levels of the game tree, the algorithm assumes you (the player) will choose whichever action maximizes your own score.
Example: at a MAX level in chess, the algorithm considers all your possible moves and picks the one leading to the best outcome for you.
I
(Alternating levels) — MAX and MIN alternate down the tree
The game tree alternates between MAX levels (your turn) and MIN levels (opponent's turn), reflecting how the players take turns in the actual game.
Example: level 1 is a MAX level (your move), level 2 is a MIN level (opponent's move), level 3 is MAX again, and so on down the tree.
N
MIN player — the opponent, minimizing your score
At MIN levels, the algorithm assumes the opponent will choose whichever action minimizes your score — always planning for the worst-case, optimal opponent.
Example: at a MIN level, the algorithm assumes the opponent will pick the move that's worst for you, not just any random move.
⚡
Alpha-Beta Pruning — free speed with identical results
Prunes (skips) branches of the game tree where it can prove the outcome cannot affect the final decision, using tracked alpha and beta bounds — producing the exact same result as full minimax but examining dramatically fewer nodes, reducing complexity from O(b^d) to O(b^(d/2)) in the best case.
Example: AlphaZero combines minimax with deep learning and self-play, using pruning-style efficiency techniques to search efficiently enough to beat world champions.
Applied Walkthrough
1
A chess engine is evaluating a game tree and encounters a branch where, partway through evaluation, it becomes clear the opponent would never allow that branch to be reached.
2
Ask: does the algorithm need to fully evaluate every remaining node in that already-doomed branch? No — alpha-beta pruning allows it to skip (prune) that branch entirely.
3
Because pruning that branch cannot change the final decision (it was already provably worse for the relevant player), the algorithm saves significant computation without sacrificing any accuracy.
4
This is why alpha-beta pruning is described as "free speed" — it produces the exact same final decision as full minimax, just with dramatically fewer nodes examined.
Exam Application
Exams test whether you understand minimax's core assumption (an optimal, worst-case opponent) and whether you know alpha-beta pruning doesn't change the final decision — it only eliminates unnecessary computation. Also expect a reference to AlphaZero as a landmark real-world application combining minimax-style search with deep learning.
⚠ Common Trap
The most common trap is assuming alpha-beta pruning is an approximation that might sacrifice some accuracy for speed. It is not — alpha-beta pruning always produces the identical final decision as full minimax; it only skips branches that are mathematically provable to be irrelevant to that decision.
✓ Quick Self-Check
1. What does the MAX player try to do at MAX levels of the game tree?
Choose the action that maximizes their own score.
Tap to reveal / hide
2. What does the MIN player try to do at MIN levels of the game tree?
Choose the action that minimizes the MAX player's score — assuming an optimal, worst-case opponent.
Tap to reveal / hide
3. Does alpha-beta pruning change the final decision compared to full minimax?
No — it produces the exact same result, just by examining dramatically fewer nodes.
Tap to reveal / hide
4. In the best case, what complexity reduction does alpha-beta pruning achieve?
From O(b^d) to O(b^(d/2)).
Tap to reveal / hide
5. What famous system combined minimax-style search with deep learning and self-play to beat world champions?
AlphaZero.
Tap to reveal / hide