Skip to content
Tutorials Center
My learning

Topics

Lesson 208 of 225 ยท Advanced Topics

Minimax, Alpha-Beta Pruning and Zobrist Hashing

Build a perfect tic-tac-toe player in Python with minimax, speed it up with alpha-beta pruning and add a transposition table keyed by Zobrist hashing.

How does a computer play chess, checkers or tic-tac-toe? It looks ahead. It imagines its move, then the opponent's best reply, then its own best reply to that, and so on, and picks the move that leads to the best outcome assuming both sides play well. That idea is minimax, and it works for every two-player game with perfect information and alternating turns.

The tree of positions grows explosively, so real programs need two accelerators. Alpha-beta pruning skips branches that cannot change the result, often searching the square root of the nodes. Zobrist hashing gives every position a cheap 64-bit fingerprint so a transposition table can remember positions already solved. We build all three for tic-tac-toe and measure the savings. This lesson builds on game theory and Nim and uses ideas from hash functions and recursion.

Game trees

A game tree has a node per position and an edge per legal move. Leaves are finished games: win, loss or draw. For tic-tac-toe, score from player X's point of view: +1 if X wins, -1 if O wins, 0 for a draw.

  • On X's turn, choose the child with the maximum score.
  • On O's turn, choose the child with the minimum score.
flowchart TD
  A["X to move: MAX"] --> B["O to move: MIN"]
  A --> C["O to move: MIN"]
  B --> D["+1"]
  B --> E["-1"]
  C --> F["0"]
  C --> G["+1"]

MIN nodes pick the smaller child (-1 and 0), so MAX picks the larger of those: 0.

Minimax

The recursive function returns the value of a position under perfect play.

Python Minimax for tic-tac-toe

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 value of the empty board is 0: with perfect play, tic-tac-toe is a draw. The search visits 549,946 positions, which is fine for a toy game, but chess has more positions than atoms, so we must cut work.

Alpha-beta pruning

Keep two numbers while searching: alpha, the best score MAX can already guarantee on the path to the root, and beta, the best (lowest) score MIN can guarantee. If at some node alpha >= beta, the opponent would never allow this position, so the remaining children cannot affect the answer and are skipped (cutoff).

Alpha-beta returns exactly the same value as minimax. With good move ordering it examines about b^(d/2) nodes instead of b^d, effectively doubling the search depth. In the worst case (bad ordering) it still searches everything.

Python Alpha-beta versus minimax

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.

Alpha-beta cuts the node count to a small fraction without changing any value. Ordering matters: trying the best move first (the center and corners in tic-tac-toe) gives bigger savings.

Transpositions and Zobrist hashing

Different move orders can reach the same position. X center, O corner, X edge reaches the same board as X edge, O corner, X center. These are transpositions, and minimax solves each one again and again. A transposition table caches the value of each position seen.

The question is how to key the table cheaply. Using the board as a tuple or string works but hashing 9 or 64 cells on every lookup is slow in big games. Zobrist hashing assigns a random 64-bit number to every (square, piece) pair, and defines a position's hash as the XOR of the numbers for the pieces on the board. Making or undoing a move updates the hash with a single XOR, because x ^ k ^ k == x.

TEXT
hash = Z[0][piece0] ^ Z[1][piece1] ^ ... ^ Z[8][piece8]   (empty squares contribute nothing)
place X on square 4:   hash ^= Z[4]['X']
undo it:               hash ^= Z[4]['X']

With 64-bit hashes the chance of two different positions colliding is tiny (about n^2 / 2^65 for n positions). Real engines accept that risk, or store extra check bits.

Python Zobrist hash with a transposition table

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 table holds 5,478 distinct positions (the number of reachable boards), and the search touches only about 16,000 nodes instead of 549,946, because 10,690 lookups hit the cache.

Putting it together: a perfect player

Combine alpha-beta with the transposition table for stronger programs. One subtlety: with alpha-beta, a stored value may be only a bound (the search was cut off), so real engines also store whether it is exact, a lower bound or an upper bound. For small games like tic-tac-toe, exact memoization plus alpha-beta on top is not needed, since the memoized plain minimax is already instant.

Python Self-play: perfect play ends in a draw

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.

Practical notes

Technique What it saves Cost
Minimax nothing, exact O(b^d) nodes
Alpha-beta skips refuted branches, same result O(b^(d/2)) with ideal ordering
Move ordering makes cutoffs happen sooner needs a good heuristic
Transposition table re-solving repeated positions memory; store exact/lower/upper bound with alpha-beta
Zobrist hash cheap incremental keys tiny risk of collisions
Depth limit and evaluation function allows big games not exact; quality depends on the heuristic

Common mistakes: forgetting to include the side to move in the table key, mutating the board without undoing the move, passing the wrong sign convention for the players (be consistent: scores always from X's view), and caching alpha-beta results as if they were exact.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In minimax scoring from X's point of view, what does the O player do at its own nodes?

    O wants the outcome that is worst for X, so O chooses the child with the smallest score.
  2. 2. What does alpha-beta pruning change about the result of minimax?

    Pruned branches provably cannot affect the root value, so the answer is identical.
  3. 3. Why is Zobrist hashing built on XOR?

    Since x ^ k ^ k = x, placing and removing a piece uses the same single XOR, which makes incremental hashing trivial.
  4. 4. What is the value of tic-tac-toe under perfect play?

    The minimax value of the empty board is 0, a draw.

Summary

  • Minimax scores a position by assuming MAX picks the largest and MIN the smallest child value; it visits O(b^d) nodes.
  • Alpha-beta pruning keeps bounds alpha and beta and stops when alpha >= beta, returning the same value with far fewer nodes (about b^(d/2) with good ordering).
  • A transposition table avoids re-solving positions reached by different move orders; remember the side to move in the key.
  • Zobrist hashing XORs random 64-bit numbers per (square, piece), giving cheap incremental position keys.
  • For big games, add a depth limit and an evaluation function; for exact bounds with alpha-beta, store whether a cached value is exact, a lower bound or an upper bound.

Next: Pick's Theorem, Half-Plane Intersection and Bresenham