skip to content

Game AI

How game characters decide, move and compete: state machines, behavior trees, planners, navmesh pathfinding, steering and game-tree search. Gameplay-AI interview loops draw on it.

on this pageshow

explore

questions

page 1 of 2

In a two-player board-game AI, how does minimax pick a move, and what does the evaluation function do at the depth limit?

level: juniorimportance: must knowfreq 55%

answer

  1. assume the opponent plays well
  2. max on your turn, min on theirs
  3. values backed up from the leaves
  4. heuristic score where the search stops

basics

~20 s

Minimax searches the game tree assuming both sides play their best: the AI takes the maximum over its moves, the opponent the minimum over theirs. At the depth limit, an evaluation function estimates how good each unfinished position is.

solid answer

~50 s

Minimax treats a two-player, zero-sum, perfect-information game as a tree of positions. A position's value is defined recursively: where the AI (MAX) moves, it is the **maximum** of its children's values; where the opponent (MIN) moves, the **minimum**; a finished game scores its outcome. Real games are far too deep to search to the end, so the search stops at a fixed depth and calls an **evaluation function**: a fast heuristic such as material plus mobility, scored from one fixed side's point of view. The AI plays the root move with the best backed-up value. Full-width cost is about `b^d` leaves for branching factor `b` and depth `d`, so playing strength rests on how deep you search and how well the evaluation ranks positions. The **negamax** form scores every position for the side to move and uses `value = max(-value(child))`, one function for both players.

go deeper

for a junior

Recall the recursive rule: maximum on the AI's turn, minimum on the opponent's, an evaluation at the depth limit. Be ready to back values up a small tree by hand.

for a middle

Explain negamax and why its evaluation must score for the side to move, and show how cost grows as b to the power d with each extra ply.

for a senior

Discuss what makes a good evaluation: speed against knowledge, win scores above every heuristic, and how the horizon effect corrupts leaf scores and what quiescence search costs.

for a principal

Treat evaluation richness and search depth as one time budget: a slower evaluation costs depth everywhere, so judge each added feature by playing strength at equal time per move.

## The game tree and the minimax value A two-player, **zero-sum**, **perfect-information** game (chess, checkers, a turn-based tactics board game) can be drawn as a **game tree**. The root is the current position, each edge is a legal move, and the levels alternate between the two players. Call the AI **MAX** and its opponent **MIN**. The **minimax value** of a position is defined recursively: - a **terminal** position (win, loss or draw) is worth its outcome, for example +10000, -10000 or 0; - a position where MAX is to move is worth the **maximum** of its children's values; - a position where MIN is to move is worth the **minimum** of its children's values. The AI plays the root move whose child carries the highest value. The assumption built in is that the opponent always picks the reply that is worst for MAX according to the same values. Against a weaker opponent that is pessimistic, but it is safe: the value is what MAX can guarantee against any reply, as far as the search can see. ## Depth limits and the evaluation function Searching to the end of the game is impossible in all but tiny games. With **branching factor** `b` (legal moves per position) and **depth** `d` in **plies** (one move by one player), full-width minimax reaches about `b^d` leaves. With `b = 30`, depth 4 is 810,000 leaves and depth 6 is 729,000,000. So the search stops at a **depth limit** and calls an **evaluation function** on every leaf that is not a finished game. An evaluation function is a heuristic estimate of how good a position is for one fixed side. What a usable one looks like: - **Fast**, because it runs at every leaf, often millions of times per move. - **Consistent with the rules**: a real win must score above any heuristic score, so a forced win is preferred to a merely pleasant position. - **Correlated with winning chances**: material balance, mobility, piece safety, territory, tempo. - Often a **weighted sum of features**, `w1*f1 + w2*f2 + ...`, with weights tuned by hand or by playing test matches. The evaluation does not need to be "true". Minimax only compares values, so what matters is that it **ranks** positions in roughly the right order. ## A small worked example MAX has moves X, Y and Z. MIN has three replies to each, and the evaluation scores the nine resulting leaves: | MAX move | Leaf values after MIN's replies | MIN picks | Backed-up value | |---|---|---|---| | X | 4, 5, 6 | 4 | **4** | | Y | 1, 15, 14 | 1 | 1 | | Z | 3, 9, 12 | 3 | 3 | MAX chooses **X**, worth 4. Y holds the best single leaf (15), but MIN would never allow it, so Y is worth only 1 against good play. Choosing Y for its 15 is the classic optimistic mistake. Choosing by each row's average (5, 10, 8) would also pick Y, because averaging models an opponent who replies at random, not one who replies against you. ## Negamax: one function for both sides In a zero-sum game a position's value for one player is the negative of its value for the other. **Negamax** uses this: every position is scored from the point of view of the **side to move**, and ``` value(position) = max over legal moves of -value(position after the move) ``` One recursive function then serves both players. The trap is the evaluation: it must also return the score for the side to move. If it always scores for one colour, the signs flip at alternate plies and the AI starts choosing the opponent's best moves. ## Where plain minimax struggles - **Cost.** Each extra ply multiplies the work by about `b`. Alpha-beta pruning returns the same root value while skipping branches that cannot change it, which is why practical game-tree searches build on it rather than on plain minimax. - **The horizon effect.** A depth-limited search can stop in the middle of an exchange: it sees the AI capture a piece but not the recapture one ply later, and scores the position as a gain. It can also play delaying moves that push an unavoidable loss just past the depth limit and then believe the loss has gone. **Quiescence search** handles the first case by extending each leaf with captures (and in some games checks) until the position is quiet, and only then evaluating. - **Evaluation blind spots.** If the evaluation ignores a feature that decides the game, such as a passed piece racing to promote, a deeper search only partly makes up for it. - **Ties and wandering.** If every win scores the same constant, the AI may keep choosing moves that keep a win in reach without ever taking it. Scoring a win as a large constant minus the number of plies to reach it makes the search prefer the fastest win and the slowest loss.

  • What is the horizon effect, and how does quiescence search reduce it?
    The horizon effect is a depth-limited search misjudging a position because the decisive move lies just past the depth limit, for example scoring a capture as a gain when the recapture is one ply deeper. Quiescence search extends each leaf with only forcing moves, usually captures, until no capture improves the side to move, letting it 'stand pat' on the static score. It fixes unfinished exchanges, not delaying tactics that push a slow loss beyond the horizon.
  • Why should a win found in fewer plies score higher than a win found deeper?
    If every win scores the same constant, all winning moves tie, and the AI can keep picking moves that keep a win available without ever completing it. Scoring a win as a large constant minus the ply at which it occurs makes the search prefer the shortest win, and the mirror rule makes it prefer the longest loss when losing, so it resists and still converts.

  • Minimax assumes the opponent picks replies at random.
  • The evaluation function is only used when the game is over.
  • Depth-limited minimax always finds the objectively best move.
  • Searching one ply deeper costs only a few more evaluations.
  • Negamax evaluation can score for a fixed colour instead of the side to move.
open as a page

In a behavior tree, how do sequence and selector nodes decide what to run, and what roles do decorators and leaf nodes play?

level: juniorimportance: must knowfreq 75%

basics

~20 s

A sequence runs its children left to right and stops at the first failure; a selector stops at the first success, so child order sets priority. Decorators wrap one child to change its result or timing; leaves are conditions and actions.

open as a page

In an NPC finite state machine, what do a state's enter, update and exit actions do, and how does one tick run?

level: juniorimportance: must knowfreq 72%

basics

~20 s

Enter runs once on arriving in a state, update runs every tick while the NPC stays, exit runs once on leaving. Each tick tests the current state's transition guards; when one passes, the old state exits and the new one enters.

open as a page

How do grid, waypoint-graph and navmesh representations of walkable space differ for game pathfinding, and what does each cost?

level: juniorimportance: must knowfreq 70%

basics

~20 s

A grid splits the world into uniform cells, a waypoint graph links hand-placed points, and a navmesh covers walkable floor with convex polygons. Grids are simple but node-heavy, waypoints sparse but rail-bound, navmeshes compact but costly to build.

open as a page

How does an NPC decide whether it can see a target using a vision cone, a sight range and a line-of-sight check?

level: juniorimportance: must knowfreq 62%

basics

~20 s

An NPC sees a target when three tests pass in cost order: the target is within sight range, inside the cone's half-angle (a dot product against the cosine of that half-angle), and an unobstructed ray reaches it from the NPC's eyes.

open as a page

In utility AI, how does a survival-game villager choose between eating, chopping firewood and sleeping on each decision cycle?

level: juniorimportance: must knowfreq 60%

basics

~10 s

Utility AI scores each candidate action between 0 and 1 from the villager's current needs and surroundings, shaping every input with a response curve, then usually runs the highest-scoring action until the next re-evaluation.

open as a page

In Reynolds-style steering, what is a desired velocity, and how does seek turn it into a capped steering force?

level: juniorimportance: must knowfreq 65%

basics

~20 s

Seek's desired velocity points from the agent straight at the target at maximum speed. The steering force is desired velocity minus current velocity, truncated to a maximum force, so the agent bends onto the new heading instead of snapping.

open as a page

How does alpha-beta pruning skip branches without changing the minimax result, and why does move ordering decide how much it saves?

level: middleimportance: must knowfreq 52%

basics

~20 s

Alpha-beta carries alpha, the score the maximiser is already guaranteed, and beta, the score the minimiser is already guaranteed. Once a node's value must fall outside that window, its remaining moves are skipped. Trying the best move first maximises cutoffs.

open as a page

In a behavior tree, what does the running status mean, and how does the tree resume a running action on the next tick?

level: middleimportance: must knowfreq 62%

basics

~20 s

Running means an action has started but needs more ticks. Next tick, a reactive tree re-checks earlier children before reaching the action again, while a composite with memory skips straight to it; a preempted action must be halted.

open as a page

A boss NPC's state machine flips between Approach and Attack every few frames at its attack range's edge; why, and how do you stop it?

level: middleimportance: must knowfreq 66%

basics

~20 s

Both transitions share one distance threshold, so small jitter near it crosses the line each tick. Add hysteresis, entering Attack below one distance and leaving only above a larger one, plus a minimum dwell time so a state commits.

open as a page

For A* on a game grid, how do you choose between Manhattan, octile and Euclidean heuristics, and how does tie-breaking cut node expansions?

level: middleimportance: must knowfreq 72%

basics

~20 s

Use the heuristic that equals unobstructed travel cost under your movement rules: Manhattan for 4-way grids, octile for 8-way grids with √2 diagonals, Euclidean for any-angle movement. Break equal-f ties toward the node nearer the goal.

open as a page

How should a stealth guard hear a thrown bottle, remember where it last saw the player, and let that memory decay?

level: middleimportance: must knowfreq 55%

basics

~20 s

A noise is a stimulus event with a position, a reach and a time; guards within reach register it. Each sighting or sound updates a memory record holding a last known position and a confidence that decays until the guard gives up.

open as a page

How does a GOAP planner use action preconditions, effects and costs to get an assault NPC through a locked door to its target?

level: middleimportance: must knowfreq 64%

basics

~20 s

GOAP models the world as facts and each action as preconditions, effects and a cost; a graph search finds the cheapest action chain that turns the current facts into the goal facts: fetch key, open door, enter, attack.

open as a page

Why does a steering agent using seek overshoot and orbit its destination, and how does arrive with a slowing radius fix it?

level: middleimportance: must knowfreq 58%

basics

~20 s

Seek always asks for full speed toward the target, so the agent arrives fast and cannot brake in time. Arrive ramps the desired speed down to zero inside a slowing radius, which must be at least the agent's braking distance.

open as a page

When would you choose a behavior tree over a finite state machine for an NPC's decision logic, and what does each make harder?

level: seniorimportance: must knowfreq 58%

basics

~20 s

Choose a behavior tree when an NPC has many prioritised reactions and reusable sub-behaviours; choose a state machine for a few clear modes with explicit transitions. Trees make remembered modes harder; state machines make adding reactions harder.

open as a page

In dynamic difficulty adjustment, how does rubber-banding differ from adapting a game to an estimated model of the player's skill?

level: juniorimportance: should knowfreq 38%

basics

~20 s

Rubber-banding reacts to the current gap or the last outcome, helping whoever is behind right now; a skill model estimates the player's lasting ability from many attempts and tunes upcoming challenges toward a target success rate.

open as a page

Why does a board-game AI with a fixed time per move use iterative deepening instead of one fixed-depth alpha-beta search?

level: middleimportance: should knowfreq 42%

basics

~20 s

Iterative deepening runs alpha-beta at depth 1, 2, 3 and so on until time runs out, so a complete answer is always ready. Shallow passes cost little, and their best moves order the next pass so alpha-beta cuts more.

open as a page

How does Monte Carlo tree search with UCT choose a move, and when would you prefer it to alpha-beta for a game AI?

level: middleimportance: should knowfreq 45%

basics

~20 s

Monte Carlo tree search repeats four steps: select a path with UCT, expand one new node, play a cheap game to the end, and back the result up. It suits games lacking a good evaluation or with huge branching.

open as a page

What is a blackboard in a behavior tree, and what problems appear when many nodes read and write it?

level: middleimportance: should knowfreq 50%

basics

~20 s

A blackboard is a key-value store a tree's nodes share: sensors write facts such as the target or ammo, conditions and actions read them. It decouples nodes but hides data flow and invites stale values, key mismatches and write conflicts.

open as a page

How does a pushdown state machine let an NPC resume an interrupted state, such as a boss returning to Attack after a stun?

level: middleimportance: should knowfreq 45%

basics

~20 s

A pushdown state machine keeps a stack of states and runs the top one. An interruption such as Stunned is pushed over Attack and popped when it ends, so Attack resumes with its data instead of restarting.

open as a page

When several transition guards in an NPC state machine pass in the same tick, which transition should fire, and how do you make that explicit?

level: middleimportance: should knowfreq 55%

basics

~20 s

Evaluation order decides, so make it a deliberate priority: test guards in a fixed, documented order, fire the first that passes and put overriding transitions such as death first. A transition table keeps that order visible and checkable in one place.

open as a page

Why does a game bot trained by behaviour cloning on recorded player matches drift into situations players never reached, and how is that countered?

level: middleimportance: should knowfreq 24%

basics

~20 s

Behaviour cloning learns only from states players visited; small bot errors lead to unfamiliar states where predictions worsen, so errors compound. Countered by labelling the bot's own states (DAgger), noisy demonstrations, reinforcement fine-tuning and an authored fallback.

open as a page

When training a game opponent by self-play, why sample opponents from a pool of past versions instead of only the latest copy?

level: middleimportance: should knowfreq 30%

basics

~20 s

Against only its latest copy, a self-play policy can forget how to beat older strategies and cycle through counters; sampling frozen past checkpoints keeps those strategies in the opponent mix, so improvement has to hold against all of them.

open as a page

How is a navmesh generated from level geometry by voxelization, and why is the walkable area eroded by the agent's radius?

level: middleimportance: should knowfreq 45%

basics

~20 s

Level triangles are rasterized into a voxel heightfield, filtered by slope, headroom and step height, shrunk by the agent radius, and split into regions whose outlines become convex polygons. Erosion lets search treat the agent as a point.

open as a page

What is an influence map in game AI, and how do propagation, decay and layered maps help NPCs reason about territory and danger?

level: middleimportance: should knowfreq 45%

basics

~20 s

An influence map is a grid or graph storing, per cell, how strongly each side controls or threatens it; units stamp values that spread with falloff and fade over time, and layers combine to locate front lines, safety and danger.

open as a page

In utility AI, why are scores from several considerations usually multiplied rather than summed, and what problem does multiplying create?

level: middleimportance: should knowfreq 45%

basics

~20 s

Multiplying lets any consideration at zero veto an action, which a sum cannot; but every extra factor below 1 shrinks the product, so actions with many considerations lose unfairly unless a compensation factor or geometric mean corrects for the count.

open as a page

In Reynolds' boids flocking, what do separation, alignment and cohesion each compute, and what decides which flockmates a boid reacts to?

level: middleimportance: should knowfreq 55%

basics

~20 s

Separation steers away from flockmates that are too close, alignment toward their average heading, cohesion toward their average position. A boid reacts only to neighbours inside a radius, often within a view angle, so the flock emerges from local rules.

open as a page

Why steer a crowd of thousands sharing one goal with a flow field instead of one path per agent, and how is the field built?

level: middleimportance: should knowfreq 42%

basics

~20 s

A flow field is built once per goal: a wavefront from the goal gives each cell its cost-to-goal and a downhill direction. Any number of agents then read their cell in constant time instead of each running its own search.

open as a page

How does expectimax handle dice rolls in a card-game AI, and what breaks when you search sampled hidden hands as if they were visible?

level: seniorimportance: should knowfreq 35%

basics

~20 s

Expectimax adds chance nodes worth the probability-weighted average of their outcomes. Searching sampled deals as fully visible (determinization) lets the AI pick different moves in situations it cannot tell apart, and it sees no value in hiding or gathering information.

open as a page

After adding a transposition table keyed by Zobrist hashes, a board-game AI occasionally blunders; what are the likely causes, and how do you track them down?

level: seniorimportance: should knowfreq 30%

basics

~20 s

Usual causes: an alpha-beta bound stored as an exact score, shallow entries used for cutoffs, a hash missing side to move or other state, unverified collisions, and mate scores not adjusted by ply. Compare against a table-free search.

open as a page

showing 1–30 of 47