Minimax & Alpha-Beta Pruning

Adversarial Game-Tree Search

1:00

How two-player adversarial games are solved optimally with minimax search, and how alpha-beta pruning cuts the cost from O(b^d) to O(b^(d/2)) without changing the answer.

By the end, you can

Explain how MAX and MIN nodes operate and why the tree alternates between them.
Trace minimax on a small game tree, computing the backed-up value at every node.
Define alpha and beta and state what each one represents during the search.
Identify where an alpha or beta cutoff fires and explain why the pruned branches cannot change the value that propagates to the root.
State the time complexity of plain minimax (O(b^d)) and best-case alpha-beta pruning (O(b^(d/2))), which roughly doubles the depth searchable in the same time.
Describe when a depth limit and evaluation function are needed (the tree is too large to search fully), and name two factors that improve pruning (good move ordering and transposition tables).

Up next in Algorithms & Graph Algorithms