MINIMAX computes the MINIMAX VALUE of each state — the utility of being in that state, assuming BOTH PLAYERS PLAY OPTIMALLY to the end of the game. MINIMAX(s) = UTILITY(s) if TERMINAL-TEST(s) max_{a ∈ ACTIONS(s)} MINIMAX(RESULT(s,a)) if PLAYER(s)=MAX min_{a ∈ ACTIONS(s)} MINIMAX(RESULT(s,a)) if PLAYER(s)=MIN THE ALGORITHM, as usually written: function MINIMAX-DECISION(state) returns an action return argmax over a in ACTIONS(state) of MIN-VALUE(RESULT(state, a)) function MAX-VALUE(state) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← −∞ for each a in ACTIONS(state) do v ← MAX(v, MIN-VALUE(RESULT(state, a))) return v function MIN-VALUE(state) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← +∞ for each a in ACTIONS(state) do v ← MIN(v, MAX-VALUE(RESULT(state, a))) return v IT IS A COMPLETE DEPTH-FIRST EXPLORATION of the game tree. The values propagate UP from the leaves: utilities are known at the terminal states, and each internal node takes the max or min of its children according to whose turn it is. PROPERTIES: COMPLETE yes, if the tree is finite OPTIMAL yes, against an optimal opponent TIME O(b^m) where m is the maximum depth SPACE O(bm) if all actions are generated at once, or O(m) if generated one at a time → the space is linear because it is depth-first; the TIME is the problem, and it is the reason for the next topic. WORKED EXAMPLE — the standard three-branch tree. MAX moves first; each of MAX's three moves leads to a MIN node with three terminal children. leaf utilities: branch A: 3, 12, 8 branch B: 2, 4, 6 branch C: 14, 5, 2 MAX ┌──────┼──────┐ A B C MIN MIN MIN / | \ / | \ / | \ 3 12 8 2 4 6 14 5 2 STEP 1 — evaluate the MIN nodes. MIN picks the SMALLEST child, because MIN is trying to minimise MAX's utility: MIN(A) = min(3, 12, 8) = 3 MIN(B) = min(2, 4, 6) = 2 MIN(C) = min(14, 5, 2) = 2 STEP 2 — evaluate the MAX node. MAX picks the LARGEST: MAX = max(3, 2, 2) = 3 THE MINIMAX DECISION IS MOVE A, with a guaranteed value of 3. READ WHAT THAT MEANS CAREFULLY, because it is the point of the algorithm: branch C contains the best leaf in the whole tree (14), and MAX does not choose it. MAX cannot reach the 14 because MIN chooses at that node and will play the 2 instead. THE 14 IS UNREACHABLE AGAINST A COMPETENT OPPONENT, so choosing C on the strength of it would be wishful thinking. Minimax values what you can FORCE, not what you can hope for. 9 leaves were evaluated. Note that number — the next topic shows how many were actually necessary.

MULTIPLAYER GAMES — the extension to more than two players: Replace the single value at each node with a VECTOR of utilities, one per player. Each node is labelled with the vector of the position's value to each player, and the player to move chooses the successor whose vector maximises THEIR OWN component. with players A, B, C, a leaf might be ⟨v_A, v_B, v_C⟩ = ⟨1, 2, 6⟩, and at a node where C moves, C selects the child with the largest third component. TWO CONSEQUENCES that do not arise in the two-player case: · ALLIANCES emerge naturally. If A and B are both weaker than C, cooperating against C may be rational for both without any explicit negotiation — and the alliance dissolves as soon as it stops paying, which is why alliances in multiplayer games are unstable. · THE ZERO-SUM ASSUMPTION IS GONE, so there may be outcomes good for several players simultaneously. Minimax's pessimism no longer captures the situation. WHAT MINIMAX ASSUMES, and where each assumption fails: 1. THE OPPONENT PLAYS OPTIMALLY. If the opponent is weak, minimax leaves value on the table — it will not set a trap that a perfect player would see through, even against an opponent who would fall for it. THE ALTERNATIVE is OPPONENT MODELLING: predict what THIS opponent will do rather than what a perfect one would. Effective, and risky: if the model is wrong, the exploitative line may lose against the move the opponent actually plays. 2. THE UTILITIES ARE KNOWN EXACTLY. They are, at terminal states. At a cutoff they are ESTIMATES from EVAL, so the propagated minimax value inherits every error in the evaluation function — and worse, MINIMAX AMPLIFIES EVALUATION ERROR, because taking a max over noisy estimates systematically selects the ones that happen to be overestimated. This is a known and slightly unsettling result: deeper search with a noisy evaluator does not always play better. 3. THE GAME IS ZERO-SUM. Not true in negotiation, in most economic settings, or in multiplayer games. 4. THE TREE IS SEARCHABLE. It is not, for any interesting game, which is why H-MINIMAX with a cutoff and an EVAL function is what is actually run. THE PRACTICAL SHAPE OF A REAL ENGINE, so that minimax is seen in context: minimax with alpha-beta pruning the search core iterative deepening so the search can be stopped by the clock and returns a usable move at any time a transposition table positions reachable by different move orders are the same position; cache them move ordering from the previous iteration's best line which makes alpha-beta far more effective quiescence search to avoid stopping mid-exchange an evaluation function material plus positional features NOTE HOW MANY OF THOSE EXIST TO CONTROL THE COST OF SEARCH RATHER THAN TO IMPROVE THE DECISION RULE. Minimax says what the right answer is; everything else in the list is an attempt to afford it. A NOTE ON ITERATIVE DEEPENING HERE: it serves a different purpose than in uninformed search. There it saved MEMORY; here it provides an ANYTIME property — a legal, reasonable move is always available when the clock runs out, and each iteration's results improve the move ordering of the next, which more than repays the repeated work.

A FOUR-PLY EXAMPLE, because exam questions use them and the alternation is where mistakes happen. MAX (root) ├── MIN b1 │ ├── MAX c1 → leaves 8, 7 │ └── MAX c2 → leaves 3, 9 ├── MIN b2 │ ├── MAX c3 → leaves 9, 8 │ └── MAX c4 → leaves 2, 4 └── MIN b3 ├── MAX c5 → leaves 1, 8 └── MAX c6 → leaves 8, 9 WORK FROM THE LEAVES UPWARD. The level above the leaves is MAX, so take maxima: c1 = max(8, 7) = 8 c2 = max(3, 9) = 9 c3 = max(9, 8) = 9 c4 = max(2, 4) = 4 c5 = max(1, 8) = 8 c6 = max(8, 9) = 9 The next level up is MIN, so take minima: b1 = min(c1, c2) = min(8, 9) = 8 b2 = min(c3, c4) = min(9, 4) = 4 b3 = min(c5, c6) = min(8, 9) = 8 The root is MAX: root = max(8, 4, 8) = 8 THE MINIMAX VALUE IS 8, achieved by moving to b1 (or b3 — both give 8, so either is optimal and a tie-break rule decides). THE COMMON MISTAKES, worth naming because they are what loses marks: · applying max at the wrong level. COUNT PLY FROM THE ROOT: the root is MAX, so odd-numbered levels below it are MIN and even-numbered ones are MAX. · taking the max over the leaves of a MIN node. MIN chooses among its children; the leaves under c4 belong to c4's MAX decision, not to b2's. · reporting the VALUE when the question asks for the MOVE, or the reverse. The minimax DECISION is the action; the minimax VALUE is the number. A USEFUL CHECK: the root value must appear somewhere in the leaf set, because every internal value is copied up from some leaf. Here 8 appears among the leaves, which is consistent. If your computed root value is not a leaf value, you have made an arithmetic error. 16 LEAVES WERE EVALUATED HERE. With b = 2 and d = 4 that is 2^4 = 16, the full tree — minimax always examines every leaf. The next topic removes that, and the saving is the difference between a program that searches 8 ply and one that searches 16.