## Definition **Minimax** is the foundational algorithm for two-player, zero-sum, perfect-information games (chess, checkers, tic-tac-toe). It assumes both players play optimally: one maximises a utility value, the other minimises it. ## The Game Tree Each node represents a game state. Children are states reachable by one move. Terminal nodes have utility values (win = +1, loss = -1, draw = 0, or any application-specific scoring). - **MAX nodes** — current player tries to maximise utility. - **MIN nodes** — opponent tries to minimise utility. The minimax value of a node is propagated up: MAX takes the max of children, MIN takes the min. ## Algorithm ``` function minimax(node, depth): if depth = 0 or node is terminal: return evaluate(node) if node is MAX: best ← -∞ for each child of node: best ← max(best, minimax(child, depth - 1)) return best else: # MIN best ← +∞ for each child of node: best ← min(best, minimax(child, depth - 1)) return best ``` ## Properties - **Optimal** assuming both players play optimally and the game tree is fully searched. - **Complete** for finite trees. - **Time complexity:** $O(b^m)$ where $b$ is branching factor and $m$ is maximum depth. - **Space:** $O(bm)$ with DFS-style traversal. ## The Problem of Depth Chess has $b \approx 35$ and games last ~80 moves. Full minimax exploration is computationally impossible. Practical chess engines: 1. **Limit search depth** to $d$ ply (half-moves). 2. **Evaluate non-terminal nodes** at depth $d$ using an **[[Evaluation Function]]** — a heuristic that estimates utility. 3. **Apply [[Alpha-Beta Pruning]]** to cut branches that can't influence the result. ## Limitations - Assumes perfect information. Poker (imperfect info) needs different approaches. - Assumes deterministic moves. For chance elements: expectiminimax (introduces "chance" nodes that compute expected values). - Two-player only — extensions to N-player games are subtler. ## Modern Game Playing - **Chess engines (Stockfish, Komodo):** alpha-beta + sophisticated evaluation + neural network refinement (NNUE). - **AlphaZero family:** replaces classical evaluation with deep neural network + [[Monte Carlo Tree Search]]; learns from self-play. Outperforms tuned alpha-beta engines on many games. ## Related - [[Alpha-Beta Pruning]] - [[Monte Carlo Tree Search]] - [[Evaluation Function]]