Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Monte Carlo tree search and stochastic games

Monte Carlo Tree Search (MCTS) is a simulation-based search algorithm used to solve large sequential decision problems and stochastic games by growing a search tree with random (or policy-based) playouts, combined with a selection rule such as UCT to balance exploration and exploitation.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

MCTS is used by engineers to make good decisions in large game trees, planning, and control problems where exact search is impossible (e.g., Go, real-time planning, imperfect-information and stochastic environments). Stochastic games extend two-player game theory to settings with randomness (chance) and state transitions; understanding them helps design agents for real-world tasks with uncertainty.

Key ideas

Start from first principles and define terms simply.

  • State: a complete description of the current situation of a game or environment. Example: position of pieces in chess. (When used below, a state is assumed to be finite or representable.)

  • Action: a legal move available to a player from a state.

  • Terminal state: a state where the game ends and a utility (reward) is assigned.

  • Reward / Utility: a numerical value given at terminal states (or per step) that measures outcome. We treat rewards as unitless here.

  • Game tree: a rooted tree whose nodes are states and edges are actions. Label each node with the player to move. In stochastic problems add chance nodes. For simultaneous-move stochastic games (Markov games), both players choose actions at state s; the model is not strictly an alternating-turn tree, and solving the Bellman equation involves a zero-sum matrix game at each state.

  • Chance node: a node where the next state is chosen randomly according to a known probability distribution (e.g., dice roll). Draw chance nodes as circles labeled "C".

  • Stochastic game (also called Markov game): a generalisation of Markov decision processes (MDPs) to multiple players, defined by (S, A1, A2, P, R1, R2, gamma) where S = states, Ai = actions of player i, P(s' | s, a1, a2) = transition probabilities, Ri(s, a1, a2) = reward for player i, and gamma = discount (if infinite horizon). In the zero-sum case R2 = -R1. Assume finite S and finite actions (and 0<=gamma<1 for infinite horizon) for most exam answers. The classical theorem (Shapley 1953) states: every finite discounted two-player zero-sum stochastic game has a well-defined value and admits optimal stationary randomized policies for both players.

  • Expectimax: an extension of minimax for chance nodes. At a Max node, value = max over child values; at a Min node, value = min; at a Chance node, value = expectation over child values according to probabilities.

  • Monte Carlo Tree Search (MCTS): an anytime algorithm that builds a search tree from the current state using repeated iterations of four steps: Selection, Expansion, Simulation (rollout), Backpropagation.

    • Selection: starting at the root, repeatedly select a child node using a policy (commonly UCT) until a node is reached that is not fully expanded or is terminal.
    • Expansion: add one (or more) child node(s) corresponding to an untried action.
    • Simulation: run a playout from the new node to a terminal state using a (usually fast) default policy; obtain reward.
    • Backpropagation: propagate the reward back up the path, updating visit counts and value estimates.
  • UCT (Upper Confidence bound applied to Trees): use the UCB1 formula at each decision node to balance exploration and exploitation when selecting children. It treats each child as a multi-armed bandit.

  • Value estimate and update: Each node stores total reward sum and visit count. A common stored estimate Q = (sum of rewards) / visits (the sample mean). When new reward r is observed at a node with previous visits n and mean Q, the incremental update is Q' = Q + (r - Q)/(n+1). Derive this by algebra: new mean = (n·Q + r)/(n+1). In two-player zero-sum alternating-turn games, be explicit about reward perspective: either store outcomes from the root player's viewpoint for all nodes, or flip the sign at alternate levels during backpropagation; be consistent in exams/code.

  • Diagrams to draw for exam answers:

    • MCTS tree: draw root node (square) labelled with state s0. Draw several child nodes (s1, s2...) with edges labelled by actions a0, a1... Mark one path as "Selection path". Mark one child as newly expanded (dashed). Draw an expanding leaf and a separate playout box showing random simulation to terminal. Label counts N(v) and value estimates Q(v) on nodes.
    • Expectimax tree: draw a small tree with a Max node at root, two chance nodes as children (circles), each chance node has two terminal leaves with probabilities (label them p and 1-p) and utilities. Compute values bottom-up and show expected value at chance nodes, then max at root.

Assumptions commonly used in exams: finite branching factor, bounded rewards, independent playout outcomes (for UCB analysis), and finite horizon or discounted infinite horizon for stochastic-game existence theorems.

Formulas

UCT value = Q_i + c * sqrt(ln N / n_i)

  • Q_i: average reward (sample mean) of child i (unitless).
  • N: visit count of parent node (unitless).
  • n_i: visit count of child i (unitless).
  • c: exploration constant (unitless), typical c = sqrt(2).
  • Applies during Selection when choosing child i to descend. If n_i = 0, select that child (treat its UCT value as +infinity) to avoid division by zero. The common choice c = sqrt(2) assumes rewards normalized to [0,1]; scale c accordingly otherwise.

Q_{new} = Q_{old} + (r - Q_{old}) / (n_{old} + 1)

  • Q_old: previous mean at node (unitless).
  • r: reward returned by a simulation (unitless).
  • n_old: previous visit count (integer).
  • Gives incremental update for sample mean.

V_{Chance} = sum_{s'} P(s'|s,a) * V(s')

  • V_Chance: value at a chance node in expectimax (unitless).
  • P(s'|s,a): probability of child s' (unitless, sums to 1).
  • V(s'): value of successor state s' (unitless).
  • Applies when computing expected value at chance nodes.

Bellman (zero-sum stochastic game, single-step): V(s) = max_{pi1 in Delta(A1(s))} min_{pi2 in Delta(A2(s))} [ sum_{a1} pi1(a1) sum_{a2} pi2(a2) ( R(s,a1,a2) + gamma * sum_{s'} P(s'|s,a1,a2) * V(s') ) ]

  • V(s): value for the maximizing player from state s (unitless).
  • pi1, pi2: stationary mixed strategies (distributions) over actions for players 1 and 2 at state s; optimizing over pure actions is not correct in general unless a pure equilibrium exists.
  • In zero-sum games R2 = -R1.
  • gamma: discount factor (0<=gamma<1 for infinite horizon) (unitless).
  • P: transition probabilities.
  • Applies to finite two-player zero-sum stochastic games with discounting; such games have a value and optimal stationary randomized policies (Shapley 1953).

Complexity notes (informal): time complexity per iteration grows with selection path length and simulation length; overall MCTS quality increases with number of iterations but not guaranteed to converge quickly in very large trees.

Worked examples

Example 1 — model theory answer (expectimax on small stochastic tree). Question: Draw the tree described and compute the value at the root. Tree description to draw: Root is a Max node (M). It has two actions A and B.

  • A leads to a Chance node C1 with two leaves: leaf a1 (utility 3, prob 0.6) and leaf a2 (utility 1, prob 0.4).
  • B leads to a Chance node C2 with two leaves: leaf b1 (utility 2, prob 0.5) and leaf b2 (utility 0, prob 0.5). Compute step-by-step:
  1. Compute expected value at C1: V(C1) = 0.63 + 0.41 = 1.8 + 0.4 = 2.2.
  2. Compute expected value at C2: V(C2) = 0.52 + 0.50 = 1.0.
  3. Root is Max: choose between A (value 2.2) and B (value 1.0) so V(root) = max(2.2, 1.0) = 2.2. A is the optimal action. Answer in exams: show the drawn tree, label probabilities on chance edges, compute the two expectations, then take max. Final answer: choose A with value 2.2.

Example 2 — Python: tiny MCTS-like sampling for a toy game (complete program) This demonstrates the mechanics of selection/average updates in code for a one-step decision problem. It is intentionally simple so output is deterministic.

# toy_mcts.py - deterministic demo of Monte-Carlo sampling over actions
# No randomness: each action has a fixed reward distribution (here single reward)

def mcts_best_action(reward_map, simulations_per_action=100):
    # reward_map: dict action -> reward (float)
    # For this toy example, each simulation just returns the reward for the action.
    best_action = None
    best_mean = float('-inf')
    for a, r in reward_map.items():
        n = simulations_per_action
        # sample mean for deterministic reward is the reward itself
        mean = r
        if mean > best_mean:
            best_mean = mean
            best_action = a
    return best_action, best_mean

if __name__ == '__main__':
    actions = {0: 0.0, 1: 0.5, 2: 1.0}  # action -> expected reward
    action, value = mcts_best_action(actions, simulations_per_action=10)
    print('Best action:', action)
    print('Estimated value:', value)

Sample input: none (program hardcodes actions) Exact output: Best action: 2 Estimated value: 1.0

Notes: This toy program is deliberately simple: it shows the selection of the action with highest estimated reward as MCTS would do after enough simulations. In real MCTS the rewards come from stochastic playouts and the tree is expanded; conceptually the same update for Q is used.

(If asked in lab exam, modify the simulation to use random rollouts and increase code complexity.)

Common mistakes

  • Using the sample mean Q but updating it incorrectly (forgetting incremental formula or mixing sum vs mean).
  • Missing the exploration term in selection (setting c=0) which makes MCTS purely greedy and often very poor.
  • In stochastic games, assuming deterministic transitions or forgetting the discount factor gamma in infinite-horizon cases.
  • Writing UCT as Q + c * sqrt(N / n) (wrong placement of ln), instead of ln(N) in numerator.

For your exam

Kinds of questions you will see:

  • Definitions: define MCTS, selection/expansion/simulation/backpropagation, chance node, stochastic game.
  • Short notes: explain UCT and the role of exploration constant c, describe expectimax vs minimax.
  • Derivations: derive incremental mean update Q' = Q + (r - Q)/(n+1) and derive the expectimax values for a tree.
  • Numerical: compute expectimax values for a small stochastic tree with given probabilities and utilities (do the arithmetic stepwise and show units if any).
  • Programs: implement a simple MCTS skeleton (pseudocode or Python) for Tic-Tac-Toe or a toy stochastic game; show playout and update.
  • Diagrams: draw MCTS search tree, label selection path, expanded node, chance nodes and probability labels.

What a full-marks answer includes:

  • Clear definitions of all terms used (bold them if instructed).
  • Correct formulas with symbols defined and assumptions stated (finite horizon, bounded rewards etc.).
  • Correct step-by-step arithmetic for numerical questions, with interim values and final boxed answer.
  • Correctly labelled diagrams where asked.
  • For program questions, working code or correct pseudocode with clear explanation of each phase.

Quick check

  1. What are the four steps of MCTS? 2) How does a chance node compute its value in expectimax? 3) Write the UCT selection formula and name the term that balances exploration. Answers: Selection, Expansion, Simulation (rollout), Backpropagation; By computing expected value V = sum_{s'} P(s'|s,a) * V(s'); UCT: Q_i + c * sqrt(ln N / n_i), exploration term is c * sqrt(ln N / n_i).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?