In the two previous lessons the NovaMarket van was finding its way in a passive world: the map did not change because the van moved. But in 02-01 we saw that many environments are multi-agent, and some are competitive: there is another agent whose goals oppose ours and who answers each decision with one of its own. In that situation planning a path is not enough; you have to ask "and what will the other one do?" at every step. The branch of AI that studies this is adversarial search, and its fundamental algorithm is minimax. We will learn it where it was born, in games: we will see what changes with respect to the search of 03-02, how a game is represented as a game tree, how minimax chooses the best move assuming the opponent also plays perfectly, and how alpha-beta pruning obtains the same answer while exploring a fraction of the tree. We will implement it for noughts and crosses, counting nodes to measure each improvement, and explain why in chess or go the search has to be cut off and positions evaluated with heuristics (the link to Deep Blue and AlphaGo from 01-01). Finally we will take it to NovaMarket with a simplified "price war" against a competitor, and discuss honestly where the usefulness of minimax ends when information is imperfect and the game is not zero-sum.

1. What changes when there is an opponent
2. Zero-sum games with perfect information
3. The game tree: MAX and MIN levels
4. Minimax step by step on a numeric tree
5. Minimax for noughts and crosses in Python, counting nodes
6. Alpha-beta pruning: idea, numeric example and implementation
7. Depth limit and evaluation function: from draughts to Deep Blue and AlphaGo
8. Landing at NovaMarket: the price war and the adaptive fraudster
9. Limits of minimax: imperfect information, non-zero-sum, uncertainty

In the search of 03-02 the agent controlled every decision: it chose a leg, the world responded deterministically and it chose the next leg as well. When an opponent appears, half of the decisions are made by someone else, and made against us. This has direct consequences:

Diego understood it with an example from his daily work: "when I plan a route, nobody changes the city on me; when I set a price, the guy across the street sees it and reacts within the hour". That reaction turns the decision into a game.

Minimax is formulated for a specific class of games, the simplest and at the same time the most studied:

• Two players who alternate turns. We will call them MAX (us, who want to maximise the utility) and MIN (the opponent, who wants to minimise it).
• Deterministic: no dice or hidden cards; the result of a move is always the same.
• Perfect information: both see the complete state (the board) at all times.
• Zero-sum: what one gains the other loses. If at the end we assign +1 to a MAX win, −1 to a MIN win and 0 to a draw, MIN's utility is exactly the opposite of MAX's, and that is why a single utility function suffices: MAX maximises it and MIN minimises it.

Noughts and crosses, draughts, chess and go satisfy all four conditions. Poker does not (imperfect information and chance), and neither do many business situations (we will see it in section 9). Formulating a game as a problem adds one element to the formulation of 02-01: the function player(state) that says whose turn it is. In summary: initial state, player(s), actions(s), result(s, a), terminal(s) and utility(s).

The game tree is the search tree of 03-02 with one difference: the levels alternate between MAX decisions and MIN decisions. The root is the current state with MAX to move; its children are the positions after each MAX move, in which it is MIN's turn; the grandchildren, the positions after each MIN reply, and so on down to the leaves, which are terminal states with their utility. For noughts and crosses, from the empty board the complete tree has 9 branches at the first level, 8 at the second, 7 at the third… up to a total of 549,946 nodes, of which 255,168 are leaves (finished games). There are fewer leaves than the 9! = 362,880 ways of filling the board because many games end before it is full, and there are more nodes than leaves because we also count every intermediate position. It is big enough to make being clever worthwhile and small enough for Python to traverse it entirely in seconds: the perfect teaching vehicle.

Before noughts and crosses, an abstract two-level tree with the utilities already placed on the leaves. MAX moves at the root A choosing between B, C and D; MIN replies at each of them choosing among three leaves.

Minimax reasoning goes bottom-up:

1. At B it is MIN's turn. Of the leaves 3, 12 and 8 it will pick the smallest: B is worth 3. Although B2 = 12 is tempting for MAX, MAX will never get it because MIN will not allow it.
2. At C, MIN picks the minimum of 2, 4, 6: C is worth 2.
3. At D, MIN picks the minimum of 14, 5, 2: D is worth 2. Notice the trap of D1 = 14: the best leaf of the tree is there, but MIN will make sure it is never reached.
4. At A it is MAX's turn, and MAX picks the maximum among 3, 2 and 2: A is worth 3, and the correct move is to go to B.

That "3" is the minimax value of the position: the utility MAX can guarantee for itself if MIN plays perfectly. If MIN makes a mistake, MAX will get more; if MIN plays well, MAX will get no less. In code, the recursion is completely transparent:

Notice that minimax is a depth-first search (03-02): the recursion goes down the first branch to the leaves before looking at the second, and it only needs memory for the current path. Its time cost is O(bᵐ), with b possible moves per turn and m levels of depth: for chess (b ≈ 35, m ≈ 80) that is a number with more than 120 digits. Hence sections 6 and 7.

Now a real game. Representation decisions (remember 03-01: representation is half the solution):

• The board is a list of 9 squares, indices 0-8 from left to right and top to bottom, holding "X", "O" or " " (empty).
• The winning lines are 8 triples of indices: 3 rows, 3 columns and 2 diagonals.
• X is MAX and always starts; O is MIN. Utility: +1 if X wins, −1 if O wins, 0 for a draw.

And the algorithm. To be able to compare with alpha-beta later, we count in the global variable nodes how many times minimax is called, that is, how many positions are examined:

Important points in the code:

• Making and undoing the move on the same list (b[m] = "X" … b[m] = " ") avoids copying the board on every call. It is the typical backtracking pattern of depth-first search; it works because, on returning from the recursion, we restore exactly the previous state.
• best_move is the "root" of the tree: it applies the same criterion as minimax, but remembering which move gives the best value, which is what we really need.
• Every call to minimax scans LINES in terminal; we could optimise it, but for 550,000 positions Python takes a few seconds, which is enough.

Let us try it in three situations:

Reading the results:

1. From the empty board the value is 0: with perfect play on both sides noughts and crosses ends in a draw, something any child discovers by playing and that minimax proves by exploring 549,945 positions (every one in the tree except the root). It returns square 0 because it is the first one with value 0; in fact all nine openings are worth 0. If you print the value of each one you will see they all tie and that the "cheapest" to analyse is the centre (55,505 nodes versus 59,705 for the corners and 63,905 for the edges), because the symmetry of the centre shortens more games.
2. With O threatening the middle column, X blocks on 7; the value is still 0 (a draw with good play), and only 205 nodes are needed because few squares remain.
3. In the third position, X plays square 3 and the value becomes +1: minimax has found the double threat (left column and middle row) against which O has no defence. This is the kind of "vision" a human player has to train and that search obtains by sheer enumeration.

If you let best_move play against itself from the empty board you will always get a draw: minimax never loses and never lets a forced win slip away.

Minimax examines the whole tree, but much of the work is useless: there are branches whose result cannot change the decision, and we can stop exploring them as soon as we know it. That is alpha-beta pruning, which returns exactly the same value and the same move as minimax, but visits far fewer nodes.

Let us go back to the numeric tree of section 4 and follow the order in which depth-first search traverses it:

1. B is explored completely: B1 = 3, B2 = 12, B3 = 8, so B = 3. MAX now knows that at A it can guarantee at least 3. That "at least" is alpha (α): the best option found so far for MAX along the path from the root.
2. C begins. The first leaf is C1 = 2. Since MIN picks the minimum, C will be worth 2 or less. But MAX already has 3 guaranteed at B; a branch worth at most 2 will never be chosen. There is no need to look at C2 or C3: they are pruned.
3. D begins. D1 = 14: D is worth at most 14, it could still beat 3, we carry on. D2 = 5: D is worth at most 5, it could still beat 3, we carry on. D3 = 2: D is worth at most 2, it can no longer beat 3. Here we saved nothing because the bad leaf came last.

Result: same value (3, go to B) exploring 11 nodes instead of 13. Step 3 shows the key to performance: order matters. Had D3 come first, D would have been pruned after a single leaf. With perfect ordering (trying the best moves first), alpha-beta explores of the order of b^(m/2) nodes instead of bᵐ: it can look twice as deep with the same effort. With random ordering the gain is smaller but still large.

Formally, two values are maintained during the recursion: α = the best utility MAX can secure so far (starts at −∞ and only rises), and β = the best utility MIN can secure so far (starts at +∞ and only falls). As soon as α ≥ β at some node, the rest of its children are discarded: MAX already has something better elsewhere (or MIN already has something worse for us elsewhere) and this branch will never be played.

Direct comparison, same move and same value in all three cases:

And a check on the effect of ordering: if in moves we return the centre first, then the corners and then the edges (the order any experienced player would try), the search from the empty board drops from 18,296 to 7,274 nodes, 75 times fewer than pure minimax. In chess engines, ordering the moves well (captures first, moves that were good in earlier searches…) is as important as the pruning itself.

Noughts and crosses can be exhausted entirely. Chess, with about 35 legal moves per position and games of 80 half-moves, has a tree of the order of 35⁸⁰ ≈ 10¹²³ nodes; go, with 250 moves per turn and games of 150 moves, of the order of 10³⁶⁰. Neither alpha-beta nor any conceivable computer can traverse them. The practical solution has two parts:

• Cut the search off at a maximum depth (for example, 6 half-moves) and treat those positions as if they were leaves.
• Replace the exact utility (known only in terminal positions) with a heuristic evaluation function that estimates how good a position is for MAX: in chess, material (pawn 1, knight 3, rook 5…), mobility, king safety; in go, territory and influence. It is the same idea as the heuristic h of A* in 03-02: a cheap estimate that guides the search when the exact answer is out of reach.

For noughts and crosses we can build a simple evaluation: the number of lines still "open" for X (with no O in them), weighted by how many Xs they already contain, minus the same for O. At depth 1 this evaluation already prefers the centre (value 4, because the centre lies on four lines) over the corners (3) and the edges (2). It proves nothing, but it points in the right direction, and in large games that is all one can ask for.

This combination (alpha-beta + limited depth + heuristic evaluation + move ordering + tables of positions already seen) is exactly the architecture of Deep Blue, which in 1997 beat Kasparov by analysing some 200 million positions per second with an evaluation function hand-designed by grandmasters and engineers, as we recalled in 01-01. It is symbolic, pure-search AI (02-02): it did not learn to play; it searched further and evaluated better than a human. Go held out for twenty more years because its branching factor is too large even for alpha-beta and because nobody managed to write a good evaluation function by hand; AlphaGo (2016) solved precisely that point by replacing the manual evaluation with a neural network trained on games and on self-play, and combining it with a form of sampling-based search. How that network is trained is a matter of reinforcement learning (04-02) and neural networks (module 5); what matters here is to see that adversarial search is still the skeleton and that what evolved was where the evaluation comes from.

Diego and Marta want to decide the weekly price of a flagship television knowing that their main competitor reacts to their moves. Let us model it as a two-level game: NovaMarket (MAX) chooses between holding the price, cutting it by 5 % or cutting it by 10 %; the competitor (MIN) responds by holding, matching or cutting even further. On the leaves we place NovaMarket's estimated weekly margin (in thousands of euros) for each combination, obtained from its historical sales data:

We reuse the generic recursion of section 4 with business names:

Minimax recommends cutting by 5 %, not because it is the option with the best leaf (the best leaf, 14, is also on that branch, but that is a coincidence), but because it is the one that guarantees the most in the worst case: whatever happens, the margin will not fall below €5,000. Holding the price has the worst guarantee (3) because it hands the initiative to the competitor. This "secure the floor" reasoning is what minimax brings to a business decision, and it is especially valuable when the cost of being wrong is high.

Use case 3 (return fraud) is another environment with an adversary: when NovaMarket tightens a rule ("block returns without a receipt from the third one in a month"), fraudsters learn it and change tactics (they spread returns across several accounts, they stay under three). A detector designed by looking only at past behaviour is like a player who ignores the opponent's replies. Thinking in minimax mode means asking, for each candidate rule, "what is the fraudster's best response to this rule, and how much fraud gets through then?", and choosing the rule whose worst response is the least damaging. In practice no explicit tree is built, but the mental habit is the same, and we will come back to it when we discuss the evaluation of fraud models in module 4.

The price war of 8.1 is useful as a thought exercise, but we should be honest about how it departs from a board game. Each difference points to a different tool:

A concrete example of the first row: if besides NovaMarket's margin we estimate the competitor's margin at each leaf and assume that they maximise their own instead of minimising ours, the predicted response to "cut 5 %" changes from "cut 10 %" (which leaves them €6,000) to "match" (which leaves them €9,000), and the margin we should expect is 8, not 5. In this case the decision does not change (cutting 5 % is still best), but the valuation does, and in other cases the decision could change too. Minimax gives the guaranteed floor; the opponent model gives the realistic expectation. A good analyst looks at both.

What is universal is the underlying lesson: when there is another agent who reacts, a decision cannot be evaluated on its own; it has to be evaluated together with the other's best response. That principle, with or without an explicit tree, is this lesson's contribution to the rest of the course.

• Forgetting to undo the move (b[m] = " ") after the recursive call: the board is left corrupted and the results are nonsense. If you prefer to avoid the risk, make a copy (new = list(b)) at the cost of more memory and time.
• Confusing the value of a position with the move: minimax returns a number; you have to wrap it (best_move) to know which move produces that number.
• Getting the pruning conditions backwards: MAX updates α and prunes if α ≥ β; MIN updates β and prunes on the same condition. A common mistake is updating β in MAX. Always check it against the tree of section 4: you must get 3, pruning C after C1.
• Believing that alpha-beta changes the result: never. If you get different values from minimax and alphabeta, there is a bug in the pruning implementation.
• Not initialising alpha and beta at the root to −∞ and +∞: any other value can prune valid branches.
• Applying minimax to a problem that is not zero-sum without realising: as in the price war, the answer will be excessively pessimistic. Always ask yourself whether "what I lose, the other gains" is literally true.
• Evaluation function with the wrong scale: if terminal positions are worth ±1 and the heuristic evaluation returns values like 4 or −3, a "promising" position may look better than a certain win. Scale the terminal utility (for example ±100) so that it dominates.

Given the following tree (MAX at the root, MIN at the second level, leaves with utilities), compute the minimax value of the root and the chosen move. Then apply alpha-beta traversing the children from left to right and state which leaves are pruned.

Modify moves so that it returns the squares in the order centre, corners, edges ([4, 0, 2, 6, 8, 1, 3, 5, 7], filtering out the occupied ones) and compare the nodes explored by best_move_ab from the empty board with the original order. Check that the value and the recommended move (now square 4) are still worth 0. Does the number of nodes of best_move (minimax without pruning) change when reordering? Why?

Add the dictionary COMP_MARGIN with the competitor's margin at each leaf (use these values: hold → 10, 11, 9; cut_5 → 7, 9, 6; cut_10 → 5, 7, 4, in the same order as the leaves of PRICE_TREE) and write a function rational_response(option) that returns the leaf where the competitor maximises their margin. For each NovaMarket option print the predicted response, our margin and theirs, and compare the recommendation with that of minimax.

Solution 1. E = min(5, 9, 4) = 4; F = min(2, 7, 8) = 2; G = min(6, 11, 3) = 3. Root = max(4, 2, 3) = 4, move E. With alpha-beta: E is explored completely (α becomes 4). At F, the first leaf is 2 ≤ α, so F cannot beat 4: 7 and 8 are pruned. At G, the first leaf is 6 > 4 (we carry on), the second 11 (we carry on), the third 3 makes G = 3 < 4; there is no pruning because the bad leaf came last. Total: 7 leaves examined out of 9 (2 saved), same result as minimax. Had the order within G been 3, 6, 11, then 6 and 11 would also have been pruned and 5 leaves would suffice.

Solution 2.

Alpha-beta drops from 18,296 to 7,274 nodes and now recommends square 4 (the centre; still worth 0 like all of them). Minimax without pruning explores exactly the same 549,945 nodes: without pruning, the order only changes when each node is visited, not whether it is visited. Ordering only has an effect when there is something to prune.

Solution 3.

The rational competitor answers "hold" by cutting 5 % (it gives them 11), and answers our cuts by matching them. The best option for NovaMarket is still cutting by 5 %, with an expected margin of 8 versus the floor of 5 that minimax guaranteed. The two ways of reasoning agree on the decision, but not on the figure: minimax is insurance against the worst case; the opponent model, a prediction of the likely.

We have added a new ingredient to search: an opponent who decides against us. We have seen that in zero-sum games with perfect information a solution is no longer a path but a strategy, and that the game tree alternates MAX and MIN levels. The minimax algorithm traverses that tree depth-first and propagates upwards, from the leaves, the value each player can guarantee; we have followed it by hand on a numeric tree and implemented it for noughts and crosses, checking that the game is a draw and that 549,945 nodes are needed to prove it. Alpha-beta pruning obtains the same result exploring 18,296 nodes (7,274 with good move ordering), and the depth limit with an evaluation function is what makes it possible to play chess or go, the road that leads from Deep Blue to AlphaGo. With NovaMarket's price war we have seen that the habit of "evaluating each decision together with the opponent's best response" is useful in business too, and we have clearly delimited when minimax stops being the right model (non-zero-sum, imperfect information, chance, repetition).

The third big problem announced at the opening of the module remains. So far we have searched for paths (03-02) and moves (03-03) by exploring the state space systematically. But the full van problem (choosing the order of all the day's deliveries) has, as we saw in 03-01, n! candidate solutions, and no systematic search exhausts it. In the last lesson of the module, Optimization Algorithms, we will change approach: instead of building the solution step by step, we will start from any complete solution and keep improving it with hill climbing, simulated annealing and genetic algorithms, to solve the van's travelling salesman problem and the assignment of orders to the Zaragoza and Getafe warehouses.