Real-time AI in Video Games: decisive & collaborative actions

Contents

• Introduction and overview
• 0. Refresher: graphs, priority queues, probability
• 1. The game loop and the real-time budget
• 2. Navigation: grids, navmesh, A*
• 3. Behaviors: state machines, behavior trees, utility
• 4. Collective decisions: steering, boids, formations
• 5. Performance, profiling and budgets
• 6. Monte-Carlo Tree Search: deciding in a few ms
• 7. Learned agents: RL and self-play in games
• 8. Cooperative and multi-agent games
• 9. Conversational NPCs (LLMs) and anti-cheat
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: an engineer with ~10 years of experience who wants game AI that fits a frame budget (pathfinding, BT, MCTS, learned agents). Empirical first: A* that stutters with 100 NPCs; MCTS that blows the tick; an LLM that freezes the main thread — then we name the game loop, AI LOD, budgets and profiling.

This module studies the decisional AI of video games: how an agent perceives, decides and acts when the game loop grants it only a few milliseconds per frame. Navigation, behaviors, tree search, learned agents and conversational NPCs meet here under a strict compute budget — which makes video games a demanding playground for the master’s decisional AI. It is also a domain where algorithmic decision-making and learning mix at every moment, in a system where everything shows on screen.

What you will be able to do

• Break down a game loop and allocate a compute budget among perception, decision and action.
• Choose a representation of space (grid, navmesh) and implement A* on it with a suitable heuristic.
• Design agent behaviors with state machines, behavior trees and utility systems.
• Program emergent collective decisions: steering, boids, formations.
• Implement Monte-Carlo Tree Search to decide in a few milliseconds.
• Articulate scripted agents and learned agents (RL, self-play) and balance their mix according to the budget.
• Integrate an LLM into a conversational NPC, together with the associated anti-cheat challenges.
• Profile a game AI and meet quantified performance budgets.

Official objectives and syllabus (2026-2027 catalog)

No 2026-2027 SynapseS sheet matches this module: the LLGA 1 - S2 track includes no video-game or real-time AI course unit. The official objectives, the exact period, the language and the assessment methods are therefore not communicated; the retained framing is that of the MSc&T brochure (36 h, 4.5 ECTS). The following table maps the brochure themes — the only “official” source available — to the sections of these materials.

Where this course fits in the program

A period-2 slot announced by the MSc&T brochure (36 h, 4.5 ECTS) but absent from the 2026–27 LLGA lists (slot TBC): these notes are kept for reference. Official prerequisites: not communicated (no SynapseS sheet for this module).

The course builds on the algorithmics refresher of the Refresher in Computer Science module — graphs, priority queues, amortized complexity — reactivated in chapter 0, with Hoeffding’s inequality from Machine Learning; the Reinforcement Learning and Autonomous Agents module, taken in parallel in P2, sheds light on the chapter devoted to learned agents.

Downstream, conversational NPCs prepare the question of agents in the Large Language Models module (M2), and the discipline of real-time budgets reappears in ML Ops and LLM Engineering Principles, where LLM inference faces the same latency constraints.

Course outline

• Refresher: graphs, priority queues, probability — the algorithmics and probability groundwork put back in hand before any real-time use.
• The game loop and the real-time budget — the architecture that governs everything else: a finite time per frame, to be split among the AI building blocks.
• Navigation: grids, navmesh, A* — representing traversable space and planning correct, inexpensive paths in it.
• Behaviors: state machines, behavior trees, utility — the major families of decision architectures for an individual NPC.
• Collective decisions: steering, boids, formations — producing convincing group behaviors through simple local rules.
• Performance, profiling and budgets — measuring, locating bottlenecks and reporting back in milliseconds.
• Monte-Carlo Tree Search: deciding in a few ms — stochastic tree search for perfect-information games, constrained by the budget.
• Learned agents: RL and self-play in games — what reinforcement learning brings to game agents, and at what cost, with a self-play lab sheet.
• Cooperative and multi-agent games — coordinating several agents whose objectives intertwine, from cooperation to negotiation.
• Conversational NPCs (LLMs) and anti-cheat — hooking a language model to a character within a latency budget, without opening the door to cheating.
• Exercises — targeted implementations for each building block, from A* to MCTS.
• Projects and assessment — proposed solo and group projects, a written exam and a rubric (no official modality is displayed).
• References — the sources underlying each chapter.

Session plan

36 h in class = 12 sessions of 3 h. The volume is the 36 h announced for this module by the MSc&T brochure — an announced volume, with no SynapseS sheet yet (the 2026–2027 catalogue has no matching course unit); no session-by-session programme is published, so the split below is our proposal for covering these notes in that time. Level 1 = foundations (reviews, definitions, first algorithms), 2 = core game-AI techniques, 3 = advanced material (multi-agent learning, recent research on LLM agents); the level never goes down from one session to the next.

Self-study, outside the 36 h: none — every chapter is covered in class; the project (Ex. 12 or a subject of the Projects and assessment section) is the personal work expected alongside.

How to study this module

• Start with the refresher chapter: A* and priority queues come back in almost all subsequent chapters.
• Implement A* and then MCTS yourself at least once, without a library, before trying to optimize.
• Measure everything in milliseconds: every building block must be visible in a profile, not by feel.
• Set yourself a constant tick budget and fit every improvement within it — that is the spirit of the course.
• Cross-reference with the reinforcement learning module of the same period: learned agents are its direct application.
• Analyze the games you know as decisional systems: spotting behaviors and their compute limits in them is the best training.

0. Refresher: graphs, priority queues, probability

Pathfinding, tree search and simulation all rest on a few algorithmic and probabilistic tools from L3. This chapter lists them and explains why games, with their hard time limits, are a demanding test bench for decision-making AI.

Why a “games” module in an AI master’s program? Because video games are the AI environment with the purest constraints: decide well, in a few milliseconds, with bounded memory, for dozens of agents at once. The same trade-offs reappear in robotics, trading, embedded systems — and games provide reproducible test benches that have produced some of the greatest breakthroughs in AI (chapters 6 and 7).

The course’s subtitle — decisive & collaborative actions — announces the two axes: deciding (individually, chapters 3 and 6) and acting together (chapters 4 and 8).

1. The game loop and the real-time budget

Everything a game computes must fit between two displayed frames. This chapter describes the loop that organizes that computation, how much time it leaves to the AI, and the two architectural choices — fixed time step and entity-component systems — that keep it predictable.

1.1. Fixed timestep and accumulator

DT = 1.0 / 30.0            # fixed simulation step (30 Hz)
acc, last = 0.0, now()
while not quit:
    t = now()
    acc += t - last
    last = t
    k = 0
    while acc >= DT and k < 5:      # anti-"spiral of death" bound
        for entity in world: entity.tick(DT)   # AI, physics, etc.
        acc -= DT
        k += 1
    render(alpha=acc / DT)          # visual interpolation between states

1.2. ECS: separating data and processing

Benefits for real-time AI:

• the queries “all entities with Position and ActiveAI” become traversals of contiguous arrays (cache-friendly; see data-oriented design);
• AI systems plug into the loop like ordinary systems, with their own budget;
• composition replaces inheritance — a “chasing and shooting enemy” = Chasing + Shooting components, reused by other types of agents.

The architecture popularized by the Overwatch GDC talk (2017) is now the pattern of modern engines (Unity DOTS, Bevy, EnTT; the concept goes back to the first “component”-based games, around Dungeon Siege, 2002).

2. Navigation: grids, navmesh, A*

An NPC that must reach a point needs a map of where it can walk and a fast way to find a short route on it. This chapter compares the map representations used in games, proves when A* returns an optimal path, and shows how it is scaled to many agents.

2.1. Representing navigable space

The navmesh is the industry standard: a path is searched polygon to polygon (visibility graph between centers / shared edges), then smoothed (the funnel algorithm to cut corners). Automatic generation by voxelization + navigable regions was popularized by the open-source library Recast/Detour (Mikko Mononen), integrated into most engines.

2.2. A* with an admissible heuristic

import heapq

def a_star(grid, start, goal):              # grid: dict {(x,y): cost}, or None = wall
    def h(p):                              # octile heuristic
        dx, dy = abs(p[0]-goal[0]), abs(p[1]-goal[1])
        return 1.4142*min(dx, dy) + (max(dx, dy) - min(dx, dy))
    open_, g = [(h(start), 0.0, start)], {start: 0.0}
    came = {}
    while open_:
        f, g_n, n = heapq.heappop(open_)
        if n == goal:                      # path reconstruction
            path = [n]
            while n in came: n = came[n]; path.append(n)
            return path[::-1]
        if g_n > g.get(n, float("inf")):   # stale entry: skip
            continue
        for dx, dy, c in ((1,0,1.0),(-1,0,1.0),(0,1,1.0),(0,-1,1.0),
                          (1,1,1.4142),(1,-1,1.4142),(-1,1,1.4142),(-1,-1,1.4142)):
            v = (n[0]+dx, n[1]+dy)
            if v not in grid: continue     # wall / off the map
            nv = g_n + c * grid[v]         # terrain: forest = 2.0, etc.
            if nv < g.get(v, float("inf")):
                g[v] = nv; came[v] = n
                heapq.heappush(open_, (nv + h(v), nv, v))
    return None                            # unreachable

2.3. At scale: hierarchies and amortization

• HPA* (2004): split the map into clusters, precompute paths at boundaries, search in the abstract graph then refine locally — order-of-magnitude gains for a near-optimal path;
• asynchronous paths: the request goes into a queue processed at a fixed budget per frame (N nodes expanded/frame); the NPC follows its old path while waiting — hence the importance of the fallback “straight ahead” behavior;
• local avoidance: the global path does not handle NPC-NPC collisions; the RVO/ORCA models (velocity obstacles) compute a collision-free velocity over a one-second horizon — the local layer, applied every frame, relies on the global path as a rail;
• crowds: beyond a few hundred agents, continuous flow simulations (density grid) rather than individuals — see chapter 5 for the budget.

3. Behaviors: state machines, behavior trees, utility

Once an NPC can move, it must choose what to do — patrol, chase, flee — and switch at the right moment. This chapter presents the three decision architectures used in industry and what each one makes easy or hard.

3.1. Finite state machines (FSM)

The FSM is the oldest and most readable of tools — the ghosts of Pac-Man (1980) are a textbook example (chase, scatter and frightened modes, switched by timers and power pellets; the four ghosts differ mainly in their chase targets), and the guards of the Metal Gear series or the units of Warcraft are archetypes of it.

Its limit is well known: the combinatorial explosion of transitions as soon as states are added (20 states ⇒ up to 400 transitions to maintain), and “siloed” behaviors (an NPC cannot patrol and listen for a noise at the same time). Hence the extensions: hierarchical FSMs (states composed of other FSMs — fleeing contains “find cover” then “run”), and above all:

3.2. Behavior trees (BT)

# Minimal behavior tree: composites + actions by hand
class Node:
    SUCCESS, FAILURE, RUNNING = "S", "F", "R"
    def tick(self, agent): raise NotImplementedError

class Action(Node):
    def __init__(self, name, fn): self.name, self.fn = name, fn
    def tick(self, agent): return self.fn(agent)      # "S"/"F"/"R"

class Sequence(Node):                                # AND: first failure stops
    def __init__(self, *children): self.children = children
    def tick(self, agent):
        for c in self.children:
            r = c.tick(agent)
            if r != Node.SUCCESS: return r
        return Node.SUCCESS

class Selector(Node):                                # OR: first success wins
    def __init__(self, *children): self.children = children
    def tick(self, agent):
        for c in self.children:
            r = c.tick(agent)
            if r != Node.FAILURE: return r
        return Node.FAILURE

# --- usage: a combined guard ---------------------------------------------
bt = Selector(
    Sequence(Action("hurt?",      lambda a: Node.SUCCESS if a.hp < 30 else Node.FAILURE),
             Action("flee",       lambda a: a.flee() or Node.SUCCESS)),
    Sequence(Action("sees enemy?", lambda a: Node.SUCCESS if a.neighbor() else Node.FAILURE),
             Action("attack",     lambda a: a.attack())),   # returns RUNNING while...
    Action("patrol", lambda a: a.patrol()))
# every frame: bt.tick(agent) — the "hurt" branch interrupts "patrol".

3.3. Utility AI: deciding with continuous scores

4. Collective decisions: steering, boids, formations

Groups — flocks, crowds, squads — would be far too costly to plan agent by agent. This chapter shows how simple local rules, computed for each agent from its neighbors only, produce smooth motion and coherent group behavior.

4.1. Steering behaviors

4.2. Boids: three local rules, one global behavior

Reynolds’ boids model (1987) simulates bird flocks with, per individual, three forces computed on its neighbors \mathcal{N}(i) (perception radius r, possibly anisotropic):

1. Separation: s_{\mathrm{sep}} = \sum_{j \in \mathcal{N}(i)} \frac{p_i - p_j}{\|p_i - p_j\|^2} — each term points from neighbor j toward i, away from the neighbor, with magnitude 1/\|p_i - p_j\|: the closer the neighbor, the stronger the push. Variants use magnitude 1/d^2, or sum only over a separation radius smaller than r;
2. Alignment: s_{\mathrm{ali}} = \bar v_{\mathcal{N}(i)} - v_i — adopt the average velocity of the neighbors;
3. Cohesion: s_{\mathrm{coh}} = \bar p_{\mathcal{N}(i)} - p_i — move toward the local center of mass.

The acceleration is a weighted blend of the three (plus seek toward a possible leader); no global variable exists: the flock is an emergent behavior.

This result — “three local rules produce a coherent group” — is the gateway to collective AI: we program the individuals, we get the crowd.

The same engine drives schools of fish, zombie hordes (to be mixed with the flow navigation of chapter 2), swarms of projectiles… The number of neighbors to consider is bounded (computational parsimony: neighborhood query by spatial partitioning — see chapter 5, and Image Analysis and Computer Vision, ch. 4 for kd-trees).

4.3. Formations: slots and the virtual leader

5. Performance, profiling and budgets

The previous chapters each assumed a small time budget; this chapter shows how such a budget is set, measured and enforced for the whole AI, and why determinism of the simulation pays off in testing and networking.

5.1. Where does the time go?

5.2. Profiling

• frame traces: time every system per frame and display the time series (Tracy, Optick, engine instrumentation); look for spikes (P99), not the average;
• cache misses: on console/embedded, the memory hierarchy dominates; measure instructions per cycle (IPC); sorting arrays for locality often beats a “smarter algorithm” on pointers;
• allocation: zero allocation in the game loop — pre-allocated object pools (the path queues of chapter 2 reuse their nodes);
• performance tests: an automated reference scene (“200 NPCs in a crowd + 20 in combat”) in continuous integration — the perf regression is caught at commit time, not at master.

5.3. Determinism, replays and networking

Determinism (chapter 1) makes possible:

• replays (store the inputs, not the state — a few KB per minute);
• lockstep simulation (RTS: only orders travel, all clients simulate identically);
• AI non-regression tests (the same scenario must produce the same behavior after a code change).

It requires: fixed step, no iteration over unordered containers with unstable hashing, fixed-point or strictly specified floating-point arithmetic, seeded random generators. It is a team discipline — and it pays off everything else in the module.

6. Monte-Carlo Tree Search: deciding in a few ms

When the right move depends on what the opponent will answer, fixed rules are not enough: the agent must look ahead. This chapter presents Monte-Carlo Tree Search, which estimates the value of each move by random play-outs and can be stopped at any moment with a usable answer.

6.1. The bandit reminder: UCB1

6.2. The MCTS loop

6.3. MCTS in real time: engineering tricks

• budget: one limits by iterations or by time (e.g. 5 ms per decision); the tree is reused at the next move (the sub-tree of the played move becomes the root);
• random rollouts too weak: replace the default policy with a learned policy or a light heuristic (dominations, patterns); or truncate and evaluate with a value function — this is the bridge toward AlphaZero (chapter 7);
• huge branching factor (continuous games, real time): progressive widening: allow only \lceil k\,N^\alpha \rceil children per node (α ≈ 0.5); in real time: “determinized” MCTS over sampled futures (imperfect-information games);
• interruptibility: MCTS is “anytime” — quality grows with the budget, and an interrupted decision remains playable (take the most visited action): perfect for the tick of chapter 1.

7. Learned agents: RL and self-play in games

Instead of writing the behavior by hand, an agent can learn it by playing millions of games. This chapter recalls the reinforcement-learning framework, explains self-play and its pitfalls, and lists where studios actually use learned agents.

7.1. The RL framework, recapped in one table

7.2. Self-play: building your own training curriculum

Three famous pitfalls:

• the exploit race (the agent discovers a pathological strategy that the opponent then counters — a cycle without progress);
• the naive self-play collapse (the agent adapts to itself and becomes vulnerable to novel styles);
• reward hacking (a poorly specified reward is optimized “to the letter” — in OpenAI’s CoastRunners experiment, 2016, the boat sails in circles collecting bonus targets instead of finishing the race).

Industrial recipes: sample opponents from a pool of past snapshots, mix optimization and exploitation (PFSP — prioritized fictitious self-play), and above all test against external bots.

7.3. Using RL in the games industry

• playing against humans: competitive game bots (Dota, StarCraft — see the table); calibrated-difficulty challenges;
• testing the game: RL agents exploring the content look for dead ends, infinite loops, off-map paths — far faster than human testers; several major studios run “quality assurance bot” pipelines;
• balancing: simulating meta-games (strategy matchups) to detect dominations before release;
• animation / motion: motor control (physics + RL) for procedural characters — see Computer Animation, ch. 10 (procedural versus data-driven motion, learned controllers) and its chapter 9 on crowds;
• imitation: learning human behaviors from player traces (behavioral cloning; learned rewards — inverse RL) for credible “human-level” NPCs without crushing domination.

7.4. Lab sheet: self-play with a snapshot pool

This lab (session 9) makes the pitfalls of section 7.2 measurable on two tiny games, in pure Python, with under a minute of computation per run.

Part A — why a pool: rock–paper–scissors. Write A for the 3 \times 3 payoff matrix of the row player (win 1, draw 0, loss −1).

1. Naive self-play: each round, play the best response to the latest copy of yourself. Print the sequence of moves: it cycles R → P → S → R forever — the exploit race of section 7.2.
2. Snapshot pool: each round, play the best response to the uniform mixture of all past snapshots. This is fictitious play (Brown, 1951). Track the exploitability of the empirical average policy \bar p, the best payoff an opponent can earn against it: \mathrm{expl}(\bar p) = \max_a\, (A \bar p)_a .
3. Expected: in our run (start from R, ties broken toward R, payoffs computed on integer counts so that ties are exact), the exploitability is about 0.07 after 100 rounds, 0.02 after 1,000 and 0.007 after 10,000, roughly a 1/\sqrt{t} decay. Payoffs in floating point break the exact ties by rounding noise and give other digits (0.014 and 0.004). The average tends to (1/3, 1/3, 1/3), as Robinson (1951) proved for zero-sum games.

Part B — tic-tac-toe by TD self-play.

1. Learner: a table V of afterstate values, seen from the player who just moved. Encoding the board as “own” and “opponent” pieces lets one table play both sides. Moves are ε-greedy with ε = 0.1.
2. Update: after each own move, apply TD(0) between consecutive own afterstates, with step 0.1; the final reward (+1, 0, −1) is the last target. This is a variant of the tic-tac-toe example of Sutton & Barto, chapter 1.
3. Two schedules: naive (the learner plays both sides, both updated) and pool (every 1,000 games a frozen snapshot joins the pool; half the games are against a snapshot drawn uniformly, and only the learner’s side is updated).
4. Evaluation every 25,000 games: the greedy table plays 500 games, alternating the first move, against a uniform random player, a one-step heuristic (win if possible, else block, else random) and a perfect minimax player. Count the losses.

Expected. In our runs (18 seeds over the two schedules, about 15 s of pure Python per 100,000 games), losses against minimax fall from 40–370 out of 500 at 25,000 games, usually under 160, to 0–3 at 100,000 games in most runs. About one run in four still loses 15–75: with a constant step and ε = 0.1 the greedy table keeps changing, so report several seeds. Both schedules behave alike: tic-tac-toe is small and has no strategy cycle, so the pool brings no gain — Part A shows when it does.

Deliverable: the two curves of Part B, the exploitability curve of Part A, and five lines explaining why the pool matters in one game and not in the other.

8. Cooperative and multi-agent games

When several agents learn or act together, each one’s environment includes the others, and success must be shared. This chapter classifies these settings, presents the dominant training pattern, and shows how to design an action that two agents perform jointly.

8.1. The structure of the problem

Moving from one to n agents changes the nature of the problem: each agent’s environment contains the other agents — non-stationary as soon as they learn. Standard decomposition (formalized as Markov games in the Reinforcement Learning module, section 7.1):

8.2. Emergent cooperative behaviors

The spectacular reference: Emergent Tool Use in Multi-Agent Interaction (OpenAI, 2019) — hide-and-seek in a physical sandbox: teams of hiders and seekers trained by PPO in self-play successively discover six strategies — running and chasing, building forts with boxes, climbing in with ramps, locking the ramps away, “surfing” on boxes, and locking the boxes too — an auto-curriculum spiral where each strategy triggers a new one.

Lesson for game design: simple rules + competitive pressure suffice to generate an escalation of strategies — exactly what a designer seeks to elicit from players.

Other results to know: Hanabi (imperfect-information cooperative — the theory of mind challenge: reasoning about what partners know); asymmetric coordination games (an “operator” player and a “runner”); and, on the theory side: communication learning (discrete channels between agents — emergent protocols) and credit assignment (team value decomposition; QMIX and the value decomposition network family).

8.3. Designing collaborative actions

9. Conversational NPCs (LLMs) and anti-cheat

Language models let a character answer anything a player types, at a cost in latency, money and control. This chapter reviews the research prototypes, the constraints that a shipped game imposes on them, and the related problem of detecting players who cheat.

9.1. Conversational agents in games

LLMs open an unprecedented slot: NPCs with unscripted dialogue, with memory and personality. The founding experiment: Generative Agents (Park et al., 2023) — a village of 25 LLM agents, each maintaining:

• a memory stream (all observed events, timestamped, with recency/importance/relevance scores for retrieval);
• a periodic reflection process (synthesizing memories into higher-level beliefs: “I am dedicating myself to my research”);
• a planner (a day of activities, revised on events).

Result: credible social behaviors, measured by human evaluation — one agent decides to host a Valentine’s Day party at Hobbs Cafe, the invitation spreads by word of mouth, and several invited agents show up “on their own”.

Voyager (2023) demonstrates the “agent in an open world” variant (Minecraft): the LLM writes and stores reusable skills (macro code) — an ever-growing skill library.

These architectures are detailed in the Reinforcement Learning module, chapter 7 (autonomous agents in the age of LLMs) and in the M2 Large Language Models module, ch. 8 — we focus here on the game constraints.

9.2. Calling an LLM from the game loop: asynchronous pattern and latency budget

A reply from a language model takes from a few hundred milliseconds to several seconds, that is tens to hundreds of frames at 60 fps. Calling it inside a tick freezes the game — the “What breaks” note of chapter 1. The cure is the one used for paths in section 2.3: the request leaves the loop, the NPC keeps acting, and the answer is applied when it arrives.

import itertools, queue, threading, time

jobs, replies = queue.Queue(), queue.Queue()
request_ids = itertools.count()

def llm_worker(generate):                   # worker thread: may block for seconds
    while True:
        req, npc_id, prompt = jobs.get()
        replies.put((req, npc_id, generate(prompt)))

def ask(npc, prompt, budget_s=1.0):         # called inside a tick: never blocks
    npc.req = next(request_ids)
    npc.deadline = time.monotonic() + budget_s
    jobs.put((npc.req, npc.id, prompt))
    npc.play("thinking")                    # filler animation, "Hmm..."

def dialogue_tick(npcs):                    # main thread, once per tick
    while not replies.empty():
        req, npc_id, text = replies.get_nowait()
        npc = npcs[npc_id]
        if req == npc.req:                  # still awaited: apply on the tick
            npc.say(moderate(text))
            npc.req = None
    now = time.monotonic()
    for npc in npcs.values():
        if npc.req is not None and now > npc.deadline:
            npc.say(npc.fallback_line())    # scripted line chosen by the BT
            npc.req = None                  # a late reply is now ignored

# start once: threading.Thread(target=llm_worker, args=(generate,), daemon=True).start()

With one worker, requests are served one at a time, so a crowd of talking NPCs builds a queue. Budgeting the latency therefore means budgeting that queue, in four steps:

1. Set the target on a percentile: for instance, the first token within 1 s for 95 % of requests (P95), since beyond about 3 s the illusion breaks (table of section 9.1). Means hide the stalls that players remember, as they hide frame spikes (section 5.2).
2. Decompose the time to first token, and measure each term on a few hundred scripted conversations: T = T_{\mathrm{retrieval}} + T_{\mathrm{queue}} + T_{\mathrm{prefill}}.
3. Check the queue. If requests arrive at random at rate \lambda and the server is busy S seconds per reply, its utilization \rho = \lambda S must stay well below 1. With Poisson arrivals and a constant S (an M/D/1 queue), the Pollaczek–Khinchine formula gives the mean wait below; it explodes as \rho \to 1, and the tail is worse than the mean, so simulate it. \mathbb{E}[T_{\mathrm{queue}}] = \frac{\rho\, S}{2(1-\rho)}
4. Allocate levers term by term: cached retrieval and shorter prompts (prefill); a smaller quantized model (smaller S); fewer callers — only the NPC facing a player calls the model, background chatter uses pre-generated lines (smaller \lambda); the deadline and fallback for what remains. A server with continuous batching (Large Language Models, ch. 6) serves several requests at once and changes this model: measure it the same way.

9.3. Cheating: detect, limit, compensate

Three families, in increasing order of difficulty for the studio:

1. information cheating (wallhack: seeing through walls): never send the client what it must not see — interest management (sending only “audible/visible” entities) is a networking and anti-cheat feature (and a bandwidth gain — see chapter 5);
2. action cheating (aimbot, speedhack): server authority (the client proposes, the server decides) + verified physical bounds (max speed, fire rate, humanly plausible reaction time);
3. statistical cheating (organized boosting, bot farming): detection by learning on game traces — reaction-time distributions, inhuman regularities, social graphs of collusion (see Graph ML, ch. 0 for modularity and Louvain communities on a player graph).

Exercises

1. ★ Fixed step. Simulate by hand the accumulator loop with \Delta t = 1/30 s and actual frames of 40, 25, 50 ms; how many ticks per frame; what happens if the anti-spiral bound is removed when a frame lasts 200 ms?

2. ★ A* on a grid. A 6×6 grid with walls \{(1,2),(1,3),(2,3),(3,3),(4,3)\}, start (0,0), goal (5,5); run octile A* by hand (open/closed table), then verify with the chapter’s code; what changes with a terrain weight of 2 on column 4?

3. ★ FSM → BT. A Guard FSM: Patrol → (noise) → Inspect → (nothing) → Patrol; Patrol → (sees player) → Attack → (low hp) → Flee. Draw the equivalent BT (selector + guard sequences); add the interruption “alerted by a comrade” to it — why is it simpler in the BT?

4. ★ Ticking a BT. On the BT of the chapter 3 code, trace the status of each node for an agent (hp = 50, enemy visible, attack in progress) over three ticks, including the one where the enemy dies; identify the “running” nodes and the selector’s re-evaluation.

5. ★ UCT by hand. Root with 15 visits; children A (n=10, w=7), B (n=3, w=3), C (n=2, w=0); c = 0.7, \ln 15 \approx 2.71. Compute the three UCT values, say which one is explored; after a winning rollout on that node, recompute and comment on the “tightening”.

6. ★ Steering. An agent at p = (0,0) with velocity v = (2,0) m/s and limits v_{\max} = 4 m/s, a_{\max} = 6 m/s²; motionless target at (8, 0) m, r_{\mathrm{arr}} = 3 m, \tau = 0.2 s.

   Compute v_{\mathrm{des}}, the arrive force and the position/velocity after a 0.1 s tick (Euler integration); why would pure seek oscillate here?

7. ★ Formations. A triangle formation of offsets \{(0,0), (-2,1), (-2,-1)\}; leader at (10, 5), heading \theta = 90°. Compute the world positions of the slots; then assign by the Hungarian algorithm to three agents at (8,4), (7,7), (12,3) (Euclidean cost); what happens if the assignment is greedy?

8. ★ AI budget. 300 agents; decision re-evaluation at 5 Hz (spread uniformly over frames), neighborhood by spatial grid (O(1) amortized), 60 fps; estimate the cost per frame (agents deciding per frame × cost of one BT) and the memory of the navigation data; compare with the “every agent every frame” option.

9. ★★ Admissibility. On an 8-connected grid (straight moves 1, diagonals \sqrt 2), show that Manhattan can overestimate h^* (give a one-cell example) and prove that the octile heuristic is admissible.

10. ★★ Rollouts. For tic-tac-toe: implement MCTS (1000 iterations) and measure the draw rate against a random player; compare budgets of 10 / 100 / 1000 / 10000 iterations; from what budget does the agent become unbeatable?

11. ★★ Dynamic assistance. Design a rubber-banding controller: input = normalized distance d to the player; output = speed bonus v \in [0.9, 1.15]; impose hysteresis (distinct rise/fall thresholds) and inertia — write the equations and discuss the tuning so that an average player notices nothing.

12. ★★★ Project. In Python (sandbox provided): a grid world with obstacles, 20 boids-navmesh agents; implement (a) A* + path following, (b) a survival BT (flee a predator, eat, wander), (c) an MCTS predator (5 ms per decision) on a discretized version of the game; measure survival rate per configuration and compute time per frame — deliver a report with the chapter 5 checklist.

Projects and assessment

The official assessment: not displayed. This module has no SynapseS 2026–2027 sheet, and the fiche above records “period (dates), language and assessment methods: not communicated”; everything below is a proposal of these notes.

The proposal: one project, solo or in a group, defended in a talk with a live demo; the lab sheets of sessions 9 and 11 (sections 7.4 and 9.2) and the exercises as practical work; a two-hour written exam. The projects exercise O7 (hands-on and industry practice: budgets, profiling, shipped constraints) and O3 (LLM-driven characters under latency and safety constraints), with O1 through self-play, O4 through graph search and player graphs, and O8 through moderation and anti-cheat false positives.

Solo projects

1. [Solo · ≈ 20 h] 200 NPCs in 2 ms: budgeted navigation. How many agents can plan paths within a 2 ms AI budget per 60 fps frame, and which lever of chapter 5 buys the most?
   • Implement: octile A* (section 2.2); HPA* with one level of clusters (Botea, Müller & Schaeffer, 2004); an asynchronous path queue with a fixed number of node expansions per frame (section 2.3); staggered decisions and AI LOD (chapters 1 and 5).
   • Data: the Moving AI Lab grid benchmarks (N. Sturtevant, “Benchmarks for Grid-Based Pathfinding”, IEEE TCIAIG, 2012): maps from Dragon Age: Origins and Baldur’s Gate II, with scenario files that give the optimal path lengths.
   • Deliverables: code; P50/P99 frame-time traces as the agent count grows from 50 to 1,000; a 4–6 page report with the eight-point checklist of chapter 5 filled in with numbers; a 10-minute talk. Chapters: ch. 1, 2, 5; extends Ex. 2, 8, 9 and 12.
   • Success: A* lengths match the scenario files to 10⁻³ relative error (after adopting their rule: no diagonal move past a blocked corner, and a diagonal cost of \sqrt 2 rather than 1.4142); 200 agents fit in 2 ms at P99; the suboptimality of HPA* is measured against A* (Botea et al. report about 1 % after smoothing).
2. [Solo · ≈ 25 h] Paper study: anytime MCTS versus AlphaZero-lite at a fixed millisecond budget. At 5, 20 and 100 ms per move, when do learned priors beat random rollouts?
   • Paper: D. Silver et al., “A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go through Self-Play” (Science, 2018), scaled down to Connect Four. The Reinforcement Learning page proposes the group version; this one fixes wall-clock budgets.
   • Implement: UCT with tree reuse and a wall-clock budget (sections 6.2–6.3); a small policy-value network trained by self-play against a snapshot pool (section 7.4), used through the PUCT rule of Reinforcement Learning, section 4.2.
   • Data: self-generated games; the UCI “Connect-4” dataset (J. Tromp, 1995: 67,557 positions after 8 plies, labelled with their game-theoretic outcome) to test the value head.
   • Deliverables: code; a win-rate table per budget over 200 games, alternating the first player; a 4–6 page report; a 10-minute talk. Chapters: ch. 6, 7.
   • Success: value-head accuracy on the UCI positions above the 65.8 % of the majority class; a budget below which PUCT beats UCT and above which the gap closes, or a measured explanation of why not; language and hardware stated.
3. [Solo · ≈ 20 h] Statistical and graph-based anti-cheat on synthetic match traces. Can per-player tests and a player graph flag aimbots and boosting rings without accusing strong humans?
   • Implement: a simulator of reaction times (log-normal humans with skill-dependent medians; aimbots near-constant, plus a “humanized” aimbot with added noise) and of match results with boosting rings (section 9.3); per-player sign tests (Example 9.3) with Benjamini–Hochberg control (Refresher in Statistics, section 6.6); Louvain communities on the who-plays-with-whom graph (Graph ML, ch. 0).
   • Data: synthetic, 10,000 players of which 1 % cheat, fixed seeds.
   • Deliverables: code; precision–recall curves; a 4–6 page report; a 10-minute talk. Chapters: ch. 9.
   • Success: a false-discovery rate of at most 5 % at the chosen threshold; the false-positive rate reported separately on the best 1 % of human players; the detection power against the humanized aimbot stated honestly.

Group projects

1. [Group of 3 · ≈ 30 h each] An LLM village under a latency budget. Can a Generative-Agents-style village run beside a game loop with a 1 s P95 first-token target, a consistent lore and no successful jailbreak?
   • Paper: J. S. Park, J. C. O’Brien, C. J. Cai, M. R. Morris, P. Liang & M. S. Bernstein, “Generative Agents: Interactive Simulacra of Human Behavior” (UIST 2023), scaled down to 5–10 agents.
   • Implement: the memory stream with retrieval by recency, importance and relevance, periodic reflection and a daily planner (section 9.1); RAG over a lore bible (Large Language Models, ch. 7); a 4-bit quantized open model of 1–4B parameters served locally (Large Language Models, ch. 6); the asynchronous pattern of section 9.2 with behavior-tree fallbacks (chapter 3).
   • Data: a 20–30 page lore bible written by the team; 200 scripted player probes (lore questions, off-topic requests); the JBB-Behaviors prompts of JailbreakBench (Chao et al., NeurIPS 2024 Datasets and Benchmarks).
   • Split: agent memory and planning; game loop, queue and fallbacks; evaluation (latency percentiles, lore consistency, safety, cost per player-hour).
   • Deliverables: code; a 6–8 page report; a 15-minute talk with a live session. Chapters: ch. 1, 3, 9; continues in Large Language Models, ch. 8 (agents).
   • Success: P95 time to first token ≤ 1 s while no tick of the main thread exceeds 1 ms of dialogue work; at least 90 % of lore probes answered consistently (two human raters, agreement reported); jailbreak and fallback rates reported with confidence intervals.
2. [Group of 3 · ≈ 30 h each] Cooperative squads: scripted roles versus centralized-training learners. On a cooperative navigation task, does a learned team beat a behavior tree with Hungarian role assignment, and at what inference cost per tick?
   • Environment: the cooperative-navigation task simple_spread of the Multi-Agent Particle Environments (Lowe et al., NeurIPS 2017; maintained by the Farama Foundation), with 3 then 6 agents.
   • Implement: a baseline that assigns agents to landmarks with the Hungarian algorithm (Refresher in Computer Science, section 7.7) and steers with arrive (chapter 4); MAPPO with a centralized critic (Definition 8.1; Yu et al., “The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games”, NeurIPS 2022); a variant whose agents exchange messages over the proximity graph through one message-passing layer (Graph ML, ch. 5).
   • Split: baseline and evaluation harness; MAPPO; graph communication and scaling study.
   • Deliverables: code; a 6–8 page report; a 15-minute talk. Chapters: ch. 4, 7, 8, with the Markov games of Reinforcement Learning, section 7.1.
   • Success: coverage (mean distance from each landmark to its nearest agent), collisions and inference time per tick over 5 seeds; the learned team within 10 % of the scripted coverage at 3 agents, or a report of why not; a scaling plot from 3 to 6 agents.

Written exam (proposal)

Format: 2 hours, one handwritten A4 sheet of notes allowed, a basic calculator, no other electronic device; four exercises, 20 points.

1. Question (5 points). (a) Describe the fixed-step accumulator loop and explain why it yields the same sequence of states whatever the frame durations. (b) Why bound the number of ticks per frame, and what does the player see when the bound is hit? (c) Give three other conditions that a deterministic simulation needs, and two uses of determinism in a game. Expected:
   • 1. Real time accumulates in a buffer; each frame runs as many ticks of constant step as the buffer holds and keeps the remainder. Tick j depends only on the state after tick j-1, the same step and the inputs stamped for tick j, so the sequence is fixed; only the interpolated rendering depends on timing (Proposition 1.3).
   • 2. Without a bound, a slow frame demands more ticks, which make the next frame slower still: the spiral of death. With the bound, the game runs slower than real time for a while instead of freezing.
   • 3. Ordered iteration (no unstable hashing), fixed-point or strictly specified floating point, seeded random generators; replays stored as inputs, lockstep networking, AI non-regression tests (section 5.3).
2. Question (6 points). A UCT root has 20 visits; its children are A (10 visits, 6 wins), B (6 visits, 4 wins) and C (4 visits, 2 wins). (a) Compute the UCT values with c = \sqrt 2 (use \ln 20 \approx 2.996) and with c = 0.5; which child is selected in each case? (b) With c = \sqrt 2, the rollout through the selected child is lost: update it and recompute (\ln 21 \approx 3.045). (c) If the budget ends now, which move is played, and why? Expected:
   • 1. With c = \sqrt 2: A 0.600 + 0.774 = 1.374, B 0.667 + 0.999 = 1.666, C 0.500 + 1.224 = 1.724, so C is selected. With c = 0.5: A 0.874, B 1.020, C 0.933, so B — a smaller constant trusts the means.
   • 2. C now has 5 visits and 2 wins: A 1.380, B 1.674, C 0.400 + 1.104 = 1.504, so B comes next.
   • 3. A, the most visited child (10 visits), not B with the best mean: the visit count is the more robust estimate (Definition 6.1).
3. Question (5 points). On an 8-connected grid with walls, a move costs 1 (straight) or \sqrt 2 (diagonal) times the terrain weight w \geq 1 of the destination cell, as in the code of section 2.2. (a) Prove that a consistent heuristic with h(\text{goal}) = 0 is admissible. (b) Prove that the octile heuristic is consistent on this grid. Expected:
   • 1. Along an optimal path from n to the goal, sum the inequalities h(n_i) \leq c(n_i, n_{i+1}) + h(n_{i+1}): the sum telescopes to h(n) \leq h^*(n). If no path exists, h^*(n) = \infty.
   • 2. The octile value of n is the shortest distance from n to the goal on the same grid without walls and with all weights 1 (Example 2.2, Exercise 9). Every real edge exists there at a cost no larger, since w \geq 1.
   • The triangle inequality of that distance then gives, with c_{\mathrm{free}} the cost of the same move on the free grid, h(n) \leq c_{\mathrm{free}}(n, n') + h(n') \leq c(n, n') + h(n'), and the octile value of the goal is 0.
4. Question (4 points). A dialogue server answers one request at a time and is busy S = 0.6 s per reply; requests arrive as a Poisson stream. (a) For \lambda = 1 request per second, compute the utilization and the mean wait (section 9.2). (b) Find the largest \lambda for which the mean wait stays at most 0.3 s. (c) Each NPC in conversation sends one request every 8 s on average: how many may talk at once? Name two levers if the designers want ten. Expected:
   • 1. \rho = 0.6; mean wait 0.6 \cdot 0.6 / (2 \cdot 0.4) = 0.45 s.
   • 2. The mean wait is 0.3\rho/(1-\rho) \leq 0.3, so \rho \leq 0.5 and \lambda \leq 0.83 per second.
   • 3. 0.83 / 0.125 \approx 6.7, so six NPCs. Levers: a model twice as fast, a second server or continuous batching, pre-generated lines for background NPCs — and a P95 check by simulation, since the mean hides the tail.

Grading rubric (proposal)

References

• S. Rabin (ed.), Game AI Pro (vol. 1–7) — the freely accessible chapters: behavior trees, utility, navigation, AI LOD.
• M. Colledanchise, P. Ögren, Behavior Trees in Robotics and AI: An Introduction, CRC/Springer, 2018 — the formalization.
• D. Isla, “Handling Complexity in the Halo 2 AI”, GDC 2005 — the introduction of behavior trees in industry.
• J. Orkin, “Three States and a Plan: The AI of F.E.A.R.”, GDC 2006 — GOAP.
• C. W. Reynolds, “Flocks, Herds and Schools: A Distributed Behavioral Model”, SIGGRAPH 1987; “Steering Behaviors for Autonomous Characters”, GDC 1999 — boids and steering.
• P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE TSSC 4(2), 1968 — A*.
• A. Botea, M. Müller, J. Schaeffer, “Near-Optimal Hierarchical Path-Finding (HPA*)”, Journal of Game Development 1(1), 2004.
• Recast/Detour — the standard open-source navmesh generation (M. Mononen).
• R. Coulom, “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search”, Computers and Games (CG 2006, Turin), LNCS 4630; L. Kocsis, C. Szepesvári, “Bandit Based Monte-Carlo Planning”, ECML 2006 — MCTS and UCT.
• C. Browne et al., A Survey of Monte Carlo Tree Search Methods, IEEE TCIAIG, 2012.
• P. Auer, N. Cesa-Bianchi, P. Fischer, “Finite-time Analysis of the Multiarmed Bandit Problem”, Machine Learning 47, 2002 — UCB1 (see RL module, chapter 4).
• G. Tesauro, “TD-Gammon, a Self-Teaching Backgammon Program”, 1992 — the self-play forerunner.
• D. Silver et al., “Mastering the Game of Go with Deep Neural Networks and Tree Search” (AlphaGo), Nature 529, 2016; “Mastering the Game of Go without Human Knowledge” (AlphaGo Zero), Nature 550, 2017; “A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go through Self-Play” (AlphaZero), Science 362, 2018.
• G. W. Brown, “Iterative Solution of Games by Fictitious Play”, in Activity Analysis of Production and Allocation, 1951; J. Robinson, “An Iterative Method of Solving a Game”, Annals of Mathematics 54, 1951 — fictitious play and its convergence (lab of section 7.4).
• R. S. Sutton, A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018 — chapter 1, the tic-tac-toe learner of section 7.4.
• O. Vinyals et al., “Grandmaster Level in StarCraft II Using Multi-agent Reinforcement Learning” (AlphaStar), Nature 575, 2019.
• C. Berner et al., Dota 2 with Large Scale Deep Reinforcement Learning (OpenAI Five), 2019.
• B. Baker et al., Emergent Tool Use in Multi-Agent Interaction (hide-and-seek), NeurIPS 2019.
• J. S. Park et al., Generative Agents: Interactive Simulacra of Human Behavior, UIST 2023.
• G. Wang et al., Voyager: An Open-Ended Embodied Agent with Large Language Models, 2023 — LLM agents in open worlds (see RL module, chapter 7, and the M2 LLMs module).
• T. Ford et al., “Overwatch Gameplay Architecture and Netcode”, GDC 2017 — the ECS architecture in production.
• R. Nystrom, Game Programming Patterns, Genever Benning, 2014 — free online (game loop, object pools, components).
• P. Bettner, M. Terrano, “1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond”, GDC 2001 — deterministic lockstep in an RTS (see section 5.3 for the synthesis).
• Instructor’s note: a period-2 slot announced by the MSc&T brochure, not in the 2026–27 LLGA lists; no instructor or lab engine (Godot/Unity/Python) is announced — the references above cover the standard game AI core.