NegaScout は、 negamax を基礎に、 最初の手は通常窓で、残りの手はまず Null Window Search で試す探索アルゴリズムである。 現在では Principal Variation Search と非常に近いものとして扱われる。
考え方は単純で、
という流れである。
手の並べ替え が良ければ、 最初の手が本当に最善である可能性が高い。 その結果、後続手の多くは cheap な null-window だけで済む。
int negascout(Position pos, int depth, int alpha, int beta) {
if (depth <= 0) {
return quiescence(pos, alpha, beta);
}
int b = beta;
bool firstMove = true;
for (Move move : generateMoves(pos)) {
Position next = doMove(pos, move);
int score = -negascout(next, depth - 1, -b, -alpha);
if (!firstMove && score > alpha && score < beta) {
score = -negascout(next, depth - 1, -beta, -alpha);
}
if (score > alpha) {
alpha = score;
}
if (alpha >= beta) {
return alpha;
}
b = alpha + 1;
firstMove = false;
}
return alpha;
}実務上は、この再探索条件や窓の置き方が 探索不安定性と深く関わる。
歴史的には NegaScout と Principal Variation Search は別名義で紹介されることが多いが、 現代エンジンの実装ではかなり近い。
厳密な差を論じるより、
という共通の発想を押さえる方が実装上は重要である。
将棋AIでも、 アルファベータ法 をそのまま使うより、 PVS / NegaScout 系で探索量を減らすのが一般的である。
ただし、
が十分に機能して初めて性能が出やすい。