Summary of "Lec 10 Adversarial or Game-Playing Search"

This lecture covers the fundamentals of adversarial or game-playing search in artificial intelligence, focusing on how search algorithms adapt when there are competing agents (players) with opposing goals. It introduces the challenges, formalizes game representations, explains the Minimax Algorithm, extends the discussion to Multiplayer Games, and introduces Alpha-Beta Pruning as an optimization technique.

Main Ideas and Concepts

Adversarial Search vs. Single-Agent Search
- Unlike single-agent search, Adversarial Search involves an opponent whose moves are unpredictable.
- The presence of an opponent makes the search problem more complex because the agent must consider all possible moves of the opponent.
- The goals of the two players are completely opposite (zero-sum games).
Complexity of Game Trees
- Example: Chess has an average branching factor of 35 and about 100 moves, leading to an enormous search tree (~35^100), making exhaustive search infeasible.
- Time constraints in real games prevent full tree exploration.
Game Formulation (Using Tic Tac Toe as Example)
- Two players: Max (starts first) and Min.
- Game defined by:
  - Initial state (empty board).
  - Player to move.
  - Actions (legal moves).
  - Transition model (result of applying an action).
  - Terminal test (detecting end of game).
  - Utility function (assigns values to terminal states, e.g., +1 for Max win, -1 for Min win, 0 for draw).
- Game tree is constructed by alternating moves between Max and Min until terminal states are reached.
Minimax Algorithm
- Assumes both players play optimally.
- Values are backed up from terminal nodes to the root:
  - At Max nodes, select the maximum utility value.
  - At Min nodes, select the minimum utility value.
- The root node’s value determines the best move for Max.
- Example walkthrough with Tic Tac Toe configurations illustrating how utilities are propagated.
- Complexity:
  - Time and space complexity: O(b^m), where b is branching factor and m is depth.
- Minimax guarantees the best outcome assuming optimal play by both sides.
Extension to Multiplayer Games
- For more than two players (e.g., players A, B, C), utility values become vectors (one value per player).
- Backup involves selecting values based on the current player’s component in the utility vector.
- Alliances can form between players, affecting strategies and payoffs.
- Alliances are dynamic and can dissolve if one player becomes weak.
Alpha-Beta Pruning
- An optimization technique to reduce the number of nodes evaluated in the minimax search tree.
- Uses two parameters: alpha (best already explored option along the path to Max) and beta (best option along the path to Min).
- If a node’s value cannot influence the final decision (because a better option is already found), the subtree is pruned (not evaluated).
- The search proceeds depth-first and left-to-right.
- Pruning does not affect the final result but significantly reduces computation.
- Example illustrations show how branches are cut off when their values cannot improve the outcome.
- Further discussion on Alpha-Beta Pruning is planned for the next session.

Methodology / Instructions for Minimax Algorithm

Input: Current game state.
Process:
1. Check if the state is terminal:
  - If yes, return the utility value of the state.
2. If it is Max’s turn:
  - For each legal move:
    - Recursively call minimax on the resulting state.
  - Return the maximum value of these recursive calls.
3. If it is Min’s turn:
  - For each legal move:
    - Recursively call minimax on the resulting state.
  - Return the minimum value of these recursive calls.
Output: The best move and its minimax value.

Methodology / Instructions for Alpha-Beta Pruning

Input: Current game state, alpha, beta values.
Process:
1. Start with alpha = -∞ and beta = +∞.
2. Traverse the tree in a depth-first manner.
3. At Max nodes:
  - Update alpha with the maximum value found so far.
  - Prune (stop exploring) child nodes if alpha ≥ beta.
4. At Min nodes:
  - Update beta with the minimum value found so far.
  - Prune child nodes if beta ≤ alpha.
Output: The same minimax value but computed more efficiently.