探索と推論：迷路を解くように答えをさがす

ねらい

このレッスンでは、人工知能が最初のブームを迎えたころに主役だった、探索（たんさく）と推論（すいろん）の考え方を学びます。

基礎

問題を状態の枝分かれとしてとらえ、初期状態から目標状態への道をさがすという大枠を迷路とハノイの塔の例でつかみます。

1. 問題を状態の枝分かれでとらえる探索木

第一次人工知能ブームのコンピュータは、2つの道具で問題に挑みました。すでに分かっている事実から、決まりに従って新しい結論を導くのが推論です。そして、ありうる場合を枝分かれとしてたどり、答えにつながる道をさがすのが探索です。どちらも問題を記号の操作に置きかえて解くという点で地続きの道具であり、このレッスンではおもに探索のしくみを追いかけます。

探索の第一歩は、問題を機械が扱える形に置きかえることです。手がかりは「いま、どういう状態にあるか」と「そこから、どんな手が選べるか」の2つです。

迷路なら、いまいる分かれ道の位置が状態で、そこから進める方向の1つずつが選べる手です。スタート地点の状態を一番上に置き、選べる手の分だけ下へ枝をのばしていくと、上から下へ広がる木のような図ができます。この図を探索木（たんさくぎ）といいます。木の枝をたどることが、迷路の道をたどることに対応します。

パズルにも同じ置きかえが使えます。ハノイの塔（とう）は、大きさの違う何枚かの円盤を別の柱へ移していくパズルで、小さい円盤の上に大きい円盤を載せてはいけないという決まりがあります。このパズルでは、円盤の置かれ方の1つずつが状態にあたります。円盤を1回動かすたびに、いまの状態から別の状態へ移ります。こうした、ありうる状態の全体は状態空間と呼ばれます。

最初の円盤の置かれ方が初期状態で、すべての円盤を移し終えた置かれ方が目標状態です。状態空間の中で、各状態から選べる手を枝として書き出せば、ハノイの塔もまた探索木で表せます。パズルを解くことは、探索木の上で初期状態から目標状態へ至る枝の道をさがすことに置きかわります。迷路もパズルも、状態と選べる手さえ書き出せば、同じ形の問題になるのです。

2. すべての道を試すブルートフォースと枝の爆発

探索木ができたら、あとは初期状態から目標状態につながる道をさがすだけです。もっとも素直なやり方は、考えられる道をすべて順に試すことです。このしらみつぶしのやり方をブルートフォースといいます。力ずくで、という意味の言葉です。

ブルートフォースの強みは、確実さにあります。すべての道を試すのですから、目標にたどり着く道がありさえすれば、見落とすことはありません。

ただし、大きな弱点があります。枝分かれが増えるほど、試す道の数がふくれあがることです。はじめて訪れた大きな駅で、出口までの道に迷った場面を思い浮かべてください。分かれ道のたびに片方を選んで進み、行き止まりに当たったら引き返して別の道を試す。歩ける道をすべて試せば、出口にはいつか必ずたどり着けます。ところが、2つに分かれる道を選ぶたびに、ありうる道すじの数は倍々にふくらみます。分かれ道を30回通り抜けるころには、道すじの組み合わせは10億本を超えます。人間の足では、一生かけても歩き切れません。ハノイの塔でも、円盤が1枚増えるだけで調べる状態の数は大きくはね上がります。盤の広いゲームになれば道すじの数は天文学的になり、どれほど速いコンピュータでも時間内に調べきれません。ここでは、この枝が増えるほど試す数が爆発的にふくらむ現象を枝の爆発と呼ぶことにします。

この先で見る工夫は、さがす順番を選ぶ、無駄な枝を切る、当たりをつけて見積もるという形で、すべてこの爆発への答えとして生まれました。

ここまでの要点

• 探索は、問題を探索木という状態の枝分かれの図に置きかえ、初期状態から目標状態への道をさがす考え方です。
• 迷路もハノイの塔も、状態と選べる手を書き出せば同じ探索の問題になります。
• すべての道を試すブルートフォースは確実ですが、枝が増えると試す数が爆発します。

まずは全体像をつかめれば十分という人は、ここで区切って大丈夫です。「問題を枝分かれの図に置きかえ、初期状態から目標状態への道をさがす」と押さえられていれば、この先の深掘りに進む土台はできています。

発展

ここからは、探索がぶつかる2つの限界、つまり記憶の限界と計算の爆発に、どんな工夫で挑んできたのかを掘り下げます。さがす順番の選び方から、読み合いの手法、評価のしかたを根本から変えた発想まで見ていきましょう。

3. 幅優先探索と深さ優先探索のトレードオフ

しらみつぶしに調べるといっても、枝をたどる順番には選びようがあります。代表的な順番は2つあり、その間には、片方を立てればもう片方が犠牲になるトレードオフの関係がひそんでいます。

1つ目は幅優先探索（はばゆうせんたんさく）です。スタートに近い浅い段から、同じ深さの枝をすべて調べ終えてから次の深さへ進みます。木を横に一段ずつなめていくイメージです。浅い道から順に調べ尽くすので、目標に至る道のうち、手数のもっとも少ない道を確実に先に見つけられます。ただし、この最短の保証には前提があります。成り立つのは、すべての枝のコストが等しい場合、つまり1手進む手間がどの枝でも同じ場合です。迷路のように1歩の重みがどこでも同じ問題なら成り立ちますが、枝ごとにかかる手間が違う問題では、手数の少ない道がもっとも楽な道とは限りません。

幅優先探索が差し出す代償は記憶です。次に調べる候補として、同じ深さの枝をすべて覚えておく必要があります。枝分かれの多い問題では、覚えておく枝の数が深さを増すごとにふくれあがり、コンピュータの記憶（メモリ）を圧迫します。

2つ目は深さ優先探索（ふかさゆうせんたんさく）です。1本の道を行き止まりに当たるまで一気に進み、だめなら1つ戻って別の枝を試します。迷路を片手で壁づたいに進むのに似ています。いまたどっている1本の道すじを覚えておけば探索を続けられるので、記憶は少なくてすみます。そのかわり、最初に見つかった道が最短だという保証はありません。運が悪ければ、遠回りの深い枝に迷いこんだまま、長い時間をかけて戻ってくることもあります。

つまり、最短の保証を取るなら記憶を差し出し、記憶の節約を取るなら最短の保証を手放すことになります。どちらが優れているかという話ではなく、問題の大きさと使える記憶の量に応じて選ぶ道具です。この、何かを得るには何かを手放すという感覚は、この先の枝刈りや見積もりの工夫にもつらぬかれています。

理解の確認

幅優先探索は、すべての枝のコストが等しい場合に手数最短の道を確実に先に見つけますが、同じ深さの枝をすべて覚える記憶が必要になります。深さ優先探索は記憶が少なくてすみますが、最初に見つけた道が最短とは限りません。

4. 相手の最善まで読む Mini-Max 法と枝刈りの αβ 法

将棋やオセロのような2人で交互に指すゲームには、迷路にはない事情があります。相手がいることです。自分がどれほど良い手を選んでも、相手はこちらにとって都合の悪い手を選び返してきます。相手の出方まで枝分かれに含めなければ、読みは成り立ちません。

そこで、自分の手番で選べる手と、その1つずつへの相手の応手、さらにその先の自分の手というように、交互の枝分かれを書き出します。この木はゲーム木と呼ばれます。探索木の考え方を2人で指すゲームに当てはめたものです。

ゲーム木には、もう1つ道具が必要です。ゲーム木は終局まで書き切れないほど深くなるので、途中の盤面で読みを打ち切り、その盤面がどちらにどれだけ有利かを比べられなければなりません。この、盤面の良しあしを1つの点数に直すしくみを評価関数（ひょうかかんすう）といいます。たとえば、駒の損得や陣地の広さを点数に換算します。どの特徴を何点と数えるかは、この時代には人間が設計していました。

この2つの道具を使う読み合いの手法が Mini-Max 法（ミニマックスほう）です。自分の番では、評価関数の点数が最大になる手を選びます。相手の番では、相手はこちらの点数が最小になる手を選んでくると想定します。点数を最大化したい自分と、最小化してくる相手が、ゲーム木の各段で交互に現れます。読みの先端の盤面の点数から、この最大と最小を交互に選び戻していき、いま指すべき手を決めます。

ただし、Mini-Max 法にも枝の爆発がついて回ります。この計算を減らす工夫が αβ 法（アルファベータほう）です。αβ 法は、読んでいる途中で「この枝は、これ以上調べても最終的な手の選択を変えない」と分かった時点で、その先を調べるのをやめます。この打ち切りを枝刈り（えだがり）と呼びます。調べなくても結論が変わらない枝だけを切るので、αβ 法は Mini-Max 法とまったく同じ結論に、より少ない手間でたどり着けます。すべてを調べずに同じ答えへ着くという、計算の爆発への賢い挑み方です。

理解の確認

Mini-Max 法は、ゲーム木の上で、評価関数の点数を自分は最大に、相手は最小にすると想定して手を選ぶ読み合いの手法です。αβ 法は、結論を変えない枝を枝刈りして、Mini-Max 法と同じ結論を少ない手間で得る工夫です。

5. ランダムな試行で見積もるモンテカルロ法と発展の手法

Mini-Max 法の生命線は評価関数です。ところが、この生命線が用意できないゲームがありました。囲碁です。囲碁は盤面が広く選べる手も膨大なうえ、石の配置の良しあしを点数の式として書き表すこと自体が難しく、確かな評価関数を人手で設計できませんでした。評価関数がなければ、Mini-Max 法は読みを打ち切った先の盤面を比べられず、力を発揮できません。

そこで、発想を根本から変えた方法が使われるようになります。盤面の点数のつけ方を人間が設計するのをやめ、ランダムな試行の結果に評価を語らせるという方法です。乱数を使った試行を数多くくり返し、その結果からおよその値や良い手を見積もる方法をモンテカルロ法といいます。

対戦ゲームでは、モンテカルロ法は次のように働きます。ある手を選んだと仮定し、そこから決着がつくまで、お互いがランダムに手を打ち続けてみます。この、終局までランダムに打ち進める試行をプレイアウトといいます。1回のプレイアウトは出たとこ勝負にすぎませんが、同じ手から何百回、何千回とプレイアウトをくり返せば、手ごとに勝ちで終わる割合が見えてきます。この勝率が高い手ほど良い手だと見積もるわけです。盤面の良しあしを式で書けなくても、終局まで打てば勝ち負けは必ず決まります。その勝ち負けの割合を評価関数の代わりに使うという工夫です。

ここからは、当たりをつけてさがす工夫を2つ挙げます。

1つ目は A*（エースター）探索です。ゴールまでの近さをおおよそ見積もる目安を使い、ゴールに近づきそうな枝を優先してたどります。このような、おおよその見積もりを手がかりにする探索はヒューリスティック探索と呼ばれます。手当たりしだいに調べるのではなく、良さそうな方向へ重点的にさがすので、効率よくゴールへ近づけます。

2つ目はモンテカルロ木探索（MCTS）です。モンテカルロ法そのものは手の良さを見積もる方法であって、木のどこを重点的に調べるかまでは決めてくれません。モンテカルロ木探索は、プレイアウトの勝敗の記録を探索木にため、勝率の高い有望な枝により多くのプレイアウトを割りふるという形で、見積もりと木のたどり方を組み合わせた手法です。人手の評価関数という壁をこの方式が越えたことで、囲碁のプログラムは大きく前進しました。深層学習と探索を組み合わせて囲碁のトップ棋士に勝ったアルファ碁（AlphaGo）も、モンテカルロ木探索を重要な部品として使っています。アルファ碁の全体のしくみは、ディープラーニングの登場を学ぶレッスンでくわしく見ます。

理解の確認

モンテカルロ法は、乱数を使った試行を重ねて手の良さを見積もる方法で、対戦ゲームでは終局までランダムに打ち進めるプレイアウトの勝率を評価の代わりに使います。発展として、ゴールへの近さの目安で枝を選ぶ A* 探索やヒューリスティック探索、プレイアウトの結果を木にためて有望な枝に試行を集めるモンテカルロ木探索があります。

6. プランニングの STRIPS と積み木の世界の SHRDLU

探索と推論の考え方は、初期の有名なプログラムに実を結びました。

1つ目は STRIPS（ストリップス）です。目標を達成するために、どの行動をどの順で行えばよいかを組み立てる、プランニングと呼ばれる行動計画のしくみです。それぞれの行動に「実行するのに必要な前提の状態」と「実行後に変わる状態」を持たせ、いまの世界のありさまを初期状態、達成したいありさまを目標状態として、そこへたどり着く行動のならびをさがします。扱うものが円盤から行動に変わっただけで、初期状態から目標状態への道を探索するという骨組みは、ハノイの塔と同じです。

2つ目は SHRDLU です。机の上に積み木が置かれた仮想の世界で、「赤い箱の上の積み木をどけて」といった言葉による指示を理解し、その世界の中で積み木を動かしてみせるプログラムでした。かぎられた世界の中で、言葉の理解と行動の計画を結びつけた先進的な試みでした。

これらのプログラムは、対象をかぎった世界の中では見事に働きました。しかし、現実の世界へ広げようとすると、考えるべき状態と枝があまりに増え、通用しませんでした。単純化した世界でしか解けないという限界は、人工知能の歴史のレッスンで見たトイ・プロブレムにほかなりません。そして、無数の可能性の中から関係のあることだけを選び出せないという壁は、知能をめぐる問いのレッスンで見たフレーム問題として立ちはだかりました。第一次ブームの探索と推論は、この2つの壁の前で勢いを失っていきました。

理解の確認

STRIPS は、行動の前提と結果を手がかりに、初期状態から目標状態へ至る行動のならびを組み立てるプランニングのしくみです。SHRDLU は、積み木の仮想世界で言葉の指示を理解して行動するプログラムでした。どちらもかぎられた世界の外へは広げにくく、その限界はトイ・プロブレムやフレーム問題という論点につながりました。

理解度の確認