Games and adversaries: minimax, alpha-beta pruning and Monte Carlo tree search

A game as a search problem, the game tree, minimax, alpha-beta pruning, evaluation functions and MCTS — on tic-tac-toe, where everything can be computed, and the road from Deep Blue to AlphaZero.

14 minutes Matěj Žalmánek 2026-10-15

Series AI basics Part 22 of 52

1. Map of artificial intelligence: what is what and how it all fits together
2. A brief history of artificial intelligence: from Turing to language models
3. Data, model, training, inference: the basic terms on a single example
4. How to read mathematical notation: symbols, indices, sums and quantifiers
5. Sets and relations: the building blocks of definitions in AI
6. Functions and mappings: why every AI model is a function
7. Logic and proofs: the rules AI reasons by
8. Graphs and trees: the structure that both search and neural networks stand on
9. Linear algebra for machine learning: vectors, matrices and why AI mostly multiplies
10. Derivatives, the gradient and the chain rule: how a model finds out which way to learn
11. Gradient descent: how a model learns
12. What probability is: from rolling dice to the Kolmogorov axioms
13. Conditional probability and Bayes’ theorem: how to update your estimate when you learn something new
14. Random variables and the cumulative distribution function: one function that tells you everything about a distribution
15. Probability density and probability mass functions: why a continuous variable has zero probability at a point
16. Expected value, variance and covariance: where a distribution lies, how wide it is and what goes with what
17. Overview of probability distributions: Bernoulli, binomial, Poisson, uniform, normal and exponential
18. Law of large numbers and central limit theorem: why averages behave so predictably
19. Statistics and parameter estimation: maximum likelihood, MAP and confidence intervals
20. Information theory: entropy, cross-entropy and KL divergence — where loss functions come from
21. State-space search: BFS, DFS, UCS and A* with animations
22. Games and adversaries: minimax, alpha-beta pruning and Monte Carlo tree search
23. Constraint satisfaction: backtracking, constraint propagation and AC-3 on sudoku and a map of Czech regions
24. Logic and knowledge systems: forward and backward chaining, resolution and expert systems
25. Planning: STRIPS, the blocks world, heuristics from relaxation and planning in AI agents
26. Local search and simulated annealing: a travelling salesman through the Czech regional capitals
27. Genetic algorithms: population, crossover, mutation and selection on a backpack for a hike
28. Evolution strategies and genetic programming: from the one-fifth rule to Kepler’s law
29. Ant colony optimization: how a pheromone trail finds a short path
30. Particle swarm optimisation: inertia, personal experience and the swarm’s experience
31. Neuroevolution: evolving the weights and shape of neural networks, and the NEAT algorithm
32. Fuzzy sets and membership functions: how to write down “somewhat warm”
33. Fuzzy logic and probability: why “somewhat warm” does not mean “probably warm”
34. Fuzzy logic: t-norms, implications and IF–THEN rules
35. Fuzzy control: Mamdani and Sugeno from a fan to a pole on a cart
36. Fuzzy clustering: the fuzzy c-means algorithm and points between clusters
37. Neuro-fuzzy systems (ANFIS): fuzzy rules that learn from data
38. Markov chains: the transition matrix, the stationary distribution and PageRank
39. Hidden Markov models: the Viterbi algorithm and the dishonest casino
40. Bayesian networks: why the grass is wet and what it means for the sprinkler
41. The Kalman filter: how to estimate where a car is and how fast it goes from imprecise measurements
42. Types of machine learning: supervised, unsupervised, semi-supervised and more
43. Prompts, context and RAG: how to give a model the right information
44. Variational autoencoders (VAE): new images from a continuous latent space
45. Generative adversarial networks (GAN): the forger versus the detective
46. Diffusion models: how pure noise becomes an image
47. Markov decision processes: states, actions, rewards and the Bellman equations
48. Q-learning and DQN: learning the value of actions, from a table to a neural network
49. Policy gradient and PPO: learning the policy directly
50. How an AI agent works: a language model in a loop with tools
51. Programming with AI agents: the task, tests and review
52. Evaluating and securing AI systems: how to measure and how to keep watch

Full series syllabus 52 of 83 topics published

In the maze from the previous part, the little figure was alone. The world stood still and every move led where it was supposed to. In a game, though, someone sits across from you who wants the exact opposite — and answers each of your moves with the one that hurts you most. Finding a path to the goal is no longer enough: you have to find a strategy that holds up against every reply. Chess, checkers and go were the yardstick of artificial intelligence for decades, and the algorithms in this part are behind both Deep Blue and AlphaGo.

It builds on the parts State-space search and Graphs and trees.

1. A game as a search problem

Definition — two-player game

A two-player game (deterministic, with perfect information and zero-sum) is a seven-tuple

Γ = (S, s₀, player, A, T, K, U)

that satisfies:

1. S is a non-empty set of states (positions) and s₀ ∈ S is the initial state;
2. K ⊆ S is the set of terminal states — where the game ends;
3. player : S ∖ K → {MAX, MIN} says whose turn it is in a state;
4. A assigns to every state s ∈ S ∖ K a finite non-empty set A(s) of moves (actions), and in terminal states A(s) = ∅;
5. T is the transition function: for s ∈ S ∖ K and a ∈ A(s), T(s, a) ∈ S is the state after move a (moves are deterministic);
6. the players take turns: if s ∈ S ∖ K, a ∈ A(s) and T(s, a) ∉ K, then player(T(s, a)) ≠ player(s);
7. U : K → ℝ is the utility of a terminal state from the point of view of player MAX; the utility for MIN is −U (zero-sum: U(s) + (−U(s)) = 0 for every s ∈ K).

Both players know the whole seven-tuple and see the current state at every moment (perfect information). The game is finite if and only if there is no infinite sequence s₀, s₁, s₂, … with s_i = T(s_i−1, a_i) for some a_i ∈ A(s_i−1) — so every game ends in K after finitely many moves. All the games in this part are finite.

A strategy of player MAX is a function σ that assigns to every state s ∈ S ∖ K with player(s) = MAX a move σ(s) ∈ A(s); a strategy τ of player MIN is defined the same way for states with player(s) = MIN. A pair of strategies (σ, τ) uniquely determines a game from state s₀, and with it its utility.

The difference from search is fundamental. The solution is no longer a path — you cannot choose one, because every other move is made by the opponent. The solution is a strategy: a rule for how to answer every move the opponent can make.

2. The game tree

Definition — game tree

Let Γ = (S, s₀, player, A, T, K, U) be a finite two-player game. The game tree of Γ is the rooted tree (see the part Graphs and trees) for which:

1. the nodes are all sequences of moves (a₁, …, a_k), k ≥ 0, that can be played from s₀, i.e. s_i−1 ∉ K, a_i ∈ A(s_i−1) and s_i = T(s_i−1, a_i) for i = 1, …, k; the node has the state s_k;
2. the root is the empty sequence () with state s₀;
3. the children of the node (a₁, …, a_k) with state s_k ∉ K are the nodes (a₁, …, a_k, a) for all a ∈ A(s_k), with states T(s_k, a);
4. the leaves are exactly the nodes whose state is terminal (s_k ∈ K).

So a node is not a position but the history that led to it — the same state can be reached by different sequences of moves and then appears in the tree several times. Nodes where MAX is to move are drawn as triangles pointing up, MIN nodes pointing down.

Let b = max_{s ∈ S ∖ K} |A(s)| be the branching factor and m the greatest length of a game (number of moves). Then the tree has at most b^m leaves.

Tic-tac-toe on a 3 × 3 board is a small game, and yet its tree has 549,946 nodes and 255,168 leaves — that is how many different games can be played. Yet there are only 5,478 different positions: you reach the same position through many orders of moves. Chess has a branching factor of about 35 and a game lasts dozens of moves; in 1950 Claude Shannon estimated its tree at 10¹²⁰ games. Go, with a branching factor of about 250, is many orders of magnitude further still. So we can walk the whole tree only for small games — for large ones we have to learn which branches to skip.

Example — an upper bound on the tic-tac-toe tree and Shannon's number

If tic-tac-toe were always played until the board is full, the tree would have exactly 9 · 8 · … · (9 − k + 1) = 9!/(9 − k)! nodes at depth k (k = 0, …, 9). In total

∑_k=0⁹ 9!/(9 − k)! = 1 + 9 + 72 + 504 + 3,024 + 15,120 + 60,480 + 181,440 + 362,880 + 362,880 = 986,410 nodes and 9! = 362,880 leaves.

The real tree has 549,946 nodes and 255,168 leaves, because a game in which someone gets three in a row ends earlier and its branch does not branch any further. The estimate b^m is therefore an upper bound; here with b falling from 9 to 1.

Shannon (Programming a Computer for Playing Chess, 1950) assumed for chess about 10³ possibilities per pair of moves (white and black) and a typical game of 40 pairs of moves: (10³)⁴⁰ = 10¹²⁰. It is a rough order-of-magnitude estimate, not an exact number.

3. Minimax

Definition — minimax value

Let Γ = (S, s₀, player, A, T, K, U) be a finite two-player game. The minimax value is the function MM : S → ℝ defined recursively for every s ∈ S:

1. MM(s) = U(s) if s ∈ K;
2. MM(s) = max_{a ∈ A(s)} MM(T(s, a)) if s ∉ K and player(s) = MAX;
3. MM(s) = min_{a ∈ A(s)} MM(T(s, a)) if s ∉ K and player(s) = MIN.

The recursion is well defined: the game is finite, so every chain of recursive calls ends in a terminal state, and A(s) is finite and non-empty, so both the maximum and the minimum exist.

A move a* ∈ A(s) is an optimal move of player MAX in a state s with player(s) = MAX if and only if

a* ∈ argmax_{a ∈ A(s)} MM(T(s, a)), i.e. MM(T(s, a*)) = MM(s);

an optimal move of player MIN is likewise an element of the argmin. A strategy that chooses an optimal move in every state is a minimax strategy.

The left MIN node picks 4 from the leaves 4, 6 and 9, the middle one picks 2 from 2, 7 and 8, the right one picks 3 from 5, 3 and 9. MAX at the root then chooses between 4, 2 and 3 and plays the left move with value 4. Notice that the right branch hides a nine — but MAX can never reach it, because MIN would play the three instead.

Theorem — what minimax guarantees

Let Γ be a finite two-player game and σ* a minimax strategy of player MAX. Then

1. for every strategy τ of player MIN, the game played by the pair (σ*, τ) has utility ≥ MM(s₀);
2. if τ* is a minimax strategy of player MIN as well, the game played by the pair (σ*, τ*) has utility exactly MM(s₀).

Proof (sketch), by induction on the height of the node: in a leaf MAX gets exactly U(s) = MM(s). In a MAX node he plays the move into the child with the largest value and by the induction hypothesis secures at least that value there, so at least MM(s). In a MIN node the opponent picks any child, but each has a value ≥ min = MM(s), and in each of them MAX by the hypothesis secures at least its value. For s = s₀ this is point 1. By the same reasoning with the roles swapped, MIN with the minimax strategy τ* secures a utility of at most MM(s₀) against every strategy of MAX; the two inequalities together give point 2. ∎

Minimax walks the tree depth-first: time O(b^m), memory O(b · m).

4. Minimax on tic-tac-toe

Tic-tac-toe on 3 × 3 is small enough for minimax to walk the whole tree. Anyone who has played it for more than a few minutes knows the result: the minimax value of the empty board is 0 — when both play without a mistake, it is always a draw. More interesting is what minimax says about a particular position. X (MAX) is to move, and each empty square shows the value of moving there:

Only one move wins — the centre. With it X sets up a fork: it threatens to complete the middle row and the diagonal, and O cannot block both. The move to the bottom middle holds the draw. The remaining three moves look innocent, but they lose: O answers them with a fork of its own. A person would have to think this through; minimax simply computes it.

def minimax(board):
    end = winner(board)                  # "X", "O", "draw", or None
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    values = [minimax(play(board, move)) for move in empty_squares(board)]
    return max(values) if to_move(board) == "X" else min(values)

5. Alpha-beta pruning

Minimax walks the whole tree, even though half of it is pointless. Look again at the middle branch: the first leaf showed 2. So in that branch MIN gets 2 or less — and MAX already has the left branch with value 4 secured. Whatever the remaining two leaves are, MAX will not go into the middle branch. He does not even need to look at them.

Definition — alpha-beta

Let Γ be a finite two-player game. Alpha-beta is a depth-first search that carries two bounds α, β ∈ ℝ ∪ {−∞, +∞} along with it:

1. α — the highest value MAX has already secured somewhere on the path from the root (initially −∞);
2. β — the lowest value MIN has already secured (initially +∞).

The function AB(s, α, β) for a state s ∈ S:

1. If s ∈ K, return U(s).
2. If player(s) = MAX, set v ← −∞; otherwise v ← +∞.
3. For the moves a ∈ A(s) one by one (in a fixed order) compute h ← AB(T(s, a), α, β) and
   • in a MAX node set v ← max(v, h) and α ← max(α, v),
   • in a MIN node set v ← min(v, h) and β ← min(β, v);
   as soon as α ≥ β, the remaining moves are pruned — they are not searched — and you continue with step 4.
4. Return v.

Alpha-beta at the root is the call AB(s₀, −∞, +∞).

Theorem. Let Γ be a finite two-player game. Then AB(s₀, −∞, +∞) = MM(s₀) — alpha-beta returns the same value at the root as minimax (in inner nodes where a cutoff occurred, it returns only a bound, not the exact value). If the tree has branching factor b and depth m and the moves are ordered in the best possible order, alpha-beta examines only O(b^m/2) nodes.

prune when α ≥ β

α

the best MAX has already secured elsewhere on the path from the root. He will never go into a branch that gives less — he has a better choice

β

the worst for MAX that MIN can already force on him in this branch. MAX will not get more than β from here, however the remaining children turn out

≥

the window [α, β] is empty: a value still worth playing for here would have to be at least α and at most β at the same time. No such value exists (on equality it would be no better than what MAX already has), so the rest of the branch cannot influence the root

Alpha-beta reached the same result — MAX plays left and gets 4 — but evaluated only 6 leaves out of 9. In the middle branch it pruned two leaves right after the two, in the right one one leaf after the three. That is why the pruned MIN nodes show only the bound “≤ 2” and “≤ 3”: we do not know the exact value, and we do not need it.

What the animation shows next to the nodes, here step by step in a table. A row captures the window of a node on entering it and then after every child that returned a value:

A MIN node receives α = 4 from its parent and changes only its own β; a MAX node, conversely, changes only α. The window of each node therefore only narrows. In the right branch the first leaf (5) does not trigger a cutoff — 5 is more than 4, here MIN could give MAX more than on the left — only the second leaf (3) pulls β below α.

On tic-tac-toe the difference is more dramatic. Full minimax from the empty board visits 549,946 positions, alpha-beta with the same move ordering only 18,297 — about thirty times fewer — and returns the same zero. The exponent m/2 in the theorem means that in the same time you see twice as deep. That is why move ordering matters so much: chess programs try captures first, along with moves that were good last time.

Example — how many leaves alpha-beta saves with the best ordering

The exact bound was proved by D. E. Knuth and R. W. Moore (An Analysis of Alpha-Beta Pruning, 1975): in a tree with branching factor b and depth d, with the best move ordering alpha-beta evaluates

b^⌈d/2⌉ + b^⌊d/2⌋ − 1 leaves instead of b^d.

Chess, b = 35, depth d = 6 plies: minimax 35⁶ = 1,838,265,625 leaves, alpha-beta 35³ + 35³ − 1 = 42,875 + 42,875 − 1 = 85,749 leaves — about 21,000 times fewer. And the other way round: alpha-beta gets through 12 plies with 35⁶ + 35⁶ − 1 ≈ 3.7 · 10⁹ leaves, i.e. for only twice the work minimax needs for 6 plies.

The small tree from the figure (b = 3, d = 2): the bound is 3 + 3 − 1 = 5 leaves. Alpha-beta evaluated 6 of them, because the order of the leaves is not the best possible — in the right branch the three comes only second.

def alphabeta(board, alpha=-inf, beta=inf):
    end = winner(board)
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    maximizing = to_move(board) == "X"
    v = -inf if maximizing else inf
    for move in empty_squares(board):
        h = alphabeta(play(board, move), alpha, beta)
        if maximizing:
            v = max(v, h); alpha = max(alpha, v)
        else:
            v = min(v, h); beta = min(beta, v)
        if alpha >= beta:
            break                          # cutoff: the rest of the branch changes nothing
    return v

6. Limited depth and evaluation functions

Not even alpha-beta walks the chess tree to the end of the game. Real programs therefore search only to a fixed depth and estimate the position where they stop.

Definition — depth-limited minimax

Let Γ = (S, s₀, player, A, T, K, U) be a two-player game. An evaluation function is a function E : S → ℝ such that E(s) = U(s) for all s ∈ K; for s ∉ K, E(s) is an estimate of MM(s). It is usually a weighted sum of n ≥ 1 features of the position f₁, …, f_n : S → ℝ with weights w₁, …, w_n ∈ ℝ:

E(s) = w₁f₁(s) + … + w_nf_n(s).

Depth-limited minimax is, for every d ∈ ℕ₀, the function MM_d : S → ℝ defined recursively on d:

1. MM_d(s) = E(s) if s ∈ K or d = 0;
2. MM_d(s) = max_{a ∈ A(s)} MM_d−1(T(s, a)) if s ∉ K, d ≥ 1 and player(s) = MAX;
3. MM_d(s) = min_{a ∈ A(s)} MM_d−1(T(s, a)) if s ∉ K, d ≥ 1 and player(s) = MIN.

The value MM_d(s) thus computes minimax only d plies ahead and replaces the positions where it stops with the estimate E. If d is at least the length of the longest game from s, then MM_d(s) = MM(s).

E(s) = ∑_i w_i · (p_i(s) − p′_i(s))

E(s)

the estimate of the value of the position from the point of view of MAX (white) — it is plugged in where the search stops, instead of the real minimax value

∑_i

over the kinds of pieces: pawn, knight, bishop, rook, queen. A sum, because in the simplest model the material of different pieces simply adds up

w_i

the value of the piece: 1, 3, 3, 5, 9. The weight converts “pieces” into a common currency so that a rook can be compared with two knights

p_i − p′_i

how many more pieces of the given kind white has than black. A difference, not a count, because the game is zero-sum: whatever the opponent has extra is a loss

def minimax_d(s, d):
    if is_terminal(s) or d == 0:
        return E(s)                        # we cannot see further: an estimate instead of the real value
    values = [minimax_d(T(s, a), d - 1) for a in actions(s)]
    return max(values) if player(s) == "MAX" else min(values)

def iterative_deepening(s, time):         # MAX is to move in s
    d, best = 1, None
    while time_left(time):
        best = max(actions(s), key=lambda a: minimax_d(T(s, a), d - 1))
        d += 1                             # next round one ply deeper
    return best

Limited depth has its trap: the horizon effect. When the search stops in the middle of an exchange of pieces — you have just taken the queen, the opponent takes it back next move — the evaluation function sees only the first half and overrates the position. Programs defend against this by searching “unquiet” positions further until they settle down. And since they never know how much time they have, they search with iterative deepening from the previous part: depth 1, 2, 3, … until time runs out. The results of the shallow passes also serve as the move ordering for the deeper ones — and alpha-beta then prunes much more.

7. Monte Carlo tree search

People tuned evaluation functions for chess for decades. For go, nobody managed to write one — a position that looks calm can be lost twenty moves later. Monte Carlo tree search (MCTS) gives up on the evaluation function entirely. Instead of estimating the position, it plays it out: randomly, many times, and looks at how often it turned out well.

Definition — one iteration of MCTS

Let Γ = (S, s₀, player, A, T, K, U) be a finite two-player game in which every game ends in a win, a draw or a loss. Input: a state s₀ ∉ K (the root) and a number of iterations (or a time limit). Output: a move a ∈ A(s₀).

MCTS builds a search tree — a part of the game tree that starts as just the root and grows by one node in every iteration. Each node i of the tree remembers:

1. its visit count n_i ∈ ℕ₀ — how many simulations went through the node;
2. the sum of results w_i ∈ [0, n_i] from the point of view of the player who moved into the node, where the result of one game is 1 for a win, ½ for a draw and 0 for a loss.

A node is fully expanded if and only if it has a child in the tree for every move a ∈ A(s) of its state s. One iteration of MCTS has four steps:

1. Selection — start at the root; as long as the current node is fully expanded and its state is not terminal, go to the child with the highest UCT value (definition below).
2. Expansion — if the state of the current node is not terminal, pick a move a not tried yet, add a child with state T(s, a) and n = w = 0, and go to it.
3. Simulation — from the state of the current node, play the game out with random moves (each of A(s) with equal probability) until a terminal state s_K ∈ K.
4. Backpropagation — for every node i on the way from the current node back to the root (both included), set n_i ← n_i + 1 and w_i ← w_i + the result of the game s_K from the point of view of the player who moved into node i.

The iterations repeat until the number of iterations or the time runs out. Then the move from the root into the child with the largest n_i is played.

def mcts(root, iterations):
    for _ in range(iterations):
        u = root
        while u.all_children() and u.children:     # 1. selection
            u = max(u.children, key=uct)
        if u.untried and not is_terminal(u.state): # 2. expansion
            u = u.add_child(random_choice(u.untried))
        s = u.state
        while not is_terminal(s):                  # 3. simulation
            s = T(s, random_choice(actions(s)))
        while u is not None:                       # 4. backpropagation
            u.n += 1
            u.w += result(s, for_=u.who_moved)     # 1, ½ or 0
            u = u.parent
    return max(root.children, key=lambda c: c.n).move

Definition — UCT

Let a node of the MCTS search tree have N ≥ 1 visits and children i = 1, …, k, each with n_i ≥ 1 visits and a sum of results w_i ∈ [0, n_i] (notation from the MCTS definition above). Let c > 0 be a fixed exploration constant, usually c = √2. The UCT value (Upper Confidence bounds applied to Trees) of child i is

UCT(i) = w_i/n_i + c · √ln N/n_i.

In the selection step the child i* ∈ argmax_{i ∈ {1, …, k}} UCT(i) is chosen. Kocsis and Szepesvári (2006) proved that as the number of iterations grows, the probability that MCTS with UCT recommends a move other than the minimax-optimal one falls to zero.

UCT(i) = w_i/n_i + c · √ln N/n_i

UCT(i)

the score of child i in selection; the largest wins. It is not an estimate of the value of the move, but of “how much it pays to try it again”

w_i/n_i

the average result of the move (0 to 1) — exploitation: moves that have turned out well so far get priority

c

the exploration constant — how much curiosity weighs against the results so far. The value √2 comes from the UCB1 rule for multi-armed bandits (Auer, Cesa-Bianchi and Fischer, 2002) for results in [0, 1]; Kocsis and Szepesvári (2006) carried it over to trees. In practice it is tuned

ln N

grows with the number of visits to the parent, but only slowly. Thanks to it the bonus of rarely tried moves slowly grows: every move gets tried again sooner or later

n_i

how many times the move has been tried — in the denominator, so the less we know it, the bigger the bonus. The square root corresponds (simplified) to how fast the average becomes more precise: its uncertainty falls like 1/√n

Let us run MCTS on the position minimax solved above. The numbers in the squares are the visits after 100, 300 and 1000 iterations, below them the average result for X:

After 100 iterations the centre has 47 visits and the other moves together have more. After a thousand it has 856 and an average result of 0.94; the drawing move at the bottom middle got 52 visits, the losing moves even fewer. And MCTS knows neither the concept of a fork nor any evaluation function — only the rules and chance. Yet it found the same move as minimax, which had to walk the entire rest of the tree.

Why this particular distribution of visits? Let us compute the UCT of the moves from the root after 1000 iterations (N = 1000, ln N ≈ 6.908, c = √2; colours as in the formula above):

The UCT values are almost the same — between 1.049 and 1.068. That is no coincidence: selection always visits the move with the highest UCT and thereby lowers its bonus (the average changes only a little in the process), so the values gradually even out. The centre has the best average, so a small bonus is enough for it to even out — that is, many visits. The other moves have a worse average and make up for it with a large bonus, for which few visits suffice. (We compute the sums in the table from unrounded values, so they may differ by 1 in the last digit.)

8. From Deep Blue to AlphaZero

• Deep Blue (1997) beat world champion Garry Kasparov. Inside was alpha-beta with a hand-written evaluation function and specialized hardware that handled about 200 million positions per second.
• Chinook played checkers against world champions as early as the 1990s, and in 2007 its authors solved the game: they went through so many positions that they proved a flawless game ends in a draw — just like tic-tac-toe on 3 × 3.
• AlphaGo (2016) beat Lee Sedol 4 : 1. It combined MCTS with neural networks: one network proposed promising moves (instead of random selection), the other estimated the value of a position (instead of a whole random playout).
• AlphaZero (2017) threw away even human games. It learned chess, shogi and go only by playing against itself — through reinforcement learning — and in each of the games beat the best program up to then.
• Games with chance and hidden information need more. In backgammon the dice decide, so chance nodes with an expected value are added to the tree (expectiminimax). In poker you do not see the opponent’s cards; even so, the program Libratus (2017) beat professionals at two-player poker.

Definition — expectiminimax

Let Γ = (S, s₀, player, A, T, K, U) be a finite game as in the definition of a two-player game, except that to the players MAX and MIN a “player” CHANCE is added: player : S ∖ K → {MAX, MIN, CHANCE}, and the turn-taking condition is not required. For every state s with player(s) = CHANCE, A(s) is a finite non-empty set of possible chance outcomes r (say the numbers on a die) and a probability distribution P_s : A(s) → [0, 1] with ∑_{r ∈ A(s)} P_s(r) = 1 is given (see the part on probability); the outcome r occurs with probability P_s(r) and leads to state T(s, r).

The expectiminimax value is the function EMM : S → ℝ defined recursively:

1. EMM(s) = U(s) if s ∈ K;
2. EMM(s) = max_{a ∈ A(s)} EMM(T(s, a)) if player(s) = MAX;
3. EMM(s) = min_{a ∈ A(s)} EMM(T(s, a)) if player(s) = MIN;
4. if player(s) = CHANCE, EMM(s) is the expected value of the values of the successors: EMM(s) = ∑_{r ∈ A(s)} P_s(r) · EMM(T(s, r)).

In MAX and MIN nodes the value is thus computed as in minimax, and in chance nodes as an average weighted by the probabilities of the outcomes. A breakdown of the last formula (P_s shortened to P):

EMM(s) = ∑_r P(r) · EMM(T(s, r))

EMM(s)

the value of a chance node — what MAX can expect from the position on average, because neither he nor the opponent can influence the outcome of the throw

∑_r

over all possible chance outcomes; instead of picking the best (max) or the worst (min), nothing is picked here — every one is counted

P(r)

the probability of the outcome as a weight: a frequent outcome influences the value more than a rare one

EMM(T(s, r))

the value of the position after the given outcome, computed recursively by the same rule

The idea “look ahead before you do something” has not disappeared from the chessboards. Planning language agents try several variants of a procedure, evaluate them and continue with the most promising one — only instead of moving pieces, they choose steps of a solution.

9. Summary

• A two-player zero-sum game is a search problem in which you share the moves with an opponent; its solution is a strategy, not a path.
• Minimax computes the value backwards: MAX takes the maximum, MIN the minimum. The result is guaranteed against any opponent.
• Alpha-beta returns the same value, but prunes branches that cannot change the result; with a good move ordering it sees twice as deep.
• Large games are searched to a limited depth with an evaluation function — and watch out for the horizon effect.
• Instead of evaluating a position, MCTS plays it out randomly many times and grows the tree where it looks promising; combined with neural networks it became AlphaGo.

Want to get hands-on? Have an AI agent write tic-tac-toe with minimax, and then count how many positions alpha-beta saves when you order the moves from the centre to the edges.

Do you see it differently? Write to support@coden-app.com.