探索・推論（シラバス 技術3）

第1次AIブームの中心

1950年代後半から1960年代の第1次AIブームでは、コンピュータに探索と推論をさせる研究が中心でした。問題の状態を1つずつたどり、ゴールに至る道筋を見つけるという考え方です。

探索木と2つの基本戦略

問題の状態を節点、状態の移り変わりを枝として、木の形に表したものを探索木と呼びます。迷路なら、スタート地点が根になり、分かれ道ごとに枝分かれします。

• 幅優先探索：根に近い節点から順に、同じ深さの節点をすべて調べてから次の深さへ進みます。手数の最も少ない解を見つけられますが、調べ途中の節点を覚えておくため、メモリを多く使います。
• 深さ優先探索：1本の枝を行き止まりまで進み、解がなければ1つ戻って別の枝を試します。メモリは少なくて済みますが、最初に見つかった解が最短とは限りません。

ハノイの塔は、探索で解ける問題の代表例です。3本の棒のあいだで、小さい円盤の上に大きい円盤を置かないように全体を移します。円盤がn枚なら、最短で「2のn乗から1を引いた回数」の移動が必要です。

プランニングと積み木の世界

• STRIPS：1971年に発表されたプランニングの仕組みです。行動を「前提条件」「行動」「結果」の組で記述し、目標の状態に至る行動の並びを探します。
• SHRDLU：テリー・ウィノグラードが1970年前後に開発したシステムです。積み木が置かれた仮想の世界で、英語の指示を理解して積み木を動かし、状況についての質問にも答えました。

ゲームの先読み

• ブルートフォース：すべての可能性をしらみつぶしに調べる方法です。抜けはありませんが、チェスや囲碁では手の組み合わせが爆発的に増え、現実的な時間では終わりません。
• Mini-Max法：自分の番では自分にとっての評価値が最大になる手を選び、相手の番では相手がその評価値を最小にする手を選ぶと仮定して、先読みの結果から手を決めます。
• αβ法：Mini-Max法の探索の途中で、結果に影響しないとわかった枝をそれ以上調べずに打ち切ります（αカット・βカット）。選ばれる手は変えずに、調べる節点を減らせます。
• モンテカルロ法：ある局面から終局までランダムに打ち進める試行（プレイアウト）を何度も繰り返し、その勝率で局面のよさを見積もります。よい評価関数を人が作りにくい囲碁で成果を上げ、のちのAlphaGoでもディープラーニングと組み合わせて使われました。