Minimax is a recursive adversarial search algorithm used in two-player zero-sum games. The MAX player (e.g., the AI) tries to maximise the heuristic value of the game state, while the MIN player (opponent) tries to minimise it; minimax performs a depth-first search to leaf nodes, then propagates values upward, alternating between taking the maximum and the minimum at each level. For a game tree of branching factor b and depth d, naïve minimax evaluates O(b^d) nodes — for chess, this is astronomically large.
Alpha-beta pruning is an enhancement that maintains two bounds — alpha (the best value MAX can guarantee) and beta (the best value MIN can guarantee) — and abandons (prunes) any subtree where a better option is already known to exist. In the best case, alpha-beta reduces the number of nodes evaluated to O(b^(d/2)), effectively doubling the search depth for the same cost. The visualiser lets you toggle pruning on and off and count the nodes evaluated in each mode.
What is the minimax algorithm and where is it used?
Minimax is a decision algorithm for two-player zero-sum perfect-information games such as chess, Go, draughts, Connect Four, and noughts-and-crosses. It assumes both players play optimally: MAX always chooses the move with the highest minimax value; MIN always chooses the move with the lowest. The algorithm was formalised by John von Neumann in his 1928 proof of the minimax theorem.
How much does alpha-beta pruning reduce the search?
In the best case (optimal move ordering, where the best move is always searched first), alpha-beta prunes enough to evaluate only O(b^(d/2)) leaf nodes instead of O(b^d). For chess (b ≈ 35), this means searching to depth 10 instead of 5 for the same computational budget. In practice, with good move ordering heuristics, real chess engines achieve 60–80% of best-case pruning, roughly doubling effective depth.
What do the alpha and beta bounds represent?
Alpha is the best score that the MAX player is guaranteed from any position along the current path — it only increases. Beta is the best score that the MIN player is guaranteed — it only decreases. When alpha ≥ beta at a MIN node (or beta ≤ alpha at a MAX node), the remaining siblings cannot possibly affect the result and are pruned. The condition alpha ≥ beta is called a cutoff.
Alpha-beta's pruning efficiency depends heavily on the order in which moves are searched. If the best move is examined first, cutoffs occur early and the maximum pruning is achieved. Common ordering heuristics include the killer move heuristic (try moves that caused cutoffs in sibling nodes), history heuristic, and searching captures before quiet moves. Modern engines like Stockfish spend significant effort on move ordering to approach best-case alpha-beta performance.
Negamax is a refactoring of minimax that exploits the zero-sum property: the value for the current player is always the negative of the value for the opponent. This allows a single recursive function instead of two alternating ones: return max over children of (−negamax(child)). Alpha-beta pruning integrates cleanly: alpha = −beta_parent, beta = −alpha_parent at each recursive call.
A transposition table is a hash map from board positions to previously computed minimax values and best moves. Since many different move sequences reach the same position, caching results avoids re-evaluating identical subtrees. Modern chess engines use 64-bit Zobrist hashing and 512 MB–2 GB transposition tables, often achieving 90%+ cache hit rates in the middlegame, greatly amplifying the effectiveness of alpha-beta.
The horizon effect occurs when a search stops at a fixed depth, causing it to miss the consequences of important events just beyond that depth. For example, a chess engine might sacrifice a piece to push an inevitable queen capture beyond the search horizon, making a losing position appear neutral. Quiescence search — extending the search at leaf nodes until a "quiet" position (no captures) is reached — mitigates this at modest additional cost.
MCTS does not use a heuristic evaluation function. Instead it runs random rollouts (simulations) from nodes to terminal states and uses the statistical results to estimate node values. This makes it well-suited for games like Go where good heuristics are hard to design. AlphaGo combined MCTS with deep neural network policy/value networks, achieving superhuman Go play in 2016. Minimax+alpha-beta remains dominant in classical games like chess where strong evaluation functions exist.
Iterative deepening depth-first search (IDDFS) repeatedly runs alpha-beta to increasing depths (1, 2, 3, …) until a time limit is reached. This seems wasteful but is efficient because the number of nodes at depth d dominates the sum of all shallower depths for typical branching factors. The key benefit is that results from shallower searches give excellent move-ordering information for the deeper search, improving pruning efficiency.
This simulation visualises minimax search on a game tree you shape yourself, showing how a red MAX player and a blue MIN player alternate turns while values bubble up from the leaves. Toggle alpha-beta pruning on to watch branches get crossed out the instant they can no longer change the result.
A game tree with a chosen branching factor and depth. Red MAX nodes take the largest child value, blue MIN nodes the smallest. In alpha-beta mode each node tracks an α/β window, and dashed grey branches mark subtrees pruned once β falls to or below α.
Pick a tree shape, then set branching factor b and depth d with the sliders. Choose Pure minimax or Alpha-beta, plus Random or Best-first move ordering, then press Step to advance one node at a time or Auto to animate at the chosen speed.
With best-first ordering, alpha-beta pruning can cut nodes examined from roughly b^d down to b^(d/2) — effectively doubling the searchable depth for the same effort, which is why chess engines rely on it.
Pure minimax visits every node to compute the correct value. Alpha-beta reaches the same result while skipping branches that provably cannot change the outcome — the "Cutoffs" counter shows how many were skipped.
Pruning only fires once a good value is known. Best-first ordering searches promising children first, tightening the window early and triggering more cutoffs; Random ordering prunes less on average.
Red nodes are MAX, trying to maximise the outcome; blue nodes are MIN, trying to minimise it. The two roles alternate at every depth level.
Once a node's α/β window closes (β ≤ α), its remaining unsearched children are skipped and drawn crossed out with a dashed line, since no value they hold could change the parent's decision.
Yes — total leaves are roughly b to the power d, so raising depth by one has a similar effect to multiplying the branching factor. Watch "Nodes total" in the stats panel.