Adversarial Games

Tags: #◇Computer Science #◇CSINTSY #◇Adversarial Games #◇Problem Solving #◇M3

---

◇Overview

In real-world settings such as board games, agents face active opponents whose decisions aim to prevent the agent from reaching its goal. Adversarial Games model these multi-agent environments using game trees. We primarily focus on 2-Player Zero-Sum Games where one player's gain is identically balanced by the other player's loss (e.g., Chess, Tic-Tac-Toe).

Modeling the Opponent: "Dumb" Opponent: Randomly selects moves with equal probability. Stochastic Opponent: Selects moves based on a specific probability distribution. Expected values are optimized using the Expectimax algorithm. Optimally Smart Opponent: Always selects moves that minimize the agent's expected utility. Evaluated using the Minimax algorithm.

Minimax Characteristics: Complete if the game tree is finite. Optimal (against an optimal opponent). Time Complexity: $O(b^d)$ and Space Complexity: $O(b^d)$ (with Depth-First Search). Due to high branching factors ($b$), simple Minimax is often computationally infeasible.

Speeding Up Techniques:

1. Prune redundant states.
2. Depth-limited search with evaluation functions.
3. $\alpha\beta$-Pruning to ignore branches that won't affect the final decision.

◇Important Formulas

Expectimax Formulation
$V_{eval}(s) = \begin{cases} \text{Utility}(s) & \text{if IsEnd}(s) \\ \max_{a} V_{eval}(\text{Succ}(s, a)) & \text{if Player}(s) = \text{agent} \\ \sum_{a} \pi_{opp}(s, a) V_{eval}(\text{Succ}(s, a)) & \text{if Player}(s) = \text{opp} \end{cases}$

Minimax Formulation
$V_{eval}(s) = \begin{cases} \text{Utility}(s) & \text{if IsEnd}(s) \\ \max_{a} V_{eval}(\text{Succ}(s, a)) & \text{if Player}(s) = \text{agent} \\ \min_{a} V_{eval}(\text{Succ}(s, a)) & \text{if Player}(s) = \text{opp} \end{cases}$

◇Theoretical Framework: Minimax & Alpha-Beta Pruning Trees

1. Classical Minimax Value Backpropagation

2. Alpha-Beta Pruning Execution Trace

3. Pruning Condition Decision Logic

◇Worked Examples

$\alpha\beta$-Pruning Mechanics:

• $\alpha$: Best already explored option along path to the root for the maximizer (lower bound on root utility). Initialized to $-\infty$.
• $\beta$: Best already explored option along path to the root for the minimizer (upper bound on root utility). Initialized to $+\infty$.
• Cutoff Criterion: If at any time $\beta \le \alpha$, the current parent can never pick this branch because a better or equal alternative is already guaranteed elsewhere. The remaining children of the node can be pruned without affecting optimality.
• Optimal Efficiency: With perfect move ordering (evaluating best moves first), the effective branching factor is reduced to $b' = \sqrt{b}$, doubling the searchable depth in the same computational time: $O(b^{d/2})$.

◇References & Navigation

• Previous Topic: ◇Heuristics and A-Star Search
• Next Topic: ◇Machine Learning Models
• Related Notes: ◇Machine Learning, ◇State-Based Models