Lecture 06.2: Minimax and Alpha-Beta Pruning

While single-move games rely on simultaneous choices, many real-world strategic games (like Chess or Tic-Tac-Toe) are Sequential Games. Players face choices repeatedly, but each time with knowledge of the history of previous choices.

Optimal Decisions: The Minimax Algorithm

In a two-player, zero-sum game, we define the players as MAX and MIN.

• MAX prefers to move to a state of maximum value.
• MIN prefers a state of minimum value.

The Minimax Value of a node is the utility of being in that state, assuming that both players play optimally from there to the end of the game.

Visualizing Minimax State Expansion

Below is a simplified game tree. MAX moves first, followed by MIN.

1. At the bottom, we evaluate the terminal utility values.
2. The MIN nodes (B, C, D) choose the smallest value from their children.
   • B chooses $\min(3, 12, 8) = 3$.
   • C chooses $\min(2, 4, 6) = 2$.
   • D chooses $\min(14, 5, 2) = 2$.
3. The root MAX node (A) chooses the largest value from its children.
   • A chooses $\max(3, 2, 2) = 3$.

Thus, MAX's optimal first move is to go down path B.

---

Alpha-Beta Pruning

The problem with pure Minimax is that the number of game states it must examine is exponential in the depth of the tree ($O(b^m)$).

Alpha-Beta Pruning allows us to compute the correct minimax decision without looking at every node in the game tree. It returns the exact same move as Minimax, but prunes away branches that cannot possibly influence the final decision.

Key Concepts

• $\alpha$ (Alpha): The value of the best (highest) choice found so far for MAX. (Starts at $-\infty$).
• $\beta$ (Beta): The value of the best (lowest) choice found so far for MIN. (Starts at $+\infty$).

The Pruning Criterion: Stop exploring a branch if $\alpha \ge \beta$.

Visualizing a Pruning Event

Let's look at how Alpha-Beta pruning avoids unnecessary work in the same tree:

1. The algorithm fully explores node B's children and determines B's value is 3.
2. It returns to root A. Now A knows it can guarantee a score of at least 3. So, $\alpha = 3$.
3. The algorithm moves to node C and evaluates its first child, finding a 2.
4. Because C is a MIN node, C's value will be $\le 2$.
5. Root A already has a guaranteed $\alpha = 3$. Since C can only offer a maximum of 2, A will never choose path C.
6. Pruning: The algorithm immediately stops evaluating C's other children (4 and 6). We save computation time because $\alpha (3) \ge \beta (2)$.

By pruning effectively, Alpha-Beta can double the searchable depth in the same amount of time compared to standard Minimax!