NegaScout negascout negascout

  # NegaScout

NegaScout は、
[negamax](/shogi/shogiwiki/search/negamax/) を基礎に、
最初の手は通常窓で、残りの手はまず [Null Window Search](/shogi/shogiwiki/search/null-window-search/) で試す探索アルゴリズムである。
現在では [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/) と非常に近いものとして扱われる。

## 概要

考え方は単純で、

- 最善と思われる手を full window で読む
- 残りの手は narrow window で試す
- その narrow window を破った手だけ再探索する

という流れである。

[手の並べ替え](/shogi/shogiwiki/search/move-ordering/) が良ければ、
最初の手が本当に最善である可能性が高い。
その結果、後続手の多くは cheap な null-window だけで済む。

## 実装例

```cpp
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;
}
```

実務上は、この再探索条件や窓の置き方が
[探索不安定性](/shogi/shogiwiki/search/search-instability/)と深く関わる。

## PVS との関係

歴史的には NegaScout と
[Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/) は別名義で紹介されることが多いが、
現代エンジンの実装ではかなり近い。

厳密な差を論じるより、

- null window による後続手のスクリーニング
- fail-high 時の再探索

という共通の発想を押さえる方が実装上は重要である。

## 将棋AIでの位置づけ

将棋AIでも、
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/) をそのまま使うより、
PVS / NegaScout 系で探索量を減らすのが一般的である。

ただし、

- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [Aspiration Windows](/shogi/shogiwiki/search/aspiration-windows/)

が十分に機能して初めて性能が出やすい。

## 注意点

- move ordering が悪いと再探索が増える
- fail-soft / fail-hard の違いや再探索窓の取り方で挙動が変わる
- [静止探索](/shogi/shogiwiki/search/quiescence-search/) や extension に依存して不安定になりやすい

## 関連項目

- [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)
- [Null Window Search](/shogi/shogiwiki/search/null-window-search/)
- [Aspiration Windows](/shogi/shogiwiki/search/aspiration-windows/)
- [探索不安定性](/shogi/shogiwiki/search/search-instability/)

## 参考にしたホームページ

- [Chessprogramming Wiki: Negascout](https://www.chessprogramming.org/NegaScout)
- [Chessprogramming Wiki: Principal Variation Search](https://www.chessprogramming.org/Principal_Variation_Search)
- [Chessprogramming Wiki: Alexander Reinefeld](https://www.chessprogramming.org/Alexander_Reinefeld)
- [www.egaroucid.nyanyan.dev: Explanation](https://www.egaroucid.nyanyan.dev/en/technology/explanation)