Can a cutoff test use more than depth?

Yes. Time, resource limits or state-dependent conditions can influence stopping.

Does reaching a cutoff mean search failed?

No. It can be an intended bounded decision procedure.

Can quiescence search eliminate every horizon problem?

No. It addresses selected unstable situations and still uses a finite analysis policy.

AI Glossary / Graphs and symbolic AI / Intermediate

Cutoff test

Definition

A cutoff test is a condition that tells a search algorithm to stop expanding a state before the complete underlying problem has necessarily ended. In depth-limited game search, it commonly stops at a chosen depth, time limit or suitable evaluation point and uses an estimated state value.

What it means

A game may have too many future positions to search all the way to a win, loss or draw. A cutoff test makes computation manageable by deciding where the search horizon ends for the current analysis.

This differs from a terminal test. A terminal state is an actual endpoint under the game rules. A nonterminal state can satisfy a cutoff test simply because the available search budget has been reached. Its score is then an estimate, not necessarily the final outcome.

The phrase is also distinct from an alpha-beta cutoff. Alpha-beta pruning can skip a branch because established bounds show it cannot affect the current minimax result. A depth cutoff instead replaces further exploration with an evaluation and can change which move appears best.

A useful search description therefore states both when expansion stops and how stopped states are scored.

How it works

At each visited state, check whether the game is terminal or the chosen stopping conditions apply. Terminal states should receive their proper outcome value. Nonterminal cutoff states are evaluated with a heuristic estimating their desirability for the relevant player.

Back up those values through the search tree, using the algorithm's decision rules. In minimax, one player selects maximum values and the opponent selects minimum values. The root decision is exact only for the constructed depth-limited evaluation tree, not automatically for the full game.

A depth rule must define what one level means: an individual action, a full turn or another unit. A time-based rule needs a policy for interrupted branches and partially completed iterations. Iterative deepening often retains a result from the last completed depth rather than treating unfinished work as equivalent evidence.

Quiescence search can extend selected unstable positions, such as positions with immediate tactical exchanges, before evaluation. It can reduce some horizon effects but also needs limits to avoid uncontrolled expansion.

The cutoff and evaluation function interact. A shallow horizon with a poor evaluator may miss consequences that a deeper search would reveal, while deeper search still depends on its eventual stopping boundary.

Three practical examples

A board-game engine stops ordinary search at a specified action depth and evaluates remaining positions heuristically.
An interactive planning demonstration imposes a time budget and clearly distinguishes its best completed analysis from unfinished branches.
A game-search experiment compares fixed-depth evaluation with selective extensions around unstable tactical positions.

Think of it this way

Think of inspecting a route only as far as the visible bend and estimating what lies beyond it. The stopping point limits the evidence used in the decision.

The analogy does not mean the route ends at the bend. Nor does a promising estimate beyond the bend establish the actual outcome. The distinction between an observation boundary and a real endpoint is the central idea.

Worked example

A horizon that reverses a move choice

At a maximizing root, two moves lead to nonterminal states A and B. A depth-one cutoff evaluates A as 8 and B as 6, so the shallow search chooses A.

Now extend one opponent response level. Suppose A allows replies with evaluated values -4 and 9. Since the opponent minimizes the root player's value, A backs up to min(-4, 9) = -4. B allows replies with values 3 and 5, so B backs up to 3.

The deeper search chooses B because 3 exceeds -4. The original score of 8 for A was a heuristic estimate at the earlier cutoff, not a proved value that the deeper search contradicted logically.

If the new reply states are still nonterminal, their values also remain estimates. Searching one level deeper improves the information available in this example but does not prove that B is optimal in the complete game. The result illustrates why stopping policy and evaluation accuracy should be assessed together.

Illustrative case study

Fictional case: Birch Games limits an engine to three action levels and describes the selected move as optimal. Reviewers find positions where an important reply falls just beyond that horizon.

The team revises the claim to identify the searched depth and evaluator, adds tactical test positions and compares equal-time performance for alternative stopping policies. It also records whether a timed search completed its final iteration.

The lesson is that a valid minimax calculation over a truncated tree does not justify an unlimited optimality claim.

Common misconceptions and mistakes

A cutoff state must be a terminal state. Search can stop at a nonterminal state because of resource limits.
A heuristic cutoff value is the actual final payoff. It is an estimate unless separately established.
Alpha-beta pruning and depth cutoff have the same guarantee. They stop work for different reasons.
A larger depth number always means more comparable evidence. Selective extensions and depth conventions can differ.
A time limit alone defines a complete algorithm. Interrupted-search handling also needs specification.

Business use

Cutoff tests make search usable under practical time and memory limits. They are relevant wherever a system must return a decision before exploring all possible consequences.

For an evaluation, report the stopping rule, depth convention, evaluator and treatment of terminal states. Compare alternatives under a budget that matches the intended application. Keep benchmark cases that expose delayed consequences rather than relying only on easy positions. When communicating results, distinguish a completed bounded search from a full solution or a proof of optimality.

Check your understanding

A state is not a game endpoint, but the search reaches its maximum depth. Should its heuristic score automatically be reported as the game's final utility?

Answer: No. It is a cutoff evaluation of a nonterminal state and should retain that interpretation.

Related terms

Terminal test
Evaluation function
Minimax
Alpha-beta pruning
Quiescence search
Search horizon
iterative deepening
bounded search

Learn next

Draw the two-move example and calculate the backed-up values at both horizons. Then change the evaluator at the cutoff states while keeping the tree unchanged. Explain separately how additional search and a better evaluator can affect the decision.

Sources

AIMA game-playing implementation, alpha_beta_cutoff_search and cutoff/evaluation interfaces: https://aimacode.github.io/aima-python/_modules/aima/games.html

AIMA fourth-edition game-playing slides, cutoff tests and quiescence: https://aima.cs.berkeley.edu/4th-ed/slides-pdf/chapter06.pdf

The move values and fictional engine review are original teaching examples.

Previous: Cut-off sampling Next: Cutset conditioning