探索 (G検定)

2026年8月12日2026年9月2日

G検定

1. 定義と概要

探索とは、問題として起こりうる状態全体、すなわち状態空間（問題として起こりうるすべての状態の集まり）を場合分けし、ある状態から別の状態への移り方をたどりながら、初期状態から目標状態に至る道筋をしらみつぶしに調べることで解を見つける処理です。

迷路の分岐を一つずつ試して出口を探す、ルービックキューブの手順を試して完成形を探す、チェスや将棋の指し手を読んで最善手を探すといった問題が代表例に挙げられます。状態と状態の移り方は探索木（状態をノード、状態の移り方を枝として木の形に表したもの）に表され、この木をどの順序でたどるかによって手法が分かれます。

従来、迷路やパズル、ゲームのような問題の攻略は人間の勘や試行錯誤に頼る面が大きい分野でした。1956年のダートマス会議（人工知能という学問分野を確立したとされる会議）を機に、問題が取りうる状態を漏れなく場合分けしてコンピュータでたどれば解にたどり着けるという発想が広まりました。探索は既知の情報から結論を導く推論（すでに持っている知識や規則から新しい結論を論理的に導き出す処理）とともに、第1次人工知能ブーム（1950年代後半〜1960年代）の中核技術となりました。

迷路やパズル、オセロやチェスのようにルールとゴールが明確なトイ・プロブレム（ルールとゴールがあらかじめ明確に決まった簡易な問題）では成果を上げました。一方、状態の場合分けが膨大になる現実の複雑な問題には対応しきれず、組合せ爆発（選択肢が増えるほど調べる対象が爆発的に増えてしまう現象）という壁に直面しました。

2. 試験対策ポイント

まず押さえておきたいのは、探索木と各アルゴリズムの関係です。探索木はたどる対象となる構造です。この木をどの順序でたどるかによって、浅い階層から順に調べる幅優先探索（同じ深さの状態をすべて調べてから次の深さに進むたどり方）、深さ優先探索（一つの道を行き止まりまで進んでから別の道を試すたどり方）といった手法に分かれます。

考えられる組み合わせを一つずつすべて試すブルートフォース（力まかせ探索）も、これらと並ぶ代表的な手法です。探索木は構造、各手法はそれをたどる手順という関係にあります。

対戦相手が存在するゲームでは、自分の手だけでなく相手の応手も含めて木を広げるゲーム木（自分の手だけでなく対戦相手の応手も含めて広げた探索木）探索が発展しました。代表的な手法として、自分の得を最大に相手の得を最小にすると仮定して手を選ぶMini-Max法（自分は得を最大に、相手の得を最小にすると仮定して手を選ぶ考え方）があります。

そのうち明らかに選ばれない手の計算を省略して高速化するαβ法（Mini-Max法のうち明らかに選ばれない手の計算を省略して高速化する工夫）も用いられます。手をランダムに終局まで進める試行（プレイアウト）を繰り返し、その勝率で手を評価するモンテカルロ法（プレイアウトを繰り返し、その結果の勝率で手を評価する方法）もあわせて押さえておきたい手法です。

盤面の大きさや駒の種類が異なるオセロ・チェス・将棋・囲碁を並べると、取りうる状態の組み合わせ数の差がはっきりします。

ゲーム	取りうる状態の組み合わせ数
オセロ	10の60乗通り程度
チェス	10の120乗通り程度
将棋	10の220乗通り程度
囲碁	10の360乗通り程度

下にいくほど桁が大きくなり、すべての状態を調べ尽くすやり方では手に負えなくなっていきます。この桁の並びは、探索という手法がどこで行き詰まるかを示す目安にもなります。

探索の効率化には、ヒューリスティックな知識（正解を保証しないが、経験則にもとづいて有望な選択肢を絞り込む目安）が使われます。コスト（ある状態から別の状態に移るのに必要な手数や負担の大きさ）とあわせて整理しておきたい要素です。

探索の限界となるのが組合せ爆発です。状態や選択肢の数が増えるほどノード数は指数関数的に増加し、迷路やパズルのようなトイ・プロブレムを超える複雑な問題には探索だけでは対応できません。この限界は第1次人工知能ブーム終焉の一因となりました。

3. 関連概念との比較・相違点

探索と最も混同しやすい概念は推論です。最大の違いは、探索が状態空間をしらみつぶしに調べて解を見つける処理であるのに対し、推論は既知の知識や規則から新しい結論を論理的に導き出す処理である点にあります。

第1次人工知能ブームでは探索と推論が両輪として組み合わされ、両者の役割を入れ替えた説明（探索を知識からの結論の導出、推論を場合分けの網羅とするような記述）は、取り違えやすい典型です。

第3次人工知能ブームで中心となった機械学習との違いも、あわせて理解しておきたいテーマです。探索・推論は人間があらかじめ定義したルールや状態の移り方に沿ってコンピュータが処理をたどるのに対し、機械学習はデータそのものからパターンや規則を自動的に学習する点が異なります。

3つの概念は、処理の内容と中心になった時代を並べると位置づけを見分けやすくなります。

概念	処理の内容	中心となった時代
探索	状態空間をしらみつぶしに調べて解を見つける	第1次人工知能ブーム
推論	既知の知識や規則から新しい結論を論理的に導き出す	第1次人工知能ブーム
機械学習	データそのものからパターンや規則を自動的に学習する	第3次人工知能ブーム

人間が手順を書いておくのか、データから規則を取り出すのかという線引きが、前の2つと機械学習を分ける軸にあたります。この違いは、探索・推論が支えた第1次人工知能ブームと、機械学習・ディープラーニングが支えた第3次人工知能ブームという時代背景の違いとしても整理されます。

4. ビジネス・実務での活用シナリオ

ナビゲーション・物流の分野では、カーナビの経路探索や配送ルートの最適化に探索の考え方が応用されています。地図上の分岐点や道路を状態空間として扱い、移動にかかる負担であるコストを考慮しながら、目的地までの道筋を探索する仕組みです。コストが小さい道筋を優先して選ぶことで、移動時間や燃料の無駄を抑える効果につながります。

ゲームAIの分野では、将棋・囲碁のAIが指し手の候補をゲーム木として展開し、Mini-Max法やモンテカルロ法で評価の高い手を探索しています。チェスのディープ・ブルーや囲碁のAlphaGo（アルファ碁）が挙げた成果は、この探索の延長線上にあるものです。人間のトップ棋士を上回る指し手を導き出した点に、探索という手法の到達点が表れています。

生産計画・スケジューリングの分野では、工程の組み方や資源配分の選択肢を状態として展開し、条件を満たす計画をヒューリスティックな知識で絞り込みながら体系的に探し出す取り組みが行われています。人手による試行錯誤に頼るよりも短い時間で、実行可能な計画へと絞り込める点に意義があります。