Qhapaq Lab 
  # Null Move Pruning

Null Move Pruning は、手番側が「何もしない手」を仮想的に試してみて、
それでも十分に良いなら、その局面は本探索でも cut できるだろうとみなして枝刈りする手法である。
現代的な alpha-beta 系探索で非常に重要な前方枝刈りのひとつである。

## 概要

直感的には、

- 実際に合法手を指すより
- 何もしないほうが普通は悪い

という `Null Move Observation` を利用する。

そこで現在局面で

1. 手番を相手に渡すだけの仮想的な null move を行う
2. 深さを少し減らして[Null Window](/shogi/shogiwiki/search/null-window-search/)で探索する
3. それでも `beta` を超えるなら、本探索でも cut できると判断する

という形で用いる。

## 実装例

```cpp
int search(Position pos, int depth, int alpha, int beta) {
    if (depth == 0 || pos.isTerminal()) {
        return evaluate(pos);
    }

    if (!inCheck(pos) && depth >= 3) {
        Position next = doNullMove(pos);
        int score = -search(next, depth - 1 - 2, -beta, -beta + 1);
        if (score >= beta) {
            return score;
        }
    }

    for (Move move : generateMoves(pos)) {
        Position next = doMove(pos, move);
        int score = -search(next, depth - 1, -beta, -alpha);
        if (score >= beta) {
            return score;
        }
        if (score > alpha) {
            alpha = score;
        }
    }

    return alpha;
}
```

上の例では、null move 後に深さを `R=2` だけ余分に減らしている。
実戦的には `R=2` や `R=3` を基準に、深さや評価値に応じて調整することが多い。

## どこで使うか

典型的には次のような条件で使う。

- 自玉に王手がかかっていない
- [PV-node](/shogi/shogiwiki/search/principal-variation/) ではない
- 深さが十分ある
- [Zugzwang](/shogi/shogiwiki/search/zugzwang/)が起こりやすい終盤では慎重にする

## 将棋AIでの注意点

将棋には「パス」は存在しないので、null move は純粋に探索上の仮想手である。
多くの局面では有効だが、

- 受けの一手しかない局面
- 終盤での手番損が致命的な局面
- 詰み周辺

では危険になることがある。

そのため、実装では verification search や局面条件による制限を加えることが多い。

## 他の技術との関係

Null Move Pruning は単体でも強力だが、

- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- [futility pruning](/shogi/shogiwiki/search/futility-pruning/)

と並ぶ選択的探索の主要技術のひとつである。

## 注意点

- [Zugzwang](/shogi/shogiwiki/search/zugzwang/)に弱い
- 王手中では使えない
- 詰み値や終盤での扱いが難しい
- reduction 値 `R` の調整で強さがかなり変わる

## 関連項目

- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [Null Window](/shogi/shogiwiki/search/null-window-search/)
- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- [futility pruning](/shogi/shogiwiki/search/futility-pruning/)
- [zugzwang](/shogi/shogiwiki/search/zugzwang/)

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

- [Chessprogramming Wiki: NULL MOVE Pruning](https://www.chessprogramming.org/Null_Move_Pruning)
- [Chessprogramming Wiki: Search](https://www.chessprogramming.org/Search)
- [Chessprogramming Wiki: LATE MOVE Reductions](https://www.chessprogramming.org/Late_Move_Reductions)