探索・推論（探索木、幅優先・深さ優先、Mini-Max法とαβ法、モンテカルロ法）

この節の練習問題（8問）

答えを見る前に選んでから開いてください。同じ問題は章別演習でランダム出題されます。

1. 問1
   探索木をたどる手法のうち、「出発点に近いノードから順にすべて調べ、必ず最短の解を見つけられるが、途中のノードをすべて記憶するためメモリを多く消費する」ものとして最も適切なものを選びなさい。
   1. 1幅優先探索
   2. 2深さ優先探索
   3. 3Mini-Max法
   4. 4モンテカルロ法
   答えと解説

   正解: 1

   幅優先探索は、探索木を浅い階層から順に横方向にすべて調べる手法で、最初に見つかった解が最短であることが保証される一方、階層ごとのノードをすべて保持するためメモリ消費が大きくなります。深さ優先探索は1本の経路を行けるところまで進む手法でメモリは少なくて済みますが、最短解の保証はありません。Mini-Max法とモンテカルロ法はゲームの手を評価する手法です。

2. 問2
   二人零和ゲームの探索において、Mini-Max法で「これ以上調べても評価が変わらない」と判断できる枝の探索を打ち切り、計算量を減らす手法を何というか。最も適切なものを選びなさい。
   1. 1STRIPS
   2. 2αβ法
   3. 3ブルートフォース
   4. 4幅優先探索
   答えと解説

   正解: 2

   Mini-Max法は、自分の手番では評価値が最大になる手を、相手の手番では最小になる手を選ぶと仮定してゲーム木を探索する手法です。αβ法はその枝刈り版で、すでに見つかった手より良くならないことが確定した枝（αカット・βカット）の探索を打ち切ることで、結果を変えずに計算量を減らします。ブルートフォースは総当たり、幅優先探索は一般的な探索法、STRIPSはプランニングの手法です。

3. 問3
   囲碁のように局面の評価が難しいゲームで、ある局面から終局までランダムに何度もプレイアウトして勝率を集計し、手の良し悪しを評価する手法として最も適切なものを選びなさい。
   1. 1深さ優先探索
   2. 2ミニマックス法
   3. 3モンテカルロ法
   4. 4アルファベータ法
   答えと解説

   正解: 3

   モンテカルロ法は、乱数を使ったシミュレーションを多数回行い、その統計から答えを近似する手法です。囲碁では局面の評価関数を作ることが難しかったため、終局までランダムに打つプレイアウトを繰り返して勝率で手を評価するモンテカルロ木探索が用いられ、AlphaGoにも組み込まれました。深さ優先探索は木構造を枝の末端まで順にたどる探索、ミニマックス法は相手が最善手を選ぶ前提で評価値を決める探索、アルファベータ法はミニマックス法の枝刈りによる効率化で、いずれもランダムなプレイアウトで評価する手法ではありません。

4. 問4
   探索において、考えられるすべての組み合わせを片端から調べて解を見つける方法を（　）という。括弧に入る語として最も適切なものを選びなさい。
   1. 1ブルートフォース（総当たり）
   2. 2モンテカルロ木探索（MCTS）
   3. 3アルファベータ法（αβ法）
   4. 4ヒューリスティック探索
   答えと解説

   正解: 1

   ブルートフォースは力任せの総当たりで、組み合わせが少なければ確実に解を見つけられますが、組み合わせの数が指数的に増える問題では現実的な時間で終わりません。αβ法は探索の枝を刈って計算量を減らす手法、モンテカルロ法はランダムな試行の統計で評価する手法、ヒューリスティック探索は経験則で有望な候補を優先する方法です。

5. 問5
   ハノイの塔のようなパズルを人工知能で解く際の基本的な考え方として、最も適切なものを選びなさい。
   1. 1専門家に最適な手順をインタビューし、その知識をif-thenルールとして記述して再現する
   2. 2盤面の状態をノード、1回の移動を枝とする探索木を作り、初期状態から目標状態に至る経路を探索する
   3. 3円盤の動かし方を大量の人間の対局データから機械学習で獲得し、確率的に次の手を決める
   4. 4円盤の物理的な重さと摩擦をシミュレーションし、力学的に最も安定する配置を計算する
   答えと解説

   正解: 2

   第一次AIブームの探索・推論では、問題の状態を「場合分け」して木構造（探索木）で表し、初期状態から目標状態までの経路を幅優先探索や深さ優先探索で見つけます。ハノイの塔は3本の柱と円盤の配置が状態、円盤の移動が枝に対応する典型例です。機械学習や物理シミュレーション、専門家の知識記述は探索・推論の考え方ではありません。

6. 問6
   1971年に開発された、「前提条件」「行動」「結果」の3つの組み合わせでロボットの行動計画（プランニング）を記述する手法と、積み木の世界で英語の指示を理解して操作するシステムの組み合わせとして正しいものを選びなさい。
   1. 1Cyc、東ロボくん
   2. 2DENDRAL、MYCIN
   3. 3STRIPS、SHRDLU
   4. 4ELIZA、ワトソン
   答えと解説

   正解: 3

   STRIPSは前提条件・行動・結果の3要素で行動を記述し、目標を達成する行動の列を探索するプランニングの手法です。SHRDLUはテリー・ウィノグラードが開発した、積み木の世界を対象に英語の指示を理解して操作するシステムです。DENDRALとMYCINはエキスパートシステム、ELIZAは対話プログラム、ワトソンは質問応答システム、Cycは常識の記述プロジェクト、東ロボくんは大学入試に挑戦した人工知能です。

7. 問7
   メモリの小さい組込み機器で迷路の解を探索させたい。最短経路でなくてもよいので、少ないメモリで解を1つ見つけたい。最も適切な探索手法を選びなさい。
   1. 1幅優先探索
   2. 2Mini-Max法
   3. 3αβ法
   4. 4深さ優先探索
   答えと解説

   正解: 4

   深さ優先探索は1つの枝を行き止まりまで進んでから戻るため、記憶するノードが少なくて済みます。最初に見つかる解が最短とは限りませんが、この場面の条件に合います。幅優先探索は最短経路を必ず見つけられる反面、途中のノードをすべて記憶するためメモリを大量に使い、Mini-Max法とαβ法は二人零和ゲームの探索手法です。

8. 問8
   将棋やチェスなどの二人零和ゲームで、自分は評価値が最大になる手を、相手は自分にとって評価値が最小になる手を選ぶと仮定して先読みする探索手法として、最も適切なものを選びなさい。
   1. 1モンテカルロ木探索
   2. 2幅優先探索
   3. 3Mini-Max法
   4. 4ブルートフォース
   答えと解説

   正解: 3

   自分の手番では評価値が最大の手、相手の手番では最小の手を選ぶと仮定して探索木をたどるのがMini-Max法で、評価が変わらない枝の探索を打ち切って効率化したものがαβ法です。モンテカルロ木探索はランダムなプレイアウトの勝率で手を評価する方法、幅優先探索は出発点に近いノードから順に調べる方法、ブルートフォースはすべての組み合わせを調べる総当たりです。