探索問題とは？
多くのAIの問題は状態空間探索として定式化できます。起こりうる状況が状態、状態間を移る行動がオペレータであり、初期状態から目標状態に至るオペレータの列を見つけることが課題です。経路探索、パズル、ロボットの経路計画、チェスのようなゲームはすべてこれに当てはまります。機械が問題を「知的に」解くという発想は、AIの定義をめぐるチューリングテストの議論にさかのぼります。
情報なし探索
- 幅優先探索（BFS）：初期状態に近い状態から順に展開する。すべてのステップのコストが等しければ最短経路を見つけるが、メモリを多く使う。
- 深さ優先探索（DFS）：一つの枝を最後までたどってから後戻りする。メモリは少なくて済むが、最短経路は保証されず、無限の空間では迷い込むことがある。
- 均一コスト探索／ダイクストラ法：これまでのコストg(n)が最小の状態を展開する。ダイクストラ（1959年）は、コストが非負であればこれで最短経路が見つかることを示した。
A*アルゴリズム
A*は1968年にスタンフォード研究所のピーター・ハート、ニルス・ニルソン、バートラム・ラファエルによって発表され、ロボットShakeyの経路計画から生まれました。A*は次の評価関数の値が小さい順に状態を展開します。
f(n) = g(n) + h(n)
- g(n)：初期状態からnまでの実際のコスト。
- h(n)：nから目標までの残りコストのヒューリスティックな推定値。地図上の直線距離やグリッド上のマンハッタン距離など。
- 許容性：h(n)が真の残りコストを決して過大評価しなければ、A*は最適経路を見つけることが保証される。
- 一貫性：隣接状態間でhの減少がステップコストを超えなければ、どの状態も再展開する必要がなく、効率が上がる。
- h(n)=0のときA*はダイクストラ法に帰着し、ヒューリスティックが正確なほど展開される状態は少なくなる。
ゲーム探索：ミニマックス
二人ゲームでは相手も勝とうとしています。ミニマックスはゲーム木の葉（または一定の深さの局面）を評価し、自分の手番（MAX）では最大値を、相手の手番（MIN）では最小値を上に伝えて最善手を選びます。その理論的基礎は1928年のフォン・ノイマンのミニマックス定理であり、クロード・シャノンの1950年の論文は、評価関数と組み合わせてコンピュータにチェスを指させることを提案しました。
アルファベータ枝刈り
ミニマックスは木全体を調べるため、深さとともにコストが爆発的に増えます。アルファベータ枝刈りは、これまでに見つかった最善値（α：MAXが確保できる最小値、β：MINが確保できる最大値）を追跡し、結果に影響しえない枝を省きます。ミニマックスと同じ答えをはるかに少ない計算で返し、KnuthとMoore（1975年）は、手の順序が完全であれば調べるノード数がおよそ平方根まで減ることを示しました。
限界とその後の発展
- 囲碁のような非常に大きなゲームでは組合せ爆発がミニマックスを制約し、ニューラルネットワークによる評価と組み合わせたモンテカルロ木探索が生まれた。
- A*は探索の最前線全体をメモリに保持するため、大きな問題ではIDA*のようなメモリ節約型の変種が使われる。
- 良いヒューリスティックや評価関数の設計自体が難しく、領域知識を必要とする。
参考文献
- von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100, 295–320.
- Shannon, C. E. (1950). Programming a computer for playing chess. Philosophical Magazine, 41(314), 256–275.
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
- Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4), 293–326.