【G検定まとめ2026】3.探索・推論

1. 探索・推論の具体例を説明できる

迷路問題と探索木

迷路問題は、探索と推論の基本的な考え方を理解するのに適した例です。コンピュータが迷路を解く過程を見ていくと、探索の仕組みがよく分かります。まず、迷路をコンピュータが処理できる形に変換します。具体的には、分岐点や行き止まりに記号を付け、迷路の枠を取り除きます。すると、迷路は木の形をした構造、つまり探索木として表現できます。探索木では、スタート地点を起点として、各分岐点や行き止まりがノードとなり、それらを線で結んだ構造になります。この探索木を順にたどっていき、ゴールにたどり着く経路を見つけることで、迷路の解答を得ることができます。

ハノイの塔と探索木

探索木は、ハノイの塔というパズルの解法にも応用できます。ハノイの塔は、3本のポールと大きさの異なる円盤を使ったパズルです。最初はすべての円盤が左側のポールに小さいものが上になるように積まれています。このパズルをコンピュータに解かせるには、まず状態をコンピュータが理解できる形で表現する必要があります。例えば、円盤の位置を数字と記号の組み合わせで表現し、それを探索木の形に変換します。探索木を用いることで、ハノイの塔の様々な状態とその間の遷移を表現できます。この木構造を探索することで、初期状態から目標状態（すべての円盤が右側のポールに移動した状態）への最適な手順を見つけることができます。

ロボットの行動計画

探索は、ロボットの行動計画（プランニング）にも応用されています。例えば、部屋の掃除をするロボットの行動を計画する場合を考えてみます。ロボット、部屋、ゴミを含む環境を1つの状態として捉え、ある状態から別の状態への遷移をロボットの行動とみなします。これらの状態と行動の関係を探索空間として表現します。プランニングでは、各状態に対して「前提条件」、「行動」、「結果」という3つの要素を定義します。これにより、ロボットは現在の状態から目標の状態に至るまでの最適な行動順序を決定することができます。このようなプランニング技術は、単純な掃除ロボットだけでなく、より複雑なタスクを行う高度なロボットシステムの開発にも応用されています。

2. 探索・推論を実現する代表的な手法を説明できる

探索木による問題解決

迷路の問題を例に、探索・推論の基本的な考え方を見てみましょう。コンピュータで迷路を解くには、問題をコンピュータが処理できる形に変換する必要があります。迷路の分岐点や行き止まりに記号を付け、それらの関係性を図式化すると、木の形をした構造が現れます。これを「探索木」と呼びます。

探索木は、迷路の問題を場合分けして表現したものです。スタート地点から探索木をたどり、ゴールにたどり着く経路を見つけることで、迷路の解答を得ることができます。

基本的な探索手法

探索木を用いて問題を解く際、主に以下の2つの手法が使われます。

幅優先探索：幅優先探索は、出発点に近いノード（探索木の各要素）から順に探索していく方法です。この方法では、最短距離でゴールにたどり着く解を必ず見つけることができます。ただし、複雑な問題では探索の途中で立ち寄ったノードをすべて記憶しておく必要があるため、メモリ不足に陥る可能性があります。

深さ優先探索：深さ優先探索は、ある経路をとにかく行けるところまで進み、行き止まりになったら1つ前のノードに戻って別の経路を探索する方法です。この方法はメモリの使用量が少なくて済みますが、最短経路を見つけられるとは限りません。また、問題の性質によっては解を見つけるまでに時間がかかる場合があります。

ゲーム戦略における探索

ボードゲームのような対戦型の問題では、自分の手と相手の手を交互に考慮する必要があります。このような状況でよく用いられる手法が、Mini-Max法です。

モンテカルロ法

近年、囲碁や将棋のコンピュータプログラムで注目されているのが、モンテカルロ法です。この方法では、ある局面からゲーム終了までをランダムに何度もシミュレーションし、その結果から最適な手を判断します。

---

キーワード解説

αβ法

Mini-Max法を改良した手法で、Mini-Max法による探索をできるだけ減らす手法。この方法では、すでに評価されたスコアを基に、不要なノードの探索を減らすことが可能だ。具体的には、αカットとβカットという2つの手法が用いられる。 - αカット：すでに出現したスコアよりも小さいノードが現れた時点で、その先につながるノードの探索をカットする。これにより、より良い結果を得られる可能性の低いノードにかかる探索コストを削減できる。 - βカット：すでに出現したスコアよりも大きいノードが現れた時点で、その先につながるノードの探索をカットする。これも同様に、探索コストの削減に寄与する。

Mini-Max法

自分が番にスコアが最大になるように、相手の番にはスコアが最小になるように戦略を立てる手法。ボードゲームにおける探索木では、一手が指され他時に盤面の状態を探索木の各ノードとし、ある盤面における状態の良し悪しはスコアによって評価される。この手法は、自分の手番と相手の手番を交互に展開することで、相手が最善手を打ったと仮定し、その中で自分の最適な手を選ぶ。具体的には、葉ノード（終端状態）までのスコアを計算し、その値を親ノードに伝搬させる。自分の手番では子ノードの最大値を選択し、相手の手番では最小値を選択することで、最適な手を決定する。MiniMax法はすべての盤面状態を調べるため、計算量が膨大になる欠点がある。

SHRDLU

1968年から1970年にかけて、テリー・ウィノグラードによって実施されたプロジェクトプランニングを実現する研究。英語による指示を受け付け、コンピュータ画面に描かれる「積み木の世界」に存在する様々な物体（ブロック、四角錐、立方体など）を動かすことができた。この成果はCycプロジェクトにも引き継がれている。

STRIPS

STRIPS(Stanford Research Institute Problem Solver)は1970年代に提案された「前提条件」・「行動」・「結果」の3つの組み合わせで記述するプランニングの手法。この手法では、状況における前提条件と目標状態を定義し、それらの間にある行動を決定することで、エージェントが目標を達成するための適切な行動計画を立てることができる。

探索木

計算機科学において特定のキーを特定するために使用される木構造のことで、学習結果を木構造で表現できるため解釈性が高い。場合分けを続けていけばいつか目的の条件に合致するという考え方に基づく。不純度が最も減少(情報利得が最も増加)するようにデータを振り分けることを繰り返す。不純度とはクラスの混ざり具合を表す指標でジニ係数やエントロピーがある。バギングを組み合わせた手法をランダムフォレストという。

ハノイの塔

円盤と3本のポールを用いたパズルの一種である。「1回に動かせる円盤の枚数は1枚のみ」「小さな円盤の上に大きな円盤を乗せることはできない」というルールに従って、全ての円を右端に移動させる。このパズルは、再帰的なアルゴリズムやプログラミングの教材としてよく用いられ、計算機科学や人工知能の分野でも重要な役割を果たしている。円盤の枚数がn枚である時、最小の手数は「（2^n）-1」回であることが知られており、この性質を利用して様々な問題解決アプローチや最適化手法を学ぶことができる。

幅優先探索

出発点に近いノード（探索木の各要素）順に検索する。出発点から遠いノードほど検索は後回しになる。最短距離でゴールにたどり着く解を見つけることができる。探索の途中で立ち寄ったノードをすべて記憶しておく必要がありメモリが多く必要となる。

深さ優先探索

深さ優先探索は、一つのノードから可能な限り深く探索を進め、行き止まりに達したら一つ前のノードに戻って再度探索を行う手法である。この方法は、メモリの使用量が少なくて済むが、必ずしも最短距離でゴールに到達するわけではない。運に左右される要素も含まれている。また、「縦型探索」とも称される。

ブルートフォース

総当たり攻撃を行う力任せな方法で、可能な組み合わせを全て試すアプローチ。人間の思考方法とは違ってブルートフォース（力任せ）で押し切る方法のため、探索しなければならない組み合わせの数が増えると、立ち行かなくなるためしばらくは囲碁でプロに勝てなかった。しかし、ディープラーニングの技術を利用し、人間の思考方法をコンピュータで再現することに成功。この結果、人間のプロ棋士に勝利を収めることが可能となった。ディープラーニングを用いた手法は、ブルートフォースとは対照的に、効率的な探索や学習が可能であることが示された。

モンテカルロ法

モンテカルロ法は乱数を用いたシミュレーションや数値計算を行う手法の総称。囲碁や将棋などにおいては、ゲームがある局面まで進んだら、あらかじめ決められた方法でゲームの局面のスコアを評価するという方法を完全に放棄する。その代わりに、コンピュータが2人の仮想的なプレイヤを演じて、完全にランダムに手を指し続ける方法でゲームをシミュレーションし終局させてしまうことをプレイアウトという。どの方法が一番勝率が高いか計算でき、ゲームのスコアを評価できる。