Qhapaq Lab

Reduction

Reduction は、特定の手やノードに対して探索深さを減らす手法の総称である。 Late Move Reductionsが代表例であり、 現代的な alpha-beta 探索では重要な高速化技術になっている。

概要

発想は extension の逆で、

  • この手は重要そうだから深く読む

ではなく、

  • この手は重要でない可能性が高いから浅く読む

という判断を使う。

典型的には、

  • 後ろに並んだ quiet move
  • hash move でも capture でも check でもない手

に対して reduction をかける。

実装例

int reduction = 0;

if (depth >= 3 && moveCount > 3 && isQuiet(move)) {
    reduction = 1;
}

int score = -search(next, depth - 1 - reduction, -alpha - 1, -alpha);

浅く読んだ結果が良ければ、通常深さで再探索するのが一般的である。

代表例

また、Improvingやノードタイプによって reduction 量を変えることも多い。

Extension との関係

  • Extension 重要な手を深く読む
  • Reduction 重要でなさそうな手を浅く読む

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

現代的な探索では、全体としては reduction の方が大きな役割を持つことが多い。

将棋AIでの位置づけ

将棋は分岐数が大きいので、reduction の恩恵が大きい。 ただし、

  • 王手
  • 受け
  • 成り
  • 打つ手

のような tactical な手を浅く読みすぎると危険である。

注意点

  • reduction しすぎると tactical miss が増える
  • 手の並べ替えが悪いと有望手まで浅く読んでしまう
  • extension や pruning との全体バランスが重要

関連項目

参考にしたホームページ