University Notes: Adversarial Search and Planning

Definition: Searching in situations where other agents or entities are outside our control.
- Worst-Case Assumption: We model other agents as opponents (adversaries) to ensure the system can handle the worst-case scenario.
Game Trees: An abstract representation of games (like Chess or Tic-Tac-Toe).
- Nodes: Represented by Squares (Agent's move) and Circles (Opponent's move).
- Root Node: The starting position of the game.
- Terminal/Leaf Nodes: The end of the game, evaluated with a result (e.g., $1$ for a win, $-1$ for a loss, $0$ for a draw).

Concept: Determines the optimal move by assuming the opponent plays perfectly. It alternates between maximizing the agent's reward and minimizing the agent's reward (from the opponent's perspective).
Process:
1. Create the entire Game Tree from the initial state to the terminal nodes (Brute Force).
2. Evaluate the terminal states (win/loss/draw).
3. Inherit values upward through the tree:
  - If the node is a Maximizer (Square), take the maximum value among its children.
  - If the node is a Minimizer (Circle), take the minimum value among its children.
4. Stop when the root node is evaluated. The result identifies the best move for the starting agent.
Non-Binary Outcomes: Minimax also works for games with numerical scores. The logic remains the same (selecting the minimum or maximum integer value).

Tic-Tac-Toe: $5,477$ possible states. It is a simple game that can be solved completely by Minimax.
Connect Four: $4.5 \times 10^{12}$ (4.5 trillion) states. Solved in 1988; the first player can guarantee a win with perfect play.
Checkers (Draughts): Approximately $5 \times 10^{20}$ states. Solved in 2007 after 18 years of computation. Perfect play leads to a draw.
Chess: State space is between $10^{11}$ and $10^{23}$ . Brute forcing the entire tree is impossible. Deep Blue (1997) was a major milestone beat Gary Kasparov.
Go: Approximately $10^{170}$ states. Traditional heuristics used for chess do not work well. DeepMind's AlphaGo used deep learning to conquer this.

Depth-Limited Search: Because full trees are too large, agents generate trees for a specific number of moves (depth) and then stop.
Evaluation Function: In place of terminal nodes (where the winner is known), a heuristic evaluates the "quality" of the current state.
Chess Heuristics Example: Assigning values to pieces:
- Queen: $9$
- Rook: $5$
- Bishop: $3$
- Knight: $3$
- Pawn: $1$
A simple heuristic calculation: $\text{Total Value of My Pieces} - \text{Total Value of Opponent's Pieces}$ .

Agnosticism: MCTS works without pre-existing domain knowledge (no predefined heuristics).
Process: Evaluates states based on the win rate from random playouts (simulations).
Random Playouts: From a child state, the agent plays the game randomly thousands of times and records the percentage of wins. High win rates suggest a strong starting move.
Selection Balance (UCT):
- Exploitation: Focusing on moves that are already known to perform well.
- Exploration: Trying moves that haven't been tested much to see if they might be better.
UCB1 Formula (Upper Confidence Bound): UCB1 = \bar{X}_j + C \times \root \frac{\text{ln}(N)}{n_j}
- $\bar{X}_j$ : Average reward/result of node $j$ .
- $C$ : Exploration constant (determines how often to try "worse" things).
- $N$ : Total visits to the parent node.
- $n_j$ : Visits to node $j$ .
Phases of MCTS:
1. Selection: Navigate the tree to a leaf node using UCB1.
2. Expansion: Create a new child node.
3. Simulation: Run a random playout from the new node until a terminal state.
4. Backpropagation: Update all nodes in the path with the result of the playout.

Deterministic vs. Stochastic: Search problems assume deterministic outcomes (Action A always leads to State B). Planning accounts for randomness (stochasticity) where actions have probabilistic outcomes.
Markov Decision Process Components:
- States ( $S$ ): A set of all possible situations.
- Actions ( $A$ ): Possible moves available in a state.
- Costs/Rewards ( $c$ ): The time, money, or penalty associated with an action.
- Transition Probabilities ( $P(s'|s, a)$ ): The probability of ending up in state $s'$ given state $s$ and action $a$ .
Policy ( $π$ ): A strategy that maps every state to a specific action. The goal is to find an optimal policy that minimizes the expected average cost.

Goal: To find the lowest expected average cost to reach a goal state.
Step-by-Step:
1. Initialize Value ( $V$ ): Set the goal state to $0$ and all other states to an arbitrarily large number (e.g., $100$ or $1,000,000$ ).
2. Update Rule: For each state, find the outcome of every possible action and choose the minimum: $V(s) \rightarrow \text{min}_{a} \text{ } \textstyle ∑_{s'} P(s'|s, a) [c(s, a, s') + V(s')]$
3. Repeat: Iterate through all states multiple times until the values converge (stop changing).

Commute to Work Scenario:
- Options: Car (walking to car: $1\text{ min}$ ), Train (walking to station: $2\text{ min}$ ), or Bike ( $45\text{ min}$ total).
- Chance Nodes:
  - Car: No traffic (20\text{%}, $t+20$ ), Medium (70\text{%}, $t+30$ ), Heavy (10\text{%}, $t+70$ ).
  - Train: Train there (90\text{%}, $t+35$ ), No train (10\text{%}, wait in room for $3\text{ min}$ ).
- Result: Through Value Iteration, we find the expected time for the Car is $33\text{ min}$ , Train is $37\text{ min}$ , and Bike is a guaranteed $45\text{ min}$ . The Car is the optimal policy.
Dice Gamble Game:
- Stay: Receive $\$4$ and roll a dice. If 1 or 2, game ends. If 3, 4, 5, or 6, repeat round.
- Quit: Receive $\$10$ and end immediately.
- Expected Value: "Stay" policy results in an average of $\$12$ (which can be modeled as a cost of $-12$ ), making "Stay" the better long-term policy.