
G検定#05|どのように答えを探す?幅優先・深さ優先
皆さん、ご安全に! 技術屋たかちゃんです。
迷路を解くとき、皆さんはどうしますか?
道を選び、行き止まりになったら引き返す。そして、別の道を試しながらゴールを目指します。
人間にとっては当たり前の行動ですが、コンピューターに同じことをさせるには、問題を解く手順を明確にする必要がありました。
1950〜1960年代の第1次AIブームでは、こうした問題解決を実現するため、「探索」の研究が進められました。今回は、人工知能の原点ともいえる、この二つの技術を解説します。
探索とは?
探索とは、複数の選択肢を調べながら、目的の答えを探すことです。
迷路でゴールまでの道を探したり、目的地までの経路を比較したりする行為が、その例です。
推論が「知識を使って結論を導くこと」なら、探索は「選択肢を調べて解決策を見つけること」といえます。AIは、これらの技術を使って、さまざまな問題を解こうとしてきました。
探索木と二つの基本手法
相棒のAI(アイ)君が調べたところでは、探索木は、問題の状態と選択肢を枝分かれする木の形で表現する方法だそうです。
木の根元から枝が伸び、その先でさらに枝分かれしていく様子を想像してください。どの選択肢を選ぶと、どの状態に進むのかを整理できます。
代表的な探索手法が「幅優先探索」と「深さ優先探索」です。
幅優先探索は、スタート地点に近い状態から順番に調べる方法です。迷路なら、まず一歩で行ける場所をすべて確認し、次に二歩で行ける場所を調べます。
移動コストがすべて同じであれば、最短経路を見つけられるのが利点です。一方、調べた候補を記憶しておく必要があるため、メモリを多く消費します。
深さ優先探索は、一つの道をできるだけ奥まで進む方法です。行き止まりになったら、分岐点まで戻り、別の道を試します。
幅優先探索に比べてメモリ使用量を抑えやすい反面、遠回りになることがあり、最短経路が見つかるとは限りません。
幅優先探索は「近い場所から順番に」、深さ優先探索は「一つの道を奥まで」。この違いが、二つの手法を理解するポイントです。
ゲームの勝敗を読む探索
探索は、チェスや将棋、囲碁などのゲームでも活用されてきました。
代表的な手法の一つが、ミニマックス法です。自分は自分にとって有利な手を選び、相手は自分にとって不利な手を選ぶと仮定して、次の一手を決めます。
相手も最善の手を選ぶと考え、先の展開を読みながら、自分にとって最も有利な手を探すのです。
ところが、すべての手を調べていては、計算量が膨大になります。そこで使われるのが、αβ法です。
この方法では、最善手の判断に影響しないと分かった分岐の探索を打ち切ります。ミニマックス法と同じ結果を得ながら、無駄な計算を減らせるのが特徴です。
また、モンテカルロ法は、ランダムな試行を繰り返し、その結果から選択肢を評価する方法です。この考え方は、囲碁AIの発展にも貢献しました。
なぜ、AIは壁にぶつかったのか?
探索の仕組みが分かると、時間をかけて選択肢を調べれば、どんな問題でも解けそうに思えます。
しかし、選択肢が増えると、必要な計算量は急激に膨らみます。これを組合せ爆発と呼びます。
例えば、一つの局面で10通りの選択肢があり、それが10手先まで続くとします。単純計算では、候補の数は最大で100億通りになります。
実際には、探索を効率化する工夫によって候補を減らせます。それでも、複雑な問題では計算が追いつかなくなります。
初期のAIは、ルールが明確なパズルやゲームでは成果を上げました。一方、現実世界には曖昧な条件や例外が数多く存在します。こうした問題に対応することは難しく、技術的な限界がAI研究の停滞を招いた要因の一つとなりました。
AIの賢さは、探し方でも変わる
探索の歴史から分かるのは、AIの能力は計算速度だけでは決まらないということです。
どの知識を使うのか。どの選択肢を調べるのか。そして、どこで探索を打ち切るのか。問題の解き方そのものが、結果を大きく左右します。
現在の生成AIは、初期の探索型AIとは異なる仕組みを中心に発展しています。それでも、限られた計算資源を活用し、適切な答えを導き出すことは、今もAI技術に共通する重要な課題です。
AIの歴史を学ぶことは、過去の技術を覚えるだけではありません。現在のAIが何を得意とし、どのような限界を持つのか。その理由を理解する手がかりにもなるのです。
技術屋たかちゃんでした。ご安全に!!
G検定 連載
前回:
次回:
目次(マガジン):
G検定重要用語集:探索とゲーム木探索
1. 探索の基本
1. 探索(Search)
複数の選択肢や状態を調べ、目的の解決策を見つける手法。AIでは、迷路の経路探索やゲームの次の一手の決定などに使われる。探索の順序や範囲によって、計算量や解の性質が変わる。
2. 推論(Inference)
既知の知識やルール、事実を使って、新しい結論を導き出すこと。探索が複数の選択肢を調べる処理であるのに対し、推論は知識に基づいて結論を導く処理を指す。
3. 探索木(Search Tree)
問題の状態と、そこから選べる行動を木構造で表現したもの。最初の状態を根、選択によって移る状態を子ノードとして表す。迷路やゲームの手順を整理し、探索するために使われる。
4. 幅優先探索(Breadth-First Search:BFS)
スタート地点から近い状態を順番に調べる探索方法。深さが浅いノードから探索する。各移動のコストが同じ場合、最短経路を発見できる。探索済み候補を保持するため、メモリ消費量は大きくなりやすい。
5. 深さ優先探索(Depth-First Search:DFS)
一つの経路をできるだけ深く進み、行き止まりになったら戻って別の経路を調べる方法。幅優先探索よりメモリを抑えやすいが、最短経路を保証しない。無限に深い経路がある場合は注意が必要。
2. ゲーム木探索
6. ゲーム木(Game Tree)
チェスや将棋などのゲームで、プレイヤーの手と、それによって変化する局面を木構造で表したもの。各ノードが局面、枝が着手を表す。先の展開を調べ、勝敗や有利不利を判断するために使う。
7. ミニマックス法(Minimax Algorithm)
自分は自分に有利な結果を最大化し、相手は自分に不利な結果を最小化すると仮定して、最善手を選ぶ方法。相手も最善の手を選ぶ前提で先の展開を読む。二人零和ゲームの基本的な探索手法。
8. 評価関数(Evaluation Function)
ゲームの局面がどれほど有利かを数値で評価する関数。例えば将棋なら、駒の価値や王の安全性などを考慮する。探索の途中で最終的な勝敗まで読めない場合、局面の良し悪しを判断するために使う。
9. αβ法(Alpha-Beta Pruning)
ミニマックス法の探索中に、最善手の決定に影響しない枝を調べずに済ませる手法。αは最大化側の下限、βは最小化側の上限を表す。探索結果はミニマックス法と同じだが、計算量を削減できる。
10. 枝刈り(Pruning)
探索木の中で、解を求めるうえで調べる必要がないと判断した枝を探索対象から除外すること。αβ法は代表的な枝刈り手法。不要な探索を減らすことで、限られた計算資源を有効に使える。
11. モンテカルロ法(Monte Carlo Method)
乱数を使った試行を繰り返し、その結果から近似的な答えや選択肢の評価を得る手法。ゲームAIでは、ある局面からランダムに対局を進め、その勝敗の割合などを使って着手の良し悪しを評価する。
12. モンテカルロ木探索(Monte Carlo Tree Search:MCTS)
ゲーム木の探索にモンテカルロ法を組み合わせた手法。選択、展開、シミュレーション、逆伝播の処理を繰り返し、有望な手を重点的に調べる。囲碁AIの発展に大きく貢献した。単純なランダム試行だけでなく、探索結果を木に蓄積して活用する。
3. 探索の限界
13. 組合せ爆発(Combinatorial Explosion)
選択肢や処理の組み合わせが増えるにつれて、必要な計算量が急激に増大する現象。ゲームでは、手数が増えるほど探索すべき局面が膨大になる。探索範囲の制限や枝刈りなどによる効率化が必要になる。
14. 計算量(Computational Complexity)
問題を解くために必要となる計算の量を表す概念。探索では、調べる状態や分岐の数によって計算量が増える。問題の規模が大きくなったとき、どの程度計算負荷が増えるかを考えるうえで重要になる。
15. 探索空間(Search Space)
問題を解く際に、探索対象となる状態や選択肢の全体を指す。迷路なら通行可能な経路や位置、ゲームなら到達可能な局面の集合が該当する。探索空間が大きいほど、解を見つけるための計算負荷も増えやすい。