Qhapaq Lab

Futility Pruning

Futility Pruning は、現在局面の静的評価に安全マージンを足しても alpha を超えそうにない手を、 探索しても無駄とみなして省く前方枝刈りである。 Late Move ReductionsやNull Move Pruningと並ぶ、 選択的探索の代表技術のひとつである。

概要

発想は単純で、

  • 現在局面の静的評価 eval
  • その手で期待できる改善量の上限 margin

を使い、

eval + margin <= alpha

なら、その手を読んでも alpha を超えないだろうと見なして枝を省く。

この判断は主に frontier node 付近の浅いノードで使われるが、 近年は深さに応じてマージンを広げる形で非葉ノードにも拡張されている。

どの手を除外するか

通常は tactical な安全性のため、

  • 王手の手
  • 王手されている局面の手
  • 明らかな captures

は futility pruning の対象から外す。

また、mate 値に近い局面では使わないことが多い。

実装例

if (!inCheck(pos) && depth == 1) {
    int margin = 150;
    int futilityValue = staticEval(pos) + margin;

    if (futilityValue <= alpha && isQuiet(move) && !givesCheck(move)) {
        continue;
    }
}

実戦的には、

  • 深さごとにマージンを変える
  • Static Exchange Evaluationで悪い captures も除く
  • move count based pruning と組み合わせる

といった拡張が入る。

将棋AIでの位置づけ

将棋は分岐数が大きく、特に quiet move を全部丁寧に読むとノード数が膨らみやすい。 そのため futility pruning は、終端近くの quiet move を大きく減らす手段として有効である。

ただし将棋では、

  • 成りによる急激な価値変化
  • 王手や受けの一手
  • 打つ手による急所の受け

があるため、除外条件はチェス以上に慎重である必要がある。

歴史的拡張

Chessprogramming Wiki では、

  • Extended Futility Pruning
  • Deep Futility Pruning

のような拡張も紹介されている。 また、Late Move Pruningとの関係も深い。

注意点

  • 王手筋や受けの急所を見落とす危険がある
  • 静的評価が不安定な局面では使いにくい
  • 終局や stalemate / 千日手相当の扱いを誤るとバグにつながる

関連項目

参考にしたホームページ