AI in Gaming (AL-702 (A)) - Unit 5 Short Notes

UNIT 5: AI IN GAMING

I. GAME THEORY AND STRATEGIC DECISIONS

Game Theory studies mathematical models of strategic interaction among rational decision-makers. In AI, it provides frameworks for designing agents that can predict and react to opponents' actions in competitive or cooperative settings.

Minimax Algorithm

A decision rule for minimizing the maximum possible loss. Used in zero-sum games.

• Functions:

  • terminal(state): Checks if game ended.

  • utility(state): Returns numerical outcome (win/loss/draw).

  • actions(state): Returns legal moves.

  • result(state, action): Returns new state after action.

  • min_value(state) / max_value(state): Recursive functions alternating between minimizing and maximizing player.

[!TIP] Minimax assumes opponent plays optimally. In practice, use alpha-beta pruning to reduce search space.

Payoff Matrices & Equilibrium

Payoff Matrix: Tabular representation of outcomes for each strategy pair.

Pure Strategy Nash Equilibrium: No player can gain by unilaterally changing strategy.

• Solving: Find cells where row player's payoff is max in its column AND column player's payoff is min in its row (for zero-sum).

Mixed Strategy Equilibrium: Players randomize over strategies.

• Example: Penalty Kicks

  Given payoff matrix (Kicker's success probability):

  | Kicker\Goalie | Left | Right | |--------------|------|-------| | Left | 1.4 | 1.5 | | Right | 1.7 | 1.5 |

  Let kicker play Left with probability $p$, Goalie play Left with $q$.

  Kicker's expected payoff if Goalie plays Left: $1.4p + 1.7(1-p)$

  If Goalie plays Right: $$\displaystyle 1.5p + 1.5(1-p) = 1.5 $$

  For indifference: $$\displaystyle 1.4p + 1.7(1-p) = 1.5 $$

  $$\displaystyle \Rightarrow 1.4p + 1.7 - 1.7p = 1.5 $$

  $$\displaystyle \Rightarrow -0.3p = -0.2 $$

  $$\displaystyle \Rightarrow p = \frac{2}{3} $$

  Similarly, solve for $q$ using Goalie's payoffs (minimize kicker's success).

  \boxed{p = \frac{2}{3},\ q = \frac{1}{3}}

Board Game Theory

Applies minimax/alpha-beta to deterministic, perfect-information games (chess, checkers). Key: evaluation function for non-terminal states.

II. SEARCH ALGORITHMS AND PATHFINDING

Breadth-First Search (BFS)

• Explores all nodes at current depth before moving deeper.

• Uses queue (FIFO).

• Guarantees shortest path in unweighted graphs.

• Time/Space Complexity: $$\displaystyle O(b^d) $$, where $b$ = branching factor, $d$ = depth.

[!TIP] BFS is memory-intensive for large maps. Use bidirectional BFS to reduce.

A* Search Algorithm

• Best-first search using heuristic: $$\displaystyle f(n) = g(n) + h(n) $$

  • $g(n)$: actual cost from start.

  • $h(n)$: admissible heuristic (never overestimates true cost, e.g., Manhattan distance for grid).

• Optimal if $h(n)$ is admissible and consistent.

• Complexity: Depends on heuristic quality; worst-case $$\displaystyle O(b^d) $$.

Example: Grid pathfinding with obstacles.
$$\displaystyle h(n) = |x_{goal} - x_n| + |y_{goal} - y_n| $$ (Manhattan).

Efficiency in Complex Problems

• Heuristic Design: Domain-specific knowledge improves efficiency.

• Complexity Trade-off: Memory vs. time. A* often faster than BFS but stores more nodes.

• Machine Learning in Pathfinding: Learn heuristics from data (e.g., neural networks predict $h(n)$).

III. GAME AI ARCHITECTURES

Rule-Based Systems

• IF (condition) THEN (action) rules.

• Example: IF enemy_visible AND health > 50% THEN attack.

• Simple but brittle; hard to scale.

Finite State Machines (FSMs)

• States (e.g., Guard, Fight, Flee) and transitions triggered by events/conditions.

• Construction:

  1. Define states.

  2. Define events/conditions.

  3. Specify transitions and actions on entry/exit.

Example: Guard AI

States: Guard, Fight, Flee

Transitions:

• Guard → Fight if see_thief AND thief_strength <= self_strength

• Guard → Flee if see_thief AND thief_strength > self_strength

• Fight → Flee if health < 30%

• Flee → Guard if thief_lost

[!TIP] FSMs suffer from state explosion for complex behaviors.

Behavior Trees

• Hierarchical nodes: Sequence, Selector, Condition, Action.

• Comparison with FSMs:

  | Feature | FSM | Behavior Tree | |---------|-----|---------------| | Structure | Flat/state-based | Hierarchical | | Reusability | Low | High (subtrees) | | Debugging | Hard (many states) | Easier (tree traversal) | | Extensibility | Poor | Good |

3D Representations

• Static: Position only $(x,y,z)$.

• Kinematic: Position + velocity/acceleration $$\displaystyle (x,y,z,v_x,v_y,v_z) $$ for smoother motion.

Fuzzy Systems & Markov Chains

• Fuzzy Logic: Degrees of truth (e.g., "health is low" = 0.7). Handles imprecise inputs.

• Markov Chains: State transitions with probabilities. Used for probabilistic behavior (e.g., wandering).

IV. MACHINE LEARNING FOR GAME AI

Decision Trees

• Recursive Induction: Split data on attribute that maximizes information gain.

  1. If all samples same class → leaf.

  2. If no attributes left → majority class leaf.

  3. Else, choose best attribute, split, recurse.

Entropy & Information Gain

Entropy (impurity): $$\displaystyle H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i $$

Information Gain: $$\displaystyle IG(S,A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v) $$

Calculation with Dataset:

1. Overall Entropy:

   • Yes: 3/7, No: 4/7

   • $$\displaystyle H(S) = -\left(\frac{3}{7}\log_2\frac{3}{7} + \frac{4}{7}\log_2\frac{4}{7}\right) \approx 0.985 $$

2. For "Credit Score":

   • High: [Yes, Yes, No] → 2 Yes, 1 No → $$\displaystyle H = -\left(\frac{2}{3}\log_2\frac{2}{3} + \frac{1}{3}\log_2\frac{1}{3}\right) \approx 0.918 $$

   • Medium: [No, Yes] → 1 Yes, 1 No → $$\displaystyle H = 1.0 $$

   • Low: [No, No] → 0 Yes, 2 No → $$\displaystyle H = 0 $$

   • Weighted Avg: $$\displaystyle \frac{3}{7} \times 0.918 + \frac{2}{7} \times 1.0 + \frac{2}{7} \times 0 \approx 0.683 $$

   • $$\displaystyle IG = 0.985 - 0.683 = 0.302 $$

3. Similarly for other attributes. Choose attribute with highest IG.

[!TIP] Entropy is base-2 by default. Ensure logs computed correctly.

Handling Noisy Data

• Pruning: Remove branches with low statistical significance (pre-pruning: stop early; post-pruning: grow full tree then trim).

• Ensemble Methods: Combine multiple trees (e.g., Random Forest) to reduce variance.

• Smoothing: Laplace correction for small samples.

Ensemble Methods

• Random Forest:

  1. Bootstrap sample (with replacement).

  2. Grow tree using random subset of features at each split.

  3. Aggregate predictions (majority vote for classification, average for regression).

• Bagging vs Boosting:

  | | Bagging | Boosting | |---|---------|----------| | Goal | Reduce variance | Reduce bias | | Sampling | Bootstrap | Weighted (misclassified get higher weight) | | Examples | Random Forest | AdaBoost, Gradient Boosting | | Parallel? | Yes | No (sequential) |

• Ensemble Robustness: Averages out errors, less prone to overfitting than single complex models.

Neural Networks: MLP

• Architecture: Input layer → Hidden layer(s) → Output layer.

• Learning: Backpropagation:

  1. Forward pass: compute output.

  2. Calculate loss (e.g., MSE).

  3. Backward pass: compute gradients via chain rule.

  4. Update weights: $$\displaystyle w_{ij} \leftarrow w_{ij} - \eta \frac{\partial L}{\partial w_{ij}} $$.

Gradient Descent Variants

• Batch GD: Use entire dataset per update (stable but slow).

• Mini-Batch GD: Use small random subset (common in practice).

• Delta Rule: For single-layer perceptron: $$\displaystyle \Delta w = \eta (t - y) x $$, where $t$ = target, $y$ = output.

Evaluation & Optimization

• Overfitting: Model fits noise. Solutions: regularization (L1/L2), cross-validation, pruning.

• Underfitting: Model too simple. Solutions: more features, complex model.

• Metrics:

  • Precision = $$\displaystyle \frac{TP}{TP+FP} $$ (accuracy of positive predictions).

  • Recall = $$\displaystyle \frac{TP}{TP+FN} $$ (coverage of actual positives).

• Holdout Method: Split data into train/validation/test sets.

Learning Paradigms

• Lazy Learning: No model building until query (e.g., k-NN). Fast training, slow prediction.

• Eager Learning: Build model upfront (e.g., decision trees). Slow training, fast prediction.

• Well-Posed Learning Problem: (1) Task defined, (2) Performance measure, (3) Experience source.

Data Preparation

• Description: Summarize statistics, distributions, missing values.

• Preparation: Cleaning (handle missing/noisy), transformation (normalization), feature selection.

Least Squares Methods

• Least Squared Error Hypothesis: Find parameters $\theta$ minimizing $$\displaystyle \sum_{i=1}^{n} (y_i - f(x_i;\theta))^2 $$.

• For linear regression: $$\displaystyle \theta = (X^TX)^{-1}X^Ty $$ (closed-form).

V. REINFORCEMENT LEARNING FOR GAMES

Fundamentals

• Agent interacts with environment in discrete steps.

• State $s$, Action $a$, Reward $r$.

• Policy $\pi(a|s)$: probability of action in state.

• Value Function: $$\displaystyle V^\pi(s) = \mathbb{E}[\sum_{t=0}^{\infty} \gamma^t r_t | s_0=s, \pi] $$

• Bellman Equation: $$\displaystyle V^\pi(s) = \sum_a \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^\pi(s') \right] $$

Temporal Difference (TD) vs Monte Carlo (MC)

• TD: Updates based on estimated value (bootstrapping). $$\displaystyle V(s_t) \leftarrow V(s_t) + \alpha [r_{t+1} + \gamma V(s_{t+1}) - V(s_t)] $$. Works online, no need episode completion.

• MC: Updates after full episode using actual return. $$\displaystyle V(s_t) \leftarrow V(s_t) + \alpha [G_t - V(s_t)] $$. Unbiased but high variance.

Model-Free Methods

• Q-Learning (off-policy):

  $$\displaystyle Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma \max_{a'} Q(s',a') - Q(s,a)] $$

  Learns optimal policy independent of behavior policy.

• SARSA (on-policy):

  $$\displaystyle Q(s,a) \leftarrow Q(s,a) + \alpha [r + \gamma Q(s',a') - Q(s,a)] $$, where $a'$ is action actually taken.

  More conservative, follows current policy.

[!TIP] Q-Learning can overestimate Q-values in noisy environments; SARSA is safer.

Policy-Based Methods

• Policy Gradient: Directly optimize policy parameters $\theta$ by gradient ascent on expected return: $$\displaystyle \nabla J(\theta) = \mathbb{E}_{\pi}[\nabla \log \pi(a|s) \cdot Q^{\pi}(s,a)] $$.

• REINFORCE: Monte Carlo policy gradient.

Dynamic Programming Approaches

• Value Iteration: Iteratively apply Bellman update until convergence: $$\displaystyle V_{k+1}(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_k(s') \right] $$. Then derive greedy policy.

• Policy Iteration: Alternate between (1) policy evaluation (solve $$\displaystyle V^\pi $$ exactly) and (2) policy improvement (make policy greedy w.r.t. $$\displaystyle V^\pi $$). Converges faster but evaluation step costly.

Advanced Topics

• Generative Adversarial Imitation Learning (GAIL):

  • Discriminator distinguishes expert vs agent trajectories.

  • Agent policy updated to fool discriminator (like GANs but for IL).

  • Difference from standard RL: RL optimizes reward; GAIL optimizes to match expert demonstrations without explicit reward.

• Recent Trends in RL Architectures:

  • Deep RL (DQN, PPO, SAC).

  • Multi-agent RL (independent learners, centralized training).

  • Hierarchical RL (options, skills).

  • Meta-RL (learning to learn).

Probabilistic Methods

• Probabilistic Modeling: Use Bayesian networks, MDPs with uncertain transitions.

• Inference: Compute posterior over states/actions given observations (e.g., POMDPs).

VI. ADVANCED ALGORITHMIC CONCEPTS

Divide and Conquer

• Steps: (1) Divide problem into subproblems, (2) Conquer recursively, (3) Combine solutions.

• Example: Merge sort: split array, sort halves, merge.

• Complexity: Often $O(n \log n)$.

Algorithm Analysis

• Characteristics: Input, output, definiteness, finiteness, effectiveness.

• Tools:

  • Time Complexity: Asymptotic notation (Big O, Ω, Θ). Count basic operations.

  • Space Complexity: Extra memory used.

  • Amortized Analysis: Average cost over sequence of operations.

Specialized Algorithms

• Stable Marriages (Gale-Shapley):

  • Input: $n$ men, $n$ women, each with preference list.

  • Output: Stable matching (no blocking pairs).

  • Algorithm: Men propose to women in preference order; women hold best proposal and reject others. Repeat until all matched.

  • Complexity: $$\displaystyle O(n^2) $$.

  • Application in ML: Matchmaking in online platforms, resource allocation.

[!TIP] Stable marriage is men-optimal/women-pessimal if men propose. Reversing roles gives opposite.