1. Adversarial Search Introduction

1.1 Foundations of Adversarial Environments

1.1.1 Active vs. Passive Search Environments

In standard single-agent search problems (such as route planning, finding the shortest path in a maze, or solving an 8-puzzle), the environment is classified as passive. In a passive environment, the world remains static or deterministic with respect to the agent's actions; the maze does not alter its structure to block the agent, and the puzzle does not dynamically adjust its configuration to counteract the agent's strategy.

In contrast, adversarial search deals with multi-agent competitive environments where the world is active. In these environments, one or more opposing intelligent agents actively work to impede the primary agent's progress and maximize their own conflicting objectives. Every action executed by the primary agent is met with a calculated counter-action designed to diminish the agent's advantage. Consequently, an action cannot be evaluated merely by its immediate outcome; it must be judged by how well it holds up against the adversary's optimal response.

1.1.2 Environment Taxonomy: Two-Player Zero-Sum Games with Complete Information

Classical AI literature focuses on a specific taxonomy of games defined by five foundational properties:

graph TD
    A[Classical AI Game Taxonomy] --> B[Two-Player]
    A --> C[Zero-Sum]
    A --> D[Turn-Taking]
    A --> E[Deterministic]
    A --> F[Complete Information]
    
    B --> B1[Exactly 2 Competing Agents]
    C --> C1[Payoff Sum = 0: Max Gain = Min Loss]
    D --> D1[Sequential Alternating Moves]
    E --> E1[No Chance or Randomness]
    F --> F1[Perfect Board Visibility / No Hidden States]

1. Two-Player: The search space involves exactly two competing decision-makers, conventionally designated as $\text{MAX}$ (the primary agent) and $\text{MIN}$ (the opponent).
2. Zero-Sum: The payoff structure is strictly complementary. Whatever utility $\text{MAX}$ gains, $\text{MIN}$ loses by the exact same magnitude. Mathematically, if $U_{\text{MAX}}(s)$ and $U_{\text{MIN}}(s)$ represent the utilities of a terminal state $s$ for $\text{MAX}$ and $\text{MIN}$ respectively, then: $$U_{\text{MAX}}(s) + U_{\text{MIN}}(s) = 0 \implies U_{\text{MIN}}(s) = -U_{\text{MAX}}(s)$$
3. Turn-Taking: Actions are sequential rather than simultaneous. Players take strict alternating turns.
4. Deterministic: State transitions are completely predictable. Executing an action $a$ in state $s$ leads to a single, deterministic outcome state $s'$ without stochastic elements (such as dice rolls).
5. Complete Information (Perfect Information): Both players have total visibility of the complete game state at all times. There are no hidden variables (such as concealed cards in poker).

1.1.3 Standard Game Examples (Tic-Tac-Toe, Checkers, Chess, Go)

This classical taxonomy encompasses well-known board games:

• Tic-Tac-Toe: A simple 3x3 grid game. Though computationally trivial, it exhibits all structural properties of adversarial search (alternating turns, complete visibility, zero-sum outcome: $+1$ win, $0$ draw, $-1$ loss).
• Checkers: Played on an 8x8 grid with forced captures and king promotions.
• Chess: A highly complex 8x8 tactical game with piece-captures, tactical maneuvers, and strategic positional control.
• Go: Played on a 19x19 grid with placement and encirclement mechanics, possessing an immense state-space complexity.

1.2 Formal Game State-Space Representation

1.2.1 The Five Essential Search Components

To formulate an adversarial game as a formal computational search problem, we define a tuple consisting of five core components:

1. Initial State ($S_0$): The starting configuration of the game (e.g., the setup of pieces on a chessboard at move 0).
2. Player Function ($\text{Player}(s) $): A mapping from a given state $s$ to the player whose turn it is to move ($\text{Player}(s) \in {\text{MAX}, \text{MIN}}$).
3. Actions Function ($\text{Actions}(s) $): Returns the set of all legal moves available to $\text{Player}(s)$ in state $s$.
4. Terminal Test ($\text{Terminal}(s) $): A boolean test that returns $\text{True}$ if the game has concluded in state $s$ (e.g., checkmate, stalemate, or full board), and $\text{False}$ otherwise. States where $\text{Terminal}(s) = \text{True}$ are termed terminal states (or leaf nodes).
5. Utility Function ($\text{Utility}(s, p) $): An objective function that assigns a numeric payoff value to a terminal state $s$ for a player $p$. In zero-sum formulations from the perspective of $\text{MAX}$, the function is simplified to $\text{Utility}(s)$:

$$\text{Utility}(s) = \begin{cases} +1 & \text{if } \text{MAX} \text{ wins} \ 0 & \text{if draw} \ -1 & \text{if } \text{MIN} \text{ wins} \end{cases}$$

1.2.2 Game Tree Architecture & Alternating Ply Layers

Using these five components, the entire state space is represented as a Game Tree:

• Nodes: Represent game states $s$.
• Edges: Represent legal action transitions $a \in \text{Actions}(s)$.
• Root Node: Represents the initial state $S_0$, where $\text{Player}(S_0) = \text{MAX}$.
• Ply (Layers): Each depth level in the tree represents a turn taken by one player. A single ply corresponds to one move by one player (so two plies constitute one full round/turn for both players).

The tree strictly alternates between two node types across layers:

• $\text{MAX}$ Nodes: Represents states where it is $\text{MAX}$'s turn to move. $\text{MAX}$ selects the child node that maximizes the utility value.
• $\text{MIN}$ Nodes: Represents states where it is $\text{MIN}$'s turn to move. $\text{MIN}$ selects the child node that minimizes the utility value (which corresponds to maximizing $\text{MIN}$'s advantage).

graph TD
    Root["MAX (Root: s0)"] --> A1["MIN (s1)"]
    Root --> A2["MIN (s2)"]
    
    A1 --> B1["MAX (s3)"]
    A1 --> B2["MAX (s4)"]
    
    A2 --> B3["MAX (s5)"]
    A2 --> B4["MAX (s6)"]
    
    B1 --> T1["Terminal: Utility = +1"]
    B1 --> T2["Terminal: Utility = -1"]
    B2 --> T3["Terminal: Utility = 0"]
    B2 --> T4["Terminal: Utility = +1"]
    B3 --> T5["Terminal: Utility = -1"]
    B3 --> T6["Terminal: Utility = -1"]
    B4 --> T7["Terminal: Utility = 0"]
    B4 --> T8["Terminal: Utility = +1"]

1.3 Computational Complexity & Solution Strategies

1.3.1 Combinatorial State-Space Explosion

In practical applications, game trees grow exponentially with depth. For a game tree with an average branching factor $b$ (the average number of legal actions per state) and maximum tree depth $m$ (number of plies to terminal states), the total number of nodes in an exhaustive game tree is given by: $$\sum\limits_{i=0}^{m} b^i = \dfrac{b^{m+1} - 1}{b - 1} = O(b^m)$$

In Chess, the average branching factor is $b \approx 35$, and a typical game lasts roughly $m \approx 80$ plies (40 moves per player). This yields approximately: $$b^m \approx 35^{80} \approx 10^{40} \text{ total game states}$$

In Go, with $b \approx 250$ and $m \approx 150$, the state space exceeds $10^{170}$ states. Because $10^{40}$ exceeds all real-time computational limits, an exhaustive search down to terminal leaf nodes is computationally intractable.

1.3.2 Strategic Trade-Offs: Exact Pruning vs. Heuristic Cutoff Depths

To navigate combinatorial explosion, computer scientists employ two primary computational paradigms:

1. Exact Pruning Algorithms (e.g., Alpha-Beta Pruning):

   • Mechanism: Dynamically identifies and eliminates ("prunes") subtrees that are mathematically proven to have no impact on the final optimal decision at the root.
   • Advantage: Preserves exact decision optimality—guaranteeing the exact same move choice as an exhaustive search.
   • Limitation: In massive state spaces, even optimal pruning cannot make full-depth search feasible.

2. Heuristic Evaluation with Depth Limits (Heuristic Minimax):

   • Mechanism: Truncates the search tree at a fixed maximum depth limit $d < m$ using a cutoff test. Non-terminal leaf nodes at depth $d$ are evaluated using a heuristic evaluation function $\text{Eval}(s)$ that estimates winning probability without expanding to terminal states.
   • Advantage: Dramatically reduces execution time, making real-time search feasible.
   • Trade-off: Sacrifices complete decision optimality in exchange for computational tractability, introducing strategic risks such as tactical blind spots (horizon effects).

2. Minimax Algorithm

2.1 Core Minimax Principles & Game Theory Assumptions

2.1.1 Optimal Play Assumption & Zero-Sum Payoffs

The Minimax algorithm is a foundational decision-rule in game theory and artificial intelligence used for calculating the optimal move in two-player, zero-sum, turn-taking games with complete information. The core philosophical premise of Minimax is the optimal play assumption:

• Both players — $\text{MAX}$ (the agent) and $\text{MIN}$ (the opponent)—are assumed to act with absolute rationality and zero errors.
• $\text{MAX}$ aims to choose actions that lead to the highest possible utility payoff, while $\text{MIN}$ simultaneously chooses actions that minimize $\text{MAX}$'s payoff (which, in a zero-sum game, strictly maximizes $\text{MIN}$'s own payoff).
• Consequently, $\text{MAX}$ plans its strategy under the pessimistic, worst-case assumption that every move will be met by $\text{MIN}$'s optimal, most damaging counter-move.

2.1.2 Depth-First Search (DFS) Traversal & Value Propagation

Computationally, Minimax operates by exploring the game tree using a recursive Depth-First Search (DFS) traversal:

1. Unfolding/Recursion Downward: The algorithm starts at the root node (representing the current state $s$ where $\text{Player}(s) = \text{MAX}$) and recursively traverses down the tree along legal action edges until it reaches terminal states (leaf nodes) at depth $m$.
2. Terminal Evaluation: Upon reaching leaf nodes, the algorithm evaluates their exact utility values using the game's objective utility function $\text{Utility}(s)$.
3. Value Propagation Upward (Backtracking): As the recursion unwinds, values are backed up level-by-level from child nodes to parent nodes. At each ply, the parent node's value is calculated according to the player whose turn it is to move at that node.

graph TD
    A["MAX Node: Pick max(children)"] --> B1["MIN Node 1: Pick min(children)"]
    A --> B2["MIN Node 2: Pick min(children)"]
    B1 --> C1["Terminal Leaf 1: Utility = +1"]
    B1 --> C2["Terminal Leaf 2: Utility = -1"]
    B2 --> C3["Terminal Leaf 3: Utility = 0"]
    B2 --> C4["Terminal Leaf 4: Utility = +1"]

2.1.3 Mathematical Formulation of MAX and MIN Value Functions

Let $\text{MinimaxValue}(s)$ denote the optimal minimax utility value associated with state $s$. The recursive mathematical definition of $\text{MinimaxValue}(s)$ is defined as follows:

$$\text{MinimaxValue}(s) = \begin{cases} \text{Utility}(s) & \text{if } \text{Terminal}(s) = \text{True} \ \ \max\limits_{a \in \text{Actions}(s)} \text{MinimaxValue}(\text{Result}(s, a)) & \text{if } \text{Player}(s) = \text{MAX} \ \ \min\limits_{a \in \text{Actions}(s)} \text{MinimaxValue}(\text{Result}(s, a)) & \text{if } \text{Player}(s) = \text{MIN} \end{cases}$$

Where $\text{Result}(s, a)$ is the transition function returning the successor state resulting from executing legal action $a$ in state $s$.

Once the values for all child nodes $s' = \text{Result}(S_0, a)$ of the root state $S_0$ are backed up, $\text{MAX}$ selects the action $a^*$ that achieves the maximum utility value:

$$a^* = \underset{a \in \text{Actions}(S_0)}{\mathop{argmax}} ~ \text{MinimaxValue}(\text{Result}(S_0, a))$$

2.2 Algorithmic Mechanics & Step-by-Step Walkthrough

2.2.1 Leaf/Terminal State Utilities & Ply Definitions

In adversarial search terminology, a ply refers to a single move by one player (a level of depth in the game tree). A full turn consists of two plies: one move by $\text{MAX}$ followed by one move by $\text{MIN}$.

For standard finite games like Tic-Tac-Toe, terminal states are explicitly evaluated as discrete utility values:

• $\text{Utility}(s) = +1$ (Win for $\text{MAX}$)
• $\text{Utility}(s) = 0$ (Draw / Tie)
• $\text{Utility}(s) = -1$ (Loss for $\text{MAX}$ / Win for $\text{MIN}$)

In general multi-state games, terminal utilities can be arbitrary integer or real numbers representing relative advantage.

2.2.2 Concrete Trace of a 2-Ply Game Tree

Consider a concrete 2-ply game tree where $\text{MAX}$ makes the first move at root node $R$, leading to three $\text{MIN}$ nodes ($A$, $B$, and $C$). Each $\text{MIN}$ node has subsequent legal actions reaching terminal leaf nodes with assigned integer utilities:

graph TD
    Root["Root: MAX"] --> A["Node A: MIN"]
    Root --> B["Node B: MIN"]
    Root --> C["Node C: MIN"]
    
    A --> A1["Leaf A1: Utility = 3"]
    A --> A2["Leaf A2: Utility = 12"]
    A --> A3["Leaf A3: Utility = 8"]
    
    B --> B1["Leaf B1: Utility = 2"]
    B --> B2["Leaf B2: Utility = 4"]
    
    C --> C1["Leaf C1: Utility = 14"]
    C --> C2["Leaf C2: Utility = 5"]
    C --> C3["Leaf C3: Utility = 2"]

Step-by-Step Value Calculation:

1. Evaluating Branch $A$ ($\text{MIN}$'s Turn): $\text{MIN}$ chooses between leaf outcomes ${3, 12, 8}$. Since $\text{MIN}$ minimizes utility: $$\text{MinimaxValue}(A) = \min\limits(3, 12, 8) = 3$$
2. Evaluating Branch $B$ ($\text{MIN}$'s Turn): $\text{MIN}$ chooses between leaf outcomes ${2, 4}$. Minimizing utility gives: $$\text{MinimaxValue}(B) = \min\limits(2, 4) = 2$$
3. Evaluating Branch $C$ ($\text{MIN}$'s Turn): $\text{MIN}$ chooses between leaf outcomes ${14, 5, 2}$. Minimizing utility gives: $$\text{MinimaxValue}(C) = \min\limits(14, 5, 2) = 2$$
4. Evaluating Root $R$ ($\text{MAX}$'s Turn): $\text{MAX}$ now evaluates backed-up values from its child choices ${A: 3, B: 2, C: 2}$. Maximizing utility gives: $$\text{MinimaxValue}(R) = \max\limits(3, 2, 2) = 3$$

Strategic Takeaway: Although branch $C$ contains the absolute highest terminal leaf value in the entire tree ($14$ at node $C1$), $\text{MAX}$ cannot achieve $14$ because rational opponent $\text{MIN}$ will actively select action $C3$ (value $2$) to prevent $\text{MAX}$ from winning. Hence, $\text{MAX}$'s optimal choice is action $A$, securing a guaranteed minimum payoff of $3$.

2.3 Complexity Analysis & Practical Limits

2.3.1 Time Complexity ($O(b^m) $) and Space Complexity ($O(bm) $)

Let $b$ represent the average branching factor (number of legal moves per state) and $m$ represent the maximum depth of the game tree (maximum plies to terminal leaf states).

• Time Complexity: Because naive Minimax performs an exhaustive depth-first traversal of the full game tree, every leaf node must be generated and evaluated. The total number of generated leaf nodes is $b^m$, yielding a time complexity of:

  $$T(b, m) = O(b^m)$$

• Space Complexity: Because Minimax utilizes recursive Depth-First Search (DFS), it evaluates sibling subtrees sequentially rather than storing them simultaneously in memory. At any peak moment, the call stack only maintains the single active path of $m$ ancestor nodes, with each stack frame tracking its branch state and the best utility value found so far. Thus, memory requirement scales linearly with tree depth:

  $$S(b, m) = O(bm)$$

2.3.2 Time Complexity ($O(b^d) $) and Space Complexity ($O(b \cdot d) $): Concrete $b=2, d=3$ Example

To understand the computational bounds of the Minimax algorithm, consider a concrete game tree with a branching factor $b = 2$ (each player has 2 legal moves) and lookahead depth $d = 3$ (the search looks 3 plies ahead):

graph TD
    R["Depth 0 (Root: MAX) [R]"] --> A["Depth 1 (MIN) [A]"]
    R --> B["Depth 1 (MIN) [B]"]
    
    A --> C["Depth 2 (MAX) [C]"]
    A --> D["Depth 2 (MAX) [D]"]
    
    B --> E["Depth 2 (MAX) [E]"]
    B --> F["Depth 2 (MAX) [F]"]
    
    C --> C1["Leaf: 3"]
    C --> C2["Leaf: 5"]
    
    D --> D1["Leaf: 2"]
    D --> D2["Leaf: 9"]
    
    E --> E1["Leaf: 1"]
    E --> E2["Leaf: 8"]
    
    F --> F1["Leaf: 0"]
    F --> F2["Leaf: 4"]

1. Time Complexity (CPU Execution: $O(b^d) $)

Time complexity represents the total number of node visits/operations the processor must perform. Because standard Minimax executes an exhaustive Depth-First Search (DFS) down to terminal states or cutoff depths, every single node in the game tree must be visited.

• Node Count Derivation by Depth Level:
  • Depth 0 (Root): $2^0 = 1$ node ($R$)
  • Depth 1: $2^1 = 2$ nodes ($A, B$)
  • Depth 2: $2^2 = 4$ nodes ($C, D, E, F$)
  • Depth 3 (Leaves): $2^3 = 8$ leaf evaluations
• Total Node Visits: $$\sum\limits_{i=0}^{d} b^i = \sum\limits_{i=0}^{3} 2^i = 1 + 2 + 4 + 8 = 15 \text{ total node visits}$$
• DFS Traversal Sequence:
  1. $R \to A \to C \to \text{Evaluate}(3)$
  2. $C \to \text{Evaluate}(5) \to \text{Compute } \max(3, 5) = 5 \text{ for } C$
  3. $A \to D \to \text{Evaluate}(2)$
  4. $D \to \text{Evaluate}(9) \to \text{Compute } \max(2, 9) = 9 \text{ for } D$
  5. Compute $\min(5, 9) = 5$ for $A$
  6. $R \to B \to \dots$ (repeats the DFS evaluation sequence for the right subtree $B, E, F$)

As depth $d$ increases, CPU operations grow exponentially as $O(b^d)$. For example, increasing $d$ to $10$ requires $\sum\limits_{i=0}^{10} 2^i = 2^{11} - 1 = 2,047$ visits; at $d = 20$, it exceeds $2$ million operations.

2. Space Complexity (Memory / Call Stack: $O(b \cdot d) $)

Space complexity is determined by the maximum call stack memory used at any single snapshot in time. Minimax does not retain all $15$ nodes in memory simultaneously. Once a sub-branch finishes evaluating and returns its score, its nodes are popped off the stack and memory is freed.

• Peak Memory Snapshot (Evaluating Leaf 3 at Depth 3):
  • Frame 3: $\text{minimax}(\text{Leaf } 3)$ $\leftarrow$ Currently evaluating score $3$
  • Frame 2: $\text{minimax}(\text{Node } C)$ $\leftarrow$ Waiting for children ($3, 5$)
  • Frame 1: $\text{minimax}(\text{Node } A)$ $\leftarrow$ Waiting for children ($C, D$)
  • Frame 0: $\text{minimax}(\text{Node } R)$ $\leftarrow$ Waiting for children ($A, B$)
• RAM Footprint at Peak:
  • Depth 0: Node $R$ and its $2$ child action references ($A, B$) $\to 2$ references
  • Depth 1: Node $A$ and its $2$ child action references ($C, D$) $\to 2$ references
  • Depth 2: Node $C$ and its $2$ child action references ($3, 5$) $\to 2$ references
  • Total Peak Memory Held: $b \cdot d = 2 \cdot 3 = 6$ node/action references in RAM.
• Backtracking and Memory Reuse:
  • After Leaf $3$ and Leaf $5$ are evaluated, Node $C$ computes $\max(3, 5) = 5$ and returns $5$ to Node $A$.
  • Node $C$ and its leaf children are popped off the stack (freed from RAM).
  • The exact same memory frames are then reused to evaluate Node $D$.

Consequently, storing only the active ancestor path and scalar tracking state keeps the overall space complexity scaling linearly with depth as $S(b, d) = O(b \cdot d)$ rather than exponentially.

2.3.3 Intractability of Naive Minimax in Real-World Games

While space complexity $O(bm)$ is modest and easily fits within memory, the exponential time complexity $O(b^m)$ makes complete Minimax search computationally impossible for non-trivial games:

• Tic-Tac-Toe: $b \approx 3$, $m \approx 9 \implies 3^9 = 19,683$ states (computationally trivial, solved in milliseconds).
• Chess: $b \approx 35$, $m \approx 80 \implies 35^{80} \approx 10^{40}$ leaf nodes. Even at 1 trillion evaluations per second, searching the full tree would require over $10^{20}$ years.
• Go: $b \approx 250$, $m \approx 150 \implies 250^{150} \approx 10^{360}$ leaf nodes.

Therefore, naive full-depth Minimax is intractable for complex real-world games, necessitating bounded search techniques.

2.4 Heuristic Depth-Limited Minimax Search

2.4.1 Cutoff States & Heuristic Evaluation Functions ($\text{Eval}(s) $)

To make adversarial search computationally practical, standard implementations replace the complete search tree with a Depth-Limited Search:

1. Cutoff Test: Replaces the terminal test $\text{Terminal}(s)$ with a depth cutoff test $\text{Cutoff}(s, d)$. The search is truncated when the current depth reaches a predetermined limit $d$ ($d \ll m$).
2. Heuristic Evaluation Function ($\text{Eval}(s) $): Non-terminal states at cutoff depth $d$ are evaluated using a heuristic evaluation function $\text{Eval}(s)$ instead of the true terminal utility function $\text{Utility}(s)$.

$$\text{Eval}(s) \approx \text{Expected Utility of state } s \text{ from MAX's perspective}$$

An effective heuristic function must satisfy three essential operational properties:

1. Strong Correlation with Winning Probability: States assigned higher evaluation scores must statistically correspond to higher actual probabilities of winning.
2. Computational Efficiency: The evaluation function must calculate quickly so that the AI can explore a larger number of nodes within its real-time turn budget.
3. Exact Terminal Alignment: At terminal states, $\text{Eval}(s)$ must equal the exact terminal utility: $\text{Eval}(s) = \text{Utility}(s)$.

2.4.2 Claude Shannon’s Linear Evaluation Model for Chess (1950) [Heuristic Evaluation Function Example]

In his landmark 1950 paper, Claude Shannon proposed replacing full-tree evaluation with a heuristic evaluation function based on domain-specific features recognized by expert chess players.

Shannon formulated $\text{Eval}(s)$ as a weighted linear combination of domain features:

$$\text{Eval}(s) = \sum\limits_{i=1}^{n} w_i \cdot f_i(s)$$

Using vector notation, letting $\overrightarrow{w} = [w_1, w_2, \dots, w_n]^T$ represent the weight vector and $\overrightarrow{f}(s) = [f_1(s), f_2(s), \dots, f_n(s)]^T$ represent the state feature vector, the heuristic function is expressed as the inner product:

$$\text{Eval}(s) = \overrightarrow{w}^T \cdot \overrightarrow{f}(s)$$

2.4.2.1 Feature Selection ($f_i$) and Weighted Combinations ($\sum\limits_{i=1}^n w_i \cdot f_i(s) $)

Key feature categories $f_i(s)$ introduced in Shannon's chess model include:

1. Material Advantage ($f_{\text{material}}$): Net difference in piece counts weighted by standard piece values (Pawn $= 1$, Knight $= 3$, Bishop $= 3$, Rook $= 5$, Queen $= 9$).
2. Piece Mobility ($f_{\text{mobility}} $): Number of legal moves available to each player, reflecting tactical flexibility.
3. King Safety ($f_{\text{king safety}}$): Degree of pawn shield protection and surrounding enemy threat count around the king.
4. Pawn Structure ($f_{\text{pawn}}$): Penalty for weak pawn formations (isolated, doubled, or backward pawns) and bonus for passed pawns.
5. Board Control ($f_{\text{control}}$): Spatial control of key central squares ($d4, d5, e4, e5$).

2.4.2.2 Dynamic Feature Weighting Across Game Phases

Static feature weights $\overrightarrow{w}$ are insufficient because the strategic importance of features changes dynamically throughout different phases of a game:

• Opening Phase: Mobility, center control, and king safety features carry high relative weight coefficients ($w_i$).
• Endgame Phase: Pawn structure and passed-pawn progression carry significantly higher weight coefficients ($w_i$), whereas early-game opening control features lose relevance.

Consequently, advanced engines dynamically adjust weight vectors $\overrightarrow{w}(t)$ as a function of game progress $t$, or learn feature representations automatically from data.

3. Alpha-Beta Pruning

3.1 Pruning Principles & State Variables

3.1.1 Concept of Subtree Elimination (Preserving Minimax Optimality)

Alpha-Beta Pruning is an algorithmic optimization applied to the standard Minimax search framework. It dramatically speeds up game-tree exploration by dynamically skipping ("pruning") subtrees that are mathematically guaranteed to have no influence on the final optimal decision at the root node.

Crucially, Alpha-Beta Pruning is an exact optimization: it does not alter or approximate the value returned by Minimax. The exact same move is chosen as would be selected by an exhaustive full-tree Minimax search, but with a fraction of the computational effort.

3.1.2 Boundary Parameters: $\alpha$ ($\text{MAX}$ Lower Bound) and $\beta$ ($\text{MIN}$ Upper Bound)

To execute pruning during Depth-First Search (DFS) traversal, the algorithm maintains two dynamic boundary scalar variables along the active search path:

1. $\alpha$ (Alpha): The highest (best) utility value that $\text{MAX}$ has guaranteed for itself so far along any evaluated path.

   • Initialized at the root as $\alpha = -\infty$.
   • $\text{MAX}$ nodes update $\alpha$ as $\alpha = \max(\alpha, v)$, pushing $\alpha$ upward as higher rewards are discovered.
   • Represents $\text{MAX}$'s strict lower bound on payoff: $\text{MAX}$ will never accept a final outcome less than $\alpha$.

2. $\beta$ (Beta): The lowest (best) utility value that $\text{MIN}$ has guaranteed for itself so far along any evaluated path.

   • Initialized at the root as $\beta = +\infty$.
   • $\text{MIN}$ nodes update $\beta$ as $\beta = \min(\beta, v)$, pushing $\beta$ downward as lower opponent scores are found.
   • Represents $\text{MIN}$'s strict upper bound on $\text{MAX}$'s payoff: $\text{MIN}$ will never allow $\text{MAX}$ to achieve an outcome greater than $\beta$.

Operational Rules for $\alpha$ and $\beta$ Updates

Node Type	What it updates from children	What it passes down unchanged	What it does NOT update
MAX	$\alpha = \max(\alpha, \text{child's return value})$	$\beta$ (inherited from parent)	$\beta$ stays frozen
MIN	$\beta = \min(\beta, \text{child's return value})$	$\alpha$ (inherited from parent)	$\alpha$ stays frozen

graph TD
    A["MAX Node: Updates alpha = max(alpha, v)"] -->|"Pushes alpha down path"| B["MIN Node: Updates beta = min(beta, v)"]
    B -->|"Pruning Triggered when alpha >= beta"| C["Pruned Subtree"]

3.1.3 The Pruning Criterion ($\alpha \ge \beta$)

As DFS recurses down the game tree, the values of $\alpha$ and $\beta$ define a dynamically narrowing window of useful utility scores $[\alpha, \beta]$.

The Pruning Condition: $$\alpha \ge \beta$$

Whenever an evaluation causes $\alpha \ge \beta$ at a node, a cutoff is triggered immediately.

Mathematical Intuition:

• Suppose $\text{MIN}$ is evaluating a child node where its current running value drops to $\beta \le \alpha$.
• Since $\text{MIN}$ minimizes, the final value returned by this $\text{MIN}$ node will be at most $\beta$.
• However, an ancestor $\text{MAX}$ node already has a guaranteed path yielding $\alpha \ge \beta$.
• Therefore, $\text{MAX}$ will never choose the branch leading to this $\text{MIN}$ node. Exploring any remaining child branches or subtrees beneath this node is completely pointlessly redundant and can be safely terminated.

3.2 Algorithmic Trace & Execution Mechanics

3.2.1 Parameter Propagation Down and Value Return Up the Tree

During the recursive execution of Alpha-Beta search:

1. Downward Pass: As DFS descends down the game tree, the current values of $(\alpha, \beta)$ are inherited and passed down from parent nodes to child nodes.
2. Upward Pass: As terminal nodes or cutoff depth leaves are evaluated, scalar utility values $v$ are passed back up to parent nodes.
   • At a $\text{MAX}$ node, $v = \max(v, \text{child val})$. If $v > \alpha$, then $\alpha$ is updated to $v$.
   • At a $\text{MIN}$ node, $v = \min(v, \text{child val})$. If $v < \beta$, then $\beta$ is updated to $v$.
3. Threshold Check: After each child branch evaluation, the node checks if $\alpha \ge \beta$. If $\text{True}$, the loop over remaining actions is broken immediately (pruning the unexpanded siblings).

3.2.2 Step-by-Step Alpha-Beta Trace Example ($b=2, d=3$)

To illustrate the concrete execution mechanics of parameter propagation down the tree and the exact conditions under which pruning occurs, consider a complete binary game tree with branching factor $b=2$ and depth limit $d=3$.

The Game Tree Architecture

The search tree alternates between $\text{MAX}$ and $\text{MIN}$ layers down to depth $d=3$:

• Depth 0 (Root): $\text{MAX}$ node $R$.
• Depth 1: $\text{MIN}$ nodes $A$ and $B$.
• Depth 2: $\text{MAX}$ nodes $C, D, E, F$.
• Depth 3 (Leaf Nodes): Terminal/heuristic utility values ${6, 7, 1, 2, 1, 0, 5, 8}$.

graph TD
    R["Root R (MAX)"] --> A["Node A (MIN)"]
    R --> B["Node B (MIN)"]
    
    A --> C["Node C (MAX)"]
    A --> D["Node D (MAX)"]
    
    B --> E["Node E (MAX)"]
    B --> F["Node F (MAX)"]
    
    C --> L1["Leaf: 6"]
    C --> L2["Leaf: 7"]
    
    D --> L3["Leaf: 1"]
    D --> L4["Leaf: 2"]
    
    E --> L5["Leaf: 1"]
    E --> L6["Leaf: 0"]
    
    F --> L7["Leaf: 5"]
    F --> L8["Leaf: 8"]

---

Step-by-Step Execution Trace

Phase 1: Exploring the Left Subtree ($A$)

1. Downward Pass to $C$ ($R \to A \to C$):

   • Root $R$ initializes boundary parameters $(\alpha = -\infty, \beta = +\infty)$ and passes them down through $A$ to node $C$.
   • Node $C$ ($\text{MAX}$) evaluates leaf $6$ ($\alpha = \max(-\infty, 6) = 6$) and leaf $7$ ($\alpha = \max(6, 7) = 7$).
   • Node $C$ returns value $7$ to parent node $A$.

2. Updating Bound at Node $A$ ($\text{MIN}$):

   • Node $A$ receives $7$ from $C$ and updates its upper bound: $$\beta = \min(+\infty, 7) = 7$$
   • Threshold check: $\alpha = -\infty < \beta = 7 \implies$ No cutoff. DFS continues to right child $D$.

3. Downward Pass to $D$ ($A \to D$):

   • Node $D$ ($\text{MAX}$) receives current bounds $(\alpha = -\infty, \beta = 7)$ from $A$.
   • Node $D$ evaluates leaf $1$ ($\alpha = \max(-\infty, 1) = 1$) and leaf $2$ ($\alpha = \max(1, 2) = 2$).
   • Node $D$ returns value $2$ to parent node $A$.

4. Updating Bound at Node $A$ and Backtracking to $R$:

   • Node $A$ receives $2$ from $D$ and updates its upper bound: $$\beta = \min(7, 2) = 2$$
   • Node $A$ finishes evaluating all children and returns value $2$ up to root $R$.

5. Updating Lower Bound at Root $R$ ($\text{MAX}$):

   • Root $R$ receives $2$ from $A$ and updates its guaranteed lower bound: $$\alpha = \max(-\infty, 2) = 2$$
   • Strategic Benchmark: Root $R$ now knows that choosing action $A$ guarantees a minimum payoff of at least $2$.

---

Phase 2: Exploring the Right Subtree ($B$) and Pruning Trigger

6. Downward Pass to $B$ ($R \to B$):

   • Root $R$ passes its updated lower bound $\alpha = 2$ and $\beta = +\infty$ down to node $B$ ($\text{MIN}$).
   • Node $B$ inherits bounds $(\alpha = 2, \beta = +\infty)$.

7. Downward Pass to $E$ ($B \to E$):

   • Node $E$ ($\text{MAX}$) inherits $(\alpha = 2, \beta = +\infty)$ from $B$.
   • Node $E$ evaluates leaf $1$ ($\alpha = \max(2, 1) = 2$) and leaf $0$ ($\alpha = \max(2, 0) = 2$).
   • Node $E$ returns value $1$ to parent node $B$.

8. Updating Bound at Node $B$ and Triggering Pruning ($\alpha \ge \beta$):

   • Node $B$ ($\text{MIN}$) receives $1$ from $E$ and updates its upper bound: $$\beta = \min(+\infty, 1) = 1$$
   • Pruning Criterion Check: Node $B$ evaluates the condition $\alpha \ge \beta$: $$\alpha = 2, \quad \beta = 1 \implies \mathbf{2 \ge 1 \quad (TRUE!)}$$
   • Cutoff Execution: A pruning cutoff is triggered immediately at node $B$.
   • Outcome: The remaining branch $F$ and its two descendant leaf nodes ($5$ and $8$) are completely pruned and skipped from expansion.

graph TD
    R["Root R: MAX (alpha=2)"] --> A["Node A: MIN (beta=2, returns 2)"]
    R --> B["Node B: MIN (beta=1 -> PRUNE!)"]
    
    A --> C["Node C: MAX (returns 7)"]
    A --> D["Node D: MAX (returns 2)"]
    
    B --> E["Node E: MAX (returns 1)"]
    B -. "PRUNED SUBTREE (alpha >= beta: 2 >= 1)" .-> F["Node F: MAX (PRUNED)"]
    
    C --> L1["Leaf: 6"]
    C --> L2["Leaf: 7"]
    
    D --> L3["Leaf: 1"]
    D --> L4["Leaf: 2"]
    
    E --> L5["Leaf: 1"]
    E --> L6["Leaf: 0"]
    
    F -. "PRUNED" .-> L7["Leaf: 5 (PRUNED)"]
    F -. "PRUNED" .-> L8["Leaf: 8 (PRUNED)"]

---

Plain-English Strategic Intuition

$\text{MAX}$ at root $R$ already secured a guaranteed payoff of $2$ by taking branch $A$. When exploring branch $B$, the first sub-branch $E$ returned $1$. Because node $B$ is controlled by opponent $\text{MIN}$, $\text{MIN}$ will choose the action that minimizes $\text{MAX}$'s payoff, guaranteeing that branch $B$ will yield at most $1$ ($\le 1$). Since $\text{MAX}$ can already achieve $2$ via branch $A$, $\text{MAX}$ will never choose branch $B$. Therefore, exploring node $F$ and its descendant leaves ($5$ and $8$) is completely redundant and wasted computational effort.

Computational Performance Comparison

Evaluating this $b=2, d=3$ game tree demonstrates the immediate processing savings achieved by Alpha-Beta Pruning:

Performance Metric	Exhaustive Minimax	Alpha-Beta Pruning	Computational Savings
Evaluated Leaf Nodes	$8$	$6$	$25%$ reduction
Total Visited Nodes	$15$	$12$	$20%$ reduction
Pruned Nodes (Skipped)	$0$	$3$ (Node $F$, Leaf $5$, Leaf $8$)	$3$ nodes eliminated

3.3 Efficiency & Move Ordering Dynamics

3.3.1 Best-Case Time Complexity ($O(b^{m/2})$) and Effective Search Depth Doubling

The computational efficiency gained from Alpha-Beta Pruning depends fundamentally on move ordering—the sequence in which actions are expanded.

In the ideal best-case scenario, where the strongest moves are always evaluated first at every node:

• $\text{MAX}$ evaluates its highest-value move first, raising $\alpha$ as high as possible as early as possible.
• $\text{MIN}$ evaluates its strongest counter-move first, lowering $\beta$ as low as possible as early as possible.

Under optimal move ordering, Alpha-Beta Pruning reduces the effective branching factor from $b$ to $\sqrt{b}$. The time complexity reduces from $O(b^m)$ to:

$$T_{\text{best}}(b, m) = O(b^{m/2}) = O((\sqrt{b})^m)$$

Practical Significance: Since $b^{m/2} = (b^2)^{m/2} = b^m$ in terms of search effort, searching to depth $m$ with Alpha-Beta Pruning requires the same computational time as searching to depth $m/2$ with naive Minimax.

• In other words, Alpha-Beta Pruning effectively doubles the lookahead depth reachable within the same processing time window.
• If naive Minimax can search $4$ plies deep in 1 second, Alpha-Beta Pruning can search $8$ plies deep in 1 second (expanding 2 full turns per player instead of 1).

3.3.2 Worst-Case Scenario ($O(b^m) $)

In the worst-case scenario, where moves are evaluated in order from worst to best:

• $\text{MAX}$ evaluates its weakest moves first, keeping $\alpha$ low.
• $\text{MIN}$ evaluates its weakest counter-moves first, keeping $\beta$ high.
• No cutoffs are triggered ($\alpha < \beta$ throughout the search).

In this worst-case scenario, the algorithm is forced to explore every single node in the complete tree, degenerating back to the naive Minimax time complexity:

$$T_{\text{worst}}(b, m) = O(b^m)$$

3.3.3 Move Ordering Heuristics (Captures, Mobility, Board Control)

Because the performance of Alpha-Beta search ranges from $O(b^{m/2})$ (best case) to $O(b^m)$ (worst case), modern AI game engines employ move ordering heuristics to sort legal actions before expanding child nodes:

1. Captures and Threats (MVV-LVA - Most Valuable Victim, Least Valuable Attacker): Prioritizes capturing high-value opponent pieces with low-value pieces (e.g., Pawn capturing Queen).
2. Transposition Table Lookup: Checks if the state was previously searched and re-orders the best move stored from earlier iterations first.
3. Killer Moves & History Heuristic: Prioritizes moves that triggered alpha-beta cutoffs at the same depth level in sibling branches.
4. Positional Mobility and Center Control: Orders moves that increase piece mobility or command central territory early in the search.

3.4 Advanced Challenges in Depth-Limited Search

3.4.1 Quiescence Search & Non-Quiescent Position Handling

A primary risk in heuristic depth-limited search is evaluating a position at a depth limit $d$ that is non-quiescent (unstable or turbulent).

• Quiescent Position: A stable position where no immediate tactical swings or major piece exchanges are occurring (e.g., standard positional maneuvering).
• Non-Quiescent Position: A position mid-tactical sequence, such as immediately after a Queen capture where the opponent is poised to recapture on the next move.

If a fixed-depth cutoff stops search directly on a non-quiescent state $s$, the static heuristic evaluation $\text{Eval}(s)$ will yield a wildly inaccurate value (e.g., reporting a massive $+9$ Material Advantage because it hasn't evaluated the immediate recapture).

Solution — Quiescence Search: When search reaches the depth limit $d$, the engine checks if the position is non-quiescent. If non-quiescent, it extends the search beyond depth $d$ specifically along capture and tactical checking lines until a stable (quiescent) state is reached before applying $\text{Eval}(s)$.

3.4.2 The Horizon Effect & Tactical Blind Spots

The Horizon Effect occurs when an inevitable negative event (such as losing a piece or facing checkmate) lies just beyond the fixed search depth horizon $d$.

Example Mechanism:

• Suppose an engine searching at depth $d=5$ faces an unavoidable Queen capture occurring at depth $6$.
• The AI may discover delaying tactics (such as giving useless sacrifices or repetitive checks) that push the unavoidable capture beyond the $d=5$ horizon.
• To the $d=5$ search engine, these delay tactics appear to "save" the Queen, causing the AI to ruin its overall positional standing to delay a disaster it cannot ultimately prevent.

graph TD
    A["Search Horizon (Depth d=5)"] --> B["AI sees no Queen loss at depth 1..5"]
    B --> C["Selects bad delaying move"]
    C --> D["Inevitable Queen Loss at Depth 6 (Beyond Horizon)"]

3.5 Modern Evolution of Adversarial Search

3.5.1 Monte Carlo Tree Search (MCTS) & Stochastic Simulations

In modern game AI for complex domains like Go (where branching factor $b \approx 250$ makes traditional Alpha-Beta pruning insufficient), classical search is augmented or replaced by Monte Carlo Tree Search (MCTS):

• Instead of evaluating all branches up to a fixed depth, MCTS builds an asymmetric search tree using stochastic random or guided simulations (rollouts).
• MCTS balances exploration (visiting under-sampled moves) and exploitation (focusing on high-win-rate branches) using upper confidence bounds applied to trees (UCT).

3.5.2 Deep Reinforcement Learning & Learned Policy/Value Networks (AlphaZero)

Modern systems like AlphaZero integrate Monte Carlo Tree Search with Deep Neural Networks trained via self-play reinforcement learning:

1. Policy Network ($\pi(a|s) $): Replaces hand-crafted move ordering heuristics by directly predicting the probability distribution over legal actions, guiding search down high-promise branches.
2. Value Network ($v(s) $): Replaces hand-tuned Shannon linear evaluation functions ($\sum\limits_{i=1}^n w_i \cdot f_i(s)$ ) with a deep neural network that evaluates complex board positions directly from raw board representations.

This hybrid approach allows modern AI to evaluate a fraction of the nodes explored by classical engines while achieving superhuman playing strength across Chess, Shogi, and Go.

4. Module Summary & Key Concepts Review

4.1 Comparative Analysis Matrix

The table below provides a comprehensive comparison across the three core search paradigms covered in this module: Standard Minimax, Alpha-Beta Pruning, and Heuristic Depth-Limited Minimax.

Comparison Feature	Exhaustive Minimax	Alpha-Beta Pruning (Exact)	Heuristic Depth-Limited Minimax
Search Horizon	Full depth $m$ (down to terminal leaf states)	Full depth $m$ (down to terminal leaf states)	Truncated cutoff depth $d$ ($d \ll m$)
Terminal Evaluation	Exact game utility $\text{Utility}(s)$	Exact game utility $\text{Utility}(s)$	Heuristic function $\text{Eval}(s) = \overrightarrow{w}^T \cdot \overrightarrow{f}(s)$
Best-Case Time Complexity	$O(b^m)$	$O(b^{m/2}) = O((\sqrt{b})^m)$	$O(b^d)$
Worst-Case Time Complexity	$O(b^m)$	$O(b^m)$ (if moves ordered worst to best)	$O(b^d)$
Space Complexity	$O(bm)$ (active DFS recursion stack)	$O(bm)$ (active DFS recursion stack)	$O(bd)$ (active DFS recursion stack)
Decision Optimality	Guaranteed exact optimal move	Guaranteed exact optimal move (preserves Minimax)	Sub-optimal / Heuristic approximation
Key Dependency / Sensitivity	Intractable for $b^m > 10^9$	Highly dependent on move ordering heuristics	Dependent on feature quality & quiescence search
Practical Applicability	Trivial games only (e.g., Tic-Tac-Toe)	Medium games or combined with depth limits	Real-world engines (Chess, Checkers, Go)

4.2 Core Mathematical & Algorithmic Formula Summary

1. Zero-Sum Utility Property

In a two-player zero-sum game, payoffs are strictly complementary across terminal states $s$:

$$U_{\text{MAX}}(s) + U_{\text{MIN}}(s) = 0 \implies U_{\text{MIN}}(s) = -U_{\text{MAX}}(s)$$

2. Minimax Value Recursive Equation

The optimal minimax value for state $s$ is defined recursively as:

$$\text{MinimaxValue}(s) = \begin{cases} \text{Utility}(s) & \text{if } \text{Terminal}(s) = \text{True} \ \ \max\limits_{a \in \text{Actions}(s)} \text{MinimaxValue}(\text{Result}(s, a)) & \text{if } \text{Player}(s) = \text{MAX} \ \ \min\limits_{a \in \text{Actions}(s)} \text{MinimaxValue}(\text{Result}(s, a)) & \text{if } \text{Player}(s) = \text{MIN} \end{cases}$$

3. Root Optimal Move Selection

At the root state $S_0$, player $\text{MAX}$ selects the action $a^*$ maximizing the backed-up minimax utility:

$$a^* = \underset{a \in \text{Actions}(S_0)} {\mathop{MinmaxValue}}~(\text{Result}(S_0, a))$$

4. Shannon's Linear Heuristic Evaluation Model

For cutoff states at depth $d$, state evaluation estimates winning probability via weighted features:

$$\text{Eval}(s) = \sum\limits_{i=1}^{n} w_i \cdot f_i(s) = \overrightarrow{w}^T \cdot \overrightarrow{f}(s)$$

5. Alpha-Beta Pruning Cutoff Condition

Subtree elimination is triggered during DFS traversal whenever lower bound $\alpha$ meets or exceeds upper bound $\beta$: $$\alpha \ge \beta$$

• $\alpha$ (Alpha): Highest score $\text{MAX}$ is guaranteed so far along active search path (initialized to $-\infty$).
• $\beta$ (Beta): Lowest score $\text{MIN}$ is guaranteed so far along active search path (initialized to $+\infty$).

6. Summary of Time & Space Complexities

• Exhaustive Minimax: Time = $O(b^m)$, Space = $O(bm)$
• Alpha-Beta Pruning (Best Case): Time = $O(b^{m/2})$, Space = $O(bm)$ — doubles effective lookahead depth.
• Depth-Limited Minimax: Time = $O(b^d)$, Space = $O(bd)$