Qhapaq Lab

Delta Pruning

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

概要

基本の考え方は、

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

を使って、

standPat + delta < alpha

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

この delta には通常、

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

などが入る。

実装例

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;
    }
}

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

なぜ有効か

静止探索 は、 地平線効果を減らす代わりにノード数が膨らみやすい。

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

特に、

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

を減らす効果がある。

将棋AIでの位置づけ

将棋では、

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

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

そのため実装では、

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

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

注意点

  • 終盤で材料差だけでは測れない局面を刈りすぎる危険がある
  • 王手や詰めろが絡む局面では安易に使わない方がよい
  • Static Exchange Evaluation と役割が近いが別物である

関連項目

参考にしたホームページ