発見的探索

1. 概要
状態空間探索問題は,「人工知能の古典的問題.初期状態に対して,基本操作をどのように適用したら目的状態に至るかを求めよ」という問題.8パズルは昔から用いられている例題.他愛ない問題ながら,発見的探索に関わるいろいろな典型的な側面を含んでいる.
2. 基本的なアルゴリズム
基本的な探索アルゴリズムは横型探索と縦型探索である.横型(breadth-first)探索は「慎重型」であり,8パズルのような場合は,大量のメモリが必要である.反面,最適解(コストが最小になる解.8パズルの場合は,与えられた状態から目的状態にたどり着くまでの最少数のタイル移動系列).
深さ優先(depth-first)探索はメモリは要らないが,最初に見つけた解が最適解であるという保証はない.また,制限を設けておかないと一つの可能性ばかり無限に探してしまう.
アルゴリズム的には横型探索と縦型探索は手順はほんの一か所しか違わないのだが,上のような性質の違いが出てしまう点に注意したい.
深さ制限型(iterative deepening)探索を基調とする反復深化探索は深さ優先探索のよさを保持しつつ欠点を克服している.探索の重複は生じるものの,最適解を見つけることができる.
プログラムを用いた実験
・基本的探索アルゴリズム (breadth-first, depth-first, iterative-deepening)のプログラム例→こちら
・ 実験のシナリオとその結果→こちら
3. ヒューリスティック関数の使用
基本的な方法でいくら頑張っても,解に至るまでに調べなければならない状態数そのものが減るわけではないので,高速化には限界がある.ヒューリスティック関数を用いる方法では,例えば,与えられた状態がどれくらいゴールに近いかといった発見的知識 ― いつも正しいとは限らないが概ね成立する経験則,あるいは,ゴールまでの下限など部分的な情報の算出の仕方 ― を表現した関数(=ヒューリスティック関数)が与えられた場合に探索を高速化する方法である.
以下で紹介する方法は,操作系列o_1,…,o_nのコストc(o_1,…,o_n)がc(o_1)+…+c(o_n)で与えられ,各o_iについてc(o_i)≧0であると仮定している.8パズルの場合は,4つの基本操作{空白を上に動かす,空白を下に動かす,空白を左に動かす,空白を右に動かす}のいずれに対してもコスト=1であり,この仮定を満足している.
状態sを経由して最小コストでゴールに至る経路のコストをf(s)としよう.状態空間で求めるものは,初期状態s_0に対するコストと,それを実現する経路である.初期状態s_0が与えられたとき,それがゴールでなければ基本操作を適用してゴールを探すしかない.s_0に適用可能な基本操作をo_kをしたとき,どのo_kを適用して得られた状態o_k(s_0)がゴールへの最短経路上にあるかを常に知ることができない(むしろ,わからないことの方が多い)というのが,状態空間探索での基本的な想定である.つまり,o_kによっては,f(o_k(s_0))>f(s_0)となってしまうかもしれないが,それはs_0に基本操作を適用しようとしているときにはわからないことであり,もっと進んでからでないと,あるいは,しらみつぶしの探索を行ってからでないとわからないことである,というのが状態空間探索でふつうに遭遇する状況である.
状態空間探索が進んで,状態sまでやってきたとしよう.初期状態から状態sにたどりつくまでのコストをg(s),状態sからゴールまでの最少コストをh(s)とすると,f(s)=g(s)+h(s)である.状態sからもはやゴールにたどり着くことができなくなってしまっていたときは,f(s)=∞としておく.8パズルであれば,もし初期状態からゴールに至る経路があれば,どのような動かし方をしてもそれを元に戻せば初期状態に帰れるから,f(s_0)が有限なら,s_0から到達可能ないかなる状態sでもf(s)は有限であるが,基本操作が非可逆であれば,途中でf(s)=∞になってしまうかもしれない.一般に,初期状態に基本操作を適用して得られる状態をsとすると,f(s)≧f(s_0)である.
状態空間探索で採り上げられる典型的な問題(例えば,8パズル)では,現在の状態sがゴールである,あるいは,特殊なケースを除いて,g(s)は得られるが,h(s)は探索前にはわからない.そこで,sから先を探索してみないとその値がわからないh(s)のかわりに,s(あるいはsに至る経路)からh(s)の近似値を算出する関数h‘(s)を導入して探索プロセスを導こう,というのがヒューリスティック探索の考え方である.ヒューリスティック探索アルゴリズムはヒューリスティック関数h‘を用いて探索を行う一般的なアルゴリズムである.ヒューリスティック関数を具体的に作り出すのは個々のプログラマの責任である.ヒューリスティック関数の性能がよいと無駄なく探索が行われるが,問題が難しくなると有効なヒューリスティック関数を作り出すのは困難になる.
8パズルの場合,よく使われるヒューリスティック関数h’(s)として,目標状態の正しい位置に置かれていないタイルの個数を数えるものがある.例えば,
246
3_5
718
の場合は,目標状態
123
8_4
765
と(空白の位置は考慮に入れない)7か所異なっているので,そのh‘値は7となる.
ヒューリスティック探索の代表的方法に山登り法,最良優先探索,A*(Aスター)がある.山登り法と最良優先探索は,h‘値だけを使って候補を順序づけするアルゴリズムである.山登り法は,h‘値の小さくなる方向に縦型探索を行う.最良優先探索は全ての可能な展開を保持しておいて,そのなかでh‘値を最も小さくする方向に展開を行う.
A*は,与えられた状態sに対して,g値とh‘値の和g(s)+h‘(s)を用いて,候補を順序づけする.h‘が楽天的なヒューリスティック(常に真の値h(s)以下の値を与える)であるとき,A*アルゴリズムは最適解を最初に出力する(このことは簡単に証明できる).どんなsに対してもh(s)=0を与える関数(どの状態に対してそれが目標状態と区別できないくらい近いと診断する)は明らかに楽天的なヒューリスティックである.全てのsに対して0を出力するh(s)=0という関数を使った探索は,横型探索と同じである.
Lispによるプログラム例→(「基本的なアルゴリズム」の項に示したファイルの中に入っています)
実行例→こちら
状態空間探索法はわかりやすく,適用範囲も広いが,万能ではない.
問題:直観的に発見的探索問題と思われるものをみつけて,状態空間探索の枠組みにうまくあてはまると思われるものとそうでないものに分類してみよう.前者については,どういうヒューリスティックを使うと解の探索が効率化するか考察し,実際にA*アルゴリズムなどにかけて動かしてみよう.後者については,なぜ難しいか考察し,どのように解くのがよいか考察してみよう.
4. 問題分解法
問題分解法は,「複雑な問題をより簡単な問題に分解し,その解を組み合わせて全体の解を得る」という解の探し方であり,「いろいろな手を使って反撃してくる敵と戦う」場合にも適用できる.問題分解法の基本構造は,AND/OR木(正確にはグラフだがここでは簡単化しておく)である.AND/OR木は,OR分岐とAND分岐が交互に繰り返される.OR分岐は「どれかの枝の先にある部分問題が解ければよい」,AND分岐は「すべての部分問題が解けなければならない」ことを表す.例えば,部分積分の問題では,与えられた問題が手におえないときは自分の知っているテクニックなかの一つを使って問題を部分問題の集まりに分解する(OR分岐).特定のテクニックを使って分解された部分問題がすべて解ければOKとなる(AND分岐).ゲームでも同様であり,相手と自分が交互に手を繰り出すとき,自分の番の時は可能な手のなかから一つを選んで相手を倒せば自分の勝ちとなる(OR分岐).相手の番の時は,相手が繰り出すいろいろな手に対しても防御ができなければならない(AND分岐).
AND/OR木を使って探索を進めるといつか終局となり,すべてが明らかになる.与えられた局面がソリューションになっているとき,あるいは,自分の勝ちのとき,その局面の(自分にとっての)スコアを+∞(プログラミング上は大きな数でよい)とする.逆に,解決不能と判明したとき,あるいは,ゲームで自分が負けたと判明したときは,スコアを-∞とする.未来のある時点ですべての局面のスコアが計算されたとき,ANDのときはmin(最小値関数),ORのときはmax(最大値関数)を使って,過去にさかのぼっていくと,いまの局面のスコアが計算される.これが基本minimax法である.
実際には,メモリや計算時間に限度があるので,ある程度「先読み」したところで探索を打ち切って,「評価関数」を使ってその局面を評価し,minimax計算を行って現在の評価値を得るのが,深さ限度付きminimax法である.一般には,先読みすると(常にそうとは限らないが)個々の問題はいまよりは簡単な問題になっていたり,盤面が煮詰まって評価しやすい状態になっているので,評価関数は盤面についてのより正確な値を返すはずであるというのがこの方法の根拠になっている.
minimaxという計算方法の性質を使って計算の効率化が可能である.OR分岐に適用できるαカットと,AND分岐に適用できるβカットである.両者は本質的に同じものである.この両方を使った探索は,α-β探索と呼ばれ,AIの古典的な手法としてよく知られている.
Lispによる基本minimax法,深さ限度付きminimax法,α-β探索演習
ここで使用するAND/OR木は次のようなものである.普通は,展開していくにつれて探索空間がこのような木構造になっていることがわかるのだが.ここでは実験用に評価値を予め与えている.

slides → こちら
ソースコード→こちら
実行例→こちら
もう少し複雑な例題
othello

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です