Does f stand for a learned evaluation function?

In the driver notation, f is the initial value guess. A separate evaluation function may be used at search leaves.

Can MTD(f) work efficiently without stored search information?

Repeated searches can revisit substantial work; memory reuse is a defining practical part of the method.

Does finding the depth-limited minimax value prove the best real-game move?

Not necessarily. Leaf evaluation and the limited horizon can differ from the eventual game outcome.

AI Glossary / Graphs and symbolic AI / Advanced

MTD(f)

Definition

MTD(f) is a minimax search algorithm that repeatedly calls a memory-enhanced alpha-beta search with a narrow, zero-window test until lower and upper bounds meet. It starts from a first guess f for the position's value. The result is the minimax value for the specified search depth and evaluation setup, not necessarily the solved value of the entire game.

What it means

A normal wide-window alpha-beta search tries to determine a value within a broad range. MTD(f) instead asks a series of threshold questions and retains the resulting bounds. Each test may prune strongly, but its answer is usually only a bound rather than a complete exact value.
The memory component is central. A transposition table stores information from searched positions so later tests can reuse it rather than starting from scratch. The name is associated with “Memory-enhanced Test Driver.” MTD(f) is a game-tree search technique, distinct from Monte Carlo tree search despite the nearby abbreviations and shared use of trees.

How it works

Initialize the lower bound below all possible scores and the upper bound above them. Use the current guess to choose a threshold beta, then run alpha-beta with the integer-score window [beta-1,beta]. A fail-low result supplies an upper bound; a fail-high result supplies a lower bound. Repeat until the bounds coincide.
When the current guess equals the lower bound, the standard integer formulation tests one score unit higher to make progress. A first guess from a previous iterative-deepening search can reduce repeated work. Correctness and efficiency depend on sound bounds, consistent search semantics, and reliable stored information; a narrow window does not make implementation errors harmless.

Three practical examples

A chess-engine experiment can use MTD(f) as a driver around an existing alpha-beta search with a suitable transposition table.
A game-search course can compare exact-value searches with repeated threshold tests on a small minimax tree.
An engine developer can investigate how first-guess quality, evaluation granularity, and table reuse affect search work on a fixed set of positions.

Think of it this way

Think of narrowing a hidden number by asking threshold questions while keeping all earlier deductions. The memory prevents repeating the same reasoning unnecessarily. The analogy is limited because each threshold question itself requires a potentially expensive game-tree search, and the returned fail-soft bound can reveal more than a simple yes or no.

Worked example

Consider an invented depth-two minimax tree. The root is a MAX node with two MIN children. Child A has leaf scores 4 and 7, so its exact value is 4. Child B has leaf scores 6 and 9, so its exact value is 6. The root's minimax value is therefore max(4,6) = 6.
Start MTD(f) with first guess 5 and bounds negative infinity and positive infinity. The first test uses beta = 5 and window [4,5]. Suppose the correct fail-soft search returns 6. This is a fail-high result, establishing lower bound 6; it does not yet establish the matching upper bound.
The guess now equals the lower bound, so the next beta is 7 and the window is [6,7]. A correct search returns 6, which is below beta and supplies upper bound 6. The bounds meet at 6, and the driver stops. The particular returned bounds are consistent with this tree. The example illustrates convergence and bound interpretation, not measured runtime or a claim that every search takes two tests.

Illustrative case study

In a fictional board-game engine, a developer replaces a wide-window search driver with MTD(f). A small test set produces inconsistent results at the same depth. Investigation finds that some cached bounds were being reused without checking whether their stored search depth was sufficient.
The team repairs table validation and compares results against a plain minimax reference on small trees before measuring speed on larger positions. It records node counts, elapsed time, and first-guess behavior separately. The case illustrates why caching correctness comes before performance claims; it does not report a real engine benchmark.

Common misconceptions and mistakes

A zero-window search does not use an empty interval in the sense of doing no work. With integer scores, adjacent bounds create a threshold test with no integer value strictly between them. For other score representations, the implementation needs an appropriate precision convention.
Do not treat a fail-high return as an exact value merely because it looks plausible. Distinguish lower bounds, upper bounds, and exact entries in the table. Also avoid assuming that MTD(f) is always faster than other alpha-beta variants. Search position, move ordering, score granularity, first guess, and memory behavior all affect performance.

Business use

MTD(f) is mainly relevant to teams building game engines or specialized adversarial search systems. Its business value is an engineering question: can repeated narrow tests reuse enough work to improve useful search depth within the product's response-time budget?
Benchmark the actual implementation on representative positions rather than extrapolating from historical claims. Hold evaluation, depth, and rule handling constant when comparing drivers. Record table size and search enhancements because these can materially affect results. If a run is interrupted, distinguish a completed depth's verified result from bounds or provisional choices at an unfinished depth.

Check your understanding

If the current lower bound is 6 and the upper bound is 9, has the minimax value been determined?

Answer: No. Several values remain possible. If a subsequent valid test lowers the upper bound to 6, the matching bounds establish the value 6 for the specified search problem.

Related terms

Minimax
Alpha-beta pruning
Transposition table
zero-window search
fail-soft search
lower bound
upper bound
iterative deepening
principal variation
move ordering

Learn next

Change child B's leaves in the worked tree to 3 and 9, making its value 3 and the root value 4. Trace threshold tests beginning from guess 5, keeping bound direction explicit. Then compare how a more accurate first guess changes the number of tests without changing the correct final value.

Sources

Sources: Aske Plaat, original author description of MTD(f), driver pseudocode, AlphaBetaWithMemory, and implementation considerations: https://people.csail.mit.edu/plaat/mtdf.html . The two-ply tree, bound trace, and fictional engine case are original teaching illustrations. Historical benchmark statements from the source are not presented as current universal performance guarantees.

Previous: MS within (MS error ) Next: Mu-law