Qhapaq Lab

探索

コンピュータ将棋における探索とは、人間が行う「先読み」をコンピュータに行わせるための技術群である。 現在の将棋AIでは、アルファベータ法を中心とする深さ優先探索が主流であり、 反復深化、手の並べ替え、置換表、静止探索などの補助技術と組み合わせて使われる。

前提知識

  • 二人零和有限確定完全情報ゲームの概要
  • コンピュータ将棋の基本的な用語
  • ゲーム木 現在局面から指し手を枝として展開した構造。探索の土台になる。
  • 将棋のルール

キホンのキ

minimax法

  • 詳細: ミニマックス法
  • 二人零和有限確定完全情報ゲームにおいて、自分は評価値を最大化し、相手はそれを最小化すると仮定して局面の価値を決める探索の基本原理。
  • コンピュータ将棋では、ゲーム木の葉で終局結果や評価関数による値を与え、その値を根へ逆向きに伝搬させることで最善手候補を求める。

negamax

  • 詳細: negamax
  • minimax 法を二人零和ゲーム向けに簡潔化した実装形式。
  • 現代的な将棋AIでは、アルファベータ探索もこの形で実装されることが多い。

アルファベータ法

  • 詳細: アルファベータ法
  • minimax 法と同じ答えを保ったまま、不要な枝を途中で打ち切る探索手法。
  • 手の並べ替えが良いほど枝刈りが増え、より深く読める。

NegaScout

  • 詳細: NegaScout
  • 最初の手だけ通常窓で読み、残りを narrow window で試す探索アルゴリズム。
  • 現代的には Principal Variation Search とかなり近い。

ノードタイプ

  • 詳細: ノードタイプ
  • PV-node、Cut-node、All-node などの分類。
  • どのノードで正確値が必要か、どこで選択性を強めるかを考える助けになる。

MTD(f)

  • 詳細: MTD(f)
  • 初期予想値を基準に narrow window 探索を繰り返し、正確値へ収束させる探索法。
  • 置換表 と 反復深化 が特に重要になる。

Extension

  • 詳細: Extension
  • 特定の重要手だけ探索深さを増やす手法。
  • 地平線効果の緩和や強制変化の追跡に使われる。

Check Extensions

  • 詳細: Check Extensions
  • 王手がかかった局面や王手をかける手に対して探索深さを延長する手法。
  • 強制変化を追いやすいが、一律に使うと探索爆発しやすい。

Singular Extensions

  • 詳細: Singular Extensions
  • 実質的に一手しかないと見なせる強い手を、通常より深く読む extension 手法。
  • 置換表 の best move を起点に判定されることが多い。

原始モンテカルロ探索

  • 評価関数が要らない探索手法。
  • ランダムシミュレーションを何回も行い、その結果で局面の価値を推定する。
  • プレイアウトやロールアウトとも呼ばれる。

モンテカルロ木探索(MCTS)

  • 原始モンテカルロ探索と木探索を組み合わせた手法。
  • 囲碁で広く使われ、将棋でも研究・応用例がある。
  • 詳細: Conspiracy Number Search
  • ルートの値をひっくり返すのに必要な葉の変化数を手掛かりに進める best-first search。
  • 実戦将棋AIの主流ではないが、Proof-Number Search 系とのつながりを理解する助けになる。
  • 詳細: Proof-Number Search
  • AND/OR 木で証明・反証に必要なコストを使って最も有望なノードを伸ばす探索。
  • 詰将棋や詰み探索の文脈で特に重要である。

キホンのホ

置換表

  • 詳細: 置換表
  • 同一局面に対する探索結果を記録し、再利用するための表。
  • 枝刈りそのものだけでなく、hash move として手の並べ替えにも大きく効く。

ハッシュテーブル

  • 詳細: ハッシュテーブル
  • キーから高速に値を引くデータ構造。
  • 置換表、評価ハッシュ、材料ハッシュなどの基盤になる。

トランスポジション

反復深化

  • 詳細: 反復深化
  • 1 手、2 手、3 手と徐々に深くしていく探索の枠組み。
  • 時間管理と相性が良く、前回反復の結果を使って手の順序も改善できる。

手の並べ替え

Principal Variation

  • 詳細: Principal Variation
  • その時点で探索器が最善とみなしている読み筋。
  • 解析表示だけでなく、次の反復での手の並べ替えにも使われる。

Triangular PV-Table

  • 詳細: Triangular PV-Table
  • Principal Variation を ply ごとに保持する古典的なデータ構造。
  • 置換表からの PV 復元との違いを理解する入口になる。

Killer Heuristic

  • 詳細: Killer Heuristic
  • 同じ深さの兄弟ノードで cut を起こした quiet move を優先する順序付け手法。
  • captures 以外の手の並べ替えで重要になる。

History Heuristic

  • 詳細: History Heuristic
  • 過去に枝刈りへ貢献した quiet move に履歴スコアを与えて優先する手法。
  • 現代的な quiet move ordering の中心になることが多い。

Countermove Heuristic

Aspiration Windows

  • 詳細: Aspiration Windows
  • 前回反復の評価値の近くにルート探索窓を絞ることで高速化する手法。
  • fail-high / fail-low 時は境界を広げて再探索する。

静止探索

  • 詳細: 静止探索
  • 葉局面で駒の取り合いなどの激しい変化が収まるまで限定的に先を読む手法。
  • 地平線効果を抑えるために重要。

Horizon Effect

  • 詳細: Horizon Effect
  • 不都合な出来事を探索の見える範囲の外へ押しやることで、局面を実際より良く見積もってしまう現象。
  • 静止探索 や Extension を導入する大きな理由のひとつである。

Static Exchange Evaluation

Delta Pruning

  • 詳細: Delta Pruning
  • 静止探索で、最大限うまくいっても alpha を超えない tactical move を省く枝刈り。
  • quiescence search のノード増加を抑えるのに使われる。

Futility Pruning

  • 詳細: Futility Pruning
  • eval + margin でも alpha を超えそうにない手を省く前方枝刈り。
  • 終端近くの quiet move を減らすのに有効だが、急所を見落とさない条件設計が重要。

Reverse Futility Pruning

  • 詳細: Reverse Futility Pruning
  • 静的評価がすでに十分高いとき、fail-high を見込んで早めに打ち切る手法。
  • Static Null Move Pruning と呼ばれることもある。

Improving

  • 詳細: Improving
  • 静的評価が 2 手前や 4 手前より改善しているかを見る指標。
  • reduction や pruning の強さ調整に使われる。

Razoring

  • 詳細: Razoring
  • 残り深さが浅く静的評価がかなり悪いとき、通常探索を省いて静止探索へ落とす手法。
  • ノード単位の強い選択性として使われる。

Null Move Pruning

  • 詳細: Null Move Pruning
  • 「何もしない手」を仮想的に試し、それでも十分良いなら枝を刈る前方枝刈り。
  • 現代的な alpha-beta 系探索で非常に重要な高速化技術のひとつ。

Zugzwang

  • 詳細: Zugzwang
  • パスできるなら有利または互角を保てるのに、手番であるために評価が悪化する局面。
  • Null Move Pruning が危険になる代表例である。

Reduction

  • 詳細: Reduction
  • 重要でないと見た手を浅く読む手法の総称。
  • 現代探索では extension より大きな役割を持つことが多い。

Late Move Reductions

  • 詳細: Late Move Reductions
  • 後ろに並んだ手を浅く読み、必要なときだけ再探索することで探索量を減らす手法。
  • 手の並べ替えと密接に関係する。

Late Move Pruning

  • 詳細: Late Move Pruning
  • 手の順序のかなり後ろにある quiet move を丸ごと省く前方枝刈り。
  • 浅いノードの探索量を大きく減らせるが、刈りすぎると tactical miss を起こしやすい。

Move Count Based Pruning

時間管理

  • 詳細: 時間管理
  • 持ち時間、秒読み、探索の進み具合に応じて各手の思考時間を配分する仕組み。
  • 実戦用の将棋AIでは、探索そのものと同じくらい重要である。

探索運用

探索パラメータの確率的最適化

  • 詳細: 探索パラメータの確率的最適化
  • グリッドサーチ、Hyperopt、Optuna、SPSA などで探索定数を自動調整する考え方。
  • 現代的な探索器の運用では実装と同じくらい重要である。

探索補助

ゾブリストハッシュ

千日手と反復局面

  • 詳細: 千日手と反復局面
  • 同じ局面が繰り返される現象と、その探索上の扱い。
  • 将棋では千日手や連続王手の千日手の扱いが重要になる。

探索不安定性

  • 詳細: 探索不安定性
  • 深さや探索窓のわずかな違いで評価値や Principal Variation が大きく揺れる現象。
  • 再探索や時間管理、表示の安定性にも影響する。

並列探索

並列探索

  • 詳細: 並列探索
  • 複数スレッドや複数コアを使って探索を高速化する技術群。
  • 共有ハッシュやスレッド同期の設計が重要になる。

Young Brothers Wait Concept

  • 詳細: Young Brothers Wait Concept
  • 最初の有望手を先に読み、後続の兄弟ノードの並列化を待つ考え方。
  • 並列 alpha-beta を理解する基礎概念として重要である。

Jamboree

Lazy SMP

  • 詳細: Lazy SMP
  • 複数スレッドが近い探索をほぼ独立に進め、共有ハッシュを通じてゆるく協調する方式。
  • 実装しやすさに対して実用上の効果が高く、現代エンジンでよく使われる。

キホンのン

PV-MCTS

  • まだ