UNIT 1: AI IN GAMING - EXAM-FOCUSED SHORT NOTES

Introduction to Unit 1

This unit forms the foundational core of game AI, covering classical search, decision-making architectures, and introductory machine learning. Past papers heavily emphasize comparative analysis (e.g., FSM vs. Behavior Trees, Bagging vs. Boosting, Q-Learning vs. SARSA) and problem-solving (e.g., entropy calculation, payoff matrix solutions, algorithm implementation).

I. GAME THEORY AND STRATEGIC DECISION-MAKING

Fundamentals of Game Theory

• Definition: The study of mathematical models of strategic interaction among rational decision-makers (players). In gaming AI, it models NPC vs. NPC or NPC vs. Player scenarios.

• Core Concepts:

  • Players: The decision-making agents.

  • Strategies: The complete plan of action for a player.

  • Payoff/Utility: The numerical reward a player receives from an outcome.

  • Zero-sum vs. Non-zero-sum: In zero-sum, one player's gain is the other's loss (e.g., chess). Most real games are non-zero-sum.

Minimax Algorithm

• Purpose: A recursive algorithm for choosing the optimal move in a two-player, zero-sum game, assuming the opponent plays optimally.

• Working Mechanism:

  1. The algorithm explores the game tree to a certain depth.

  2. At max nodes (AI's turn), it selects the move with the maximum value.

  3. At min nodes (opponent's turn), it assumes the opponent will select the move with the minimum value (worst-case for AI).

  4. Values are propagated back up the tree.

• Key Components:

  • Evaluation Function (f(n)): Estimates the "goodness" of a non-terminal board state. Design is critical.

  • Depth Limitation: Prevents exponential blow-up. Leads to the horizon effect (missing threats just beyond the search depth).

• Alpha-Beta Pruning: An optimization that prunes branches of the tree that cannot influence the final decision, significantly reducing nodes evaluated without affecting the result.

[!TIP] Exam Focus: Be prepared to draw the minimax tree for a small example (e.g., tic-tac-toe) and show alpha-beta pruning.

Payoff Matrices and Nash Equilibrium

• Payoff Matrix: A tabular representation of payoffs for all combinations of players' pure strategies.

  • Rows: Player A's strategies.

  • Columns: Player B's strategies.

  • Entry (a_ij): (Payoff_A, Payoff_B).

• Pure Strategy Equilibrium: A cell where no player can improve their payoff by unilaterally changing strategy. (Row player's entry is max in its column; column player's entry is min in its row).

• Mixed Strategy Equilibrium: Players randomize over strategies to make the opponent indifferent. The expected payoff is equal for all strategies used with non-zero probability.

• Nash Equilibrium (NE): A set of strategies (pure or mixed) where no player has an incentive to deviate given the other player's strategy.

  • Calculating 2x2 NE (Penalty Kick Example):

    Let p = probability Kicker chooses Left. Goalie chooses Left with q.

    Kicker's expected payoff for Left: E(L) = q*1.4 + (1-q)*1.7

    Kicker's expected payoff for Right: E(R) = q*1.5 + (1-q)*1.5 = 1.5

    For indifference: E(L) = E(R) → 1.4q + 1.7 - 1.7q = 1.5 → -0.3q = -0.2 → q = 2/3.

    Similarly, solve for Goalie's indifference to find p. The NE is (p*, q*).

[!TIP] Common Pitfall: Forgetting that in a mixed strategy NE, each player must be indifferent between the strategies they randomize over.

II. SEARCH AND PATHFINDING ALGORITHMS

Breadth-First Search (BFS)

• Implementation: Explores all nodes at the present depth before moving to nodes at the next depth level. Uses a FIFO queue.

• Properties:

  • Complete: Yes (if branching factor is finite, finds solution if one exists).

  • Optimal: Yes, for unweighted graphs (finds shortest path in terms of number of steps).

  • Time/Space Complexity: O(b^d), where b is branching factor, d is solution depth. High memory usage.

A Search Algorithm*

• Core Idea: Best-first search that uses a heuristic function h(n) to guide the search towards the goal more efficiently than BFS.

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

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

  • h(n): Admissible heuristic (never overestimates the true cost to goal).

• Admissibility & Optimality: If h(n) is admissible and consistent (monotone), A* is optimal and complete.

• Common Heuristics for Grids:

  • Manhattan Distance: For 4-direction movement. h = |dx| + |dy|.

  • Euclidean Distance: For 8-direction movement. h = sqrt(dx² + dy²).

  • Octile Distance: For 8-direction with different costs for cardinal/diagonal moves.

[!TIP] Exam Example: Given a grid with obstacles, manually expand A* nodes, showing g, h, and f values for each.

Efficiency in Complex Problems

• Challenge: The combinatorial explosion in state space makes exhaustive search (like BFS) infeasible for large problems.

• Heuristic Trade-offs:

  • Admissible vs. Inadmissible: Admissible heuristics guarantee optimality but may be less informed. Inadmissible heuristics (e.g., h=0 is BFS) can be faster but sacrifice optimality.

  • Heuristic Strength: A more informed heuristic (closer to true cost) reduces the number of nodes expanded.

  • Memory vs. Time: A* is optimal but memory-intensive. Algorithms like IDA* (Iterative Deepening A*) trade memory for time.

III. AI BEHAVIOR REPRESENTATION AND CONTROL

Rule-Based Systems

• Architecture: Condition-Action (IF-THEN) rules stored in a Rule Base. An Inference Engine matches conditions against the current state (Working Memory) and fires applicable rules.

• Components:

  1. Rule Base: IF <condition> THEN <action>.

  2. Working Memory: Current state facts.

  3. Conflict Resolution Strategy: Determines which rule to fire if multiple are applicable (e.g., specificity, recency).

• Example (Guard AI):

  • IF (ThiefDetected == true) AND (ThiefStrength > MyStrength) THEN Action = FLEE

  • IF (ThiefDetected == true) AND (ThiefStrength <= MyStrength) THEN Action = FIGHT

  • IF (ThiefDetected == false) THEN Action = PATROL

3D Representations: Static vs. Kinematic

Coordinated Movement

• Goal: Create believable, non-robotic movement for agents.

• Components:

  1. Steering Behaviors: Forces applied to achieve a goal (e.g., Seek, Flee, Arrive, Wander, Obstacle Avoidance, Path Following).

  2. Path Following: Following a pre-calculated path (from A*). Uses a look-ahead point on the path to steer towards.

  3. Collision Avoidance: Predictive steering to avoid future collisions with other agents or obstacles (e.g., ORCA - Optimal Reciprocal Collision Avoidance).

  4. Group Movement: Flocking (separation, alignment, cohesion) or formation keeping.

• Algorithm Structure: DesiredVelocity = (TargetPosition - CurrentPosition).normalize() * MaxSpeed → Apply steering force to adjust current velocity → Update position.

Motor Learning (Animation)

• Stages: A process to create smooth, responsive character motion from high-level AI commands.

  1. Motor Control: AI issues a command (e.g., "move to point X", "attack").

  2. Motion Synthesis: System selects or blends motion clips (e.g., walk, run, turn-left) or procedurally generates motion (e.g., inverse kinematics for foot placement).

  3. Motor Execution: The selected motion is played back, often with procedural adjustments (e.g., root motion, IK for feet/hands) to match the exact desired velocity/position.

• Application: Bridges the gap between discrete AI decisions (FSM state change) and continuous, fluid animation.

IV. DECISION-MAKING ARCHITECTURES

Finite State Machines (FSM)

• Construction: A model with a finite number of states, transitions between them, and actions associated with states/transitions.

• Design Principle: Each state represents a distinct behavior or mode (e.g., PATROL, CHASE, ATTACK, FLEE). Transitions are triggered by events or conditions.

• Guard/Thief Example:

  
  [GUARD] --(Thief Seen & Strong)--> [FLEE]
  
  [GUARD] --(Thief Seen & Weak)--> [FIGHT]
  
  [FIGHT] --(Losing)--> [FLEE]
  
  [FLEE] --(Safe)--> [GUARD]
  
  [GUARD] --(No Thief)--> [GUARD] (Self-loop/Patrol)
  
  

• Limitations: Can become a "spaghetti code" of transitions for complex agents. Hard to reuse behaviors.

Behavior Trees (BT)

• Structure: A tree of nodes that control the flow of execution. Traversal is typically tick-based (from root every update).

• Common Node Types:

  • Selector (?): Ticks children in order until one succeeds. Fails if all fail. (Fallback/priority).

  • Sequence (→): Ticks children in order until one fails. Succeeds if all succeed. (Conditional AND).

  • Condition Node: Checks a game state (e.g., IsThiefVisible?). Returns Success/Failure.

  • Action Node: Executes a behavior (e.g., MoveTo, Attack). Returns Success/Running/Failure.

• Advantages over FSM:

  • Hierarchical & Modular: Easy to build complex behaviors from simple subtrees.

  • Reusability: Subtrees (e.g., "Find Cover") can be reused across different agents.

  • Readability: Flow is clearer in a tree diagram than in a state transition diagram with many states.

  • Dynamic Replanning: Can be interrupted and re-ticked from root, allowing reactivity.

[!TIP] Key Difference: FSM is state-centric (what state am I in?). BT is task-centric (what do I need to do next?).

Flowchart-Based AI Design (Context: Fuzzy & Markov)

• Average-Based Fuzzy Time Series: Uses fuzzy logic to handle uncertainty in state transitions. Instead of sharp thresholds (e.g., health < 30% → FLEE), it uses fuzzy sets (e.g., health is "Low" with degree 0.7). Transition probabilities are weighted averages of fuzzy membership values.

• Markov Chains with Modified Frequency Partitioning:

  • Standard Markov Chain: Next state depends only on current state (P(next|current)).

  • Modified Frequency Partitioning: The state space is partitioned not just by discrete states, but by features (e.g., (HealthLevel, DistanceToEnemy)). Transition probabilities are learned from gameplay data by counting frequency of moving from one feature partition to another. Allows for more generalized policies.

V. MACHINE LEARNING FOR GAME AI

Decision Trees

• Goal: Learn a tree structure that classifies instances (game states) or predicts outcomes by splitting data on feature values.

• Key Metrics:

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

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

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

    \boxed{H(S) = 0 \text{ (pure)}, H(S) = 1 \text{ (max impurity for binary)}}

*   **Information Gain (`IG`):** The **reduction in entropy** achieved by 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 the subset of `S` where attribute `A` has value `v`.

    \boxed{\text{Choose split with highest } IG}

• Recursive Induction (ID3/C4.5):

  1. Start with all training data at root.

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

  3. Else, select the attribute with highest IG.

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

  5. Recurse on each branch's subset.

• Handling Noisy Data & Overfitting:

  • Pruning: Remove branches that provide little predictive power (pre-pruning: stop early; post-pruning: grow full tree then trim).

  • Minimum Samples per Leaf: Don't split if a node has too few instances.

  • Use Continuous Attributes: Discretize or use thresholds.

  • Ensemble Methods: Use multiple trees (see below).

[!TIP] Exam Calculation: Given a small dataset (like the Credit Score example), calculate entropy for the target, then IG for each attribute step-by-step. Show p_i fractions clearly.

Ensemble Methods

• Random Forest Algorithm:

  1. For b = 1 to B (number of trees):

     • Draw a bootstrap sample from training data.

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

  2. Final prediction = majority vote (classification) or average (regression) of all trees.

• Why More Robust? Ensemble methods average out noise and individual model biases/variances. A single tree might overfit; a forest of diverse trees generalizes better by capturing different patterns.

Neural Networks (Multi-Layer Perceptron - MLP)

• Architecture:

  • Input Layer: One neuron per feature.

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

  • Output Layer: Number of neurons depends on task (1 for binary, k for k-class classification).

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

• Learning Process (Backpropagation):

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

  2. Compute Loss: Compare output ŷ with true label y using a loss function (e.g., Cross-Entropy, MSE).

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

  4. Weight Update: Use Gradient Descent (or variant like Adam) to update parameters:

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

    where `η` is the **learning rate**.

• Role in Games: Function approximation for value functions (RL), complex policy networks, NPC behavior classification.

Least Squares Methods

• Application: Primarily for regression tasks in game AI (e.g., predicting player score based on actions, fitting a curve to in-game economy data).

• Linear Least Squares: Finds coefficients β that minimize the sum of squared residuals between observed y and predicted ŷ = Xβ.

  Solution (Normal Equation):

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

\boxed{\text{Closed-form solution for linear regression.}}

• In Games: Used in linear function approximation for value functions (e.g., in RL when state space is too large for tabular methods). Features φ(s) are multiplied by weights w to estimate V(s) ≈ w^T φ(s).

VI. REINFORCEMENT LEARNING FOR GAME AI

Fundamental Concepts

• Markov Decision Process (MDP): Formal framework defined by (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'): Reward received.

  • γ: Discount factor [0,1], weights future vs. immediate reward.

• Policy (π): A mapping from states to actions (π(a|s)). The agent's strategy.

• Value Functions:

  • State-Value: Vπ(s) = Expected discounted return starting from state s and following π.

  • Action-Value: Qπ(s,a) = Expected return starting from s, taking a, then following π.

Bellman Equations

• Context: Recursive definitions of value functions based on the MDP structure. They are the foundation for all RL algorithms.

• Bellman Expectation Equations:

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

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

• Bellman Optimality Equations (for optimal V*, Q*):

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

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

\boxed{\text{Optimal policy } \pi^*(s) = \arg\max_a Q^*(s,a)}

Value-Based Methods

[!TIP] Crucial Difference: In Q-Learning, the max over next actions makes it greedy w.r.t. the learned Q-values. In SARSA, the update uses the actual next action, so it accounts for exploration.

Policy-Based Methods

• Policy Gradient: Directly parameterize the policy π(a|s, θ) (e.g., using a neural network with softmax output). Optimize the expected return J(θ) by gradient ascent:

$$\nabla_\theta J(\theta) \approx \mathbb{E}[\nabla_\theta \log \pi(a|s,\theta) \cdot G_t]$$

where `G_t` is the actual return from time `t`.

• Basic Approach: Sample trajectories, compute returns, adjust θ to increase probability of actions that led to high returns.

• Advantage: Can learn stochastic policies (good for exploration, multi-agent) and handle continuous action spaces more naturally than value-based methods.

Advanced RL Topics

• Temporal Difference (TD) Learning vs. Monte Carlo (MC):

  | TD Learning (Q, SARSA) | Monte Carlo | | :--- | :--- | | Bootstraps: Updates estimate based on other estimates (r + γ Q(s')). | Awaits termination: Updates only after complete episode using actual return G_t. | | Can learn online, from incomplete sequences. | Must wait for episode end. | | Lower variance (uses model estimate), but biased. | Unbiased (uses true sample mean), but higher variance. | | Works in continuing tasks. | Requires episodic tasks. |

• Generative Adversarial Imitation Learning (GAIL) vs. Standard RL:

  • Standard RL: Agent learns a policy to maximize a given reward signal R(s,a).

  • GAIL: Agent learns a policy to imitate expert demonstrations without a predefined reward. Uses a discriminator (like in GANs) that tries to distinguish agent trajectories from expert trajectories. The agent's reward is the discriminator's "real/fake" score. Goal: Match the expert's behavioral distribution, not just maximize a hand-designed reward.

• Recent Trends in RL Architectures:

  • Deep RL: Combining deep neural networks with RL algorithms (DQN, DDPG, PPO, SAC). Handles high-dimensional state/action spaces.

  • Multi-Agent RL (MARL): Training multiple agents that interact. Challenges: non-stationarity, credit assignment, scalability.

  • Hierarchical RL (HRL): Decomposing complex tasks into sub-policies (options) at different temporal abstractions.

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

VII. INTEGRATED GAME AI MODELS

Model of Game AI (Comprehensive Framework)

A modern game AI system is layered and hybrid:

1. Perception Layer: Sensors, raycasts, hearing models. Provides world state.

2. Decision-Making Layer: Architecture core (often a Behavior Tree or Utility-based system). May use ML models (e.g., a neural network policy) for specific sub-tasks.

3. Movement & Animation Layer: Pathfinding (A*), steering behaviors, motor control (animation blending, IK).

4. World Model: Internal representation of the game state (often simplified/abstracted from the full game world).

5. Learning Layer (Optional): RL agent or online adaptation system that modifies parameters of the decision or movement layers based on experience.

[!TIP] Integration Principle: Traditional AI (FSM/BT/Pathfinding) provides reliable, predictable, debuggable core behavior. ML/RL is used for specific, complex, or adaptive tasks (e.g., combat tactics, racing lines, dynamic difficulty) where hand-coding is infeasible.

Application-Specific Topics (Synthesis)

• Decision Trees in Game Dev Pipelines: Used during design/analysis (e.g., modeling player decision trees for quests, balancing item choices). Less common for runtime NPC AI due to static nature; often replaced by BTs or utility systems.

• Board Game AI Implementation:

  • Perfect Information Games (Chess, Go): Minimax with alpha-beta is standard. Monte Carlo Tree Search (MCTS) is dominant for large state spaces (Go). Neural networks often used to guide MCTS (AlphaGo).

  • Imperfect Information Games (Card games): Requires belief states (probability distribution over opponent's hand). Algorithms like CFR (Counterfactual Regret Minimization) are used.

• Integration of ML/RL with Traditional Game AI:

  • Hybrid Approach: Use a BT for high-level mission logic, but have a leaf node that calls an RL policy for a complex sub-task (e.g., "Engage Enemy" node uses a DQN for precise movement and shooting).

  • Offline Learning: Use Imitation Learning (like GAIL) to train a policy from designer playtests or expert data, then deploy it as a black-box behavior module.

  • Online Adaptation: Use RL to tune parameters of a utility system or FSM transition thresholds based on player performance data.

Final Exam Strategy: When answering, first define the term/concept clearly, then explain its structure/mechanism, and finally provide a specific game-related example or comparison. For calculation questions (entropy, payoff matrices), show all steps and box the final answer. For architecture questions (FSM, BT), draw a simple diagram and label components. Always connect back to why it's used in games (performance, predictability, believability, scalability).