COMP 3200 - Intro to Artificial Intelligence - Lecture 09 - MiniMax Search + AlphaBeta Pruning

Overview

Dave Churchill introduces minimax search for two-player, alternating-move, zero-sum games, then develops alpha-beta pruning as a way to preserve minimax’s result while avoiding branches that cannot affect the choice. Using chess, tic-tac-toe, and worked game trees, he explains depth-limited heuristic evaluation, alpha and beta bounds, move selection, and iterative deepening for time-limited searches.

Key takeaways

Minimax searches alternating turns by maximizing the root player’s value and minimizing the opponent’s, so its decision accounts for an opponent who chooses the strongest available response.
Depth-limited minimax can guarantee the best choice only within the searched tree; nonterminal leaves require a heuristic, while terminal leaves can use true win, loss, or draw values.
Alpha-beta pruning preserves minimax’s value but skips branches that cannot affect the result, using alpha for the maximizing player’s best alternative and beta for the minimizing player’s.
With ideal move ordering, alpha-beta reduces a B^D search to roughly B^(D/2); poor ordering can eliminate most of that benefit.
Iterative deepening makes search usable under a clock: increase depth one level at a time and return the best action from the last fully completed iteration.
The search must retain the root action as well as the returned value; record a new best action when a better value is found at depth zero.

Chapters

0:00 Two-Player Games, Payoffs, and Zero-Sum Objectives

The lecture shifts from single-agent pathfinding to games where two players make decisions against each other.
Games vary by player count and structure: chess and Go are two-player alternating-move games, while Dota and League of Legends use five-player teams.
In a zero-sum game, one player’s utility gain corresponds to the other player’s loss; chess outcomes can be scored as win = 1, loss = −1, and draw = 0.

4:15 Chess Evaluation and Deep Blue’s 1997 Match

Traditional board games such as chess are typically two-player, zero-sum, alternating-move, perfect-information, deterministic, and discrete.
IBM’s Deep Blue defeated world chess champion Garry Kasparov in 1997 using search alongside specialized chess-evaluation hardware.
Chess evaluation can combine piece values—such as pawn = 1, rook = 5, and queen = 9—with positional features such as control of the board’s center.

6:21 Why Hardcoded Chess Rules Give Way to Lookahead

Strategy-specific rules and large collections of if-then statements are brittle and tend to encode a programmer’s understanding rather than general search.
Lookahead evaluates the states produced by candidate actions, allowing the same approach to apply across different two-player games.
A one-move strategy selects the legal action whose resulting state has the highest evaluation from the current player’s perspective.

10:49 One-Ply Evaluation in Tic-Tac-Toe

The basic procedure generates every legal action, creates its child state, evaluates that state, and returns the action with the highest value.
In tic-tac-toe, placing X in a winning square can receive a positive evaluation for X and the corresponding negative value for O.
Nonterminal positions need a heuristic evaluation, such as scoring two-in-a-row patterns; one-ply search may miss what the opponent can do next.

14:11 Game-Tree Complexity and the Limits of Exhaustive Search

With branching factor B and search depth D, a full game tree contains on the order of B^D possibilities.
Tic-tac-toe has at most 3^9 board configurations, making exhaustive enumeration feasible for a simple solver.
Chess’s game tree is too large to enumerate completely, so practical programs search a limited depth rather than solve every possible game.

17:29 Minimax Models a Maximizing Player and a Best-Responding Opponent

Minimax evaluates leaf states from the root player’s perspective: the maximizing player seeks higher values, while the minimizing opponent seeks lower ones.
The opponent’s response matters because a player cannot assume an opponent will allow a favorable line to continue.
At each level, the search alternates between choosing a maximum and a minimum, backing the resulting values up from evaluated leaves.

23:30 Depth-Limited Minimax and Heuristic Leaf Scores

The max-value and min-value procedures recurse through alternating turns and return a true outcome when they reach a terminal game state.
A depth limit D stops the recursion before the game ends and applies a heuristic evaluation to nonterminal leaf states.
Minimax is optimal for the searched depth under its opponent model, but the quality of a depth-limited choice depends on the leaf-evaluation function.

28:27 Negamax, Nash Equilibrium, and Minimax’s Assumptions

Negamax uses the zero-sum identity max(a, b) = −min(−a, −b) to express both player turns through one recursive form.
Churchill recommends the more explicit max/min version for implementation and debugging, and says Negamax is not required for the exam or Assignment 3.
Minimax assumes both players respond optimally; this corresponds to best responses and a Nash-equilibrium perspective, not to exploiting a weaker opponent’s mistakes.

35:00 Alpha-Beta Pruning Uses Bounds to Skip Search Branches

Alpha-beta pruning adds bounds to minimax so search can stop exploring a branch once it cannot change an ancestor’s decision.
Alpha tracks the best alternative available to the maximizing player on the current path; beta tracks the minimizing player’s best alternative.
The bounds narrow a search window: a minimizing branch known to be no better than an existing maximizing option, for example, can be pruned.

41:46 Tracing Alpha and Beta Through a Worked Game Tree

The alpha-beta version passes alpha and beta down recursive calls, starting the root with negative infinity and positive infinity.
In the example, a maximizing node already has value 7; when a minimizing child finds 3, the remaining children can be skipped because that branch cannot improve the choice.
The bounds are passed by value down the tree, while recursive calls return their computed values upward; the root’s final value remains the same as minimax.

55:41 Ideal Move Ordering Can Reduce Alpha-Beta Search Dramatically

With ideal action ordering, alpha-beta can reduce search from roughly B^D nodes to roughly B^(D/2), an exponential saving in depth.
Poor move ordering can prevent cuts and make the search approach ordinary minimax’s workload.
Because pruning preserves the minimax result and adds only a small amount of bookkeeping, Churchill recommends using alpha-beta whenever implementing minimax.

58:30 Compact Alpha-Beta Code and Recording the Root Move

Churchill derives a shorter alpha-beta implementation by combining repeated max/min logic, but warns that the compact form can be harder to debug.
A minimax or alpha-beta value alone does not identify which move produced it; an AI must record the best action at the root.
The implementation can store that action when a new maximum is found at depth zero; for Assignment 3, Churchill recommends first implementing long-form minimax, then adding alpha-beta.

1:08:20 Iterative Deepening for a Fixed Search-Time Budget

A fixed depth can take unpredictable time, so iterative deepening searches depth 1, then 2, then 3, continuing until the time budget expires.
When a deeper iteration is interrupted, the program must return the best action from the last fully completed depth.
A partially searched depth may not have examined every root action, so its current best move is not reliable.

1:12:00 Stopping Recursive Search Safely with Exceptions

A time-limit implementation may need to stop while execution is inside nested minimax or alpha-beta calls.
Churchill describes using a thrown exception to escape recursion, then catching it at the appropriate level to return the last completed iteration’s action.
A catch-all handler can hide unrelated programming errors, so exception handling must distinguish the intentional search timeout from genuine bugs.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.