Qhapaq Lab 
  # Null Window Search

Null Window Search は、探索窓をほぼ幅 0 にして、
「この手が基準値より良いか悪いか」だけを高速に判定する探索である。
`alpha == beta - 1` のような非常に狭い窓で探索するため、
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)の枝刈り効果を最大化しやすい。

## 概要

通常の alpha-beta 探索は、`alpha` から `beta` の区間の中で正確な値を求めようとする。
これに対して Null Window Search は、

- 値が `alpha` を超えるか
- それとも超えないか

だけを判定する。

したがって返る情報は概ね

- fail-high
- fail-low

の二値に近い。

この性質は、

- [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)
- [Scout](/shogi/shogiwiki/search/principal-variation-search/)
- [MTD(f)](/shogi/shogiwiki/search/mtd-f/)

のような探索法の基礎になる。

## なぜ速いのか

探索窓が狭いほど、ある手が境界を超えた時点で cut しやすくなる。
そのため、

- 有望そうでない手を軽く試す
- fail-high した手だけ広い窓で読み直す

という使い方ができる。

現代的な探索器では、
[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)が効いていることを前提に、
後続手の大半を null window で調べることが多い。

## 実装例

```cpp
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での位置づけ

将棋AIでは、
[反復深化](/shogi/shogiwiki/search/iterative-deepening/)で得られた前回反復の最善手や
[置換表](/shogi/shogiwiki/search/transposition-table/)の hash move を先に読むことで、
後続手を null window で処理しやすくしている。

また、

- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)
- [Aspiration Windows](/shogi/shogiwiki/search/aspiration-windows/)

とも相性が良い。

## 注意点

- 正確値は分からないので、fail-high した手は再探索が必要になる
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)が悪いと再探索が増える
- 評価が揺れやすい局面では、[探索不安定性](/shogi/shogiwiki/search/search-instability/)が目立つことがある

## 関連項目

- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)
- [Aspiration Windows](/shogi/shogiwiki/search/aspiration-windows/)
- [探索不安定性](/shogi/shogiwiki/search/search-instability/)

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

- [Chessprogramming Wiki: NULL Window](https://www.chessprogramming.org/Null_Window)
- [Chessprogramming Wiki: Principal Variation Search](https://www.chessprogramming.org/Principal_Variation_Search)
- [people.csail.mit.edu: Mtdf.Html](https://people.csail.mit.edu/plaat/mtdf.html)