本文へ移動
← 目次 生成AI発展講座 DAY 07

第2章|人工知能をめぐる動向

DAY 07 ・ 約30分

ゲーム木と推論

Mini-Max法とαβ法から、先を読む計算を理解する。

今日できるようになること

自分と相手が交互に選ぶ問題をゲーム木で表し、Mini-Max法とαβ法が何を計算し、評価関数と探索深さが結果へどう影響するか説明できる。

01 言葉を知る02 仕組みを理解する03 実例で理解する04 今日の理解度を確認する05 今日の整理をする
01|言葉を知る

言葉を知る

用語を暗記するだけでなく、似た概念との違いと、何を判断するための言葉かまで整理します。

ゲーム木

現在の局面から可能な手を枝、手の結果を次の局面として表す木です。自分の手番と相手の手番が交互に現れます。

Mini-Max法

自分は評価を最大化し、相手は自分の評価を最小化すると仮定して、先の局面から現在の最善手を逆算する方法です。

評価関数

途中の局面が自分にどれだけ有利かを数値化する物差しです。最後まで探索できないとき、葉の代わりに局面を評価します。

αβ法

Mini-Max法と同じ結論を保ちながら、すでに調べた結果から選ばれないと分かる枝を省く方法です。

手の並べ替え

有望な手を先に調べることでαβ法の枝刈りを増やす工夫です。最終結論を変えず、計算量を減らします。

探索深さ

現在から何手先まで読むかを表します。深いほど先を見られますが、候補数と計算時間が増えます。

完全情報ゲーム

Mini-Max法の基本形は、二人、交互手番、完全情報、運なし、利害が反対という条件を想定します。

02|仕組みを理解する

仕組みを理解する

1.相手も最善を選ぶ前提で、計画を立てる

通常の経路探索では、道が突然こちらの不利になるよう選択するとは考えません。対戦ゲームでは、自分がよい手を選んでも、相手がそれを打ち消す手を選びます。そこで自分の選択だけでなく、相手の返答、その次の自分の手まで交互に並べたゲーム木を作ります。 Mini-Max法は、自分の手番では評価が最大になる枝、相手の手番では自分の評価が最小になる枝を選ぶと仮定します。相手の能力を低く見積もって都合のよい返答だけを期待せず、最も厳しい返答を受けても残る価値を比較します。これはチェスだけでなく、価格交渉、攻撃と防御、競合が反応する意思決定を考える基本形です。ただし現実の相手が常に完全合理的とは限らず、前提の限界は残ります。

2.終端の値を、手前の局面へ逆向きに戻す

小さな木で考えます。自分にAとBの二手があり、それぞれへ相手の返答が二つあるとします。Aの先の評価が8と2なら、相手は自分に不利な2を選ぶと考え、Aの価値を2とします。Bの先が5と4ならBの価値は4です。自分は2と4の大きい方、Bを選びます。最高の結果8ではなく、相手の最善応答後に残る4を選ぶ点が重要です。 このように、木の一番先の値を相手の層では最小、自分の層では最大として交互に戻します。どの節点が最大化側かを取り違えると結論が逆になります。評価値は通常、自分から見た有利さへ統一します。勝ちを正、負けを負、引き分けをゼロなどとし、どちらの手番でも同じ基準を使います。

3.最後まで読めないとき、評価関数で途中を測る

チェスや囲碁は最後までの手順が多く、すべての終局を計算できません。決めた深さで探索を止め、その局面を評価関数で数値化します。チェスなら駒の価値、王の安全、動ける範囲などを組み合わせます。評価関数は勝敗そのものではなく、その時点から勝ちやすいと考える代理指標です。 代理指標が悪ければ、深く探索しても望ましい手を選べません。目先の駒得を高くし過ぎると、数手後の詰みを見落とすことがあります。探索をちょうど危険な局面で切る「地平線効果」も起こります。駒の交換が落ち着くまで追加で読む静止探索などの対策があります。評価関数と停止位置は、アルゴリズム本体と同じくらい結果を左右します。

4.αβ法は、結論に影響しない枝を読まない

Mini-Max法では多くの枝を調べますが、途中で結果が確定する場合があります。自分がすでに価値5の手を見つけているとき、別の手の中で相手が価値3へ落とせる返答を持つと分かれば、その別の手を自分は選びません。相手の残り返答をすべて調べなくても、最大5を超えないことが確定します。 αは最大化側が現在までに確保できる下限、βは最小化側が現在までに押さえられる上限です。探索中にα以上を相手が許さない、またはβ以下を自分が選ばないと分かった枝を打ち切ります。省いた枝を評価していないだけで、Mini-Max法が選ぶ最終手は変わりません。近似して答えを変える方法ではなく、不要な計算を証拠付きで省く方法です。

5.有望な手を先に読むと、枝刈りが増える

αβ法の効果は、手を調べる順番に左右されます。最初に強い手を読めば、よいαや厳しいβが早く得られ、後の枝を多く切れます。逆に弱い手から調べると比較基準が緩く、ほとんど省けません。前回の探索結果、駒を取る手、専門知識、学習モデルの予測などで手を並べ替えます。 ここで学習と探索を組み合わせられます。学習モデルは有望な手や局面価値を予測し、探索は相手の返答を明示的にたどります。予測だけに任せるのでも、全候補を力任せに読むのでもありません。推定が外れても正しい枝を完全に捨てない設計なら、最終結果を保ちながら計算順を改善できます。

6.運・非公開情報・複数人では、木の意味が変わる

Mini-Max法の基本形は、二人、交互手番、完全情報、運なし、利害が反対という条件を想定します。バックギャモンのサイコロなら、相手の最小化だけでなく確率による期待値の節点が必要です。ポーカーでは相手の手札が見えず、観測した行動から可能性を推定します。三人以上では、一人の利益が他全員の損失とは限りません。 現実の交渉でも、相手の目的や情報は完全には分かりません。「相手は必ず自分を最も不利にする」と置くと、過度に防御的な結論になる場合があります。基本モデルを理解したうえで、確率、信念、協力、誤りを追加します。適用条件を言わずMini-Max法を万能な意思決定へ広げないことが重要です。

7.ゲームAIの強さは、探索だけでは決まらない

探索深さを増やすには計算資源、重複局面の再利用、手の並べ替え、評価関数が必要です。同じ局面へ別の手順で到達する場合、局面と結果を表へ保存して再利用できます。時間制限がある場合は浅い探索を終えてから一段ずつ深くする反復深化を使い、途中で時間切れになっても直前の完成結果を返します。 現代のゲームAIでは、深層学習が局面評価や有望な手の確率を学び、モンテカルロ木探索などが先を読みます。それでも中心にあるのは、候補、相手の応答、評価、計算上限です。『AIが直感で選んだ』とまとめず、学習が予測した部分と探索が検証した部分を分けて捉えます。

8.DAY 7では、二手ずつのゲーム木を計算する

自分の選択をA・B、相手の返答を各二つ用意し、終端へ自分から見た評価値を書いてください。相手の層で最小値を選び、その結果を自分の層で最大化します。次に、Aを先に調べた場合とBを先に調べた場合で、どこをαβ法により省けるかを確認します。 最後に、その評価値が何を表すかを書きます。利益だけか、失敗確率や関係維持も含むか。相手が完全合理的でない場合に結論がどう変わるかも考えます。計算手順と前提条件を一緒に説明できれば、Mini-Max法を用語ではなく推論のモデルとして使えています。

9.深さを増やしても、常に判断が改善するとは限らない

一般には先を深く読めば見落としを減らせますが、葉で使う評価関数が偏っていれば、その偏りを遠くまで計算します。時間切れで深い探索が途中のままなら、完成した浅い結果より不安定になることもあります。反復深化では、深さ一、二、三と完成結果を残し、期限内の最も深い結果を使います。 実務のシナリオ分析でも同じです。遠い将来を細かく枝分かれさせるほど、仮定の誤差が重なります。近い範囲は詳しく、遠い範囲は複数シナリオとして扱い、状況が変われば更新します。「何手先まで読んだか」だけでなく、「各層の仮定を確かめられるか」を評価します。

10.対戦モデルを、人間関係の断定へ使わない

ゲーム木は利害が対立する問題を整理できますが、相手を常に敵と置くと、協力で得られる結果を見落とします。取引では価格以外に品質、継続性、情報共有があり、双方の利益が増える案もあります。相手の最悪反応だけで決める方法は、被害の上限を知るには役立っても、通常の予測とは異なります。 最悪値、期待値、協力案を並べ、どの目的でどのモデルを使ったかを書きます。相手の意図をAIが推定した場合も事実として扱わず、観察した行動と仮説を分けます。Mini-Max法の厳密さは、現実を単純な敵対ゲームと断定する許可ではありません。

03|実例で理解する

実例で理解する

具体例で考える

小売店が期間限定商品の値下げ時期を考え、競合店も価格を変更すると仮定します。自店は「今週値下げ」「来週まで維持」の二手、競合はそれぞれに「追随値下げ」「価格維持」を選びます。終端評価には粗利益、売れ残り、顧客の価格期待を含めます。 自店が今週値下げした場合、競合追随で評価2、維持で7なら、相手が厳しい2を選ぶとします。自店が維持した場合、競合値下げで1、競合維持で5なら価値は1です。Mini-Maxでは最悪時に2が残る今週値下げを選びます。しかし、競合が必ず自店を妨害するとは限りません。 実務では競合の過去行動から各反応の確率も置き、期待値と最悪値を並べます。価格変更の法的・契約的制約も別に確認します。ゲーム木は未来を断定する予言ではなく、相手の反応を含めて選択肢と前提を見える形にする道具です。 評価表には、利益だけでなく欠品、廃棄、顧客への説明、次回購入への影響を別項目で記録します。一つの合計点にすると重みの置き方で結論が変わるため、各項目の値と採用した重みを残します。競合の返答を一つ断定せず、最悪の場合、過去頻度から見た場合、協調的な場合の三つを比較します。 また、二手先まで読む案と四手先まで読む案で結論が変わるか確認します。変わるなら、遠い局面の評価へ強く依存しています。実行前に観測できる指標を決め、売れ行きや競合価格が想定から外れた時点で木を作り直します。木の作成日、前提に使った資料、評価担当も保存し、後から「予測が外れた」のか「前提が変わった」のかを区別します。選ばなかった手の理由も残せば、次回の評価関数を見直せます。

手を動かして理解する

  1. 提供ケース「紙に描いた小さな配送経路を、状態・行動・ゴール・規則へ分解する」または自分が説明できる身近な事例を一つ選び、DAY7「ゲーム木と推論」の判断観点で整理してください。提出物には、①対象と目的、②本文の用語を使った判断、③判断の根拠、④未確認事項または限界を記します。最後に学習目標「自分と相手が交互に選ぶ問題をゲーム木で表し、Mini-Max法とαβ法が何を計算し、評価関数と探索深さが結果へどう影響するか説明できる。」を満たす説明になっているか自己確認してください。紙または端末の標準メモだけで実施でき、外部サービスへの登録や有料契約は不要です。 実在人物の個人情報、機密情報、未公開資料は使わず、架空または匿名化した情報だけを使ってください。

04|今日の理解度を確認する

今日の理解度を確認する

1 / 5
QUESTION 01

Mini-Max法が置く基本的な前提はどれですか。

QUESTION 02

自分の手Aの先が8と2、手Bの先が5と4で、相手が小さい値を選ぶときMini-Maxが選ぶ手はどれですか。

QUESTION 03

最後までゲーム木を読めない場合に評価関数を使う理由はどれですか。

QUESTION 04

αβ法について正しい説明はどれですか。

QUESTION 05

αβ法で枝刈りを増やす工夫として適切なものはどれですか。

05|今日の整理をする

今日の整理をする

この3点を持ち帰る

  • ✓ Mini-Max法は、自分の最大化と相手の最小化を交互にたどる
  • ✓ αβ法はMini-Maxと同じ結論を保ち、選ばれない枝の計算を省く
  • ✓ 評価関数・探索深さ・相手についての仮定が、結果の意味を決める

講義本文 4,062字

PRIMARY SOURCES

確認に使った一次資料・原典

本文は各資料を参照し、初学者向けに独自構成・独自表現で解説しています。
NEXT LESSONDAY 8「知識表現とエキスパートシステム」へ次のDAYに進む →