MTD(f)

MTD(f) is a game tree search algorithm that modifies alpha-beta search so that it only makes zero-window searches, in which the upper and lower bounds are equal or differ by one unit, and reuses earlier results through a memory structure, usually a transposition table. Its name is short for Memory-enhanced Test Driver with node n and value f. It depends on a good first guess of the final minimax value, because each zero-window call returns only a bound, and the algorithm calls alpha-beta repeatedly to close the gap between the upper and lower bounds. It was introduced in 1994 in a University of Alberta technical report by Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin, and largely replaced NegaScout in programs for chess, checkers and Othello. Tests with the Chinook, Phoenix and Keyano programs found it outperforming other searches, though newer methods such as Best Node Search are suggested to do better.