探索 search

  # 探索

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

## 前提知識

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

## キホンのキ

### minimax法

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

### negamax

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

### アルファベータ法

- 詳細: [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- minimax 法と同じ答えを保ったまま、不要な枝を途中で打ち切る探索手法。
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)が良いほど枝刈りが増え、より深く読める。

### NegaScout

- 詳細: [NegaScout](/shogi/shogiwiki/search/negascout/)
- 最初の手だけ通常窓で読み、残りを narrow window で試す探索アルゴリズム。
- 現代的には [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/) とかなり近い。

### ノードタイプ

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

### Principal Variation Search

- 詳細: [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)
- 最初の手だけ通常窓で読み、残りをまず狭い窓で試すことで探索量を減らす手法。
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)や[反復深化](/shogi/shogiwiki/search/iterative-deepening/)が良いほど効果が高い。

### Null Window Search

- 詳細: [Null Window Search](/shogi/shogiwiki/search/null-window-search/)
- 探索窓を極端に狭くして、値が境界を超えるかどうかだけを高速に判定する探索。
- [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)や [MTD(f)](/shogi/shogiwiki/search/mtd-f/) の土台になる。

### MTD(f)

- 詳細: [MTD(f)](/shogi/shogiwiki/search/mtd-f/)
- 初期予想値を基準に narrow window 探索を繰り返し、正確値へ収束させる探索法。
- [置換表](/shogi/shogiwiki/search/transposition-table/) と [反復深化](/shogi/shogiwiki/search/iterative-deepening/) が特に重要になる。

### Extension

- 詳細: [Extension](/shogi/shogiwiki/search/extensions/)
- 特定の重要手だけ探索深さを増やす手法。
- 地平線効果の緩和や強制変化の追跡に使われる。

### Check Extensions

- 詳細: [Check Extensions](/shogi/shogiwiki/search/check-extensions/)
- 王手がかかった局面や王手をかける手に対して探索深さを延長する手法。
- 強制変化を追いやすいが、一律に使うと探索爆発しやすい。

### Singular Extensions

- 詳細: [Singular Extensions](/shogi/shogiwiki/search/singular-extensions/)
- 実質的に一手しかないと見なせる強い手を、通常より深く読む extension 手法。
- [置換表](/shogi/shogiwiki/search/transposition-table/) の best move を起点に判定されることが多い。

### 原始モンテカルロ探索

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

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

- 詳細: [モンテカルロ木探索(MCTS)](/shogi/shogiwiki/search/monte-carlo-tree-search/)
- 原始モンテカルロ探索と木探索を組み合わせ、訪問回数や評価値を更新しながら有望手へ探索資源を集中させる手法。
- 囲碁で広く使われ、将棋では [AlphaZero](/shogi/shogiwiki/alphazero/) 型や [dlshogi](/shogi/shogiwiki/softs/dlshogi/) の文脈で重要になる。

### PUCT

- 詳細: [PUCT](/shogi/shogiwiki/search/puct/)
- MCTS の子ノード選択で、探索済みの価値、訪問回数、方策ネットワークの事前確率を組み合わせる規則。
- [AlphaZero](/shogi/shogiwiki/alphazero/) 型の MCTS で、方策・価値ネットワークを探索に接続する重要な考え方である。

### Dirichlet noise

- 詳細: [Dirichlet noise](/shogi/shogiwiki/search/dirichlet-noise/)
- [AlphaZero](/shogi/shogiwiki/alphazero/) 型の自己対局で、ルートノードの方策 prior に加える探索用ノイズ。
- [PUCT](/shogi/shogiwiki/search/puct/) の探索入口を少し揺らし、自己対局データの多様性を確保するために使われる。

### 温度パラメータ

- 詳細: [温度パラメータ](/shogi/shogiwiki/search/temperature/)
- MCTS 後の訪問回数分布を鋭くしたり平らにしたりするパラメータ。
- [AlphaZero](/shogi/shogiwiki/alphazero/) 型の自己対局では、序盤の多様化と終盤・評価時の決定性を調整するために使われる。

### ONNX / TensorRT

- 詳細: [ONNX / TensorRT](/shogi/shogiwiki/search/onnx-tensorrt/)
- PyTorch などで学習した方策・価値ネットワークを ONNX へ変換し、ONNX Runtime や TensorRT で高速推論するための技術。
- [dlshogi](/shogi/shogiwiki/softs/dlshogi/) では `convert_model_to_onnx.py`、`usi_onnxruntime`、`usi/nn_tensorrt.cpp` がこの流れに関わる。

### バッチ推論

- 詳細: [バッチ推論](/shogi/shogiwiki/search/batch-inference/)
- 複数の葉局面をまとめて方策・価値ネットワークへ入力し、GPU 推論を効率化する技術。
- [dlshogi](/shogi/shogiwiki/softs/dlshogi/) では `DNN_Batch_Size` や `policy_value_batch_maxsize` として、USI 探索・自己対局生成の両方に関わる。

### Virtual loss

- 詳細: [Virtual loss](/shogi/shogiwiki/search/virtual-loss/)
- 並列 MCTS で、評価中の経路を一時的に選ばれにくくして探索の重複を減らす技術。
- [dlshogi](/shogi/shogiwiki/softs/dlshogi/) のように、バッチ推論しながら複数の探索を進める実装で重要になる。

### FPU reduction

- 詳細: [FPU reduction](/shogi/shogiwiki/search/fpu-reduction/)
- PUCT で未訪問手の初期価値を少し低く見積もり、低 prior の手へ探索が広がりすぎることを抑える技術。
- [dlshogi](/shogi/shogiwiki/softs/dlshogi/) では `C_fpu_reduction` や `C_fpu_reduction_root` として調整対象になる。

### NN キャッシュ

- 詳細: [NN キャッシュ](/shogi/shogiwiki/search/nn-cache/)
- 方策・価値ネットワークの推論結果を局面キーで保存し、同じ局面の再推論を避けるキャッシュ。
- [dlshogi](/shogi/shogiwiki/softs/dlshogi/) の自己対局生成では、policy prior と value を LRU キャッシュへ保存してバッチ推論の負荷を減らす。

### Conspiracy Number Search

- 詳細: [Conspiracy Number Search](/shogi/shogiwiki/search/conspiracy-number-search/)
- ルートの値をひっくり返すのに必要な葉の変化数を手掛かりに進める best-first search。
- 実戦将棋AIの主流ではないが、[Proof-Number Search](/shogi/shogiwiki/search/proof-number-search/) 系とのつながりを理解する助けになる。

### Proof-Number Search

- 詳細: [Proof-Number Search](/shogi/shogiwiki/search/proof-number-search/)
- AND/OR 木で証明・反証に必要なコストを使って最も有望なノードを伸ばす探索。
- 詰将棋や詰み探索の文脈で特に重要である。

## キホンのホ

### 置換表

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

### ハッシュテーブル

- 詳細: [ハッシュテーブル](/shogi/shogiwiki/search/hash-table/)
- キーから高速に値を引くデータ構造。
- 置換表、評価ハッシュ、材料ハッシュなどの基盤になる。

### トランスポジション

- 詳細: [トランスポジション](/shogi/shogiwiki/search/transposition/)
- 異なる手順から同じ局面へ到達する現象。
- [置換表](/shogi/shogiwiki/search/transposition-table/)が有効に働く根拠のひとつ。

### 反復深化

- 詳細: [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- 1 手、2 手、3 手と徐々に深くしていく探索の枠組み。
- [時間管理](/shogi/shogiwiki/search/time-management/)と相性が良く、前回反復の結果を使って手の順序も改善できる。

### 手の並べ替え

- 詳細: [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- 候補手を調べる順番を工夫して、[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)の枝刈り効率を上げる技術。
- hash move、killer heuristic、history heuristic などが代表的。

### Principal Variation

- 詳細: [Principal Variation](/shogi/shogiwiki/search/principal-variation/)
- その時点で探索器が最善とみなしている読み筋。
- 解析表示だけでなく、次の反復での手の並べ替えにも使われる。

### Triangular PV-Table

- 詳細: [Triangular PV-Table](/shogi/shogiwiki/search/triangular-pv-table/)
- Principal Variation を ply ごとに保持する古典的なデータ構造。
- [置換表](/shogi/shogiwiki/search/transposition-table/)からの PV 復元との違いを理解する入口になる。

### Killer Heuristic

- 詳細: [Killer Heuristic](/shogi/shogiwiki/search/killer-heuristic/)
- 同じ深さの兄弟ノードで cut を起こした quiet move を優先する順序付け手法。
- captures 以外の手の並べ替えで重要になる。

### History Heuristic

- 詳細: [History Heuristic](/shogi/shogiwiki/search/history-heuristic/)
- 過去に枝刈りへ貢献した quiet move に履歴スコアを与えて優先する手法。
- 現代的な quiet move ordering の中心になることが多い。

### Countermove Heuristic

- 詳細: [Countermove Heuristic](/shogi/shogiwiki/search/countermove-heuristic/)
- 直前手に対する自然な返し手を記録して優先する順序付け手法。
- [History Heuristic](/shogi/shogiwiki/search/history-heuristic/)と併用されやすい。

### Aspiration Windows

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

### 静止探索

- 詳細: [静止探索](/shogi/shogiwiki/search/quiescence-search/)
- 葉局面で駒の取り合いなどの激しい変化が収まるまで限定的に先を読む手法。
- [地平線効果](/shogi/shogiwiki/search/horizon-effect/)を抑えるために重要。

### Horizon Effect

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

### Static Exchange Evaluation

- 詳細: [Static Exchange Evaluation](/shogi/shogiwiki/search/static-exchange-evaluation/)
- ある升での取り合いが最終的に得か損かを静的に見積もる手法。
- [静止探索](/shogi/shogiwiki/search/quiescence-search/)や[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)の補助に使われる。

### Delta Pruning

- 詳細: [Delta Pruning](/shogi/shogiwiki/search/delta-pruning/)
- [静止探索](/shogi/shogiwiki/search/quiescence-search/)で、最大限うまくいっても `alpha` を超えない tactical move を省く枝刈り。
- quiescence search のノード増加を抑えるのに使われる。

### Futility Pruning

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

### Reverse Futility Pruning

- 詳細: [Reverse Futility Pruning](/shogi/shogiwiki/search/reverse-futility-pruning/)
- 静的評価がすでに十分高いとき、fail-high を見込んで早めに打ち切る手法。
- `Static Null Move Pruning` と呼ばれることもある。

### Improving

- 詳細: [Improving](/shogi/shogiwiki/search/improving/)
- 静的評価が 2 手前や 4 手前より改善しているかを見る指標。
- reduction や pruning の強さ調整に使われる。

### Razoring

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

### Null Move Pruning

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

### Zugzwang

- 詳細: [Zugzwang](/shogi/shogiwiki/search/zugzwang/)
- パスできるなら有利または互角を保てるのに、手番であるために評価が悪化する局面。
- [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/) が危険になる代表例である。

### Reduction

- 詳細: [Reduction](/shogi/shogiwiki/search/reductions/)
- 重要でないと見た手を浅く読む手法の総称。
- 現代探索では extension より大きな役割を持つことが多い。

### Late Move Reductions

- 詳細: [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- 後ろに並んだ手を浅く読み、必要なときだけ再探索することで探索量を減らす手法。
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)と密接に関係する。

### Late Move Pruning

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

### Move Count Based Pruning

- 詳細: [Move Count Based Pruning](/shogi/shogiwiki/search/move-count-based-pruning/)
- 一定数の手を読んだ後、後続の late quiet moves を省く枝刈り。
- [Late Move Pruning](/shogi/shogiwiki/search/late-move-pruning/)を move count の観点から整理した記事である。

### 時間管理

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

## 探索運用

### PolicyBook

- 詳細: [PolicyBook](/shogi/shogiwiki/search/policy-book/)
- 定跡データベースの遷移確率や評価値を、方策・価値ネットワークの policy/value と混ぜて MCTS の prior として使う考え方。
- [dlshogi](/shogi/shogiwiki/softs/dlshogi/) では `Use_Book_Policy` や `BOOK_POLICY` の文脈で、定跡と policy prior を接続している。

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

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

## 探索補助

### ゾブリストハッシュ

- 詳細: [ゾブリストハッシュ](/shogi/shogiwiki/search/zobrist-hashing/)
- 局面を固定長整数へ写像するハッシュ方式。
- [置換表](/shogi/shogiwiki/search/transposition-table/)や反復局面検出の基盤になる。

### 千日手と反復局面

- 詳細: [千日手と反復局面](/shogi/shogiwiki/search/repetitions/)
- 同じ局面が繰り返される現象と、その探索上の扱い。
- 将棋では千日手や連続王手の千日手の扱いが重要になる。

### 探索不安定性

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

## 並列探索

### 並列探索

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

### Young Brothers Wait Concept

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

### Jamboree

- 詳細: [Jamboree](/shogi/shogiwiki/search/jamboree/)
- 最初の子を逐次に読み、残りを narrow window で並列に試す並列探索法。
- [Young Brothers Wait Concept](/shogi/shogiwiki/search/young-brothers-wait-concept/) や [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/) とあわせて理解しやすい。

### Lazy SMP

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

## キホンのン

### PV-MCTS

- まだ