Qhapaq Lab

Move Count Based Pruning

Move Count Based Pruning（MCBP）は、 あるノードで一定数の手を読んだ後、それ以降の late quiet moves を省く枝刈りである。 実務上は Late Move Pruning とほぼ重なることが多く、 LMP を move count しきい値で定式化した説明として扱われることもある。

概要

基本的な考え方は単純で、

  • 先頭の数手は読む
  • moveCount が深さに応じたしきい値を超えたら
  • 後続の quiet move を打ち切る

というものである。

この判定は主に、

  • 非 PV-node
  • 深さが浅い
  • 王手中ではない
  • tactical な手ではない

といった条件の下で使われる。

なぜ有効か

反復深化と 手の並べ替えが十分に機能していれば、 有望な手は上位に並ぶ可能性が高い。

そのため、後ろの quiet move をまとめて省くことで、 探索量を大きく減らせる。

特に shallow node では、 1 手 1 手を浅く読むより、怪しい手を最初から読まない方が効率がよいことがある。

実装例

int pruneAfter = 3 + depth * depth;

for (Move move : generateMoves(pos)) {
    ++moveCount;

    if (!pvNode
        && depth <= 5
        && moveCount > pruneAfter
        && isQuiet(move)
        && !inCheck(pos)
        && !givesCheck(move)) {
        continue;
    }

    Position next = doMove(pos, move);
    int score = -search(next, depth - 1, -beta, -alpha);

    if (score >= beta) {
        return score;
    }
    if (score > alpha) {
        alpha = score;
    }
}

しきい値は固定値ではなく、

で調整されることが多い。

将棋AIでの位置づけ

将棋AIでも、浅い探索で分岐を抑える補助として有効である。 ただし将棋では、

  • 打ちによる詰めろ
  • 成りで急変する手
  • 受けの急所

が後ろから出てくることがあるため、静的条件だけで強く刈りすぎると危険である。

実際には、Late Move Reductions、 Futility Pruning、 Static Exchange Evaluationなどと組み合わせて使われる。

注意点

  • move count のしきい値が小さすぎると tactical miss が増える
  • 手の並べ替えが前提なので ordering が弱いと危険
  • PV-nodeでは通常使わない

関連項目

参考にしたホームページ