Qhapaq Lab

探索不安定性

探索不安定性（Search Instability）は、探索深さや探索窓、手順順序などのわずかな違いで評価値や Principal Variation が大きく揺れる現象である。 Aspiration WindowsやPVSの再探索と深く関係する。

概要

探索は理想的には深くなるほど滑らかに精密化してほしいが、 実際には

  • ある深さで高評価
  • 次の深さで急落
  • さらに次で元に戻る

といった揺れが起きることがある。

原因としては、

がある。

どんなときに問題になるか

探索不安定性が強いと、

  • Aspiration Windowsの再探索が増える
  • Principal Variation が頻繁に入れ替わる
  • 時間管理が難しくなる
  • 棋譜解析で表示が落ち着かない

といった問題が起きる。

典型例

  • 静かな局面だと思っていたら、少し深く読んで tactical な筋が見つかる
  • LMRで浅く読んだ手が再探索で急に有力になる
  • RazoringやFutility Pruningの境界付近で挙動が揺れる

将棋AIでの位置づけ

将棋は分岐数が大きく、王手・受け・成り・打つ手の影響が大きいので、 探索不安定性が起こりやすい。

そのため実装では、

  • 重要ノードでは選択性を弱める
  • fail-high 後の再探索条件を工夫する
  • Principal Variationの更新規則を安定化させる

といった対策が取られる。

注意点

  • 不安定性を完全に消すことは難しい
  • 速度を上げる選択性と安定性はしばしばトレードオフになる
  • 単に評価値が揺れるだけでなく、最善手自体が変わるかも見る必要がある

関連項目

参考にしたホームページ