Qhapaq Lab

Null Move Pruning

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

概要

直感的には、

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

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

そこで現在局面で

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

という形で用いる。

実装例

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 ではない
  • 深さが十分ある
  • Zugzwangが起こりやすい終盤では慎重にする

将棋AIでの注意点

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

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

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

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

他の技術との関係

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

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

注意点

  • Zugzwangに弱い
  • 王手中では使えない
  • 詰み値や終盤での扱いが難しい
  • reduction 値 R の調整で強さがかなり変わる

関連項目

参考にしたホームページ