Minimax Search
Minimax is the foundational algorithm for adversarial decision-making. It assumes both players act rationally - one maximizing utility, and the other minimizing said utility. Each game state’s value represents the best guaranteed score achievable through perfect play:
\begin{cases}
U(s) & s \text{ is terminal} \
\max\limits_{s’\in succ(s)}V(s’) & s \text{ is a max node} \
\min\limits_{s’\in succ(s)} V(s’) & s \text{ is a min node}
\end{cases}
Minimax is best understood through **game trees**, where: - Nodes alternate between maximizing and minimizing roles. - Terminal nodes store fixed utilities, while intermediate nodes propagate these values upward. - The resulting optimal move at the root guarantees the agent the best possible outcome, even against a perfect adversary. The algorithm performs a post-order depth-first traversal of the tree, evaluating bottom-up in $O(b^m)$ complexity, where $b$ is the maximum branching factor, and $m$ is the depth of the tree. Game search is infeasible in games with large $m$. As such, **depth-limited Minimax** uses an **evaluation function** to approximate utilities of non-terminal nodes with weights $w_{i}$: $$E(s) = \sum_{n=1}^{N} w_n f_n(s).$$ Additionally, **Alpha–Beta Pruning** improves efficiency by skipping branches that cannot influence the final decision. It introduces two bounds: $\alpha$ is the best value achievable by the maximizer so far, while $\beta$ is the best value for the minimizer: - When $\alpha \geq \beta$, the parent already has an option that’s at least as good (for max) or as bad (for min) as what this subtree could ever yield, so there’s **no need to explore further**. - Another interpretation of this is that: - At a **min node**, if $V_{\text{child}} \le \alpha$, then even if later children are better, the max ancestor would never let this branch happen - prune it. - At a **max node**, if $V_{\text{child}} \ge \beta$, the min ancestor would never allow it - prune it. An outcome of this is that **the leftmost root-terminal branch in alpha–beta pruning can never be pruned.** Pruning reduces complexity to $O(b^{(m / 2)})$ while not affecting correctness by skipping irrelevant subtrees once their influence on the outcome is logically impossible.