Алгоритм MTD(f): поиск с нулевым окном в игровых деревьях

Zero window Alpha Beta game tree search algorithm
MTD(f) is an alpha beta game tree search algorithm modified to use ‘zero window’ initial search bounds, and memory (usually a transposition table) to reuse intermediate search results. MTD(f) is a shortened form of MTD(n,f) which stands for Memory enhanced Test Driver with node ‘n’ and value ‘f’. The efficacy of this paradigm depends on a good initial guess, and the supposition that the final minimax value lies in a narrow window around the guess (which becomes an upper/lower bound for the search from root). The memory structure is used to save an initial guess determined elsewhere. MTD(f) was introduced in 1994 and largely supplanted NegaScout (PVS), the previously dominant search paradigm for chess, checkers, othello and other game automatons.

MTD(f) was first described in a University of Alberta Technical Report authored by Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin, which would later receive the ICCA Novag Best Computer Chess Publication award for 1994/1995. The algorithm MTD(f) was created out of a research effort to understand the SSS* algorithm, a best first search algorithm invented by George Stockman in 1979. SSS* was found to be equivalent to a series of Alpha beta pruning|alpha beta calls, provided that alpha beta used storage, such as a transposition table. The name MTD(f) stands for Memory enhanced Test Driver, referencing Judea Pearl's Test algorithm, which performs Zero Window Searches. MTD(f) is described in depth in Aske Plaat's 1996 PhD thesis.

A "zero window" search is an alpha beta search whose upper and lower bounds are identical, or differ by one unit, so that the return value is guaranteed to fall outside the bound(s) (or in an exceptionally lucky case, be equal to the bound). MTD(f) derives its efficiency by only performing zero window alpha beta searches, with a previously determined "good" bound (i. e. beta). In MTD(f), AlphaBeta fails high or low, returning a lower bound or an upper bound on the minimax value, respectively. Zero window calls cause more cutoffs, but return less information only a bound on the minimax value. To find the minimax value, MTD(f) calls AlphaBeta a number of times, converging towards it and eventually finding the exact value. A transposition table stores and retrieves the previously searched portions of the tree in memory to reduce the overhead of re exploring parts of the search tree.

MTD(f) calls the zero window searches from the root of the tree. MTD(f) depends on a transposition table to perform efficiently. Zero window searches hit a cut off sooner than wide window searches. They are therefore more efficient, but, in some sense, also less forgiving, than wide window searches. However, wider search windows are more forgiving for engines with large odd/even swings and fine grained evaluation functions. For this reason some chess engines have not switched to MTD(f). In tests with tournament quality programs such as Chinook (checkers), Phoenix (chess), and Keyano (Othello), the MTD(f) algorithm outperformed all other search algorithms. Recent algorithms like Best Node Search are suggested to outperform MTD(f).