Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 46 ยท Adversarial Search

Evaluation Functions and Depth-Limited Search

Make game search practical: write a heuristic evaluation for Connect Four, cap the search depth, use iterative deepening, and see the horizon effect and quiescence search.

Minimax and alpha-beta pruning give perfect play, but only if the search can reach the end of the game. In chess there are roughly 10^40 positions and in Go far more, so no computer will ever search to the bottom. Even in Connect Four, with its modest board, a full search from the first move is heavy for a plain Python program.

The practical fix has two parts. First, stop searching at a fixed depth. Second, at that cutoff, replace the real game result with a quick guess of how good the position looks: an evaluation function. In this lesson you will write one for Connect Four, watch how the answer changes as the depth grows, search with a budget instead of a fixed depth, and meet the main weakness of the whole approach, the horizon effect.

From terminal test to cutoff test

Plain minimax asks one question at every node: "is the game over?" If yes, it returns the true utility (win, draw, loss). Depth-limited minimax replaces that with a cutoff test: "is the game over, or have I searched deep enough?" At a cutoff node that is not a real end of the game, the program returns evaluate(position) instead of a true utility.

graph TD
    R["Current position<br/>(MAX to move)"] --> A["Move A"]
    R --> B["Move B"]
    A --> A1["Reply 1<br/>evaluate() = +12"]
    A --> A2["Reply 2<br/>evaluate() = +4"]
    B --> B1["Reply 1<br/>evaluate() = +7"]
    B --> B2["Reply 2<br/>evaluate() = +9"]

With a depth limit of 2, the leaves are scored by the evaluation function, not by the true end of the game. MIN picks 4 under A and 7 under B, so MAX plays B.

Everything else, including alpha-beta pruning, stays exactly the same. The quality of the play now depends almost entirely on the quality of evaluate.

What makes a good evaluation function

An evaluation function maps a position to a number from MAX's point of view: large and positive when MAX is doing well, large and negative when MIN is. A good one has three properties.

  1. It agrees with the true outcome at real game endings. A won position must score higher than any unfinished one.
  2. It is fast. It runs at every leaf, so a million leaves means a million calls. A slightly worse function that is ten times faster usually wins because it lets the search go deeper.
  3. It correlates with winning chances. Positions that look better to the function should win more often than positions that look worse.

The classic recipe is a weighted sum of features: eval = w1*f1 + w2*f2 + .... In chess the features are things like material count, pawn structure and king safety. For Connect Four the natural feature is a window: any run of four adjacent cells (horizontal, vertical or diagonal). There are exactly 69 such windows on the 6 by 7 board. A window that holds only your pieces and empty cells is still a possible win for you. A window with pieces from both players is dead. So we score:

  • a window with three of your pieces and one empty cell: +50 (a real threat);
  • two of your pieces and two empty cells: +5;
  • the same patterns for the opponent, with the sign flipped;
  • a small bonus for the centre column, which belongs to the most windows.

The weights 50, 5 and 3 are guesses, and that is typical. Tuning them, by hand or by automatic learning from game records, is a large part of building a strong game program.

Python Connect Four: evaluation and depth-limited alpha-beta

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.

Run it and read the table. The static evaluation of the board is 13, a slight edge for X. As the depth grows, the node count rises (8, 35, 167, 452, 2,374, 5,040) and the reported value jumps around: 103, 48, 128, 78, 173, 108. The best column also changes, from 1 to 2 and finally to 4. Deeper search is not always "more of the same": it keeps discovering replies that the shallower search could not see.

Why the values zigzag

Look at the pattern in the values: odd depths (1, 3, 5) report higher numbers than the even depths next to them. This is a real effect, not a bug. At an odd depth the last ply was played by MAX, so every leaf shows a position where MAX has just made a nice move and MIN has not yet answered. The evaluation is optimistic. At an even depth MIN has just moved and the leaves look worse for MAX.

The cure is to search deeper, to prefer comparing results at the same parity, or to use a more careful cutoff rule such as quiescence search, which comes at the end of this lesson.

Iterative deepening for games

How deep should you search? In a real game you do not choose a depth, you have a clock: "30 seconds for this move". A fixed depth either wastes time (the answer was ready long ago) or runs out before it finishes (no answer at all).

Iterative deepening solves this. Search to depth 1, then to depth 2, then depth 3, and so on, and always remember the best move from the last completed depth. When time runs out, play that move. This is the same idea as iterative-deepening DFS from uniform-cost and iterative deepening, with a very different purpose: here it gives an anytime algorithm.

graph LR
    S["depth = 1"] --> R["search to this depth,<br/>best move first"]
    R --> K{"budget left?"}
    K -- "yes" --> M["remember best move<br/>depth = depth + 1"]
    M --> R
    K -- "no" --> P["play the move from<br/>the last finished depth"]

Each iteration repeats the earlier work, but the earlier work is tiny compared with the newest layer.

Repeating the shallow searches sounds wasteful, but because the tree grows exponentially, the last iteration dominates. And the earlier iterations give something valuable back: the best move from depth dโˆ’1 is usually the best, or nearly the best, move at depth d. Searching it first makes alpha-beta prune much more. Real programs also store the whole best line (the principal variation) in a transposition table.

To keep the demo deterministic we use a node budget instead of a clock. A real engine would check time.time() in the same place.

Python Iterative deepening with a node budget

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.

With a budget of 500 nodes the program gets through depth 3 and plays column 2. With 3,000 it reaches depth 5 and plays column 4. With 8,000 it finishes depth 6 after a cumulative 7,257 nodes and still plays column 4. For comparison, the direct depth-6 search uses 5,040 nodes, so iterative deepening costs about 44% more in total here. In return the program always holds a usable answer, and in a bigger game the early iterations are an even smaller fraction of the total.

Iterative deepening gives you a free move-ordering heuristic. In the demo the previous best move is simply put first at the root. Real engines apply the same idea at every node using stored best moves, the killer move trick and history tables.

The horizon effect

Depth-limited search has a famous failure. The program can only see to its horizon, and a bad event just beyond the horizon looks like it never happens.

Imagine a chess program searching two plies. It can capture a pawn with its queen. The pawn is defended, so the opponent will recapture the queen on the next ply, but that ply is beyond the horizon. The evaluation at the cutoff says "I am a pawn up!" and the program makes the losing capture. The reverse is just as bad: facing an unavoidable loss, a program may throw away pieces with useless delaying checks to push the loss over the horizon.

graph LR
    ROOT["Root"] -- "grab the pawn" --> G["Cutoff here: +9<br/>looks great"]
    G -. "beyond the horizon" .-> RC["Recapture: -1<br/>the real value"]
    ROOT -- "develop a knight" --> D["Cutoff here: +1"]

The grab is scored at the horizon, one ply before the opponent's recapture.

The standard defence is quiescence search. The evaluation function is only trustworthy in quiet positions, where nothing dramatic is about to happen. So when the depth limit is reached in a volatile position (a pending capture, a check, an unstoppable threat), the program does not stop. It keeps searching, but only along the volatile moves, until the position calms down, and only then calls evaluate. Real quiescence search also lets the side to move "stand pat", meaning it may declare the current evaluation good enough rather than being forced to continue a bad capture sequence.

The demo below uses a tiny hand-made game tree so you can see the effect in isolation. Each node stores who moves, a static value, and a flag saying whether the position is volatile.

Python The horizon effect and quiescence on a tiny tree

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.

A plain depth-1 search sees the grab as +9 and takes it. Depth 2 sees the recapture and corrects the value to -1. The depth-1 search with quiescence reaches the same answer as depth 2, because the volatile node g1 is not scored until the recapture has been played. In practice quiescence is cheaper than a full extra ply, since only a few forcing moves are explored.

Putting it together

A typical game-playing program for a new game follows this plan.

  1. Write the game rules (moves, terminal test, utilities).
  2. Write a cheap evaluation from a few features and weights.
  3. Add alpha-beta pruning and good move ordering.
  4. Wrap it in iterative deepening with a time limit.
  5. Add quiescence where the evaluation is unstable.
  6. Tune the weights by playing the program against itself and older versions.

Tuning by self-play is exactly what the Connect Four project at the end of this course asks you to do.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a depth-limited game search return at a cutoff node that is not a finished game?

    The cutoff test replaces the terminal test, and the heuristic evaluation function replaces the true utility at those nodes.
  2. 2. Why is iterative deepening useful in a game with a clock?

    It is an anytime method. It repeats some work, but it always holds a finished answer, and the previous best move improves move ordering for the next, deeper iteration.
  3. 3. What is the horizon effect?

    A fixed cutoff hides what happens one ply later, for example a recapture. This can make bad captures look good or make delaying moves look attractive.
  4. 4. When does quiescence search keep searching after the depth limit?

    Evaluations are only reliable in quiet positions, so volatile positions are searched further, along forcing moves only, until they calm down.
  5. 5. Which property matters most when choosing between two evaluation functions of similar accuracy?

    The function runs at every leaf. Extra speed buys extra search depth, which usually improves play more than a slightly better estimate.

Summary

  • Depth-limited search replaces the terminal test with a cutoff test and the true utility with an evaluation function.
  • A good evaluation is accurate at game endings, fast, and correlated with winning; it is often a weighted sum of features such as Connect Four windows.
  • Deeper search changes values and best moves, and odd and even depths show a zigzag because the last mover differs.
  • Iterative deepening searches depth 1, 2, 3, ... under a time or node budget, keeps the last finished answer and improves move ordering.
  • The horizon effect hides events beyond the cutoff; quiescence search extends volatile positions until they are quiet.

Next: Expectiminimax and Monte Carlo Tree Search.