人工知能の黎明期（1950〜1960年代）、研究の中心にあったのは「探索」と「推論」です。
コンピュータに「ルール」と「探索手順」を与えることで、人間のように問題解決を行わせようとする試みでした。
この分野は 第1次AIブーム を支えた重要な技術であり、G検定でも頻出です。
探索アルゴリズムの基礎
探索とは「状態空間（可能な選択肢の集合）」の中から解を見つける手法です。
幅優先探索（Breadth-First Search）
- スタートからゴールまでの最短経路を保証する探索。
- 例：迷路探索。
- メリット：最短手順を見つけられる。
- デメリット：探索領域が広がりやすく、メモリ消費が大きい。
深さ優先探索（Depth-First Search）
- 一つの道をとことん深く掘り進め、行き止まりになったら戻る探索。
- メリット：実装が簡単、メモリ効率が良い。
- デメリット：必ずしも最短解を見つけられない。
ゲーム木探索
探索・推論の応用先として特に有名なのが ゲームAI です。
チェスや将棋のような2人完全情報ゲームでは「探索木」を用いて最適手を求めます。
ミニマックス法
- 自分の得点を最大化し、相手の得点を最小化する手を選ぶアルゴリズム。
- すべての可能手を計算するため、計算量が膨大。
αβ法（アルファベータ法）
- ミニマックス法の改良版。
- 「この手はすでに他より悪い」と分かったら、その枝を切り捨てる（枝刈り）。
- 無駄な探索を省略し、計算効率を大幅に向上。
- チェスや将棋プログラムで広く使われた。
確率的手法とモンテカルロ法
状態空間が膨大な場合、完全探索は不可能。
その代替として「確率的シミュレーション」による近似解法が登場しました。
モンテカルロ法
- ランダムサンプリングによって解を近似。
- 例：円周率の近似計算、確率分布の推定。
モンテカルロ木探索（MCTS）
- ゲーム木にモンテカルロ法を組み込み、勝率を統計的に推定。
- AlphaGo（2016年） で採用され、囲碁チャンピオンに勝利。
- ディープラーニングと組み合わせることで大きな成果を挙げた。
探索・推論の限界
- 組み合わせ爆発
- 状態空間のサイズが指数関数的に増加。
- チェスや囲碁では全探索が不可能。
- 実世界への応用の難しさ
- ルールや条件が明確でない現実問題に適用しにくい。
- これらの課題が「第1次AI冬の時代」の原因となった。
まとめ
- 探索・推論は 第1次AIブーム の中心テーマ。
- 幅優先探索・深さ優先探索：基本アルゴリズム。
- ミニマックス法・αβ法：ゲーム木探索。
- モンテカルロ法・MCTS：確率的探索、AlphaGoにつながる重要技術。
- 課題は 計算量爆発 と 現実問題への適用困難。
出題傾向
- 「αβ法の特徴」
- 「モンテカルロ木探索を応用した有名AI」＝AlphaGo
- 「第1次AIブームの中心テーマ」＝探索・推論
練習問題（例題）
問題：次のうち、αβ法（アルファベータ法）の説明として最も適切なものはどれか？
- ランダムにサンプリングして解を推定する探索手法
- 迷路探索に特化したアルゴリズム
- ミニマックス法で不要な探索を省く枝刈り手法
- データからルールを自動的に学習する手法
👉 正解：3
