探索・推論

みかん

今回はG検定の第2章「人工知能をめぐる動向」の1節「探索・推論」を解説します。第1次AIブームで中心的な役割を果たした探索・推論の研究について学んでいきましょう。

みかん

迷路のような問題を、コンピュータを使って解くことを考えましょう。コンピュータで問題を解くためには、まず問題をコンピュータで処理できるような形式に変換する必要があります。

みかん

迷路の分岐や行き止まりに記号を付けて、枠を取り去って起点から下げてみると、木のような構造で表現できます。これを「探索木」（ツリー構造）と呼びます。

みかん

その通りです。探索木をたどって正解にたどり着く方法は複数ありますが、基本的な検索の手法としては「幅優先探索」と「深さ優先探索」の2つがあります。

みかん

「幅優先探索」では、出発点に近いノード（探索木の各要素）を順に検索します。出発点から近いノードほど検索は後になります。幅優先探索であれば、最短距離でゴールにたどり着く解を必ず見つけることができます。

みかん

「深さ優先探索」では、あるノードからとにかく行けるところまで行って、行き止まりになったら1つ手前のノードに戻って探索を行うことを繰り返します。メモリはあまり要りませんが、最短距離でゴールにたどり着けるとは限りません。

みかん

その通りです。実際にはこの2つの良いところを組み合わせる方法や、特殊なケースに限って速く探索できる方法などの研究が古くからされており、今も脈々と続いています。

みかん

「ハノイの塔」は、3本のポールと大きさの異なる複数の円盤を使ったパズルです。円盤は一回に一枚ずつ別のポールに移動でき、小さな円盤の上に大きな円盤を乗せることはできません。すべての円盤を右端のポールに移動させればパズルの完成です。

みかん

このパズルもコンピュータが理解できる形式に問題を変換する必要があります。円盤に1、2、3と番号を振り、3本のポールにP、Q、Rと名前を付けると、ハノイの塔の状態を数学的に表現できます。

みかん

ハノイの塔も探索木として描くことができます。すべての円盤をルールに従って右端のポールに移動するパスは複数存在しますが、最短で移動させるには一番右端のパスを選択すればよいことが分かります。

みかん

ロボットの行動計画も探索を利用して作成できます。これは「プランニング」と呼ばれる技術で、古くから研究されています。ロボットや部屋、ゴミを含む現場を1つの状態と考え、状態から別の状態への遷移を探索空間とみなして構成します。

みかん

プランニングの研究では、あらゆる状態について＜前提条件＞、＜行動＞、＜結果＞という3つの組み合わせで記述する「STRIPS」（Stanford Research Institute Problem Solver）が有名です。

みかん

「SHRDLU」は1968年から1970年にかけてテリー・ウィノグラードによって開発されたシステムで、英語による指示を受け付け、コンピュータ画面に描かれる「積み木の世界」に存在する様々な物体を動かすことができました。

みかん

「積み木の世界」という限定された世界の中だけでしたが、自然な会話をすることができました。この成果は後に「Cycプロジェクト」にも引き継がれていきます。

みかん

ボードゲームをコンピュータで解く基本は探索ですが、その組み合わせの数が天文学的な数字になってしまうという問題があります。代表的なボードゲームでの組み合わせ数を見てみましょう。

みかん

効率よく探索するために「コスト」の概念を取り入れます。たとえば、東京から大阪に移動する際に、どの経路や交通手段を使うかによって、時間や費用といったコストに違いが生じます。あらかじめ知っている知識や経験を利用してコストを計算すれば、探索を短縮できます。

みかん

ここで利用する知識を「ヒューリスティックな知識」と呼びます。「ヒューリスティック」とは「経験的な」「発見的な」という意味があり、必ずしも正解を保証しないものの、探索や推論を効率よく進めることに役立ちます。

みかん

ボードゲームは迷路やパズルとは違い、相手がいます。自分が指した後に相手が指し、また自分が指すということを繰り返す探索木を作らなければなりません。

みかん

ゲーム戦略は「Mini-Max法」と呼ばれる手法を使って立てます。自分の番ではスコアが最大（自分が有利）になるように手を打ち、相手の番では自分のスコアが最小になるように相手が打つと仮定して戦略を立てます。

みかん

未来の局面から現在の局面に向けて逆算することで戦略を立てます。三手先まで先読みした例では、枝の一番下から上に向かって各ノードのスコアを順に決定していきます。

みかん

Mini-Max法は単純なゲーム戦略ですが、論理的に考えて無駄な探索が生じます。その無駄を省く方法を「αβ法」と呼びます。αβ法では評価（スコア計算）する必要のないノードは探索対象から外してしまいます。

みかん

αβ法には「βカット」と「αカット」の2つの枝刈りがあります。βカットは、自分の番の局面で、探索する必要のない相手の枝を切り落とす行為です。スコアが最大となるものを選択する局面で、より小さいスコアの候補が見つかった時点で残りの探索を打ち切ります。

みかん

「αカット」は、相手の番の局面で、スコアが最小となるものを選択する局面で、探索する必要のない自分の枝を切り落とす行為です。

みかん

囲碁や将棋ソフトは近年とても強くなっていますが、探索するノード数が膨大なため、ゲーム盤のスコア（コスト評価）に問題があることが分かってきました。従来の方式では、過去の膨大な戦歴を元に人間がスコアを決めていたのです。

みかん

「モンテカルロ法」では、ゲームがある局面まで進んだら、あらかじめ決められた方法でスコアを評価する代わりに、完全にランダムに手を指し続けてゲームをシミュレーションし、とにかく終局させてしまいます。これを「プレイアウト」と呼びます。

みかん

ある局面からプレイアウトを複数回実行すると、どの方法が一番勝率が高いか計算できるので、ゲームのスコアを評価できるのです。「数多く打って最良のものを選ぶ」という評価方法が優れていることが分かり、9×9の囲碁では人間のプロ棋士とほぼ同レベルに達しました。

みかん

その通りです。盤が大きくなると探索しなければならない組み合わせが爆発的に増えます。網羅的に探索する「ブルートフォース（力任せ）」の方法と同様に、立ち行かなくなるからです。

みかん

しかし、AlphaGoが19×19の囲碁で世界トップのプロ棋士に勝利したことは画期的でした。AlphaGoはブルートフォースではなく、「ディープラーニングの技術」を使って人間の思考方法をコンピュータで実現し、世界トップのプロ棋士に勝利したのです。

みかん

1つ目、迷路やパズルなどの問題は「探索木」として表現でき、「幅優先探索」と「深さ優先探索」が基本的な探索手法です。

みかん

2つ目、ロボットの行動計画（プランニング）では、STRIPSのように前提条件・行動・結果の組み合わせで記述します。SHRDLUは「積み木の世界」で自然な会話を実現しました。

みかん

3つ目、ボードゲームでは「Mini-Max法」で戦略を立て、「αβ法」で無駄な探索を枝刈りして効率化します。「ヒューリスティック」な知識も探索の効率化に重要です。

みかん

4つ目、「モンテカルロ法」はランダムなシミュレーション（プレイアウト）でスコアを評価する手法です。AlphaGoはディープラーニングを組み合わせて19×19の囲碁で世界トップのプロ棋士に勝利しました。

みかん

ということで今回は探索・推論について解説しました