UNIT 3: AI IN GAMING – SHORT NOTES

I. FOUNDATIONS OF GAME AI

Models and Architectures of Game AI

A Game AI system orchestrates non-player character (NPC) behavior and game dynamics. A typical layered architecture includes:

1. Decision Layer: High-level goals and strategies (e.g., using behavior trees or planners).

2. Navigation Layer: Pathfinding and movement (e.g., A* on a navigation mesh).

3. Animation & Physics Layer: Executes movements and interactions.

4. Perception Layer: Simulates senses (vision, hearing) for the AI.

[!TIP] Exam Focus: Be prepared to draw/describe a generic Game AI architecture diagram, labeling these core components.

Applications of AI in Gaming

II. GAME THEORY AND STRATEGIC DECISION-MAKING

Fundamentals of Game Theory

• Players: Decision-makers (e.g., two opposing chess players).

• Strategies: Complete plan of action for a player.

• Payoffs: Numerical reward received by a player for a strategy profile.

• Zero-Sum Game: One player's gain is exactly the other's loss (e.g., chess). Total payoff = 0.

• Non-Zero-Sum Game: Gains/losses are not necessarily balanced (e.g., prisoner's dilemma).

[!TIP] Common Pitfall: Not all competitive games are zero-sum. Cooperative games are non-zero-sum.

Payoff Matrices and Solution Concepts

Normal-Form Game: Represented by a payoff matrix.

• Dominant Strategy: A strategy that yields a higher payoff regardless of the opponent's choice.

• Saddle Point (Pure Strategy Equilibrium): Entry that is the minimum in its row and maximum in its column. Value of the game.

• Nash Equilibrium (NE): A profile of strategies where no player can unilaterally deviate to improve their payoff. Can be pure (specific strategies) or mixed (probability distribution over strategies).

Example: Penalty Kick (from Nov 2023 paper)

• No pure NE: For Kicker, best response to Goalie Left is Right (1.7 > 1.4). For Goalie, best response to Kicker Right is Right (0.4 > 0.5? Wait, 0.5 > 0.4, so Goalie's best to Right is Left). Check all.

• Mixed NE: Solve for probabilities where each player is indifferent. Let Kicker play Left with probability p.

  • Goalie's expected payoff for choosing Left: 0.6p + 0.4(1-p) = 0.4 + 0.2p

  • Goalie's expected payoff for choosing Right: 0.5p + 0.4(1-p) = 0.4 + 0.1p

  • Indifference: 0.4 + 0.2p = 0.4 + 0.1p => p = 0. This suggests a corner solution. Re-evaluate payoffs: Kicker's success rates? Usually, payoffs are success probabilities. Let's assume payoffs are Kicker's success probability, Goalie's save probability.

  • Correct indifference for Goalie: 0.6p + 0.4(1-p) = 0.5p + 0.4(1-p) => 0.6p = 0.5p => p=0. So Kicker always kicks Right? But then Goalie should always go Right? Check: If Kicker always Right, Goalie's payoff: Left=0.4, Right=0.4. Indifferent. So (Right, any mix) is NE? Not stable. Need proper calculation. For exam, show setting up indifference equations.

Board Game Theory

• Perfect Information Games: All players know the complete state (e.g., chess, checkers). Solved using search trees (Minimax).

• Imperfect Information Games: Players have private information (e.g., poker). Requires opponent modeling and belief states.

III. SEARCH ALGORITHMS FOR GAME PLAYING AND PATHFINDING

Breadth-First Search (BFS)

• Algorithm: Explores all nodes at current depth before moving deeper. Uses a FIFO queue.

• Properties: Complete (finds solution if exists), Optimal for uniform-cost graphs.

• Example (Grid Pathfinding): Start at S. Expand all neighbors (N, S, E, W) in queue order. Mark visited to avoid cycles.

A* Search Algorithm

• Cost Function: f(n) = g(n) + h(n)

  • g(n): Actual cost from start to node n.

  • h(n): Heuristic estimate from n to goal.

• Heuristic Properties:

  • Admissible: Never overestimates true cost (h(n) ≤ h*(n)).

  • Consistent (Monotonic): For every node n and successor n', h(n) ≤ c(n,n') + h(n'). Guarantees optimality with graph search.

• Advantages: More efficient than BFS/Dijkstra by guiding search. Optimal if h is admissible.

• Example: Grid with Manhattan distance h(n) = |x_goal - x_n| + |y_goal - y_n| (admissible for 4-way movement).

[!TIP] Key Distinction: g(n) is actual cost so far; h(n) is estimated remaining cost. f(n) is estimated total cost.

Minimax Algorithm

• Core Idea: For two-player, zero-sum, perfect-information games. Assumes opponent plays optimally.

• Game Tree: Nodes = game states, Edges = moves. Alternating MAX (AI) and MIN (opponent) layers.

• Functions:

  
  def minimax(state, depth, maximizingPlayer):
  
      if depth == 0 or state.is_terminal():
  
          return evaluate(state)  # Heuristic evaluation function
  
      if maximizingPlayer:
  
          maxEval = -∞
  
          for child in state.get_children():
  
              eval = minimax(child, depth-1, False)
  
              maxEval = max(maxEval, eval)
  
          return maxEval
  
      else:  # minimizing player
  
          minEval = +∞
  
          for child in state.get_children():
  
              eval = minimax(child, depth-1, True)
  
              minEval = min(minEval, eval)
  
          return minEval
  
  

• Limitations: Exponential complexity O(b^d) (branching factor b, depth d). Requires depth-limited search with a cutoff and evaluation function for non-terminal states.

Heuristics and Problem Complexity

• Heuristic Design: A strong heuristic dramatically prunes the search space. Admissibility vs. informedness trade-off.

• Complexity: Game tree size grows astronomically (e.g., chess ~35^100). Techniques like alpha-beta pruning (cuts branches that cannot affect final decision) are essential.

IV. BEHAVIOR MODELING AND STATE MACHINES

Finite State Machines (FSMs)

• Components:

  • States: Distinct behaviors (e.g., Patrol, Chase, Attack, Flee).

  • Transitions: Conditions triggering state change (events).

  • Actions: Operations executed upon entering, in, or exiting a state.

• Example: Guard-Thief FSM (from Nov 2023 paper)

  DiagramCANVAS: FSM with states: Guard, Fight, Flee, Escape. Transitions: "See Thief" (Guard->Fight), "Thief Strong?" (Fight->Flee), "Losing?" (Fight->Flee), "Escaped" (Flee->Guard).

• Advantages: Simple, intuitive, easy to debug.

• Limitations: Combinatorial explosion with many states/conditions. Poor for complex, reactive behaviors.

Behavior Trees

• Node Types:

  • Selector (?): Tries children in order until one succeeds.

  • Sequence (→): Executes children sequentially; fails if any child fails.

  • Leaf: Condition (checks world state) or Action (executes behavior).

• Comparison with FSMs:

  | Feature | FSM | Behavior Tree | | :--- | :--- | :--- | | Structure | Graph of states | Tree of tasks | | Modularity | Low (transitions scattered) | High (encapsulated subtrees) | | Readability | Complex for many states | High, hierarchical | | Reactivity | Requires explicit transitions | Inherent (re-evaluates from root each tick) |

• Example (Combat): Selector: [Is Health Low? → Flee Sequence, Has Ammo? → Attack Sequence, Reload].

Rule-Based Systems

• Structure:

  1. Rule Base (Knowledge Base): IF <condition> THEN <action>.

  2. Inference Engine: Matches rules against Working Memory (facts), resolves conflicts.

  3. Working Memory: Current set of known facts/assertions.

• Example: NPC decision-making:

  
  IF (player_in_sight) AND (player_armed) AND (health_low) THEN state = Flee
  
  IF (player_in_sight) AND (player_unarmed) THEN state = Attack
  
  

• Challenges: Conflict resolution (which rule fires first?), rule prioritization, knowledge acquisition bottleneck.

V. MOVEMENT, ANIMATION, AND COORDINATION

3D Representations

Components of Coordinated Movement

1. Path Planning: High-level route (A* on navmesh).

2. Obstacle Avoidance: Local, reactive adjustments (steering behaviors).

3. Steering Behaviors: Forces applied to achieve movement goals (e.g., seek, flee, arrive, obstacle avoidance).

4. Animation Blending: Smoothly transitioning between motion clips.

Movement Algorithm Flow: Goal → Path Plan → Steering Forces → Physics/Animation Execution.

Stages of Motor Learning (for AI Skill Acquisition)

1. Cognitive Stage: AI explores actions, high error/variance.

2. Associative Stage: Refines policy, error decreases.

3. Autonomous Stage: Policy stabilizes, efficient execution.

• Application: RL agents progressing from random exploration to skilled play.

VI. MACHINE LEARNING FOR GAME AI

A. DECISION TREES

Entropy and Information Gain

• Entropy (H): Measure of impurity/uncertainty in a set S.

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

where `p_i` is proportion of class `i` in `S`, `c` is number of classes.

• Information Gain (IG): Reduction in entropy after splitting on attribute A.

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

where `S_v` is subset of `S` where `A` has value `v`.

Worked Example (Credit Score Dataset from Dec 2025 paper):

1. Overall Entropy H(S):

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

   • H(S) = - (3/7 log₂(3/7) + 4/7 log₂(4/7)) ≈ 0.985

2. IG for "Credit Score":

   • S_High (Samples 1,4,7): Yes=2, No=1 → H= - (2/3 log₂(2/3) + 1/3 log₂(1/3)) ≈ 0.918

   • S_Medium (2,5): Yes=1, No=1 → H= 1.0

   • S_Low (3,6): Yes=0, No=2 → H= 0.0

   • IG = 0.985 - [ (3/7)*0.918 + (2/7)*1.0 + (2/7)*0.0 ] ≈ 0.985 - 0.689 = 0.296

Recursive Induction (ID3/C4.5)

• Top-Down, Greedy: At each node, select attribute with highest IG (or gain ratio) to split.

• Stopping Criteria: All instances same class, no attributes left, or minimum samples.

• Pruning: Remove branches that may overfit (e.g., reduced-error pruning).

Handling Noisy Data

• Effect: Noise causes overfitting (tree learns exceptions).

• Strategies:

  1. Pruning: Remove unreliable branches (pre or post-pruning).

  2. Ensemble Methods: Random Forest (averaging reduces variance).

  3. Smoothing: Assign probabilities based on parent node.

Decision Trees in Game Development

• NPC Decision-Making: Simple, interpretable rules for behavior selection.

• Content Classification: Categorizing player-generated content.

• Player Behavior Analysis: Predicting player actions or churn.

B. ENSEMBLE METHODS

Bagging vs Boosting

Random Forest Algorithm

1. For t = 1 to T (number of trees):

   • Draw bootstrap sample D_t from training data D.

   • Grow decision tree on D_t: At each split, select best split from random subset of features (not all features).

2. Prediction: Majority vote (classification) or average (regression).

3. Out-of-Bag (OOB) Error: Estimate using samples not in bootstrap (~37%) as validation.

Robustness of Ensembles

• Why Better? Combines diverse, weak learners. Variance reduction via averaging. Errors of individual models often uncorrelated, so they cancel out.

• Game AI Use: Ensemble of policies (e.g., multiple decision trees for NPC combat style) yields more robust, adaptable behavior than a single complex model.

C. NEURAL NETWORKS (Multi-Layer Perceptron - MLP)

• Architecture: Input Layer → [Hidden Layer(s)] → Output Layer. Fully connected.

• Activation Functions: ReLU, Sigmoid, Tanh (introduce non-linearity).

• Learning Process:

  1. Forward Propagation: Compute output ŷ = f(W·x + b).

  2. Loss Calculation: L(y, ŷ) (e.g., Cross-Entropy, MSE).

  3. Backpropagation: Compute gradient ∇L w.r.t. weights via chain rule.

  4. Weight Update: W ← W - η ∇L (η = learning rate).

• Game AI Application: Function approximation in Deep RL (e.g., DQN uses MLP to approximate Q-values from raw pixels).

D. REGRESSION TECHNIQUES (Least Squares)

• Linear Regression (Ordinary Least Squares - OLS): Find coefficients β that minimize Residual Sum of Squares (RSS).

$$\text{RSS} = \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 = \sum_{i=1}^{n} (y_i - \beta_0 - \beta_1 x_{i1} - ...)^2$$

• Solution (Closed-form):

$$\hat{\beta} = (X^T X)^{-1} X^T y$$

• Game AI Use: Predictive modeling for game parameters (e.g., predicting match duration, player score based on features).

VII. REINFORCEMENT LEARNING FOR GAMES

A. FUNDAMENTALS

Bellman Equations

• Bellman Expectation Equation (State-Value):

$$v_\pi(s) = \mathbb{E}_\pi [R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]$$

• Bellman Expectation Equation (Action-Value):

$$q_\pi(s,a) = \mathbb{E}_\pi [R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]$$

• Bellman Optimality Equation (for v* and q*): Replaces expectation with max over actions.

$$q_*(s,a) = \mathbb{E} [R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') | S_t=s, A_t=a]$$

• Role: Recursive definitions of optimal value functions. Foundation for DP, TD, and control algorithms.

Value Iteration vs Policy Iteration (Dynamic Programming)

Temporal Difference (TD) Learning vs Monte Carlo (MC)

| Data | Online, after every step (can learn from incomplete episodes). | Episodic, waits until end of episode.

| Bias-Variance | Bias (from current estimate), Low Variance. | Unbiased, High Variance (depends on full trajectory).

| Example | TD(0): V(S_t) ← V(S_t) + α [R_{t+1} + γ V(S_{t+1}) - V(S_t)] | First-Visit MC: V(s) ← average of all returns from first visit to s. |

B. MODEL-FREE ALGORITHMS

Q-Learning (Off-Policy)

• Update Rule:

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

• Behavior: Learns optimal policy π* independent of exploration policy (e.g., ε-greedy). "Optimistic" about next state.

• Exploration-Exploitation: ε-greedy: with probability ε choose random action, else argmax_a Q(s,a).

SARSA (On-Policy)

• Update Rule:

$$Q(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma Q(s',a') - Q(s,a) \right]$$

where `a'` is action *actually taken* in `s'` according to current policy.

• Behavior: Learns the value of the policy being followed (including exploration). More "cautious."

Comparison: Q-Learning vs SARSA

C. ADVANCED REINFORCEMENT LEARNING

Policy Gradient Methods

• Idea: Directly optimize the policy π_θ(a\|s) (parameterized by θ) to maximize expected return J(θ) = E_π [G_t].

• Objective Gradient (REINFORCE):

$$\nabla J(\theta) = \mathbb{E}_\pi [\nabla \log \pi_\theta(a\|s) \cdot G_t]$$

• Algorithms: REINFORCE ( Monte Carlo policy gradient), Actor-Critic (uses critic to estimate value function, reducing variance).

• Advantages: Natural for stochastic policies and continuous action spaces (e.g., vehicle control).

Generative Adversarial Imitation Learning (GAIL)

• Framework: Two networks:

  1. Generator (Policy π_θ): Outputs actions.

  2. Discriminator (D_φ): Distinguishes expert demonstrations from agent trajectories.

• Objective: Minimax game: π tries to fool D, D tries to correctly classify. No reward function; learns by matching expert state-action distributions.

• Difference from RL: Inverse RL/Imitation paradigm. Uses adversarial loss instead of maximizing reward.

• Game AI Use: Mimicking human playstyles from gameplay videos (e.g., for NPCs in racing games).

D. RECENT TRENDS IN RL ARCHITECTURES

• Deep RL: Combines RL with deep neural networks.

  • DQN (Deep Q-Network): Uses CNN + experience replay + target network for Atari from pixels.

  • DDPG (Deep Deterministic Policy Gradient): For continuous control (actor-critic).

  • PPO (Proximal Policy Optimization): Stable, on-policy algorithm with clipped objective.

• Hierarchical RL (HRL): Decomposes tasks into sub-policies (options).

• Multi-Agent RL (MARL): Multiple agents learning jointly/competitively (e.g., OpenAI Five for Dota 2).

• Applications: AlphaGo/AlphaZero (self-play + MCTS), OpenAI Five, robotic control.

VIII. PROBABILISTIC AND STOCHASTIC METHODS

Markov Chains in Games

• Definition: A sequence of states with Markov Property: P(S_{t+1} \| S_t, S_{t-1}, ...) = P(S_{t+1} \| S_t).

• Transition Matrix P: P_ij = P(S_{t+1}=j \| S_t=i).

• Steady-State Distribution π: π = πP (left eigenvector of P with eigenvalue 1).

• Game Application: Modeling random enemy patrol patterns, weather systems, or loot drops. P defines state transition probabilities.

Fuzzy Time Series

• Purpose: Handle uncertainty in temporal data (e.g., "player is somewhat frustrated").

• Average-Based Fuzzy Time Series (from Nov 2023 paper):

  1. Fuzzify: Convert crisp time series data into fuzzy sets (e.g., Low, Medium, High).

  2. Establish Relationships: Find fuzzy logical relationships between consecutive fuzzy states.

  3. Forecast: Use established rules to predict next fuzzy state, then defuzzify.

• Integration with Markov Chains: Use modified frequency partitioning to define fuzzy states based on Markov transition probabilities, creating a Fuzzy Markov Chain for more robust, uncertain modeling of game events.

IX. EVALUATION AND OPTIMIZATION (GAME CONTEXT)

Classifier Evaluation Metrics (for AI behavior classification)

• Precision: TP / (TP + FP) - Of all predicted "Attack", how many were correct?

• Recall: TP / (TP + FN) - Of all actual "Attack" events, how many were found?

• F1-Score: Harmonic mean: 2 * (Precision * Recall) / (Precision + Recall).

• Use: Evaluating NPC behavior classifiers (e.g., "is player aggressive?").

Overfitting and Underfitting in Game AI Models

• Overfitting: Model learns noise/outliers in training data (e.g., NPC reacts to specific, rare player trick but fails generally). Symptoms: High training accuracy, low validation accuracy.

• Underfitting: Model too simple to capture underlying pattern (e.g., NPC uses only one strategy).

• Mitigation (Game AI):

  • Cross-Validation: Train/validate on different play sessions.

  • Regularization: Add penalty to loss (L1/L2) to constrain model complexity.

  • Feature Engineering: Use more relevant game state features.

  • Ensemble Methods: As discussed, reduce variance.

[!TIP] Exam Tip: Relate overfitting to "rock-paper-scissors" meta in fighting games—an AI that overfits to a player's current dominant strategy becomes exploitable.

\boxed{\text{End of Unit 3 Notes}}