UNIT 4: AI IN GAMING - SHORT NOTES

1. Foundations of Game AI

Definition and Scope

Game AI refers to the algorithms and techniques used to create responsive, adaptive, or intelligent behavior in non-player characters (NPCs) and game systems. Its scope includes pathfinding, decision-making, opponent modeling, and procedural content generation, aiming to enhance player experience rather than achieve human-level general intelligence.

Game Theory & Application to AI

• Key Concepts:

  • Players: Decision-makers (e.g., two soccer teams).

  • Strategies: Complete plan of action for a player.

  • Payoffs: Numerical rewards/outcomes for each strategy combination, represented in a payoff matrix.

• Solving Payoff Matrices:

  • Pure Strategy: A single, deterministic best response. Exists if a saddle point (maximin = minimax) is present.

  • Mixed Strategy: Probability distribution over strategies. Used when no pure strategy equilibrium exists.

• Nash Equilibrium: A set of strategies where no player can unilaterally change their strategy to improve their payoff, given the other player's strategy.

  Example (Penalty Kick): Kicker (Player 1) and Goalie (Player 2). If kicker kicks Left with prob p and Right with 1-p, goalie dives Left with prob q and Right with 1-q. The equilibrium is found by making the opponent indifferent between their choices.

  • Kicker's Indifference: 1.4q + 1.7(1-q) = 1.5q + 1.5(1-q) → Solve for q.

  • Goalie's Indifference: 1.4p + 1.5(1-p) = 1.5p + 1.5(1-p) → Solve for p.

  Result: Equilibrium mixed strategies (p*, q*) where both are indifferent.

Model of Game AI (Overall Architecture)

A typical layered architecture:

1. Input Layer: Perceives game state (sensors, world data).

2. Decision Layer: Uses AI techniques (FSM, Behavior Trees, RL) to choose actions.

3. Action Layer: Executes chosen actions (animation, movement, sound).

4. Output Layer: Affects the game world.

This decouples perception, decision, and execution for modularity.

Board Game Theory

Focuses on deterministic, perfect-information, sequential games (e.g., Chess, Checkers).

• Game Tree: Represents all possible future states (nodes) and moves (edges).

• Minimax Principle: Assumes opponent plays optimally. The algorithm maximizes the minimum possible payoff.

• Complexity: For a game with branching factor b and depth d, the tree has ~b^d nodes. This necessitates pruning (e.g., Alpha-Beta) and evaluation functions for non-terminal states.

2. Search and Pathfinding Algorithms

Uninformed Search: Breadth-First Search (BFS)

• Idea: Explores all nodes at the present depth before moving to the next depth level. Guarantees shortest path in an unweighted graph/grid.

• Implementation Steps:

  1. Initialize queue with start node.

  2. While queue not empty:

     • Dequeue node n.

     • If n is goal, reconstruct path.

     • Else, enqueue all unvisited neighbors of n.

• Example: Grid with obstacles. BFS expands in concentric "waves" from start until goal is found.

Complexity: Time & Space = O(b^d), where b is avg. branching factor, d is solution depth. Can be memory-intensive.

Informed Search: A Algorithm*

• Idea: Best-first search using a heuristic to guide exploration towards the goal. Optimal and complete if heuristic h(n) is admissible (never overestimates true cost) and consistent.

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

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

  • h(n): Heuristic estimated cost from n to goal.

  • f(n): Estimated total cost of the cheapest path through n.

• Common Heuristics for Grids:

  • Manhattan Distance: |x₁ - x₂| + |y₁ - y₂| (for 4-direction movement).

  • Euclidean Distance: √((x₁ - x₂)² + (y₁ - y₂)²) (for any direction).

• Example Walkthrough:

  DiagramSEARCH: "A* search grid pathfinding example"

  1. Start node: f = g + h.

  2. Expand node with lowest f.

  3. Update neighbors' g and f if a cheaper path is found.

  4. Repeat until goal is dequeued.

Adversarial Search: Minimax Algorithm

• Application: Two-player, zero-sum, perfect-information games.

• Functions:

  • MAX: Our turn. Choose move that maximizes the minimum value the opponent can force.

  • MIN: Opponent's turn. Choose move that minimizes the maximum value we can achieve.

• Evaluation Function (eval(n)): Estimates the utility of a non-terminal state n from MAX's perspective (e.g., material balance in chess).

• Process: Recursively build game tree to a fixed depth, apply eval() at leaf nodes, then propagate values up using MAX/MIN rules.

Complexity: O(b^m), where m is search depth. Pruning (Alpha-Beta) is essential.

Efficiency in Complex Problem Solving

• Complexity Issues: Exponential growth of search space (b^d) makes exhaustive search infeasible for large d.

• Strategies to Improve Efficiency:

  1. Pruning: Alpha-Beta pruning eliminates branches that cannot affect the final decision.

  2. Heuristics: Guide search (A*), reduce effective branching factor.

  3. Iterative Deepening: Repeatedly run depth-limited search with increasing limits. Combines BFS's memory efficiency with DFS's time efficiency.

  4. Transposition Tables: Hash previously evaluated states to avoid re-computation.

  5. Move Ordering: Explore best moves first to maximize pruning effectiveness.

3. Decision-Making Architectures

Rule-Based Systems

• Definition: Systems that use a set of IF <condition> THEN <action> rules and an inference engine to match conditions against facts in a working memory.

• Components:

  • Rule Base: Collection of rules.

  • Inference Engine: Matches rules to facts (forward chaining: data → conclusion; backward chaining: goal → data).

  • Working Memory: Current set of known facts.

• Example (Guard/Thief):

  • IF NOT (see thief) THEN action = guard

  • IF see thief AND thief is strong THEN action = flee

  • IF see thief AND thief is NOT strong THEN action = fight

Finite State Machines (FSM)

• Components:

  • States: Distinct behaviors (e.g., Guard, Fight, Flee).

  • Transitions: Directed edges between states, triggered by events or conditions (e.g., see_thief, health_low).

  • Actions: Entry/Exit actions or actions during a state.

• Construction Example (Guard/Thief):

  DiagramCANVAS: "FSM with states: Guard (start), Fight, Flee. Transitions: from Guard on 'see_thief_strong' -> Flee; on 'see_thief_weak' -> Fight. From Fight on 'losing' -> Flee. From Flee on 'safe' -> Guard."

• Pros/Cons: Simple, predictable. Becomes messy ("spaghetti") with many states/transitions.

Behavior Trees

• Node Types:

  • Selector (?) : Tries children in order until one succeeds. Falls back if failure.

  • Sequence (→) : Executes children in sequence. Fails if any child fails.

  • Leaf (Task/Condition): Actual actions (e.g., MoveTo, Attack) or checks (e.g., IsThiefVisible?).

• Comparison with FSMs:

  | Feature | FSM | Behavior Tree | | :--- | :--- | :--- | | Structure | Graph of states | Tree of tasks | | Flexibility | Low (hardwired transitions) | High (reusable subtrees) | | Scalability | Poor (state explosion) | Good (modular composition) | | Debugging | Hard (distributed logic) | Easier (hierarchical) |

Algorithm Structure for Coordinated Movement

• Key Components:

  • Pathfinding: High-level route (A* on navigation mesh).

  • Path Following: Low-level steering to follow the path (e.g., Seek next waypoint).

  • Obstacle Avoidance: Reactive steering (e.g., SteerAway from obstacles detected via sensors).

  • Animation: Blend between walk/run/jump based on velocity.

4. Machine Learning for Game AI

Decision Trees in Game Development

• Recursive Induction: Build tree top-down by repeatedly splitting the dataset on the attribute that best separates the classes.

• Splitting Criteria: Choose attribute that maximizes Information Gain (IG) or Gain Ratio.

• Entropy & 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:** 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) $$

*   **Example Calculation (Loan Dataset):**

    | Sample | Credit Score | Loan Approved |

|--------|--------------|---------------| | 1 | High | Yes | | 2 | Medium | No | | 3 | Low | No | | 4 | High | Yes | | 5 | Medium | Yes | | 6 | Low | No | | 7 | High | No |

    1.  **Parent Entropy H(S):** 4 Yes, 3 No.

        `p_yes = 4/7, p_no = 3/7`

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

    2.  **Split on Credit Score:**

        *   **High (3 samples):** 2 Yes, 1 No → `H(High) ≈ 0.918`

        *   **Medium (2 samples):** 1 Yes, 1 No → `H(Medium) = 1.0`

        *   **Low (2 samples):** 0 Yes, 2 No → `H(Low) = 0.0`

    3.  **Weighted Avg Entropy:**

        `(3/7)*0.918 + (2/7)*1.0 + (2/7)*0.0 ≈ 0.653`

    4.  **IG(S, Credit Score):** `0.985 - 0.653 = 0.332`

    > **Result:** Credit Score has IG = 0.332. Repeat for other attributes to find best split.

Handling Noisy Data

• Effects: Causes overfitting—tree learns noise as pattern, poor generalization to new data.

• Strategies to Overcome:

  1. Pruning: Remove branches that have little statistical significance.

     • Pre-pruning: Stop splitting early (min samples per leaf, max depth).

     • Post-pruning: Build full tree, then remove branches (e.g., reduced error pruning).

  2. Setting Minimum Samples: Require a minimum number of samples in a node to consider splitting.

  3. Using Ensemble Methods: Random Forests inherently reduce overfitting via averaging.

Ensemble Methods

• Bagging (Bootstrap Aggregating):

  • Train multiple models (e.g., trees) on random subsets (with replacement) of training data.

  • Final prediction: Average (regression) or majority vote (classification).

  • Effect: Reduces variance (good for unstable, high-variance models like deep trees).

• Boosting:

  • Train models sequentially. Each new model focuses on errors of previous ones.

  • Final prediction: Weighted sum of model predictions (weights based on accuracy).

  • Effect: Reduces bias (good for weak learners).

  • Examples: AdaBoost, Gradient Boosting, XGBoost.

• Comparison:

  | Aspect | Bagging | Boosting | | :--- | :--- | :--- | | Sampling | Bootstrap samples | Weighted samples (focus on errors) | | Model Relation | Parallel, independent | Sequential, dependent | | Primary Goal | Reduce variance | Reduce bias | | Overfitting Risk | Low (averaging) | Higher (if too many rounds) |

Random Forest Algorithm

• Working Mechanism:

  1. Create N bootstrap samples from training data.

  2. For each sample, grow a decision tree with a twist: at each split, consider only a random subset of features (e.g., √total_features).

  3. Final prediction: Majority vote (classification) or average (regression) of all trees.

• Robustness in Game AI Context:

  • Handles high-dimensional feature spaces (player stats, game state).

  • Resistant to overfitting (due to feature randomness and bagging).

  • Provides feature importance scores (useful for game design insights).

  • Works well with noisy game data.

Why Ensembles Offer Greater Robustness

• Bias-Variance Tradeoff: Single models often have high bias (underfit) or high variance (overfit). Ensembles balance this.

• Error Averaging: Random errors of individual models cancel out; systematic errors are corrected by diversity.

• Diversity is Key: Ensembles work best when models make different errors. Random Forest ensures diversity via data and feature randomness.

• Result: Lower overall generalization error, more stable predictions across varied game scenarios.

Supervised Learning: Least Squares Methods

• Application in Games: Predict continuous outcomes like player score, time-to-completion, or win probability based on features (player level, items, playtime).

• Linear Least Squares: Fit a linear model y = β₀ + β₁x₁ + ... + βₙxₙ by minimizing sum of squared residuals Σ(yᵢ - ŷᵢ)².

• Solution: Normal equation β = (XᵀX)⁻¹Xᵀy. Used for simple regression tasks or as a baseline.

Neural Networks: Multi-Layer Perceptron (MLP)

• Architecture:

  • Input Layer: One neuron per feature (e.g., health, ammo, distance to enemy).

  • Hidden Layer(s): Apply non-linear transformations via activation functions (ReLU, Sigmoid, Tanh).

  • Output Layer: Produces final prediction (e.g., action probabilities, value estimate).

• Learning Process:

  1. Forward Pass: Compute output for a given input.

  2. Loss Calculation: Compare output to target (e.g., Cross-Entropy for classification, MSE for regression).

  3. Backpropagation: Compute gradient of loss w.r.t. all weights using chain rule.

  4. Weight Update: Adjust weights via gradient descent: w = w - η * ∇L, where η is learning rate.

• In Game AI: Used for complex function approximation (e.g., value networks in AlphaGo, policy networks in DQN).

5. Reinforcement Learning for Games

Core Concepts

• Markov Decision Process (MDP): Formalization (S, A, P, R, γ).

  • S: Set of states.

  • A: Set of actions.

  • P(s'|s,a): Transition probability to state s' from s taking a.

  • R(s,a,s'): Immediate reward.

  • γ: Discount factor (0 ≤ γ ≤ 1).

• Policy (π): Mapping from states to actions (deterministic or stochastic).

• Value Functions:

  • State-Value: Vπ(s) = E[Σ γᵗ R_t | s₀=s, π] = Expected return starting from s following π.

  • Action-Value: Qπ(s,a) = E[Σ γᵗ R_t | s₀=s, a₀=a, π] = Expected return taking a in s then following π.

Bellman Equations

• Definition: Recursive relationships defining value functions.

• State-Value Bellman Equation:

$$ Vπ(s) = \sum_a π(a|s) \sum_{s',r} P(s',r|s,a) [r + γ Vπ(s')] $$

• Action-Value Bellman Equation:

$$ Qπ(s,a) = \sum_{s',r} P(s',r|s,a) [r + γ \sum_{a'} π(a'|s') Qπ(s',a')] $$

• Optimal Value Functions (V, Q):** Satisfy Bellman Optimality Equations:

$$ V^*(s) = \max_a \sum_{s',r} P(s',r|s,a) [r + γ V^*(s')] $$

$$ Q^*(s,a) = \sum_{s',r} P(s',r|s,a) [r + γ \max_{a'} Q^*(s',a')] $$

> The optimal policy is greedy w.r.t. Q*: `π*(s) = argmax_a Q*(s,a)`.

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

Value-Based Methods

• Q-learning vs SARSA:

  | Aspect | Q-learning | SARSA | | :--- | :--- | :--- | | Policy Type | Off-policy | On-policy | | Update Rule | Q(s,a) ← Q(s,a) + α [r + γ max_a' Q(s',a') - Q(s,a)] | Q(s,a) ← Q(s,a) + α [r + γ Q(s',a') - Q(s,a)] | | Next Action | Uses greedy action for bootstrap (may explore in next step) | Uses actual next action a' taken by current policy | | Behavior | More optimistic, learns optimal policy regardless of exploration | More conservative, learns policy including exploration | | Risk | Can overestimate values, unstable with function approximation | Safer, converges to policy that respects exploration |

• Value Iteration: Repeatedly apply Bellman optimality update to all states until convergence. V_{k+1}(s) = max_a Σ P(s'|s,a)[r + γ V_k(s')]. Then derive greedy policy. Guaranteed convergence to V*.

• Policy Iteration: Alternate between:

  1. Policy Evaluation: Compute Vπ for current π (solve linear system or iterative TD).

  2. Policy Improvement: Make π greedy w.r.t. Vπ: π'(s) = argmax_a Σ P(s'|s,a)[r + γ Vπ(s')].

  Terminates when policy doesn't change. Often fewer iterations than Value Iteration but each iteration costlier.

Policy Gradient Methods

• Basic Idea: Directly optimize the policy π(a|s; θ) parameterized by θ (e.g., neural network) to maximize expected return J(θ) = E[Σ γᵗ R_t].

• Update Rule (REINFORCE): θ ← θ + α ∇ log π(a|s;θ) G_t.

• Advantages over Value-Based:

  • Continuous Action Spaces: Natural (output distribution parameters).

  • Stochastic Policies: Can learn exploration strategies explicitly.

  • Convergence: Often converge to local optimum more stably than Q-learning with function approximation.

  • No Max Operator: Avoids overestimation bias and instability.

Advanced Topics

• Generative Adversarial Imitation Learning (GAIL):

  • Difference from Standard RL: Does not use hand-designed reward function. Instead, learns a policy by imitating expert demonstrations.

  • Mechanism: Two networks:

    1. Generator (Policy π): Takes state, outputs action.

    2. Discriminator (D): Distinguishes state-action pairs from expert vs. agent.

  • Objective: Minimize JS divergence between agent's and expert's state-action distributions. Policy is trained to fool discriminator.

• Recent Trends in RL Architectures:

  • Deep RL: Combining deep neural networks with RL (DQN, PPO, SAC).

  • Hierarchical RL (HRL): Decomposes tasks into sub-policies (options) at different time-scales.

  • Multi-agent RL (MARL): Multiple learners interacting (cooperative, competitive, mixed). Challenges: non-stationarity, credit assignment.

  • Meta-RL: "Learning to learn" – adapt quickly to new tasks/games.

  • Model-Based RL: Learn environment model P(s'|s,a) to plan, improving sample efficiency.

6. Specialized Topics in Game AI

Character Movement and Animation

• Static vs Kinematic Representation (3D):

  | Static (Kinematic) | Dynamic (Kinematic) | | :--- | :--- | | Position only (x,y,z). | Position and velocity/acceleration (v, a). | | No concept of momentum. | Simulates physics (inertia, forces). | | Used for pathfinding nodes (navmesh). | Used for actual character movement (steering). | | Example: Waypoint on navmesh. | Example: Seek steering force applied to velocity. |

• Components of Coordinated Movement:

  1. Pathfinding: High-level route on navigation mesh (A*).

  2. Path Following: Low-level steering to follow path (e.g., Seek waypoint, Arrive slow down).

  3. Obstacle Avoidance: Reactive steering (raycasts, potential fields, SteerAway).

  4. Coordination/Blending: Arbitration between behaviors (e.g., priority-based, weighted sum of steering forces).

  5. Animation: Root motion or procedural animation driven by movement velocity/direction.

• Stages of Motor Learning (for NPCs):

  1. Acquisition: Initial learning phase (e.g., training a neural network policy).

  2. Refinement: Fine-tuning with more experience/exploration.

  3. Retention: Maintaining learned behavior over time (preventing catastrophic forgetting in lifelong learning).

Probabilistic Methods

• Fuzzy Time Series (Average-based Partitioning):

  • Partition state space (e.g., distance to player) into fuzzy sets (e.g., Close, Medium, Far) based on average values of historical data.

  • Use fuzzy logic rules for decision-making under uncertainty.

• Markov Chains (Modified Frequency Partitioning):

  • Model state transitions as a Markov process.

  • Modified Frequency Partitioning: States are defined by clustering based on transition frequencies between observed game states (e.g., "chasing", "fleeing" states).

  • Integration in Game AI: Opponent modeling, predicting player behavior patterns, generating plausible non-deterministic NPC actions.

3D Representation Techniques

• Navigation Mesh (NavMesh): 2D polygon representation of walkable areas in 3D space. Used for pathfinding.

• Octrees: Spatial partitioning tree for efficient 3D queries (collision, visibility, AI sensing).

• Spatial Partitioning Grids: Divide world into cells for broad-phase collision and AI perception (e.g., "is player in same cell?").

7. Cross-Cutting Applications and Evaluation

Applying ML/RL to Specific Game Genres

• Board Games: Deep RL + Search (AlphaGo, AlphaZero). Self-play, Monte Carlo Tree Search (MCTS) guided by neural networks.

• Sports Games: Policy gradient methods for continuous control (running, kicking). Imitation learning from human motion capture.

• RPGs/RTS: Hierarchical RL for long-term planning (quests, build orders). Multi-agent RL for squad tactics.

• Racing Games: Model-based RL for learning car dynamics, combined with search for racing lines.

Integration of Classical and Modern AI

• Hybrid Approach: Use classical algorithms for guarantees and structure, ML for adaptation and generalization.

  • Example 1: A* for pathfinding + RL policy for dynamic obstacle avoidance.

  • Example 2: FSM/Behavior Tree for high-level state management + neural network for low-level combat decisions.

  • Example 3: MCTS (search) guided by neural network policy/value (AlphaZero).

Evaluation Metrics for Game AI

Key Insight: Optimal game AI is not necessarily the strongest; it's the one that provides the best player experience (challenging but fair, believable, fun).

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