MTD(f) (Memory-enhanced Test Driver, first guess f) is this site's
second use of a null-window search — Principal
Variation Search's own scout question, "is this better than what I've already got, yes or no,"
decorating one full-window alpha-beta search. Here the null-window probe isn't a decoration at all —
it's the entire search strategy. No full-window search ever runs. Instead, MTD(f) starts
from a guess at the position's value, probes with the narrowest window that still means anything —
one point wide, straddling the guess — and reads which direction the probe fails in to learn which
way to move the guess next: fail low, and the true value is now known to be at most the guess; fail
high, and it's known to be at least the guess. Repeat, narrowing a floor and a ceiling toward each
other one probe at a time, until they meet. Wherever they meet is the exact minimax value, found
without any single probe ever seeing the whole picture at once.
Same fixed board as Minimax, Transposition Tables, and Principal Variation Search, O to move. Pick a first guess — 0 (the standard default), 7 (the exact true value, for comparison), or one of two guesses far off in either direction — and a mode: the correct algorithm, which tags every stored value as exact, a lower bound, or an upper bound, or a deliberately broken version that stores every value as if it were exact. Press Step or Run. Each probe is announced before it starts; a dotted border marks a node resolved instantly from a bound already sitting in memory, without any search beneath it.
A null-window search proves less than a full-window one, but what it proves is still useful. Search with a window one point wide and one of exactly two things happens: the true value turns out to be inside the window (an exact answer, just narrowly framed), or the search cuts off the instant it can prove the true value lies outside the window in one particular direction — a bound, not an exact number, exactly the fact Transposition Tables' own Pitfalls section runs into when a bound gets cached and later misread as exact. Principal Variation Search treats that bound as disposable — a scout that fails high just triggers a full re-search, and the bound itself is thrown away. MTD(f) does the opposite: it keeps the bound, tagged so a later probe knows exactly what kind of value it's looking at — exact (the search landed inside its own window), a lower bound (the search failed high — the true value is at least this), or an upper bound (the search failed low — the true value is at most this). That tagging is precisely the bookkeeping Transposition Tables' own Pitfalls section names as the fix its page doesn't build, pairing itself with plain minimax specifically to avoid needing it.
The driver loop is what turns a string of these tagged bounds into an exact answer. Start with a
floor of -Infinity and a ceiling of +Infinity; each probe's window
straddles the current guess, one point wide. A probe that fails low hands back a new, tighter
ceiling; one that fails high hands back a new, tighter floor. The next guess is always pinned to
whichever bound just moved, so every probe genuinely narrows the gap — floor and ceiling can never
pass each other, only converge, and because every score in this game is an integer a fixed distance
apart, that convergence finishes in a bounded number of probes, not an unbounded search. Checked
directly on this page's own board: a first guess of 0 takes 3 probes
to converge on the true value, 7; a first guess of 7 — already
correct — takes only 2 (one probe to confirm nothing beats it, one to confirm
nothing exceeds it); guesses of 10 and -10, on opposite sides of the true
value, take 2 and 4 respectively. All four land on the identical
answer, 7 — MTD(f)'s correctness never depends on how good the first guess is, only
its cost does.
What makes that cost worth paying is that the memory table isn't cleared between probes. A
plain transposition table already saves work
within a single search, catching one branch's re-derivation of a position another branch already
solved. MTD(f)'s table saves work across probes too — an entirely fresh, independently
issued search each time — because a bound proven by probe 2 can immediately resolve a node probe 3
would otherwise have to re-expand from scratch. Checked directly: searching this page's own board
from a first guess of 0 visits 40 freshly evaluated nodes across all
three probes combined, plus 9 more resolved instantly from memory — nodes that a
naive "run three separate searches" approach, with no shared table, would have had to fully
re-expand a second and third time.
function negamaxMem(board, depth, color, alpha, beta, table) {
const key = board.map(c => c || '.').join('');
const entry = table.get(key);
const origAlpha = alpha, origBeta = beta;
if (entry) {
if (entry.lower >= beta) return entry.lower; // already proven at least this good
if (entry.upper <= alpha) return entry.upper; // already proven at most this good
alpha = Math.max(alpha, entry.lower);
beta = Math.min(beta, entry.upper);
}
const w = winner(board);
if (w) return color * score(w, depth);
if (isFull(board)) return 0; // draw
const mark = color === 1 ? 'X' : 'O';
let best = -Infinity;
let a = alpha;
for (const cell of emptyCells(board)) {
board[cell] = mark;
const value = -negamaxMem(board, depth + 1, -color, -beta, -a, table);
board[cell] = null; // undo
best = Math.max(best, value);
a = Math.max(a, best);
if (a >= beta) break;
}
// tag what kind of value this is before storing it — the step a plain cache skips
const stored = entry ? { lower: entry.lower, upper: entry.upper } : { lower: -Infinity, upper: Infinity };
if (best <= origAlpha) stored.upper = best; // failed low: true value is at most this
else if (best >= origBeta) stored.lower = best; // failed high: true value is at least this
else { stored.lower = best; stored.upper = best; } // inside the window: this is exact
table.set(key, stored);
return best;
}
function mtdf(board, firstGuess, color, table) {
let g = firstGuess;
let lowerbound = -Infinity;
let upperbound = Infinity;
while (lowerbound < upperbound) {
const beta = (g === lowerbound) ? g + 1 : g; // widen by one point when pinned to the floor
g = negamaxMem(board, 0, color, beta - 1, beta, table);
if (g < beta) upperbound = g; else lowerbound = g;
}
return g;
}
// root call for O to move, standard first guess of 0:
// mtdf(board, 0, -1, new Map())Storing every returned value as if it were exact — skipping the lower-bound/upper-bound
tag entirely — doesn't slow MTD(f) down, it silently returns the wrong answer. This is the
exact gap Transposition Tables' own Pitfalls
section names, made concrete: without the tag, a later probe's lookup can't tell "the true value is
at least this" apart from "the true value is exactly this," and treats both as license to cut a
branch short. Checked directly with the standard first guess of 0 — the literature's
own default, not a cherry-picked bad case — the broken version returns 0 for this
page's own board after just 2 probes and 12 freshly evaluated
nodes, a plausible-looking result (a draw) that arrives quickly and quietly. The correct, tagged
version needs 3 probes and 40 nodes to reach the true answer,
7 — O can force a win in this position, not fight to a draw. The bug doesn't
always announce itself as a change in behavior, either: run the broken version from the empty board
with a first guess of 10 and it returns 5; the true value, confirmed by
every other Game Trees entry on this site that searches the same empty board, is 0. A
different starting guess on the same broken code (0, on the empty board) happens to
land on the correct answer by coincidence — the same "looks fine on one input, wrong on another"
shape Principal Variation Search's own
Pitfalls section found when it skipped its re-search step.
MTD(f) is not reliably cheaper than a single plain full-window search — checked directly,
a bad first guess on a small tree can cost more total work, not less. Plain alpha-beta
finds this page's own board's answer in one pass, 40 nodes. MTD(f) with the best
possible first guess (7, the true value) does slightly better: 30
fresh nodes plus 7 memory hits, 37 total. MTD(f) with a poor
first guess (-10) does worse: 45 fresh nodes plus 11
hits, 56 total — 40% more work than the single plain search it's competing
against, and the extra work isn't even a story of "further from the truth costs more" in any simple
sense: a first guess of 10, three units further from the true value than
-10's seventeen... no — further in absolute terms from 7 than
0 is, costs less than the standard default guess of 0 does
(40 total against 49). Guess quality matters, but not through
straightforward distance from the truth — it's which side of a fail-low/fail-high boundary each
probe happens to land on, and that depends on the tree's actual shape, not just a number line. The
technique only reliably pays off once the tree is large enough that memory reuse across probes
swamps the overhead of needing more than one probe at all: from the empty board, every first guess
tested here — 0, 10, and -10 — costs at most
6,099 total lookups, against plain alpha-beta's 20,866, regardless
of how good or bad the guess was.
Time: each probe is a null-window alpha-beta search, O(b^d) worst
case per probe, the identical bound Minimax's own alpha-beta
pruning carries. The number of probes is bounded by the game's own score range, since every score
here is an integer and each probe moves the relevant bound by at least one point toward the other —
checked directly, this page's own board converges in 2 to 4
probes across the four first guesses tried above, never stalling or looping. Total work is the sum
across every probe, but the shared memory table keeps that sum well under "probes × one full
search": 49 total lookups (40 fresh, 9 reused)
for the standard first guess of 0 on this page's own board, and — the case where the
payoff actually shows up — as few as 4,377 total lookups from a completely empty
board, against 20,866 for one plain full-window alpha-beta search covering the
identical tree. Space: O(distinct positions reached), the same order
Transposition Tables pays, though every entry
here carries two bounds instead of one raw value.
This is the site's ninth Game Trees entry, and the page where two earlier entries' own loose threads finally tie together. Transposition Tables' own Pitfalls section names the fix its page doesn't build — tagging every cached value exact, lower-bound, or upper-bound instead of trusting it blindly — and stops there, pairing itself with plain minimax specifically to avoid needing it. Principal Variation Search's own null-window scouts are, in its words, "a search strategy built specifically to return a bound instead of an exact value whenever a full search isn't needed" — the exact kind of value Transposition Tables' page says a naive cache can't tell apart from an exact one. MTD(f) is where both threads get picked back up at once: it needs exactly the bound-tagged memory Transposition Tables' page stops short of building, and it gets those bounds by doing nothing but null-window searches, Principal Variation Search's own tool used everywhere instead of just once per node. Neither earlier page was wrong to stop where it did — plain minimax's own full-window search never needed a bound in the first place, every return value already exact — but MTD(f) is the entry that actually spends the extra bookkeeping both of them priced out. See Choosing a Game Tree Search Algorithm for how all ten compare side by side, including when the extra probes this page's own Pitfalls section measures are worth paying for and when they aren't.