第１次AIブーム：探索・推論
学習目標
第1次ブームで中心的な役割を果たした推論・探索の研究について学ぶ。
迷路（探索木）
ハノイの塔
ロボットの行動計画
ボードゲーム
モンテカルロ法
キーワード：探索木、幅優先探索、深さ優先探索、プランニング、STRIPS、SHRDLU、AlphaGo（アルファ碁）、ヒューリスティックな知識、Mini-Max法、αβ法、ブルートフォース
探索木
探索木を使った行動計画（プランニング）が活用されました。探索木を使うことによってコンピュータで問題を解くことができる利点があります。
迷路
例えば、A地点にいるロボットがB地点で他のロボットと合流したいといったケースは探索木で解くことができます。
探索木では状態（例:A地点に居る）と行動（例：X地点に移動する）があり、行動を選ぶことによって状態が変わります。
探索木を使って正解に辿り着く道を見つけ出す手法は大きく分けて２つあります。
以下は、左から右へと探索する順番を幅優先探索と深さ優先探索で表示しました。
ちなみに、幅優先探索と深さ優先探索の両方とも右側を優先して探索することも可能です。
ハノイの塔
探索木で問題が解決できるのは、状態と行動を場合分けしていくことでいつかはゴールの条件を満たした状態に行き着くという考えが当てはまる場合です。もう一つの有名な例としてハノイの塔があります。
ハノイの塔も全て可能な状態を探索木に当てはめることで解決することができます。繰り返しになりますが、探索木にするとコンピュータで解を見つけられるのがポイントです。これによって人間の試行錯誤が探索木を使ったプログラムになりました。
ハノイの塔では、円盤を一度に一つしか動かせません。また、円盤はより大きい円盤の上にしか乗せられません。この制限を元に全ての状態遷移を探索木にしていきます。
初期状態からは次の二つの状態に遷移可能です。
この二つの状態からまた次の状態へと枝分かれ（場合分け）していきます。これをゴール状態が出るまで繰り返せば探索木の完成になり、幅優先探索か深さ優先探索を使えば解が見つかります。解が複数存在するので幅優先探索を使えば最短の移動手順が割り出せます。
ロボットの行動計画
プランニング
ロボットの行動計画に探索を利用する技術をプランニングと呼びます。ちなみに、公式テキストで登場するお掃除ロボットは書籍「エージェントアプローチ人工知能」（原題：Artificial Intelligence：A Modern Approach）を参考にしているようです。
ロボットは部屋Aと部屋Bを掃除する必要があります。もちろん、ゴミがなければ掃除する必要はありません。
簡単な行動計画としては、ゴミがあったら掃除してなかったら別の部屋へ行くというものです。
上記の規則に従って行動すれば両方の部屋が常に掃除されている状態になります。このように、プランニングでは状態、行動、結果などを記述して行動計画を立てます。
STRIPS
プランニングの研究で有名なものにSTRIPS（Stanford Research Institute Problem Solver）があり、以下の情報を記述して目標を達成するための行動計画を立てます。
初期状態（例：部屋Aにいる。そしてゴミがある）
目標状態（例：全ての部屋にゴミがない）
行動（例：掃除する。部屋を移動する）
また、行動には以下が含まれる:
事前条件（例：掃除する条件はゴミがあること）
効果・事後条件（例：掃除をするとゴミがなくなる）
SHRDLU
SHRDLUは人工知能研究初期の研究開発プロジェクト。1968年から1970年にかけて、テリー・ウィノグラード（スタンフォード大学の計算機科学者）によって実施された。コンピュータに英語で指示を出すと、物体を動かしてくれるもので質問にも答えられる。
上図左の画像はオリジナルの「積み木の世界」の映像で、右は後にカラー化されたものです。
自然言語を使って「積み木の世界」にあるブロック、円錐、球体を積み上げたり下ろしたりできる。以下にSHRDLUのサイトから引用します。（日本語訳は私がつけました）
ウィノグラードは、ラリー・ペイジを1995年より指導していました。ラリー・ペイジは当時ウェブ検索を含む研究計画に参加していたスタンフォード大学の博士課程の学生でしたが、1998年に休学し「グーグル」 (Google) の共同設立者となりました。2002年には、なんとウィノグラードもサバティカル休暇をとってグーグルで客員研究員として過ごし人間とコンピュータの相互関係の理論と実践の交わりについて研究しました。近年は、スタンフォードで人間とコンピュータの相互関係 (Human-Computer Interaction, HCI) の講義とセミナーを担当しているそうです。
ちなみに、SHRDLUという名前は組版鋳造機のキーボードの並びにある意味のないフレーズだそうです。
ここでの成果は第２次AIブームへ引き継がれ、Cyc（サイク）プロジェクトへと発展していきます。
ボードゲーム
オセロ、チェス、将棋、囲碁などのボードゲームをコンピュータで解くのにも探索が使われます。
Mini-Max法
ボードゲームでは二人のプレイヤーが交互に次の手を打つのでMini-Max法によって次の一手を決めることができます。
Mini-Max法の基本は深さ優先探索にボードの状態を評価する関数を組み合わせた手法です。評価関数は人間が決めた何らかの方法で計算した値を出します。この値をスコアと呼び、ボードの状態が有利か不利かの指標となります。
簡単な例で説明します。
架空のゲームで自分（青）の番が来たとします。相手（赤）と交互に打つ手を決めるのですが、青は２手先まで読んで次の一手を決めようとしています。
なお、青も赤も合理的にプレイするので、青は青のスコアを最大化することを目指し、赤は赤のスコアを最大化することを目指します。言い方を変えると、青は青のスコアを最大化し、赤は青のスコアを最小化することを目指します。
上から深さ優先探索で順番に探索し、２段下の左１番目に到着します。そこでスコアを計算します。
2手先までしか読まないので、次は２段下の左２番目の一番下のスコアを計算します。
今度は１段上に戻って、赤がどの手を打つか決めます。赤は青のスコアを最小化するために、スコアが２になる手を選びます。
次に右側の探索をします。２段下の右２番目のスコアを計算します。
次に２段下の右１番目のスコアを計算します。
今度は赤がスコアを最小化するようにスコア１になる手が選びます。
よって青がスコアを最大化するためにスコアが２になる手を次の一手として選択します。
スコアの予測が正しく、自分も相手も合理的に行動すれば上記のようにゲームが展開するはずです。
これがMini-Max法で、終局まで先読むすることができれば勝敗がわかるので最適な次の一手を見つけられます。全ての状態を隈なく調べる方法をブルートフォースと呼びます。
しかし、探索する深さが増すと組み合わせが指数的に増大し天文学的な数になるので、実際には先読みする深さを制限したり（五手先までとか）、無駄な探索を減らすなどの工夫が必要になります。
αβ法
αβ法はMini-Max法による探索を効率よく行う手法です。探索を続けるのが不要な状態を探索から切り捨てることで無駄を省きます。
先ほどと同じ例で説明します。ただし、２手先より下にもたくさんのレベルがあることを図では明示しておきます。Mini-Max法と同じ手順（深さ優先探索）で２段下の右２番目のスコアが１と出るところまで来ました。
先ほどは、続いて２段下の１番右のスコアを計算しましたが、実はこれは必要ありません。ここでαβが出てきます。
スコアを最大化する側（青）のもつベストの手をαと呼びます。現状、αによるスコアは２です。青はこれより低いスコアの手を選択しません。
スコアを最小化する側（赤）のもつベストの手をβと呼びます。現状、βによるスコアは１です。赤はこれより高いスコアの手を選択しません。
つまり、αのスコアが２でβのスコアが１なので青が右側の手を選ぶことは無く、これ以上探索を続ける必要がないのです。
上記のように、αβ法ではたくさんの探索の手間（コスト）を省くことが可能です。また、αβ法のように経験則からの知識やルールをヒューリスティックと呼びます。
モンテカルロ法
Mini-Max法やαβ法ではスコアの正確さが重要となります。先読みのレベルが制限されているので、終盤になるまでは勝ち負けがわからず、途中の状態でのボードの評価が正確でないと最善な次の一手を選べません。終局まで遠い場合は特にスコアを正確に予測するのは困難になる傾向があります。
モンテカルロ法では、ある局面からゲームが終了するまでを完全にランダムにシミュレーション（プレイアウト）し勝敗を決めます。このプレイアウトを何度も繰り返すことで、どの次の一手を打つと勝つ割合（確率）が高いのかがわかってきます。
プレイアウトの数が増えるほど、モンテカルロ法はブルートフォースによる全ての組み合わせを隈なく調べる方法に近付くので正確さが増していきます。よって、人間の考えた評価関数より正しい可能性が高くなります。また、終盤になるほどプレイアウトを速くたくさん実行できます。
しかし、囲碁は19×19のマスがあり、プレイアウトの数を十分にするだけの時間がありません。
AlphaGo（アルファ碁）ではこの問題をディープラーニングで解決し人間のプロ棋士に勝利しました。
