Part 7: Game Trees

Perfect information. Poker is not fully observable (you cannot see the opponent's cards), and minimax as defined on p.15 needs to know which state it is in to evaluate it. The deck's own summary on p.38 files partial-information games separately, under "Solution methods for partial-information games in economics (poker)".

The axis that is merely postponed is deterministic or stochastic. A die or a shuffled deck adds chance nodes, which is exactly the extension in Part 8 (expectimax). The remaining three axes (two players, turn-taking, zero sum) are the "standard game" assumptions of p.9.

Carried over: initial state s₀, Actions(s), and the transition model Result(s, a). These are exactly the Part 3 ingredients.

New: (i) Player(s) says whose turn it is, which is required because the backup rule at a node depends on the mover, not on the depth alone; (ii) Terminal-Test(s) replaces the goal test, and it can end the game in a loss as well as a win, so it is not a goal test; (iii) Utility(s, p) returns a number rather than a boolean, so terminal states are ranked instead of merely accepted. A single-agent search problem had a goal test and a path cost; a game has a terminal test and a terminal utility.

The reasoning is too literal. What minimax needs is that the two players' utilities are strictly opposed, so that maximising one is the same as minimising the other. Any constant-sum game has that property: if U_A + U_B = c for a fixed c, then U_B = c − U_A, and the ordering B prefers is exactly the reverse of A's. The deck states the property as "Agents have opposite utilities" and "One maximizes, the other minimizes" (p.10), not as an arithmetic identity.

What genuinely breaks minimax is independent utilities, where B's ranking is not determined by A's. That is the right-hand column, and it is the case handled by generalized minimax in section 14.

Costs on edges accumulate downward as you extend a path, so g is known the moment you build a path. Utilities at leaves propagate upward, so nothing is known about an internal node until its subtree has been explored. That is precisely why the lecturer argues in T6 that the minimax tree should be built depth first: a breadth-first build would produce a large frontier and still know nothing, because no utility is available until a terminal node is reached.

V(s) = known utility if s is terminal; V(s) = max_{s' ∈ successors(s)} V(s') otherwise. The missing ingredient is a guarantee that every branch reaches a terminal state in finitely many steps, that is, a finite game tree. Deck p.18 supplies m, the maximum number of steps before a terminal state, and uses it in the complexity bound. Sections 11 and 13 below remove that guarantee deliberately and replace the terminal case with an evaluation function.

The move does not change, the value can. Minimax at every node depends only on the ordering of the values among the children, and rescaling −1 to −100 leaves the order −100 < 0 < +1 identical to −1 < 0 < +1. So max and min pick the same children throughout and the optimal policy is unchanged, while the number backed up to the root may become −100 instead of −1.

Carry this forward: the same "only the ordering matters" argument does not survive contact with chance nodes, because an expectation over utilities is sensitive to the actual magnitudes. That is one of the sharp contrasts in Part 8.

Left MIN = min(−8, −5) = −8. Right MIN = min(−10, +8) = −10. Root = max(−8, −10) = −8, which is what the slide prints.

The root is negative, so under the assumption of optimal play by both sides the agent will lose whatever it does. Minimax then buys the smallest loss: it takes the left action, because −8 beats −10. Note that the +8 leaf on the right is irrelevant. It sits under the opponent's choice, and the opponent will never hand it over.

minimax_value returns a number, the value of the position. minimax-decision returns an action, the move to play. An exam question that says "which move should MAX play" is answered by naming a branch, not by writing 3. The distinction also matters mechanically: after alpha-beta pruning the value returned by a pruned child is only a bound, so the number attached to that child cannot be quoted as its minimax value even though the root's value and the root's best action are both still correct.

(i) b^m = 35¹⁰⁰ ≈ 2.55 × 10¹⁵⁴, a 155-digit number. (ii) b × m = 35 × 100 = 3500 nodes, which fits in a pocket calculator.

Time is the blocker, not space. That is why the two fixes in this deck both attack the number of leaves visited: alpha-beta (visit fewer of them) and bounded lookahead (stop before reaching them). Neither fix targets memory, because memory was never the problem.

MIN nodes: min(3, 12, 8) = 3, min(2, 4, 6) = 2, min(14, 5, 2) = 2. Root = max(3, 2, 2) = 3, so MAX plays the leftmost action. All 9 leaves were evaluated, because plain minimax has no mechanism for skipping any.

Verified by executing minimax and alpha-beta on this tree in Python; both return 3.

Because the cut condition is checked after each child, and the first child of MIN-3 is 14. At that moment the node's running value is 14, and 14 ≤ α = 3 is false, so the loop continues. Then 5: still false. Only at 2 does the test pass, and by then there is nothing left to skip. Alpha-beta is not clairvoyant; it can only react to values it has already seen. The lecturer makes the same point in T6: those nodes had to be explored further because the branch could still have turned out interesting, and here it did not.

This is also the whole argument for child ordering. Had the 2 come first in that group, its two siblings would have been cut, exactly as in the middle group.

Only f. Trace: left MIN evaluates 10 (β := 10), then 8, and returns 8. Root: v = 8, α := 8. Right MIN inherits α = 8, evaluates leaf 4, and 4 ≤ 8, so it returns immediately and f is never followed. Root = max(8, 4) = 8. Three of the four leaves are evaluated.

Why not the others: a and d must be taken because the algorithm knows nothing before descending; b must be taken because the left MIN has no value yet; c must be taken because at that point the left MIN is only "10 or less" and 8 is genuinely lower, so it changes the answer; e must be taken to get any information about the right MIN at all. In T6 the lecturer works exactly this list, and his reason for c is that without expanding it you would never learn that the value is 8, which is what makes the left MIN node worth 8 rather than 10.

Verified by executing the p.26 pseudocode: root 8, 3 leaves evaluated, 1 pruned.

Two cuts, three leaves saved.

1. Arc g is cut at a MAX node. Left MIN gets 10 from the b subtree, so β := 10 and the e subtree inherits β = 10. Its first leaf is 100, and 100 ≥ β = 10, so the MAX node at e returns 100 at once and leaf 8 is never seen. This is the β test, the one that lives in max-value.
2. Arc l is cut at a MIN node. Root now has α = 10. Right MIN inherits α = 10; the i subtree returns 2; and 2 ≤ 10, so right MIN returns 2 and the entire l subtree, leaves 20 and 4, is never generated. This is the α test, the one in min-value.

Root = max(10, 2) = 10. Five of eight leaves evaluated. Verified in Python.

The lecturer introduces the first of those cuts in T6 as the reverse principle of pruning, and points out what changed: there is no longer a MIN node sitting directly above the leaf values, there is a MAX node.

First a caveat about what "the pseudocode's α" even means at a node that returns early. The code tests before it updates: if v ≥ β return v comes before α = max(α, v). So at the MAX node under e, and at the right MIN node, both of which return early, the update line is never reached and those nodes' own α and β are left exactly as they were passed in. Taken literally, the code writes no α = 100 and no β = 2 anywhere. The reading under which the slide's annotations make sense is "the bound this node would hold once the child just returned is folded in", and that is the reading used below.

Under that reading, the letters printed next to a node record that node's own best-so-far among its children: the MAX node under i has seen 1 and 2, so its own best is 2. The pseudocode's α parameter is a different quantity: it is that local best combined with everything inherited, so α = max(10, 2) = 10. At the other annotated nodes on this slide the two readings agree; only this node separates them.

Neither number is the one that cuts arc l. The cut happens one level up, at the right MIN node, and it compares that MIN node's own value (2, the value returned by the i subtree) against the α the MIN node inherited from the root (10). So it is 2 ≤ 10 that does the work. Verified by execution.

The α label marks the value of the alternative that MAX already has in hand: it is the value of a child of the MAX node above, and that child happens to be a MIN node. The letter names MAX's best option, and the option is a subtree whose root is a MIN node. That is the same convention as p.21, where "α = 3" is written next to MIN nodes that received the 3 from the root.

The distance is arbitrary because α is defined over "any choice point along the current path from the root", not over the parent. A cut at n can be justified by a MAX node many levels above. This is the single feature that makes alpha-beta a whole-path algorithm rather than a local rule, and it is why the parameters are threaded through every recursive call in the pseudocode.

The root value never changes: both versions are correct algorithms, because a child whose value merely ties α cannot improve on what MAX already has. The pruning count does change: the strict version keeps expanding on ties and therefore prunes less.

For the exam, use the deck's non-strict version, because the answers you will be compared against were produced with it. The clearest case is p.27, treated in the next section, where a tie of 10 against 10 is enough to cut.

Left MIN returns 10; root sets α := 10. Right MIN inherits α = 10 and evaluates its first leaf, 10. The test v ≤ α is 10 ≤ 10, which is true, so right MIN returns 10 immediately and the leaf 0 is never evaluated. Root = max(10, 10) = 10.

With a strict test the leaf 0 would be evaluated, the right MIN would return 0, and the root would still be max(10, 0) = 10. Same answer, one more leaf touched. That is the theorem on this slide in miniature: the pruning changed the work, not the value. Verified by execution: 2 of 3 leaves evaluated.

Constructed example (not from the course material; built for this chapter and verified by executing the p.26 pseudocode in Python).

Layers: root R is MAX; its children M1 and M2 are MIN; their children X1, X2 and Y1, Y2 are MAX; the leaves are below those.

                        R (MAX)
              /                        \
        M1 (MIN)                        M2 (MIN)
        /      \                        /      \
   X1(MAX)   X2(MAX)              Y1(MAX)   Y2(MAX)
    /   \     /   \                /   \     /   \
   3     8   9     1              2     6   7     0

Sanity check against exhaustive minimax: max( min(max(3,8), max(9,1)), min(max(2,6), max(7,0)) ) = max( min(8, 9), min(6, 7) ) = max(8, 6) = 8. Same value, three fewer leaves.

How to write part (ii) in words. Something close to this earns the marks:

Let β be the best (lowest) value MIN can already secure at any choice point on the current path from the root. While expanding a MAX node n, keep its running value v = max over the children seen so far. Since v can only increase as more children of n are examined, the moment v ≥ β we know MIN, at the ancestor holding β, will never choose the branch leading to n: it already has an option worth at most β. The remaining children of n therefore cannot influence the value backed up to the root, and are skipped. Formally: at a MAX node, if v ≥ β then return v. The mirror rule at a MIN node is: if v ≤ α then return v, where α is the best (highest) value MAX can already secure on the path. Neither rule changes the minimax value at the root; both change how much of the tree is generated.

Draw both cuts on your tree and label each with its inequality. That way the answer is complete under either of the two namings documented in section 8.

(a) Without pruning the cost of depth d is 35^d. 35⁴ = 1,500,625, already slightly over 1M; 35⁵ is about 5.25 × 10⁷. So the honest answer is depth 4, half of what alpha-beta buys. That is precisely the "Doubles solvable depth!" claim of p.27, restated in seconds instead of in exponents.

(b) Left MIN = min(−1, −2) = −2. Right MIN = min(4, 9) = 4. Root = max(−2, 4) = 4, which is what the slide prints. The cloud is the part of the tree below the horizon: it exists, it would change the true values, and the search simply refuses to look at it. The four numbers are not utilities of terminal states; they are outputs of an evaluation function applied to non-terminal positions.

He gets trapped. At depth 2 the danger from the second ghost is beyond the horizon, so both moves look equally safe and the tie is broken by whatever the evaluation function rewards, typically getting closer to food. The lecturer describes it in T6: Pacman cannot escape the ghosts because he can reason only two steps into the future.

On this slide the responsible ingredient is the depth: a deeper search on the same board, p.33, solves it. Keep that answer separate from the deeper lesson in the box below, which is about a different situation where depth is not the fix.

Because at depth 10 the search sees far enough to know that the immediate threat is the blue ghost, and that stepping towards the orange one is safe for now while it changes what the blue ghost does later. The lecturer's account in T6 is that with a depth of 10 the best choice is to move closer to the orange ghost first, since there is no immediate danger from it; the blue ghost then makes a different decision, and Pacman can finally reach the last white pellet.

The general lesson: a move produced by a deep search is part of a contingent plan (deck p.8) and can look locally wrong. Judging an agent by whether its next move looks sensible is not a valid test. This is the same object the course calls a policy in Part 9.

Neither change alters a single move. Minimax uses only max and min, which depend on the order of the children's values and on nothing else. So any strictly increasing relabelling of the utilities, not just scaling and shifting, leaves every choice and therefore the whole policy unchanged.

How much survives Part 8: only the affine part. A chance node takes a weighted average, and averaging commutes with a · x + b when a > 0, so multiplying by 10 and adding 7 are still harmless. The wider claim is not. Constructed counterexample: MAX chooses between a chance node worth 0 or 10 with probability 1/2 each (value 5) and a sure 4, so it prefers the chance node. Relabel utilities with the strictly increasing map 0 → 0, 4 → 100, 10 → 101. The chance node is now worth 0.5(0) + 0.5(101) = 50.5, the sure option is worth 100, and MAX switches. The ordering of the outcomes never changed; only their spacing did. That is one concrete way in which expectimax is not just "minimax with probabilities".

Pacman's layer (maximise component 3): max((1,1,6),(0,0,7)) = (0,0,7); max((9,9,0),(8,8,1)) = (8,8,1); max((9,9,0),(7,7,2)) = (7,7,2); max((0,0,8),(0,0,7)) = (0,0,8).

Blue ghost's layer (component 2): max((0,0,7),(8,8,1)) = (8,8,1); max((7,7,2),(0,0,8)) = (7,7,2).

Red ghost's root (component 1): max((8,8,1),(7,7,2)) = (8,8,1), which is what the slide prints.

Why nobody gets (9,9,0): both copies of it sit under a Pacman node, and Pacman scores 0 there against 1 and 2 in the alternatives, so he never selects it. The ghosts never get the chance to prefer it. This is the "cooperation and competition dynamically" bullet made concrete: the two ghosts have identical interests here and are effectively cooperating, and the outcome is still decided by the player whose turn falls in between.

Verified by executing the tuple backup in Python.

Player 3's layer (maximise component 3): max((1,2,3),(4,2,1)) = (1,2,3) since 3 > 1; max((6,1,2),(7,4,−1)) = (6,1,2) since 2 > −1; max((5,−1,−1),(−1,5,2)) = (−1,5,2) since 2 > −1; max((7,7,−1),(5,4,5)) = (5,4,5) since 5 > −1.

Player 2's layer (component 2): max((1,2,3),(6,1,2)) = (1,2,3) since 2 > 1; max((−1,5,2),(5,4,5)) = (−1,5,2) since 5 > 4.

Player 1's root (component 1): max((1,2,3),(−1,5,2)) = (1,2,3) since 1 > −1.

Note how badly player 1 does out of this: he takes 1 when a leaf worth 7 to him exists in the tree twice. Both are blocked by players 2 and 3 acting on their own components. Verified in Python against the solution slides.

One printing slip to be aware of: the final solution slide writes the comparison as MaxFirstPlayer([1,2,3],[-1,5,4]) = [1,2,3], while the tuple actually carried up from the layer below, and drawn on the same slide, is [-1,5,2]. The winner is unaffected, because the decision uses the first components (1 against −1). Trust the drawn tree.

(a) Minimax. The twelve MIN nodes just above the leaves: 3, 1, 2, 4, 7, 2, 0, 3, 0, 2, 3, 1. The six MAX nodes: 3, 2, 7, 0, 3, 3. The two MIN nodes: 2 and 0. Root = max(2, 0) = 2.

(b) Alpha-beta in the given order: 10 leaves evaluated, 17 pruned. The solution deck's own caption is "17 static evaluations saved". The four cuts, in the order they fire:

1. At the MIN node [2,1] under MAX1: v = 2 and 2 ≤ α = 3, so the leaf 1 is skipped. 1 leaf.
2. At MAX3: its first MIN child returns 4, and 4 ≥ β = 2 (β came from MIN-L, which had already collected 3 and 2), so its two remaining MIN children are skipped. 3 leaves (7, 3, 2).
3. At the MIN node [1,4,0] under MAX4: v = 1 and 1 ≤ α = 2, so leaves 4 and 0 are skipped. 2 leaves.
4. At MIN-R: MAX4 returned 1, and 1 ≤ α = 2, so MAX5 and MAX6 are skipped whole. 11 leaves.

1 + 3 + 2 + 11 = 17. The 10 leaves actually evaluated are 4, 3, 5, then 2, then 4, 2, 3, then 5, 4, then 1.

(c) Best-first reordering: 8 leaves evaluated, 19 pruned ("19 static evaluations saved" in the solutions). The rule is the same as in section 9: MIN nodes take their smallest child first, MAX nodes their largest. That gives

root MAX
 |-- MIN-L : MAX[2,3,4] , MAX([3,4,5],[1,2]) , MAX([7],[4,5],[2,3])
 '-- MIN-R : MAX[0,1,4] , MAX([3,5],[0])     , MAX([3,6],[2,4,7],[1,3,5])

and the four cuts become: MAX with children [3,4,5],[1,2] stops at 3 ≥ β = 2 (2 leaves); MAX with children [7],[4,5],[2,3] stops at 7 ≥ β = 2 (4 leaves); the MIN node [0,1,4] stops at 0 ≤ α = 2 (2 leaves); MIN-R stops at 0 ≤ α = 2 (11 leaves). 2 + 4 + 2 + 11 = 19.

Root value: 2 in both runs. That is the theorem of p.27 again, now on 27 leaves.

The claim is true, and it is true of the trace as well. Under the p.26 pseudocode a single-child MAX node is an exact pass-through. It receives (α, β), passes the same (α, β) straight down to its only child, and returns that child's value unchanged: with one child the loop body runs once, so whether the cut test fires or the loop simply ends, the returned value is the child's value and no bound was ever narrowed. Contracting it changes nothing computationally.

Verified by execution: running the exercise tree with MAX2 and MAX4 contracted gives the same root value 2, the same 10 leaves evaluated, the same evaluation order, and the same four cuts (only the path labels shift). Across 4000 randomly generated trees, contracting every single-child node changed the root value or the leaf count in 0 of them. One caveat on how you check this yourself: a node's MAX or MIN role comes from Player(s), a property of the state, not from its depth. If your code alternates by level instead, contraction will flip the roles below the contracted node and you will see spurious differences.

So why trace what is drawn? Not for correctness, but for marks. This archetype is graded on the α and β you write at each drawn node, and an answer that silently deletes nodes the question drew leaves the grader with nothing to check at those positions. Simplify in your head if it helps; write out the drawn structure.