【G 検定】探索・推論
G 検定シラバス 2021 に基づき，第1次ブームで中心的な役割を果たした推論・探索の研究について学ぶ。
探索木
探索木とは，場合分けである。場合分けを続けていけば，いつか目的の条件に合致するものが出現するという考え方を基礎にしている。
基本的な検索をする手法としては，幅優先探索，深さ優先探索という 2 つの方法がある。
幅優先探索
幅優先探索 (BFS : Breadth-First Search) では，出発点に近いノード（探索木の各要素）順に検索する。したがって，出発点から遠いノードほど検索は後になる。
幅優先探索であれば，最短距離でゴールにたどり着く解を必ず見つけることができる。しかし探索の途中で立ち寄ったノードをすべて記憶しておかなければならないため，複雑な迷路になるとメモリ不足で処理を続行できなくなる可能性がある。
深さ優先探索
深さ優先探索 (DFS : Depth-First Search) では，あるノードからとにかく行けるところまで行って，行き止まりになったら 1 つ手前のノードに戻って探索を行うということを繰り返す。
深さ優先探索の場合，解が見つからなければ 1 つ手前のノードに戻って探索し直せばよいのでメモリはあまり要らない。しかし解が見つかったとしても，それが最短距離でゴールにたどり着く解であるとは限らない。また，運がよければ早く解が見つかり，運が悪ければ解を見つけるのに時間がかかる。
ハノイの塔
探索木を使ってハノイの塔というパズルを解くことができる。
ハノイの塔というパズルは，3 本のポールがあり，最初はすべて左側のポールに大きさの異なる複数の円盤を小さいものが上になるように順に積み重ねられている。円盤は一回に一枚ずつ別のポールに移動させることができるが，小さな円盤の上に大きな円盤を乗せることはできない。
このルールに従い，すべての円盤を右端のポールに移動できればパズルの完成である。
ロボットの行動計画
ロボットの行動計画も探索を利用して作成できる。これはプランニングと呼ばれる技術で，古くから研究されている。
プランニングの研究では，前提条件，行動，結果という 3 つの組み合わせで記述する STRIPS (Stanford Research Institute Problem Solver) が有名である。
ボードゲーム
ボードゲームをコンピュータで解く基本は探索であるが，その組み合わせの数が天文学的な数字になってしまうため，事実上すべてを探索しきれないという問題がある。
代表的なボードゲームにおける組み合わせは次表のとおり。
| ボードゲーム | 組み合わせ |
|---|---|
| オセロ | 8 × 8 の盤で駒が白黒で裏返しあり，約 10 の 60 乗通り |
| チェス | 8 × 8 の盤で駒が白黒 6 種類ずつ，約 10 の 120 乗通り |
| 将棋 | 9 × 9 の盤で駒が 8 種類ずつ，かつ獲得した駒が使える，約 10 の 220 乗通り |
| 囲碁 | 19 × 19 の盤（19 路盤）で駒が白黒，約 10 の 360 乗通り |
Mini-Max 法
ゲーム戦略は Mini-Max 法と呼ばれる手法を使って立てる。
考え方は単純で，ゲーム盤の状態が自分にとって有利なほどスコアが大きくなるように評価されているのであれば，自分が指す時にスコアが最大（つまり自分が有利）になるように手を打つ，また，相手が指す時にスコアが最小（つまり相手が有利＝自分が不利）になるように手を打つはずであるということを前提に戦略を立てる。
αβ 法
Mini-Max 法による探索をできるだけ減らす手法を αβ 法と呼ぶ。
例えば，最大のスコアを選択する過程でスコアが小さいノードが出現したら，その時点でそのノードを探索対象から外してしまう。つまり，探索を端折ってしまうわけである。これは探索する必要のない枝を切り落としてしまう行為で，α カットと呼ばれている。
同様に，スコアが最小のものを選ぶ過程で，すでに出現したスコアよりも大きいノードが現われた時点でその先につながるノードの探索をやめてしまう。これを β カットと呼ぶ。
このように不要な探索を省くことで，探索する量を減らす工夫をしている。
モンテカルロ法
モンテカルロ法という手法では，ゲームがある局面まで進んだら，あらかじめ決められた方法でゲームの局面のスコアを評価するという方法を完全に放棄してしまう。その代わり，どのようにスコアを評価するかというと，コンピュータが 2 人の仮想的なプレーヤーを演じて，完全にランダムな手を指し続ける方法でゲームをシミュレーションし，とにかく終局させてしまう。
このようにゲームを終局させることをプレイアウトと呼ぶ。
ある局面からプレイアウトを複数回実行すると，どの方法が一番勝率が高いか計算できるので，ゲームのスコアを評価できるのである。
