Reverse Futility Pruning reverse-futility-pruning reverse-futility-pruning

  # Reverse Futility Pruning

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

## 概要

[Futility Pruning](/shogi/shogiwiki/search/futility-pruning/)が
「どうせ `alpha` を超えないから探索しない」
という下側の枝刈りであるのに対し、
RFP は
「どうせ `beta` を超えるから探索しない」
という上側の枝刈りである。

典型的には、

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

を使って、

`eval - margin >= beta`

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

## 実装例

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

実際には、

- [Improving](/shogi/shogiwiki/search/improving/)なら margin を少し下げる
- PV-node では使わない
- mate 領域では使わない

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

## Futility Pruning との関係

- [Futility Pruning](/shogi/shogiwiki/search/futility-pruning/)
  `alpha` を超えないと見て手を省く
- Reverse Futility Pruning
  `beta` を超えると見てノードごと打ち切る

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

ただし実際には、RFP は null move observation に近い発想を使うため、
[Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)の軽量版として見ることもできる。

## 将棋AIでの位置づけ

将棋では、

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

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

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

では過信が危険である。

## 注意点

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

## 関連項目

- [Futility Pruning](/shogi/shogiwiki/search/futility-pruning/)
- [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)
- [Improving](/shogi/shogiwiki/search/improving/)
- [探索不安定性](/shogi/shogiwiki/search/search-instability/)

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

- [Chessprogramming Wiki: Reverse Futility Pruning](https://www.chessprogramming.org/Reverse_Futility_Pruning)
- [Chessprogramming Wiki: Futility Pruning](https://www.chessprogramming.org/Futility_Pruning)
- [Chessprogramming Wiki: Improving](https://www.chessprogramming.org/Improving)