Source of Delta Pruning delta-pruning

  # Delta Pruning

Delta Pruning は、
[静止探索](/shogi/shogiwiki/search/quiescence-search/)で
「最大限うまくいっても `alpha` を超えない」と判断した候補手を省く枝刈りである。
主に captures や昇格などを読む quiescence search の高速化に使われる。

## 概要

基本の考え方は、

- 現在の stand-pat 値
- その手で得られる最大利益の上限 `delta`

を使って、

`standPat + delta < alpha`

なら、その手を読んでも `alpha` に届かないだろうと見なすことである。

この `delta` には通常、

- 取れる最大駒価値
- 成りで増える価値

などが入る。

## 実装例

```cpp
for (Move move : generateTacticalMoves(pos)) {
    int delta = capturedPieceValue(move);

    if (canPromote(move)) {
        delta += promotionGain(move);
    }

    if (!inCheck(pos) && standPat + delta + 200 < alpha) {
        continue;
    }

    Position next = doMove(pos, move);
    int score = -quiescence(next, -beta, -alpha);

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

安全マージンは評価スケールやゲームに応じて調整される。

## なぜ有効か

[静止探索](/shogi/shogiwiki/search/quiescence-search/) は、
地平線効果を減らす代わりにノード数が膨らみやすい。

そこで delta pruning を使うと、
見込みの薄い tactical move を早めに切り捨てられる。

特に、

- 価値の低い取り
- `alpha` から大きく離れた局面での無駄な tactical move

を減らす効果がある。

## 将棋AIでの位置づけ

将棋では、

- 駒打ち
- 成り
- 連続王手

があるため、delta の上限見積もりはチェスより難しい。

そのため実装では、

- 王手中は使わない
- 受けの必要な局面では弱める
- 終盤や駒数の少ない局面では無効化する

といった保守的な条件が入りやすい。

## 注意点

- 終盤で材料差だけでは測れない局面を刈りすぎる危険がある
- 王手や詰めろが絡む局面では安易に使わない方がよい
- [Static Exchange Evaluation](/shogi/shogiwiki/search/static-exchange-evaluation/) と役割が近いが別物である

## 関連項目

- [静止探索](/shogi/shogiwiki/search/quiescence-search/)
- [Horizon Effect](/shogi/shogiwiki/search/horizon-effect/)
- [Static Exchange Evaluation](/shogi/shogiwiki/search/static-exchange-evaluation/)
- [Futility Pruning](/shogi/shogiwiki/search/futility-pruning/)

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

- [Chessprogramming Wiki: Delta Pruning](https://www.chessprogramming.org/Delta_Pruning)
- [Chessprogramming Wiki: Quiescence Search](https://www.chessprogramming.org/Quiescence_Search)
- [www.gnu.org: Gnuchess.Pdf](https://www.gnu.org/software/chess/manual/gnuchess.pdf)
- [sites.google.com: History 2](https://sites.google.com/site/chronosce/history-2)
Delta Pruning delta-pruning delta-pruning
