MTD(f) は MTD(n, f) (Memory-enhanced Test Driver with node n and value f) の略で、アルファ・ベータ法やNegaScoutよりも効率の良いミニマックス法アルゴリズムの一種である。MTD(f) は、ミニマックス値を見積もった値 f から、 Null Window Search を何度も繰り返す事で実際のミニマックス値に向けて近づいていく探索法である。ミニマックス値が見つかると、再び Null Window Search を行っても同じ値が返るようになるので、これを探索の終了条件とする。以下に MTD(f) の擬似コードを示す。Zero Window Search とも。アルファ・ベータ法やそれを改良した探索法におけるα（下限値）とβ（上限値）の幅を Window (探索窓)といい、この幅を Null(Zero) にして行う探索を Null Window Search と言う。（但し、通常の実装では Null Window の幅は１とする。）十分広い探索窓を設定して探索をすれば返る値はミニマックス値であるが、狭い探索窓を設定して探索をすると、ミニマックス値がその範囲内に無い場合、探索窓の上限値以上の評価値が返る事がある。この状態を fail-high といい、これはミニマックス値がその評価値以上である事を示している。また、同様に探索窓の下限値以下の評価値が返る事もある。この状態を fail-low といい、こちらはミニマックス値がその評価値以下である事を示している。つまりNull Window Searchを行えばミニマックス値の存在範囲を知ることができる。このような探索は MTD(f) だけでなく NegaScout法でも使われている。MTD(f)はその性質上、何度も同じノードを展開するので、効率改善のために置換表付きアルファ・ベータ法が用いられる。置換表に前回の計算結果（探索窓の上限値や下限値）を保持しておく事で再探索時の計算を削減する事ができる。以下に置換表付きアルファ・ベータ法の擬似コードを示す。MTD(f)は、チェスなどのゲームに於いてNegaScout法などの探索アルゴリズムよりも探索ノード数が少なくて済む事が示されている。しかし置換表に強く依存する事や、探索の非安定性などの問題が存在するので、現在のチェスプログラムではNegaScout法も今だに広く使われている。

出典:wikipedia