Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 46 ยท Adversarial Search

Games and Minimax

Learn how AI plays two-player games: game formulation, zero-sum games, game trees and the minimax algorithm, with a perfect tic-tac-toe player and real state and node counts.

Every search method so far assumed a world that sits still while you plan. In a game, the world pushes back: after each move you make, an opponent chooses a reply designed to hurt you. A plan that works only if the opponent cooperates is worthless. Adversarial search is how a program chooses moves while assuming the other player is trying to win too.

This lesson introduces the formal setup for two-player games, the game tree, and the minimax algorithm that finds perfect play. You will implement it for tic-tac-toe, count how large even this tiny game really is, and see why the same idea cannot be applied directly to chess. The next lessons show how to prune the tree and how to cope when it is too big.

What kind of game?

The classical theory covers games that are:

  • Two-player, turn-taking: players alternate moves (we call them MAX and MIN).
  • Deterministic: no dice or shuffled cards.
  • Perfect information: both players see the entire state (chess, checkers, Go, tic-tac-toe; not poker).
  • Zero-sum: whatever one player gains, the other loses. A win is +1, a loss is -1 and a draw is 0, so the payoffs always add up to zero. MAX tries to maximize the value and MIN tries to minimize it.

Dice (backgammon), hidden cards (poker) and more than two players need extensions, some of which appear in Expectiminimax and Monte Carlo Tree Search.

Formulating a game

A game is described much like a search problem, with extra pieces:

Component Meaning Tic-tac-toe
Initial state How the game starts The empty 3x3 board, X to move
to_move(s) Whose turn it is in state s X if equal marks, else O
actions(s) The legal moves The empty squares
result(s, a) The state after move a Board with the mark added
is_terminal(s) Is the game over? Three in a row, or full board
utility(s) The final payoff (from MAX's view) +1 X wins, -1 O wins, 0 draw

These functions define the game tree: the root is the initial state, the children of a node are the states reachable by one legal move, and the leaves are terminal states. Each level of the tree is called a ply, which is one move by one player.

The minimax idea

Suppose the whole tree is available. Label every leaf with its utility. Now work upward:

  • At a node where MAX moves, MAX picks the child with the highest value, so the node's value is the maximum of its children.
  • At a node where MIN moves, MIN picks the child with the lowest value, so the node's value is the minimum of its children.

The value of the root is the outcome both players can force with perfect play, and the child that achieves it is the best move. This is minimax.

graph TD
    R["MAX to move<br/>value = 6"] --> A["MIN<br/>value = 5"]
    R --> B["MIN<br/>value = 4"]
    R --> C["MIN<br/>value = 6"]
    A --> a1["6"]
    A --> a2["9"]
    A --> a3["5"]
    B --> b1["4"]
    B --> b2["12"]
    B --> b3["8"]
    C --> c1["7"]
    C --> c2["10"]
    C --> c3["6"]

A tiny two-ply tree. Each MIN node takes the smallest of its leaves (5, 4, 6) and the MAX root takes the largest of those, so the best move is the third one and the guaranteed value is 6.

Notice what the algorithm assumes: that MIN always plays the reply that is best for MIN. That is pessimistic but safe. If the opponent blunders, you can only do better than the minimax value.

TEXT
minimax(state):
    if state is terminal: return utility(state)
    if MAX to move: return max(minimax(child) for each child)
    if MIN to move: return min(minimax(child) for each child)

It is a depth-first traversal, so it uses memory proportional to the depth of the tree, but time proportional to the whole tree: with branching factor b and depth m, O(b^m) time and O(b * m) space (or O(m) if moves are generated one at a time).

Counting the tic-tac-toe universe

Before running minimax it is worth knowing how big the game is. Tic-tac-toe looks trivial, yet the full game tree has hundreds of thousands of nodes, and the number of distinct positions is much smaller because different move orders reach the same board.

Python Tic-tac-toe: states, game tree and outcomes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same game appears as 5,478 distinct positions but a tree of 549,946 nodes, because each position is reached through many different move orders. Those orders correspond to 255,168 complete games. Of these, X (the first player) wins 131,184, O wins 77,904, and 46,080 end in a draw. Hold on to the contrast between 5,478 and 549,946: in the next lesson one remedy for it is a transposition table.

Implementing minimax

Here is the algorithm on the full game. The function returns the minimax value from X's perspective (+1, 0, -1) and counts how many nodes it visited.

Python Minimax from the empty board

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The run visits exactly 549,946 nodes, the same as the tree count above, and the empty board has value 0: with perfect play from both sides, tic-tac-toe is a draw. In the tactical position, minimax finds the immediate win at square 2 and returns +1. The next demo shows that every opening move for X also has value 0, so no first move can force a win against a perfect opponent (though some are easier for a careless opponent to answer wrongly).

Terminal states stop the search. The 549,946 count includes every node down to a win or a full board. Minimax visits exactly as many nodes as the tree has. In a game that goes on for 80 or more moves, this full enumeration is impossible, and that is the motivation for everything that follows.

Perfect play in action

Because the minimax value is the best result a player can guarantee, a player that always picks a minimax move can never lose tic-tac-toe. The next demo uses a memoized version of minimax (remembering each position's value so it is computed once) and plays 200 games of the perfect player against a random opponent, in each seat, with a fixed seed. Then two perfect players play each other.

Python Perfect player versus random player

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first line lists the value of all nine opening moves: all 0. As the theory predicts, the perfect player never loses. Moving first it wins 194 of 200 games against the random opponent and draws the other 6; moving second it wins 153 and draws 47. Perfect against perfect ends in a draw in all 20 games.

Why minimax is not enough

Tic-tac-toe has about half a million tree nodes. Chess has an average branching factor of roughly 35 and games of about 80 plies, so the tree has on the order of 35^80, or around 10^120 nodes, vastly more than the number of atoms in the observable universe. Go is far larger still. Minimax is the correct definition of optimal play but it cannot be run to the end of the game.

Two families of ideas rescue it, and they fill the rest of this chapter:

  1. Do less work for the same answer: alpha-beta pruning skips branches that provably cannot change the result, and transposition tables avoid re-searching positions.
  2. Settle for an estimate: cut the search off at a depth limit and score unfinished positions with an evaluation function.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a zero-sum two-player game, what does MIN try to do?

    Utility is measured from MAX's side. Because the game is zero-sum, MIN's gain is MAX's loss, so MIN picks moves with the lowest values.
  2. 2. How is the minimax value of a MAX node computed?

    MAX chooses the best move for itself, so the node's value is the maximum over its children. MIN nodes take the minimum.
  3. 3. What is the minimax value of the empty tic-tac-toe board?

    With perfect play by both sides tic-tac-toe is a draw, so the value is 0.
  4. 4. Why does the tic-tac-toe game tree (549,946 nodes) have far more nodes than there are distinct positions (5,478)?

    The tree counts one node per path, so a position reached by many orders of moves appears many times. Transposition tables exploit this.
  5. 5. What is the time complexity of minimax for branching factor b and depth m?

    Minimax explores the entire game tree, which has about b^m nodes. Its memory use is only linear, because it is a depth-first search.

Summary

  • Adversarial search chooses moves while assuming the opponent plays well; the standard model is a two-player, turn-based, deterministic, perfect-information, zero-sum game.
  • A game is defined by an initial state, to_move, actions, result, a terminal test and a utility function; together they define the game tree.
  • Minimax gives MAX nodes the maximum and MIN nodes the minimum of their children's values, and returns the value both sides can force.
  • Tic-tac-toe has 5,478 positions but a 549,946-node game tree; its minimax value is 0 (a draw), and a perfect player never loses.
  • Minimax takes O(b^m) time, which is hopeless for chess or Go; pruning and evaluation functions are the way out.

Next: Alpha-Beta Pruning.