Qhapaq Lab

Reverse Futility Pruning

Reverse Futility Pruning（RFP）は、静的評価がすでに十分高く、 少し安全マージンを引いても beta を超えそうなら、そのノードを fail-high とみなして早めに打ち切る手法である。 Static Null Move Pruning と呼ばれることもある。

概要

Futility Pruningが 「どうせ alpha を超えないから探索しない」 という下側の枝刈りであるのに対し、 RFP は 「どうせ beta を超えるから探索しない」 という上側の枝刈りである。

典型的には、

  • 静的評価 eval
  • 深さ依存の安全マージン margin

を使って、

eval - margin >= beta

なら fail-high とみなしてその場で返す。

実装例

if (!inCheck(pos) && depth <= 4) {
    int margin = 100 + depth * 80;
    if (staticEval(pos) - margin >= beta) {
        return staticEval(pos) - margin;
    }
}

実際には、

  • Improvingなら margin を少し下げる
  • PV-node では使わない
  • mate 領域では使わない

といった条件が入ることが多い。

Futility Pruning との関係

  • Futility Pruning alpha を超えないと見て手を省く
  • Reverse Futility Pruning beta を超えると見てノードごと打ち切る

という対称的な関係にある。

ただし実際には、RFP は null move observation に近い発想を使うため、 Null Move Pruningの軽量版として見ることもできる。

将棋AIでの位置づけ

将棋では、

  • 大きく優勢な局面
  • 相手に有効な受けが少ない局面

で RFP が効きやすい。 一方で、

  • 王手筋
  • 受けの一手
  • 詰み近辺

では過信が危険である。

注意点

  • 静的評価への依存が強い
  • 王手や詰み周辺では使いにくい
  • 探索不安定性が強い局面では fail-high を誤る危険がある

関連項目

参考にしたホームページ