探索の基本：目的地までの道を探せ！

AIはどうやって問題を解く？

AIにパズルを解かせるには、まず問題をコンピュータがわかる形に整理します。

どんなゲームも「いまの状況」と「できる操作」に分けられます。15パズルなら盤面と、空きマスの隣を動かす操作です。

15パズルで考える

空きマスの隣をタップしてみましょう。1手ごとに盤面がどう変わるかを見てみてください。

状態と行動の定義

15パズルで1手動かすたびに変わる盤面の1枚1枚を状態と呼びます。完成できる盤面だけで約10兆通りもあります。

ある状態を別の状態へ変える「7を左へ」のような操作が行動です。

迷路を解くAIにおいて「現在地が(X:2, Y:3)のマスにいる」ことは、次のうちどれにあたりますか？

問題：迷路を解くAIが「いま(X:2, Y:3)のマスにいる」と記録しました。これは次のどれにあたりますか？

1. いまの状態（正解）
2. 次に取る行動
3. 迷路のゴール

解説：「いまどうなっているか」を写した1枚が状態です。「右へ1マス進む」のように、その状態を変える操作が行動にあたります。

スタートとゴールを決める

迷路のスタート地点のような、最初の状態が初期状態です。

「この状態で右へ進むと隣のマスへ」と次の状態を返すルールが遷移モデル、ゴールに着いたか確かめるのがゴールテストです。

問題の要素を揃える

この4つに遷移モデルを足すと、AIは探索を始められます。迷路でもパズルでも、同じ形で書けます。

次に調べる場所をメモする

AIは、見つけたけれどまだ調べていない候補をメモに並べます。このメモをフロンティアと呼びます。

メモから1つ取り出し、ゴールでなければ行ける状態をメモに足します。メモが空なら道はありません。

深さ優先探索の動き

「自動で進む」を押し、最後に足した候補から調べる順番を見てみましょう。

後入れ先出しのスタック

最後に足したメモを取り出す入れ物がスタックです。積んだ本を上から取るイメージです。

これをフロンティアに使うと、奥へ深掘りする深さ優先探索になります。

幅優先探索の動き

「自動で進む」を押し、一番古い候補から順に調べていく広がり方を見てみましょう。

先入れ先出しのキュー

最初に足したメモから取り出す入れ物をキューと呼びます。レジの行列と同じです。

フロンティアをキューにすると、1歩先を全部見てから2歩先へ進む幅優先探索になります。

データ構造と探索の対応

○か✕か：フロンティアにスタックを使うと、幅優先探索になる。

答え：✕。スタックは最後に足した候補から取り出すので、1本の枝を掘り下げる深さ優先探索になります。幅優先探索になるのは、古い候補から取り出すキューを使ったときです。

同じ場所をぐるぐる回らない

AとBを行き来できる迷路では、AからB、BからAとメモが増え続け、探索が止まりません。

そこで、一度調べた状態を探索済みセットに記録し、2度目はメモに足さないようにします。

探索モデルの基本セット

• 問題を状態・行動・初期状態・遷移モデル・ゴールテストで書き直す
• まだ調べていない候補をフロンティアに並べる
• フロンティアがスタックなら深さ優先、キューなら幅優先になる
• 調べ終えた状態を探索済みセットに記録して、堂々めぐりを防ぐ

AIが迷路探索で元の場所に戻って永久ループになるのを防ぐために絶対に必要なものは？

問題：迷路を探索するAIが、AとBの2マスを永遠に行き来して止まりません。このAIに足りないものはどれ？

1. 調べ終えた状態の記録（正解）
2. まだ調べていない候補のメモ
3. ゴールに着いたかの判定

解説：候補のメモもゴールの判定もあるのに止まらないのは、調べた状態を覚えていないからです。探索済みセットがあれば、同じマスを2度メモに足しません。お疲れ様でした。ただ、幅優先探索はゴールが東にあっても西を同じだけ調べます。次は、ゴールまでの距離を見積もって、最短を保ったまま調べる数を減らすA*探索を見ます。