Null Window Search
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2009/11/07 08:47 UTC 版)
「MTD-f」の記事における「Null Window Search」の解説
Zero Window Search とも。 アルファ・ベータ法やそれを改良した探索法におけるα(下限値)とβ(上限値)の幅を Window (探索窓)といい、 この幅を Null(Zero) にして行う探索を Null Window Search と言う。(但し、通常の実装では Null Window の幅は1とする。) 十分広い探索窓を設定して探索をすれば返る値はミニマックス値であるが、 狭い探索窓を設定して探索をすると、ミニマックス値がその範囲内に無い場合、探索窓の上限値以上の評価値が返る事がある。 この状態を fail-high といい、これはミニマックス値がその評価値以上である事を示している。 また、同様に探索窓の下限値以下の評価値が返る事もある。 この状態を fail-low といい、こちらはミニマックス値がその評価値以下である事を示している。 つまりNull Window Searchを行えばミニマックス値の存在範囲を知ることができる。 このような探索は MTD(f) だけでなく NegaScout法でも使われている。
※この「Null Window Search」の解説は、「MTD-f」の解説の一部です。
「Null Window Search」を含む「MTD-f」の記事については、「MTD-f」の概要を参照ください。
- Null Window Searchのページへのリンク