Source of Futility Pruning futility-pruning

  # Futility Pruning

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

## 概要

発想は単純で、

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

を使い、

`eval + margin <= alpha`

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

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

## どの手を除外するか

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

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

は futility pruning の対象から外す。

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

## 実装例

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

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

実戦的には、

- 深さごとにマージンを変える
- [Static Exchange Evaluation](/shogi/shogiwiki/search/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](/shogi/shogiwiki/search/late-move-pruning/)との関係も深い。

## 注意点

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

## 関連項目

- [Static Exchange Evaluation](/shogi/shogiwiki/search/static-exchange-evaluation/)
- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)
- [Razoring](/shogi/shogiwiki/search/razoring/)

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

- [Chessprogramming Wiki: Futility Pruning](https://www.chessprogramming.org/Futility_Pruning)
- [www.semanticscholar.org: Efficiency OF Three Forward Pruning Techniques IN HOKI Muramatsu](https://www.semanticscholar.org/paper/Efficiency-of-three-Forward-Pruning-Techniques-in-Hoki-Muramatsu/)
- [GitHub: official-stockfish/Stockfish](https://github.com/official-stockfish/Stockfish/issues/6519)
Futility Pruning futility-pruning futility-pruning
