Aspiration Windows は、反復深化の前回反復で得た評価値の近くに探索窓を絞って、 アルファベータ法やPVSを高速化する手法である。
通常のルート探索では、最初は非常に広い探索窓を使う。 しかし前回反復の評価値がすでに分かっているなら、
と期待できる。
そこで、たとえば
+80[-20, +180]のように狭めて探索する。
窓が狭いほど枝刈りが増え、探索は速くなる。
問題は、本当の評価値が窓の外に出る場合である。
beta 以上なら fail-highalpha 以下なら fail-lowとなり、探索をやり直す必要がある。
そのため実装では、失敗した側の境界だけを徐々に広げる
gradual widening がよく使われる。
int aspirationSearch(Position pos, int depth, int guess) {
int delta = 32;
int alpha = guess - delta;
int beta = guess + delta;
while (true) {
int score = pvs(pos, depth, alpha, beta);
if (score <= alpha) {
alpha -= delta;
delta *= 2;
continue;
}
if (score >= beta) {
beta += delta;
delta *= 2;
continue;
}
return score;
}
}このように、片側だけを広げて再探索することが多い。
Aspiration Windows は、前回反復の値を初期予測として使うため、 反復深化とほぼセットで使われる。
また、PVSとも相性が良い。
将棋AIでは、
がまとめてルート探索の骨格になることが多い。
ただし局面が不安定なときや、詰み筋が見え始めたときは評価値が大きく跳ねるため、 再探索のコストが増えることがある。