大項目2 人工知能をめぐる動向（探索・推論）
G検定の探索アルゴリズム（幅優先・深さ優先・Mini-Max法・αβ法）
G検定の出題範囲には、探索・推論の用語として、探索木、幅優先探索、深さ優先探索、ブルートフォース（力任せ探索）、Mini-Max法、αβ法があります。このページは、7ノードの木とゲーム木を作り、調べる順番と枝を切る場面を実際に追います。用語の定義を暗記するより、小さな木を手で追うほうが、違いを説明できるようになります。
定義は覚えたのに、探索の順番や調べる葉の数を問われると迷う人向けの内容です。
木の形と数値はすべて架空です。出題を予想するものではありません。
公式情報の確認
試験日、料金、申込条件、試験方式など変動する情報は、公式情報を最終確認してください。 当サイトの一次情報確認日: 2026-10-02。
試験の出題範囲・実施要項は変動するため、受験前に公式情報を確認してください。
結論
- 探索木は、状態をノード、操作を枝で表した木で、根から答えのノードまでの道を探す
- 幅優先探索は浅い順に全部調べ（キューを使う）、深さ優先探索は1本の枝を深く進んでから戻る（スタックを使う）
- ブルートフォースは「全候補を順に調べる」考え方で、幅優先・深さ優先は調べる順番を決めた手順
- Mini-Max法は、自分の番は最大、相手の番は最小の評価値を選ぶと仮定して、根の手を決める
- αβ法はMini-Max法と同じ答えを返しながら、結果に影響しない枝を調べない。このページの例では葉9枚が6枚になる
探索木とは何か
探索木は、問題の「状態」をノード、次の状態へ進む「操作」を枝にして描いた木です。いちばん上のノードを根、先のないノードを葉と呼びます。探索とは、根から出発して、条件を満たすノード（ゴール）に着く道を探すことです。
次の節では、根をA、Aの子をBとC、Bの子をDとE、Cの子をFとGとした7ノードの木を使います。子は左から順に調べます。
幅優先と深さ優先を7ノードの木で比べる
英語版Wikipediaによると、幅優先探索は根から始めて、現在の深さのノードをすべて調べてから次の深さへ進みます。まだ調べていない子を覚えておくために、通常は待ち行列（キュー）を使います。 深さ優先探索は、根から始めて各枝をできるだけ深く進み、行き止まりで戻ります。戻るために通ったノードを覚えるスタックを使います。
7ノードの木で、全ノードを調べる順番は次のようになります。
- 幅優先探索：A → B → C → D → E → F → G（深さ0、深さ1、深さ2の順）
- 深さ優先探索：A → B → D → E → C → F → G（左の枝を底まで進んでから戻る）
ゴールの位置によって、先に見つかる方法が入れ替わります。
| ゴール | 幅優先で見つかるまで | 深さ優先で見つかるまで |
|---|---|---|
| C（根の右の子） | A→B→C の3つ目 | A→B→D→E→C の5つ目 |
| E（左の子のさらに右の子） | A→B→C→D→E の5つ目 | A→B→D→E の4つ目 |
ゴールが根の近くにあれば幅優先が早く、左の枝の奥にあれば深さ優先が早い、というように、どちらが速いかは木の形で決まります。また、英語版Wikipediaは、辺の数で測った最短経路を求められる点を、幅優先探索の利点として挙げています。
ブルートフォースとの関係
英語版Wikipediaは、ブルートフォース探索（総当たり探索）を、あらゆる候補を順に調べて、問題の条件を満たすかを確かめる一般的な手法と説明しています。例として、自然数nの約数を求めるために、1からnまでの整数を順に割り切れるか確かめる方法が挙げられています。
幅優先探索と深さ優先探索は、ノードを調べる順番が違うだけで、最悪の場合はどちらも全ノードを調べます。ブルートフォースは、この「全部調べる」という考え方につけた名前だと整理すると、3つの用語の関係が混ざりません。
Mini-Max法でゲーム木を評価する
2人で交互に手を指すゲームでは、先の局面を木にして、葉に評価値をつけます。評価値は大きいほど自分に有利、小さいほど相手に有利とします。Mini-Max法は、自分の番では評価値が最大の手を、相手の番では最小の手を選ぶと仮定して、葉から根へ値を戻す方法です。英語版Wikipediaは、最悪の場合の損失を最小にする決定規則と説明しています。
根が自分の番、その下の3つのノードが相手の番で、それぞれ葉が3枚ずつあるゲーム木を考えます。葉の評価値は次のとおりです。
- 左の枝の葉：5、9、7
- 中の枝の葉：4、8、2
- 右の枝の葉：6、3、10
- 相手の番の3ノードは最小を選ぶ：左は5、中は2、右は3
- 自分の番の根は、その中の最大を選ぶ：max(5、2、3) ＝ 5
- 選ぶ手は左の枝で、期待できる評価値は5
このとき葉は9枚すべてを調べています。局面が増えると葉の数は急に増えるので、調べなくてよい枝を見つけることが課題になります。
αβ法で葉9枚を6枚に減らす
英語版Wikipediaによると、αβ法はMini-Max法が調べるノードの数を減らす探索で、通常のMini-Max木に使うとMini-Max法と同じ手を返します。最終決定に影響しない枝を切り落とすだけです。
根の自分が確保できる最低の評価値がα、相手が確保できる最高の評価値がβです。βがαより小さくなった枝は、実際の対局で選ばれないため、残りを調べません。
先ほどのゲーム木を、左の枝から順に調べます。
| 枝 | 調べる葉 | わかること |
|---|---|---|
| 左（5、9、7） | 3枚とも調べる | 最小値は5。根の下限（α）が5になる |
| 中（4、8、2） | 最初の4を見た時点で打ち切り（8と2は調べない） | 4は5未満なので、この枝は根に選ばれない |
| 右（6、3、10） | 6、3まで調べて打ち切り（10は調べない） | 3は5未満なので、この枝も根に選ばれない |
調べた葉は 3＋1＋2 ＝ 6枚で、9枚から3枚（8、2、10）が省かれました。根の評価値は、Mini-Max法と同じ5です。調べる葉が減っても、答えは変わりません。
ただし、調べる順番が悪いと効果が出ません。同じ木を、枝の順だけ右・中・左にして（各枝の中は左から）調べると、右は3枚すべて、中は4と8のあとに2を見ても残りの葉がなく、左も3枚すべて調べるため、葉は9枚のままです。英語版Wikipediaも、手の順番が最適に近いと探索が大きく浅くなり、順番が悪いと効率が落ちると説明しています。
問題文から読み取る
このページの計算例から導いた読み方です。出題を予想するものではありません。
- 「根に近いノードから順に調べる」とあれば、幅優先探索
- 「1本の枝を行き止まりまで進んでから戻る」とあれば、深さ優先探索
- 「すべての候補を順に調べる」とあれば、ブルートフォース（力任せ探索）
- 「自分の番は最大、相手の番は最小を選ぶ」とあれば、Mini-Max法
- 「結果に影響しない枝を調べずに省く」とあれば、αβ法（Mini-Max法と答えは同じ）
G検定の学習に使う書籍（Amazon）
試験範囲を通して読むときの1冊です。読んだ章は、このサイトの章別問題で確かめられます。
よくある質問
幅優先探索と深さ優先探索の違いは何ですか？
幅優先探索は、根に近い深さのノードをすべて調べてから次の深さへ進みます。深さ優先探索は、1本の枝をできるだけ深く進み、行き止まりで戻ってから別の枝を調べます。英語版Wikipediaは、前者が待ち行列（キュー）、後者がスタックを使うと説明しています。
ブルートフォース（力任せ探索）と幅優先探索は同じものですか？
同じではありません。ブルートフォースは、すべての候補を順に調べて条件を満たすかを確かめる考え方の名前です。幅優先探索と深さ優先探索は、候補（ノード）を調べる順番を決めた具体的な手順です。どちらも、最悪の場合はすべてのノードを調べます。
Mini-Max法は、どんなゲームに使いますか？
2人で交互に手を指し、一方の得がもう一方の損になるゲーム（二人零和ゲーム）で使います。英語版Wikipediaは、Minimaxを「最悪の場合の損失を最小にする決定規則」と説明しています。自分の番では評価値が最大の手を、相手の番では最小の手を選ぶと仮定して、根から選ぶ手を決めます。
αβ法を使うと、Mini-Max法と答えが変わりますか？
変わりません。英語版Wikipediaは、αβ法が通常のMini-Max木に使うとMini-Max法と同じ手を返し、最終決定に影響しない枝を切り落とすだけだと説明しています。このページの例でも、どちらも根の評価値は5です。
αβ法で調べる葉の数は、いつも減りますか？
いつも同じだけ減るわけではありません。英語版Wikipediaは、最適に近い順に手を調べたときに探索が大きく浅くなり、順番が悪いと効率が落ちると説明しています。このページの例では、左から調べると葉は6枚、右から調べると9枚で、減りません。