UNIT 2: AI IN GAMING – SHORT NOTES

I. GAME THEORY AND STRATEGIC DECISION-MAKING

Fundamentals of Game Theory

• Definition: Study of mathematical models of strategic interaction among rational decision-makers (players).

• Core Concepts:

  • Players: The decision-making entities.

  • Strategies: Complete plan of action for each player.

  • Payoffs: Numerical rewards/utilities received by players for each strategy combination.

• Application in AI: Provides formal framework for designing AI agents that can make optimal decisions in competitive or cooperative multi-agent environments (e.g., NPCs in strategy games, adversarial search).

[!TIP] Exam Focus: Be ready to define the three core components (Players, Strategies, Payoffs) and explain why game theory is crucial for AI (models strategic interaction, predicts opponent moves).

Minimax Algorithm

• Purpose: Decision rule for two-player, zero-sum games (one player's gain is the other's loss). Aims to minimize the maximum possible loss.

• Functions/Components:

  • MAX player: Aims to maximize its score.

  • MIN player: Aims to minimize MAX's score (or maximize its own in zero-sum).

  • Game Tree: Tree structure representing all possible future moves.

  • Terminal Nodes: End states with known utility/payoff values.

  • Backtracking: Algorithm propagates values upward: MAX nodes take max(child values), MIN nodes take min(child values).

• Workflow: Build tree → Assign values to leaves → Recursively propagate min/max up to root → Choose move leading to root's value.

[!TIP] Common Pitfall: Minimax assumes a perfectly rational opponent. In practice, depth limits and evaluation functions (heuristic estimates of non-terminal states) are used.

Solving Payoff Matrices

• Matrix Representation: Rows = Player A's strategies, Columns = Player B's strategies. Cell (i,j) contains (Payoff_A, Payoff_B).

• Pure Strategy Equilibrium (Saddle Point): A cell where the row's minimum equals the column's maximum. Both players have no incentive to unilaterally change strategy.

  • Value of the game (V): The saddle point payoff.

• Mixed Strategy Equilibrium: Players randomize over strategies with specific probabilities (p, 1-p). No pure equilibrium exists.

  • Solution Method: Set expected payoffs equal for opponent's strategies to make them indifferent. Solve linear equations.

  • Expected Payoff (for Player A):

$$E[A] = p \cdot (a_{11} \cdot q + a_{12} \cdot (1-q)) + (1-p) \cdot (a_{21} \cdot q + a_{22} \cdot (1-q))$$

where `q` is opponent's probability for a column.

Game Equilibrium Analysis (Nash Equilibrium)

• Nash Equilibrium: A set of strategies where no player can improve their payoff by unilaterally changing their strategy, given the other players' strategies.

• Finding in Simple Scenarios (e.g., Penalty Kicks):

  1. Identify best responses for each player to the other's possible pure strategies.

  2. Find intersection where both are playing best responses.

  3. For mixed strategies, solve for probabilities that make the opponent indifferent between their pure strategies.

• Example (Penalty Kick from paper):

  | Kicker\Goalie | Left | Right | | :--- | :--- | :--- | | Left | 1.4, 0.6 | 1.5, 0.5 | | Right | 1.7, 0.4 | 1.5, 0.4 |

  • Kicker's Best Response: If Goalie Left → Right (1.7 > 1.4). If Goalie Right → Left (1.5 = 1.5, indifferent).

  • Goalie's Best Response: If Kicker Left → Left (0.6 > 0.5). If Kicker Right → Right (0.4 = 0.4, indifferent).

  • Pure NE? (Left, Left): Kicker wants to switch to Right. (Right, Right): Goalie indifferent, Kicker indifferent. (Right, Right) is a Nash Equilibrium (neither can gain by switching alone).

Board Game Theory

• Theoretical Foundations: Application of combinatorial game theory (CGT) to deterministic, perfect-information games (Chess, Checkers, Go).

• Key Concepts:

  • Game Trees: Massive state spaces.

  • Complexity: Many are PSPACE-complete or EXPTIME-complete.

  • Solution Techniques: Minimax with alpha-beta pruning, Monte Carlo Tree Search (MCTS), endgame tablebases.

  • Evaluation Functions: Crucial for non-terminal positions (material balance, piece-square tables, mobility).

• Application: Forms the backbone of classic board game AI (e.g., Deep Blue, AlphaGo's policy/value networks guide MCTS).

II. SEARCH ALGORITHMS AND PATHFINDING

Breadth-First Search (BFS)

• Purpose: Unweighted graph/tree traversal to find the shortest path (in terms of number of edges) from a start node to a target.

• Implementation:

  1. Use a queue (FIFO).

  2. Enqueue start node, mark visited.

  3. While queue not empty: Dequeue node → if target, reconstruct path. Else, enqueue all unvisited neighbors, mark visited, store parent pointer.

• Properties: Complete (finds solution if exists), optimal for unweighted graphs, time/space complexity O(b^d) (b = branching factor, d = depth).

[!TIP] Example: Grid pathfinding where each move (N, S, E, W) has equal cost.

A* Pathfinding Algorithm

• Purpose: Best-first search that uses a heuristic to find the lowest-cost path efficiently.

• Cost Evaluation Function:

$$f(n) = g(n) + h(n)$$

*   `g(n)`: Exact cost from start to node `n`.

*   `h(n)`: **Heuristic** (admissible & consistent) estimating cost from `n` to goal.

*   `f(n)`: Estimated total cost of the cheapest path going through `n`.

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

• Consistent (Monotonic) Heuristic: For every node n and successor n', h(n) ≤ c(n,n') + h(n'). Ensures f(n) is non-decreasing along a path.

• Common Heuristics (Grid):

  • Manhattan Distance: |x1-x2| + |y1-y2| (4-directional movement).

  • Euclidean Distance: √((x1-x2)² + (y1-y2)²) (8-directional).

  • Octile Distance: For 8-direction with diagonals.

• Step-by-Step: Uses a priority queue (min-heap) ordered by f(n). Expands node with lowest f(n). If a better g(n) path to an existing node is found, updates its priority.

[!TIP] Key: Admissibility + Consistency = Optimal & Efficient. A* expands far fewer nodes than BFS in weighted graphs.

Algorithm Efficiency in Complex Problems

• Factors Affecting Efficiency:

  • State Space Size (Branching Factor b): Larger b → exponential explosion.

  • Solution Depth d: Deeper solutions → more nodes.

  • Heuristic Quality: Poor h(n) ≈ BFS; good h(n) directs search.

  • Memory Constraints: Storing all generated nodes (BFS, A*) can be prohibitive.

• Mitigation Strategies:

  • Alpha-Beta Pruning: In Minimax, eliminate branches that cannot affect the final decision.

  • Iterative Deepening A (IDA):** Memory-efficient variant of A* using depth-first search with increasing f-cost thresholds.

  • Hierarchical Pathfinding (HPA):* Decompose map into clusters, plan high-level path between clusters, then low-level within clusters.

  • Jump Point Search (JPS): Optimizes A* on uniform-cost grids by "jumping" over symmetric nodes.

  • Bounded Planning: Use time or depth limits, rely on evaluation functions.

Pathfinding Algorithm Structure

• General Flow:

  1. Initialization: Create open list (priority queue), closed list (hash set). Add start node to open list.

  2. Main Loop: While open list not empty:

     • Get node current with lowest f(n) from open list.

     • If current is goal → SUCCESS, reconstruct path.

     • Move current from open to closed list.

     • Expand: For each neighbor n of current:

       • If n is impassable or in closed list → skip.

       • Calculate tentative g(n) = g(current) + cost(current, n).

       • If n not in open list OR new g(n) is lower:

         • Update n.parent = current.

         • n.g = tentative_g.

         • n.h = heuristic(n, goal).

         • n.f = n.g + n.h.

         • If n not in open list → add it.

  3. If loop ends → FAILURE (no path).

[!DIAGRAM: CANVAS: Flowchart showing initialization, main loop with open/closed lists, node expansion, and path reconstruction.]

III. AI BEHAVIOR MODELING

Rule-Based Systems

• Structure: IF (condition/antecedent) THEN (action/consequent). A set of such rules forms the knowledge base.

• Components:

  • Rule Base (Knowledge Base): Collection of IF-THEN rules.

  • Inference Engine: Matches facts against rule conditions to fire applicable rules.

  • Working Memory: Stores current facts/assertions.

  • Agenda: Set of activated but not yet fired rules.

• Execution Cycle (Rete Algorithm typical):

  1. Match: Compare facts in working memory with rule conditions → create conflict set.

  2. Conflict Resolution: Select one rule from the set (e.g., specificity, recency).

  3. Act: Execute rule's action (add/remove/modify facts in working memory).

  4. Repeat until no rules fire or halt condition.

• Example (Guard AI):

  • IF (state == patrolling) AND (time > 5min) THEN (change_state_to_investigate)

  • IF (sees_thief == true) AND (thief_health > my_health) THEN (state == flee)

Finite State Machines (FSM)

• Core Elements:

  • States: Distinct modes of behavior (e.g., Idle, Patrol, Chase, Attack, Flee).

  • Transitions: Directed edges between states, labeled with triggering events/conditions (e.g., see_player, low_health, timer_expired).

  • Actions: Entry/Exit actions or do-actions while in a state.

• Construction (Guard/Thief Example):

  • States: Guard, Fight, Flee.

  • Transitions:

    • Guard → Fight on see_thief AND thief_strength <= my_strength

    • Guard → Guard (loop) on no_thief

    • Fight → Flee on health_low

    • Flee → Guard on lost_sight

• Pros: Simple, intuitive, predictable.

• Cons: Can lead to state explosion for complex behaviors; transitions become tangled ("spaghetti code").

Behavior Trees

• Structure: Hierarchical node tree. Execution flows from root to leaves.

• Key Node Types:

  • Control Flow Nodes:

    • Selector (?): Runs children in order until one succeeds; if all fail, fails. (Fallback/OR logic).

    • Sequence (→): Runs children in order until one fails; if all succeed, succeeds. (AND logic).

  • Decorator Nodes: Modify outcome/flow of a single child (e.g., Inverter, Succeeder, Repeater, Limit).

  • Leaf Nodes (Tasks): Actual conditional checks or actions (e.g., IsHealthLow?, MoveTo, Attack). Return Success, Failure, or Running.

• Execution: Tick from root. Nodes return status. Running allows resumption next tick.

• Pros: Modular, reusable, easy to design complex behaviors, handles interruption naturally.

FSM vs. Behavior Trees

[!TIP] Exam Question: Be prepared to draw an FSM for a given scenario (like guard/thief) and compare/contrast FSM and BT in a table.

IV. 3D REPRESENTATION AND MOVEMENT SYSTEMS

Static vs. Kinematic Representation in 3D

• Static Representation:

  • Describes an object's position and orientation at a single instant.

  • Components: Position vector (x, y, z), Orientation (quaternion (w, x, y, z) or Euler angles (pitch, yaw, roll)).

  • Use: Defining initial poses, keyframes in animation, collision geometry.

• Kinematic Representation:

  • Describes an object's movement over time.

  • Components: Velocity (vx, vy, vz), Angular Velocity (ωx, ωy, ωz), Acceleration.

  • Use: Physics simulation, character controllers, animation blending, path following (steering behaviors).

• Key Difference: Static = where and how it's oriented. Kinematic = how it moves (derivatives of position/orientation).

Coordinated Movement Components

• Breakdown for Game Characters:

  1. Pathfinding: High-level route (A* on navigation mesh). Outputs a path (sequence of waypoints).

  2. Steering: Low-level, frame-by-frame motion to follow the path. Uses kinematic output (forces, velocities). Implements:

     • Seek: Accelerate towards target.

     • Arrive: Decelerate to stop at target.

     • Obstacle Avoidance: Raycasts/volumes to steer away.

     • Flocking: Cohesion, Separation, Alignment.

  3. Animation: Visual representation of movement. Driven by:

     • Root Motion: Animation drives position (e.g., walk cycle).

     • Inverse Kinematics (IK): Solves for joint angles to place end-effector (foot, hand) at a world position.

     • Blending: Smoothly transition between animations (walk/run, turn).

  4. Integration: Steering outputs desired velocity → Animation system uses it to select/blend animations → Final transform updates.

Stages of Motor Learning (AI Agents)

Based on motor learning theory, applied to training AI characters:

1. Cognitive Stage: Agent understands the task but performs poorly. High variability, conscious control. (e.g., New steering behavior, erratic movement).

2. Associative Stage: Agent refines performance, reduces errors. Movement becomes more consistent and efficient. (e.g., Smoothing path following, better obstacle avoidance).

3. Autonomous Stage: Skill is automatized. Requires little conscious processing, robust to perturbations. (e.g., Expert-level navigation in complex dynamic environments).

[!TIP] Application: Used in procedural animation and learning-based controllers (e.g., training a neural network to output walking gaits). Progression can be simulated by adjusting policy parameters or animation blend tree weights over "practice" time.

V. MACHINE LEARNING TECHNIQUES FOR GAME AI

A. DECISION TREES

Entropy and Information Gain

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

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

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

*   `H(S)=0` (pure, all same class). `H(S)=1` (maximally impure, equal class distribution for 2 classes).

• Information Gain (IG): Reduction in entropy achieved by splitting dataset on an 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 attribute `A` has value `v`.

• Calculation (from exam dataset):

  • Total Samples |S| = 7. Classes: Yes (3), No (4).

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

  • Split on Credit Score (High, Medium, Low):

    • High: [Yes, Yes, No] → H= - (2/3 log₂(2/3) + 1/3 log₂(1/3)) ≈ 0.918

    • Medium: [No, Yes] → H= - (1/2 log₂(1/2) + 1/2 log₂(1/2)) = 1.0

    • Low: [No, No] → H= 0 (pure)

    • IG(S, Credit Score) = 0.985 - [(3/7)*0.918 + (2/7)*1.0 + (2/7)*0] ≈ 0.985 - 0.668 ≈ 0.317

Recursive Induction in Decision Trees

• Process: Top-down, greedy algorithm (ID3, C4.5, CART).

  1. Start with all training samples at root.

  2. If all samples belong to same class, make leaf with that class.

  3. Else, select best attribute (highest Information Gain / lowest Gini Impurity) to split on.

  4. Create a branch for each value of that attribute.

  5. Recurse on each branch's subset of samples and remaining attributes.

• Significance: Automatically discovers hierarchical, rule-based decision structure from data. Handles both categorical and (with discretization) numerical data.

Handling Noisy Data

• Impact of Noise: Causes overfitting. Tree grows overly complex, capturing random fluctuations (outliers, mislabeled data) → poor generalization to new data.

• Strategies to Overcome:

  1. Pruning: Remove branches that provide little predictive power.

     • Pre-pruning (Early stopping): Stop tree growth based on criteria (min samples per leaf, max depth, min IG gain).

     • Post-pruning: Grow full tree, then remove nodes (e.g., reduced error pruning, cost-complexity pruning).

  2. Ensemble Methods: Use multiple trees (Random Forest, Gradient Boosting) which average out noise.

  3. Data Cleaning: Identify and correct/remove noisy instances.

  4. Use Robust Splitting Criteria: Gini Impurity can be slightly more robust than Entropy.

Application in Game Development

• NPC Behavior Decision Making: Classify combat stance (aggressive/defensive) based on health, ammo, distance to player.

• Dynamic Difficulty Adjustment (DDA): Predict player skill/ frustration level from gameplay metrics (time to complete, deaths, accuracy) and adjust AI parameters.

• Procedural Content Generation (PCG): Decide level layout or item placement based on features (e.g., "is this room too hard?").

• Player Modeling: Classify player type (explorer, achiever) from in-game actions.

B. ENSEMBLE METHODS

Bagging vs. Boosting

Random Forest Algorithm

• Architecture: Ensemble of N decision trees.

• Working Mechanism (Bootstrap Aggregation + Feature Randomness):

  1. For each of N trees:

     • Create a bootstrap sample (random sample with replacement) from training data (~63.2% unique).

     • Grow a decision tree on this sample. At each split, consider only a random subset of features (e.g., √(total_features)). This decorrelates trees.

  2. Prediction: For classification, take majority vote of all trees. For regression, take average.

• Key Hyperparameters: n_estimators, max_features, max_depth, min_samples_split.

• Application in Games: Robust player behavior classification, feature importance analysis (which game metrics predict success?), anomaly detection in game telemetry.

Robustness of Ensemble Methods

• Why Ensembles Outperform Single Models:

  1. Error Reduction: Different models make different errors. Averaging/voting cancels out individual model errors (law of large numbers).

  2. Reduced Variance (Bagging): Averaging multiple high-variance models (like deep trees) stabilizes predictions.

  3. Reduced Bias (Boosting): Sequentially focusing on hard cases improves overall fit.

  4. Increased Complexity without Overfitting: Can model complex relationships while controlling overfitting via diversity and averaging.

• Benefits for Game AI:

  • Stability: Less sensitive to noise in training data (e.g., imperfect human play traces).

  • Accuracy: Higher predictive performance for complex mappings (player state → action).

  • Generalization: Better performance on unseen game states/player behaviors.

  • Feature Insights: Random Forest provides feature importance scores, helping designers understand key drivers.

C. NEURAL NETWORKS

Multi-Layer Perceptron (MLP)

• Architecture:

  • Input Layer: One neuron per input feature (e.g., game state vector: health, ammo, distance).

  • Hidden Layer(s): One or more layers of neurons with non-linear activation functions (ReLU, Tanh, Sigmoid). Enable learning complex patterns.

  • Output Layer: Neurons represent output. For game actions: Softmax (probability distribution over discrete actions) or linear (continuous value like steering angle).

  • Fully Connected: Each neuron in layer l connected to all neurons in layer l+1.

• Learning Process (Backpropagation):

  1. Forward Pass: Input x → compute weighted sum z = Wx + b at each layer → apply activation a = f(z) → propagate to output ŷ.

  2. Compute Loss: Compare ŷ to true target y using loss function (Cross-Entropy for classification, MSE for regression).

  3. Backward Pass (Backprop): Apply chain rule to compute gradient of loss w.r.t. every weight W and bias b.

     • ∂Loss/∂W = ∂Loss/∂a * ∂a/∂z * ∂z/∂W

  4. Weight Update (Gradient Descent): Update weights to minimize loss.

$$W_{new} = W_{old} - \eta \cdot \frac{\partial Loss}{\partial W}$$

    where `η` is learning rate.

• Application in Games: Function approximation for value functions (RL), policy networks (AlphaGo), end-to-end learning from pixels (Deep Q-Networks).

D. OTHER ML METHODS

Least Squares Methods

• Overview: Family of methods for regression (predicting continuous values) by minimizing the sum of squared residuals (differences between predicted and actual values).

• Linear Least Squares (Ordinary Least Squares - OLS): Finds coefficients β in y = Xβ + ε that minimize ||y - Xβ||².

  • Closed-form solution:

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

*   **Assumptions:** Linear relationship, no multicollinearity, homoscedasticity, normal errors.

• Application in Game Analytics:

  • Predicting player lifetime value (LTV) from early gameplay metrics.

  • Modeling relationship between difficulty parameters and player completion rate.

  • Polynomial Regression: Fitting curves to non-linear progression data (e.g., skill rating vs. time).

• Limitation: Sensitive to outliers, assumes linearity. Often regularized (Ridge, Lasso) in practice.

VI. REINFORCEMENT LEARNING FOR GAMES

A. FUNDAMENTALS

Bellman Equations

• Role: Fundamental recursive equations defining the relationship between the value of a state and the values of successor states. They are the cornerstone of dynamic programming and RL.

• For State-Value Function V(s) (expected return from state s under policy π):

$$V_\pi(s) = \sum_{a} \pi(a|s) \sum_{s',r} p(s',r|s,a) \left[ r + \gamma V_\pi(s') \right]$$

• For Action-Value Function Q(s,a) (expected return from taking action a in s):

$$Q_\pi(s,a) = \sum_{s',r} p(s',r|s,a) \left[ r + \gamma \sum_{a'} \pi(a'|s') Q_\pi(s',a') \right]$$

• Key Terms:

  • π(a|s): Policy (probability of taking action a in state s).

  • p(s',r|s,a): Model (transition probability & reward function).

  • γ (gamma): Discount factor (0 ≤ γ ≤ 1), weights immediate vs. future reward.

• Application: Used in Value Iteration and Policy Iteration to compute optimal value functions and policies if the model is known.

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

B. MODEL-FREE RL ALGORITHMS

Q-learning vs. SARSA

• Common Ground: Both are TD control algorithms that learn the optimal action-value function Q*(s,a) without a model.

• Key Difference: On-Policy vs. Off-Policy

  • SARSA: On-policy. Learns Q for the policy being followed (often ε-greedy). Update uses actual next action A_{t+1}.

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right]$$

*   **Q-learning:** **Off-policy.** Learns `Q` for the **greedy policy**, regardless of behavior policy. Update uses **max over next actions**.

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_{a} Q(S_{t+1}, a) - Q(S_t, A_t) \right]$$

• Exploration: SARSA's Q is influenced by exploration (ε-greedy), so it learns values for the exploring policy. Q-learning learns the optimal greedy policy, exploration only affects data collection.

• Game Implication: Q-learning can be more efficient but may be unsafe in risky environments (learns optimal, but exploration might lead to death). SARSA learns a more cautious policy if exploration is random.

Value Iteration and Policy Iteration

• Context: Model-based dynamic programming algorithms. Assume known MDP (p(s',r|s,a)).

• Value Iteration:

  1. Initialize V(s) arbitrarily (e.g., 0).

  2. Repeat until convergence:

$$V_{k+1}(s) \leftarrow \max_a \sum_{s',r} p(s',r|s,a) [r + \gamma V_k(s')]$$

    (Apply Bellman optimality update for `V*`).

3.  Derive greedy policy: `π*(s) = argmax_a Σ p(...)[r + γ V*(s')]`.

*   **Convergence:** Guaranteed. Each iteration improves `V`.

• Policy Iteration:

  1. Policy Evaluation: For current policy π, compute V_π exactly (solve linear system) or iteratively until Δ small.

$$V_{\pi}(s) \leftarrow \sum_{a} \pi(a|s) \sum_{s',r} p(s',r|s,a) [r + \gamma V_{\pi}(s')]$$

2.  **Policy Improvement:** Make policy greedy w.r.t. `V_π`.

$$\pi_{new}(s) = \argmax_a \sum_{s',r} p(s',r|s,a) [r + \gamma V_{\pi}(s')]$$

3.  If `π_new == π` (stable), stop. Else, `π ← π_new` and repeat.

*   **Convergence:** Guaranteed in finite MDPs. Often fewer iterations than Value Iteration but each iteration costlier (policy evaluation).

• Game Application: Solving small, perfect-information games with known dynamics (e.g., solving a simplified combat state MDP).

C. POLICY-BASED METHODS

Policy Gradient Methods

• Fundamentals: Directly parameterize the policy π_θ(a|s) (e.g., with a neural network with softmax output). Optimize parameters θ to maximize expected return J(θ) = E_π[G].

• Objective Function (REINFORCE - Monte Carlo Policy Gradient):

$$J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^T \gamma^t R_t \right]$$

where `τ` is a trajectory.

• Gradient Ascent Update (Intuitive):

$$\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$$

The gradient `∇_θ J(θ)` points in direction of increasing `J(θ)`.

• REINFORCE Gradient Estimate (Monte Carlo):

$$\nabla_\theta J(\theta) \approx \mathbb{E} \left[ \sum_{t=0}^T \nabla_\theta \log \pi_\theta(A_t|S_t) \cdot G_t \right]$$

*   **Interpretation:** Increase probability `π_θ(A_t|S_t)` of actions `A_t` that led to **high returns `G_t`**.

• Application in Games: Essential for continuous action spaces (e.g., steering angle, force magnitude in racing games, robotic manipulation). Used in algorithms like A2C/A3C, PPO, TRPO.

D. ADVANCED RL TOPICS

Generative Adversarial Imitation Learning (GAIL)

• How it differs from standard RL:

  • Standard RL: Agent learns a policy π to maximize hand-specified reward r(s,a).

  • GAIL: Agent learns a policy π to imitate expert demonstrations τ_E without a predefined reward function. It learns the reward function from data.

• Mechanism (Adversarial):

  1. Discriminator D: Trained to distinguish state-action pairs from expert trajectories vs. agent trajectories.

     • Loss: L_D = -E_{τ_E}[log D(s,a)] - E_{π}[log(1-D(s,a))]

  2. Generator (Agent Policy π): Trained to fool the discriminator (generate trajectories that look expert-like). Uses a reward signal from the discriminator: r(s,a) = log D(s,a).

     • Policy gradient update uses this learned reward.

  3. Result: π converges to a policy that produces state-action distributions matching the expert, while D cannot distinguish them (outputs ~0.5).

• Application in Games: Learning NPC behaviors from human gameplay recordings (e.g., driving style in racing game, combat tactics in FPS) without manually crafting reward functions.

Recent Trends in RL Architectures

• Deep RL: Combining deep neural networks with RL (DQN, DDPG, PPO) for high-dimensional state spaces (pixels).

• Hierarchical RL (HRL): Decomposing complex tasks into subtasks using options/meta-controllers. Useful for long-horizon game quests.

• Multi-Agent RL (MARL): Training multiple agents that interact/cooperate/compete (e.g., team-based games, crowd simulation).

• Model-Based RL: Learning the environment model p(s',r|s,a) and using it for planning (e.g., Dreamer, MuZero). More sample-efficient.

• Offline RL (Batch RL): Learning a policy from a fixed dataset of past interactions (crucial for games where online exploration is costly/dangerous).

• Imitation + RL Hybrids: Using demonstrations to initialize or guide RL (e.g., GAIL, DQfD). Reduces sample complexity.

• Meta-RL: "Learning to learn" – agents that adapt quickly to new game tasks or opponents.

VII. ADVANCED DECISION-MAKING MODELS

Fuzzy Time Series Methods

• Concepts: Applies fuzzy logic to time series forecasting. Handles linguistic uncertainty (e.g., "high", "medium" demand) and non-linear relationships.

• Basic Steps:

  1. Fuzzify: Partition universe of discourse into fuzzy sets (e.g., Low, Medium, High) with membership functions.

  2. Fuzzify Observations: Convert crisp historical data F(t) into fuzzy values F_t based on membership degrees.

  3. Establish Fuzzy Logical Relationships (FLRs): Find patterns like "If F_t is A, then F_{t+1} is B".

  4. Forecast: For current state F_t, find all FLRs starting with A, defuzzify the consequent fuzzy sets to get forecast F_{t+1}.

• Application in Predictive Game AI: Forecasting player demand for server resources, predicting in-game economy trends (item prices), modeling player engagement cycles.

Markov Chains

• Basics: Stochastic model describing a sequence of states where the probability of next state depends only on the current state (Markov Property).

• Components:

  • States: S = {s1, s2, ..., sn}

  • Transition Matrix P: P[i][j] = P(S_{t+1}=s_j | S_t=s_i). Rows sum to 1.

  • Initial State Distribution π_0

• Use in State Transition Modeling:

  • Player State Transitions: Model flow between game states (menu → playing → paused → quit).

  • NPC Behavior States: Simplified FSM with probabilistic transitions (e.g., Patrol → Chase with probability 0.3 if player seen).

  • Weather/Environment Cycles: Day/night, weather patterns in open-world games.

• Analysis: Find steady-state distribution (long-term probability of being in each state) by solving π = πP.

Fuzzy-Markov Hybrid Approaches

• Integration: Combines fuzzy logic's ability to handle vague, linguistic concepts with Markov chains' ability to model stochastic state transitions.

• Typical Structure (e.g., Fuzzy Markov Chain):

  1. States are Fuzzy: Each "state" is defined by a fuzzy set (e.g., Low_Population, Medium_Population).

  2. Transitions are Probabilistic: Transition probabilities between these fuzzy states are estimated from data.

  3. Observation/Measurement is Fuzzy: Current system state is inferred from noisy/crisp observations via fuzzy membership.

• Application in Uncertainty Handling for Game AI:

  • Dynamic Difficulty Adjustment: Model player "frustration" or "skill" as fuzzy states (Very Frustrated, Engaged, Bored). Transitions depend on game events (deaths, successes). AI adjusts difficulty based on current fuzzy state.

  • Traffic/ Crowd Simulation: Agent "intent" (shopping, commuting) as fuzzy states. Transitions influenced by environment (time, location).

  • Predictive Maintenance (Server Games): Server "health" as fuzzy states (Healthy, Degrading, Failing). Transitions based on metrics (CPU, memory usage).

VIII. GAME AI ARCHITECTURE AND DESIGN

Model of Game AI

• Overall Architecture: Typically a layered or component-based system.

  1. Perception Layer: Gathers world state (sensors, raycasts, game events). Outputs world model.

  2. Decision Layer: Core reasoning. Uses techniques from this unit:

     • Strategic/Long-term: Game Theory, MCTS, Planning (for RTS).

     • Tactical/Medium-term: Behavior Trees, FSMs, Utility Systems.

     • Operational/Short-term: Rule-Based Systems, Decision Trees, RL Policies.

  3. Movement/Animation Layer: Executes decisions. Uses pathfinding (A*), steering behaviors, animation controllers (FSM/BT for animations).

  4. World Interaction Layer: Sends commands to game engine (move, attack, use item).

• Integration: Data flows upward from perception → decision → execution. Blackboard architectures (shared data space) are common for decoupling modules.

Application-Specific Theories (Practical Use)

• Decision Trees in Game Development:

  • Runtime: Lightweight, interpretable rules for simple NPC decisions (e.g., "If health < 30% AND enemy visible → flee").

  • Design-Time/Offline: Analyze player data to discover decision patterns, segment players, balance game mechanics.

• Board Game Theory Implementation:

  • Minimax + Alpha-Beta: Chess, Checkers, Othello engines.

  • Monte Carlo Tree Search (MCTS): Go, Hex. Simulates random playouts from current state.

  • Endgame Tablebases: Precomputed perfect play for late-game positions (Chess 6-piece, Checkers solved).

• Motor Learning Stages in Character AI:

  • Cognitive (Scripted): Initial implementation using hard-coded animations/steering.

  • Associative (Parameter Tuning): Adjusting animation blend times, steering force weights, jump heights via designer input or simple optimization.

  • Autonomous (Learning-Based): Using Reinforcement Learning (Policy Gradient, PPO) or Motion Matching to let the AI discover natural, robust movement from motion capture data or through self-play.

[!TIP] Final Exam Strategy: For "Model of Game AI" or "Application-Specific Theories", structure your answer by listing the theory, briefly defining it, and giving ONE concrete, specific game example (e.g., "Behavior Trees are used in Halo for squad AI, where a Selector node chooses between Combat, Cover, and Grenade throw subtrees").