04_Adversarial_Games

Tags: #◇CSINTSY #◇Computational Thinking #◇Computer Science #◇Artificial Intelligence #◇Machine Learning #◇Intelligent Systems #◇Probability #◇Data Analysis

---

◇Overview

Adversarial Games involve environments with multiple agents where the agents have conflicting goals. These are typically modeled as Zero-Sum Games.

◇Details / Theory

4. Adversarial Games Reviewer

◇Overview

Adversarial Games involve environments with multiple agents where the agents have conflicting goals. These are typically modeled as Zero-Sum Games.

◇Key Concepts

Zero-Sum Game

Definition: A game where one player's gain is exactly equal to the other player's loss. The total utility sum is constant (usually 0). Example: Chess, Tic-Tac-Toe. If Player A wins (+1), Player B loses (-1). Sum = 0.

Players

MAX: The agent we control. Tries to maximize the utility value. MIN: The opponent. Tries to minimize the utility value (which is bad for MAX).

Game Tree

A tree where nodes are game states and edges are moves. Layers alternate between MAX and MIN turns. Terminal State: A state where the game ends (win, lose, draw). Utility Function: Assigns a numeric value to terminal states (e.g., +1 for Win, -1 for Loss, 0 for Draw).

◇Algorithms

1. Minimax Algorithm

Strategy: A recursive algorithm to determine the optimal move for MAX, assuming MIN also plays optimally. Process:

1. Generate the game tree down to terminal states (or a depth limit).
2. Calculate utility values for terminal states.
3. Backpropagate values up the tree:
   At a MAX node: Choose the child with the maximum value.
   At a MIN node: Choose the child with the minimum value.
4. The value at the root is the Minimax value of the game. Complexity:
   Time: $O(b^m)$ (Exponential) - where $b$ is branching factor, $m$ is max depth.
   Space: $O(bm)$ (Linear) - Depth-first exploration.

2. Alpha-Beta Pruning

Goal: Optimize Minimax by cutting off (pruning) branches that do not need to be explored because they cannot influence the final decision. Parameters:
$\alpha$ (Alpha): The best (highest) value found so far for MAX along the path. Initialized to $-\infty$.
$\beta$ (Beta): The best (lowest) value found so far for MIN along the path. Initialized to $+\infty$. Pruning Rule:
If $\alpha \ge \beta$, prune the remaining children of the current node.
Reason: The current node (say, MIN) has found a move that is worse for MAX than a move MAX has already found elsewhere ($\alpha$). So MAX will never choose the path to this node. Updates:
MAX Node: Updates $\alpha = \max(\alpha, \text{value})$.
MIN Node: Updates $\beta = \min(\beta, \text{value})$.

Example of Pruning

Consider a MAX node with current $\alpha=3$. It has a child MIN node.
The MIN node explores its first child and gets a value of 2.
Now, the MIN node's value will be $\le 2$.
Since $\alpha=3$ (MAX already has a move worth 3 elsewhere) and the current branch is worth at most 2, MAX will never choose this branch.
So, we stop exploring the other children of this MIN node. Pruned!

◇Solved Example: Minimax with Alpha-Beta Pruning

Tree Structure:
Root (MAX) has children B (MIN) and C (MIN). B (MIN) has children D (3) and E (5). C (MIN) has children F (2) and G (9).

Goal: Find the value of Root and show pruning.

Step-by-Step Execution:

1. Initialize: Root has $\alpha = -\infty, \beta = +\infty$.
2. Visit B (MIN): Pass $\alpha = -\infty, \beta = +\infty$.
   Visit D: Value is 3.
   Update B: B is MIN, so it wants minimum. Current best for B is 3.
   Update Beta at B: $\beta = \min(+\infty, 3) = 3$.
   Check Pruning: Is $\alpha \ge \beta$? ($-\infty \ge 3$?) No. Continue.
   Visit E: Value is 5.
   Update B: $\min(3, 5) = 3$.
   Return 3 to Root.
3. Back at Root (MAX):
   Root gets 3 from B.
   Update Root: MAX wants maximum. Current best is 3.
   Update Alpha at Root: $\alpha = \max(-\infty, 3) = 3$.
4. Visit C (MIN): Pass $\alpha = 3, \beta = +\infty$.
   Visit F: Value is 2.
   Update C: C is MIN. Current best for C is 2.
   Update Beta at C: $\beta = \min(+\infty, 2) = 2$.
   Check Pruning: Is $\alpha \ge \beta$? ($3 \ge 2$?) YES!
   PRUNE: We do not visit G.
   Reason: C is guaranteed to be $\le 2$. Root (MAX) already has a move (to B) worth 3. MAX will never choose C (value $\le 2$) over B (value 3). So we stop looking at C's other children.
   Return 2 (or $\le 2$) to Root.
5. Back at Root (MAX):
   Root compares current best (3) with C's value (2). $\max(3, 2) = 3$.
   Final Value: 3.
   Optimal Move: Go to B.

---

---

◇Common Pitfalls

Confusing MAX (maximizing) and MIN (minimizing) levels in the game tree. Pruning incorrectly — $\alpha$ is the best already explored for MAX, $\beta$ for MIN; prune when $\alpha \ge \beta$. Forgetting that Alpha-Beta pruning gives the same result as Minimax — it only saves computation, not changes the answer.

◇Summary

TL;DR — Minimax evaluates game trees by alternating MAX/MIN layers. Alpha-Beta pruning eliminates branches that cannot affect the final decision ($\alpha \ge \beta$ cutoff), reducing computation while preserving the optimal Minimax value.

◇Links

Related: Source / Reference:

---

Made by 2ru17

Please contact me through discord or my the university email for any problems regarding the reviewer. Thanks!

◇References & Navigation

• Previous Topic: ◇Informed Search
• Next Topic: ◇Machine Learning
• Related Notes: ◇Adversarial Games