Null Window Search は、探索窓をほぼ幅 0 にして、
「この手が基準値より良いか悪いか」だけを高速に判定する探索である。
alpha == beta - 1 のような非常に狭い窓で探索するため、
アルファベータ法の枝刈り効果を最大化しやすい。
通常の alpha-beta 探索は、alpha から beta の区間の中で正確な値を求めようとする。
これに対して Null Window Search は、
alpha を超えるかだけを判定する。
したがって返る情報は概ね
の二値に近い。
この性質は、
のような探索法の基礎になる。
探索窓が狭いほど、ある手が境界を超えた時点で cut しやすくなる。 そのため、
という使い方ができる。
現代的な探索器では、 手の並べ替えが効いていることを前提に、 後続手の大半を null window で調べることが多い。
int nullWindowSearch(Position pos, int depth, int alpha) {
int beta = alpha + 1;
return search(pos, depth, alpha, beta);
}
int pvs(Position pos, int depth, int alpha, int beta) {
bool firstMove = true;
for (Move move : generateMoves(pos)) {
Position next = doMove(pos, move);
int score;
if (firstMove) {
score = -pvs(next, depth - 1, -beta, -alpha);
firstMove = false;
} else {
score = -pvs(next, depth - 1, -alpha - 1, -alpha);
if (score > alpha && score < beta) {
score = -pvs(next, depth - 1, -beta, -alpha);
}
}
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score;
}
}
return alpha;
}将棋AIでは、 反復深化で得られた前回反復の最善手や 置換表の hash move を先に読むことで、 後続手を null window で処理しやすくしている。
また、
とも相性が良い。