In a two-player board-game AI, how does minimax pick a move, and what does the evaluation function do at the depth limit?
answer
- assume the opponent plays well
- max on your turn, min on theirs
- values backed up from the leaves
- heuristic score where the search stops
basics
~20 sMinimax searches the game tree assuming both sides play their best: the AI takes the maximum over its moves, the opponent the minimum over theirs. At the depth limit, an evaluation function estimates how good each unfinished position is.
solid answer
~50 sMinimax treats a two-player, zero-sum, perfect-information game as a tree of positions. A position's value is defined recursively: where the AI (MAX) moves, it is the **maximum** of its children's values; where the opponent (MIN) moves, the **minimum**; a finished game scores its outcome. Real games are far too deep to search to the end, so the search stops at a fixed depth and calls an **evaluation function**: a fast heuristic such as material plus mobility, scored from one fixed side's point of view. The AI plays the root move with the best backed-up value. Full-width cost is about `b^d` leaves for branching factor `b` and depth `d`, so playing strength rests on how deep you search and how well the evaluation ranks positions. The **negamax** form scores every position for the side to move and uses `value = max(-value(child))`, one function for both players.
go deeper
Recall the recursive rule: maximum on the AI's turn, minimum on the opponent's, an evaluation at the depth limit. Be ready to back values up a small tree by hand.
Explain negamax and why its evaluation must score for the side to move, and show how cost grows as b to the power d with each extra ply.
Discuss what makes a good evaluation: speed against knowledge, win scores above every heuristic, and how the horizon effect corrupts leaf scores and what quiescence search costs.
Treat evaluation richness and search depth as one time budget: a slower evaluation costs depth everywhere, so judge each added feature by playing strength at equal time per move.
## The game tree and the minimax value A two-player, **zero-sum**, **perfect-information** game (chess, checkers, a turn-based tactics board game) can be drawn as a **game tree**. The root is the current position, each edge is a legal move, and the levels alternate between the two players. Call the AI **MAX** and its opponent **MIN**. The **minimax value** of a position is defined recursively: - a **terminal** position (win, loss or draw) is worth its outcome, for example +10000, -10000 or 0; - a position where MAX is to move is worth the **maximum** of its children's values; - a position where MIN is to move is worth the **minimum** of its children's values. The AI plays the root move whose child carries the highest value. The assumption built in is that the opponent always picks the reply that is worst for MAX according to the same values. Against a weaker opponent that is pessimistic, but it is safe: the value is what MAX can guarantee against any reply, as far as the search can see. ## Depth limits and the evaluation function Searching to the end of the game is impossible in all but tiny games. With **branching factor** `b` (legal moves per position) and **depth** `d` in **plies** (one move by one player), full-width minimax reaches about `b^d` leaves. With `b = 30`, depth 4 is 810,000 leaves and depth 6 is 729,000,000. So the search stops at a **depth limit** and calls an **evaluation function** on every leaf that is not a finished game. An evaluation function is a heuristic estimate of how good a position is for one fixed side. What a usable one looks like: - **Fast**, because it runs at every leaf, often millions of times per move. - **Consistent with the rules**: a real win must score above any heuristic score, so a forced win is preferred to a merely pleasant position. - **Correlated with winning chances**: material balance, mobility, piece safety, territory, tempo. - Often a **weighted sum of features**, `w1*f1 + w2*f2 + ...`, with weights tuned by hand or by playing test matches. The evaluation does not need to be "true". Minimax only compares values, so what matters is that it **ranks** positions in roughly the right order. ## A small worked example MAX has moves X, Y and Z. MIN has three replies to each, and the evaluation scores the nine resulting leaves: | MAX move | Leaf values after MIN's replies | MIN picks | Backed-up value | |---|---|---|---| | X | 4, 5, 6 | 4 | **4** | | Y | 1, 15, 14 | 1 | 1 | | Z | 3, 9, 12 | 3 | 3 | MAX chooses **X**, worth 4. Y holds the best single leaf (15), but MIN would never allow it, so Y is worth only 1 against good play. Choosing Y for its 15 is the classic optimistic mistake. Choosing by each row's average (5, 10, 8) would also pick Y, because averaging models an opponent who replies at random, not one who replies against you. ## Negamax: one function for both sides In a zero-sum game a position's value for one player is the negative of its value for the other. **Negamax** uses this: every position is scored from the point of view of the **side to move**, and ``` value(position) = max over legal moves of -value(position after the move) ``` One recursive function then serves both players. The trap is the evaluation: it must also return the score for the side to move. If it always scores for one colour, the signs flip at alternate plies and the AI starts choosing the opponent's best moves. ## Where plain minimax struggles - **Cost.** Each extra ply multiplies the work by about `b`. Alpha-beta pruning returns the same root value while skipping branches that cannot change it, which is why practical game-tree searches build on it rather than on plain minimax. - **The horizon effect.** A depth-limited search can stop in the middle of an exchange: it sees the AI capture a piece but not the recapture one ply later, and scores the position as a gain. It can also play delaying moves that push an unavoidable loss just past the depth limit and then believe the loss has gone. **Quiescence search** handles the first case by extending each leaf with captures (and in some games checks) until the position is quiet, and only then evaluating. - **Evaluation blind spots.** If the evaluation ignores a feature that decides the game, such as a passed piece racing to promote, a deeper search only partly makes up for it. - **Ties and wandering.** If every win scores the same constant, the AI may keep choosing moves that keep a win in reach without ever taking it. Scoring a win as a large constant minus the number of plies to reach it makes the search prefer the fastest win and the slowest loss.
- What is the horizon effect, and how does quiescence search reduce it?The horizon effect is a depth-limited search misjudging a position because the decisive move lies just past the depth limit, for example scoring a capture as a gain when the recapture is one ply deeper. Quiescence search extends each leaf with only forcing moves, usually captures, until no capture improves the side to move, letting it 'stand pat' on the static score. It fixes unfinished exchanges, not delaying tactics that push a slow loss beyond the horizon.
- Why should a win found in fewer plies score higher than a win found deeper?If every win scores the same constant, all winning moves tie, and the AI can keep picking moves that keep a win available without ever completing it. Scoring a win as a large constant minus the ply at which it occurs makes the search prefer the shortest win, and the mirror rule makes it prefer the longest loss when losing, so it resists and still converts.
- Minimax assumes the opponent picks replies at random.
- The evaluation function is only used when the game is over.
- Depth-limited minimax always finds the objectively best move.
- Searching one ply deeper costs only a few more evaluations.
- Negamax evaluation can score for a fixed colour instead of the side to move.