ミニマックス法（Minimax Algorithm）

Minimax Algorithm

探索・推論 重要度：高

概要

ミニマックス法（Minimax Algorithm）とは、二人零和有限確定完全情報ゲームにおいて、自分の利得を最大化（maximize）し、相手の利得を最小化（minimize）する最適戦略を求める探索アルゴリズムです。チェス、将棋、囲碁、オセロなどのボードゲームAIで広く使用されてきた、ゲーム理論に基づく基本的な手法です。

ミニマックス法では、ゲームの局面を木構造（ゲーム木）として表現し、自分の手番の層（MAX層）では評価値が最大となる手を選び、相手の手番の層（MIN層）では評価値が最小となる手を選ぶことで、双方が最善を尽くした場合の結果を予測します。

詳細解説

ゲーム木の構造

ミニマックス法の基盤となるゲーム木は、以下の要素で構成されます。

  • ルートノード：現在のゲーム局面（自分が次に打つ状態）
  • MAX層：自分の手番。評価値が最大の手を選択する
  • MIN層：相手の手番。評価値が最小の手を選択する（相手にとって最善）
  • リーフノード：ゲームの終了状態、または探索の打ち切り深さに達した局面
  • 評価関数：リーフノードの局面を数値で評価する関数。自分に有利なら大きい値、不利なら小さい値を返す

ミニマックス法のアルゴリズム

ミニマックス法は以下の手順で動作します。

  1. ゲーム木を末端（リーフノード）まで展開する
  2. リーフノードに評価関数を適用して評価値を算出する
  3. MIN層のノードでは、子ノードの評価値の最小値を選択する
  4. MAX層のノードでは、子ノードの評価値の最大値を選択する
  5. ルートノードまで評価値を伝搬させ、最大値を持つ子ノードに対応する手を選択する

計算量の問題

ミニマックス法の計算量は、ゲーム木のサイズに依存します。分岐数をb、探索の深さをdとすると、計算量はO(b^d)となります。

ゲーム分岐数（概算）ゲーム木の規模
三目並べ約4約9!（362,880）
オセロ約10約10^58
チェス約35約10^120
将棋約80約10^226
囲碁約250約10^360

チェスや将棋、囲碁のような複雑なゲームでは、ゲーム木全体を探索することは計算量的に不可能です。そのため、探索の深さを制限して評価関数で局面を近似評価したり、αβ法などの枝刈り手法を組み合わせたりする工夫が必要となります。

評価関数の役割

実際のゲームAIでは、ゲーム木を末端まで展開できないため、途中の局面で探索を打ち切り、評価関数によって局面の有利・不利を数値化します。評価関数の精度がゲームAIの強さを大きく左右するため、駒の価値、配置の有利さ、制御している領域の広さなど、ゲームの専門知識を組み込んだ高度な評価関数が設計されます。

歴史・背景

ミニマックス法の理論的基盤は、1928年にジョン・フォン・ノイマンが発表したミニマックス定理に遡ります。フォン・ノイマンは、二人零和ゲームにおいて最適戦略が存在することを数学的に証明しました。

1950年代には、クロード・シャノンがチェスプログラムの設計についての論文を発表し、ゲーム木探索にミニマックス法を適用する考え方を示しました。シャノンは、探索の深さを制限して評価関数を使用するアプローチ（Type-A戦略）と、有望な手のみを深く探索するアプローチ（Type-B戦略）を提案しました。

その後、1997年にIBMのディープブルーがチェス世界チャンピオンのガルリ・カスパロフに勝利した際にも、ミニマックス法とαβ枝刈りを基盤とした探索が用いられていました。このように、ミニマックス法はゲームAIの発展において中心的な役割を果たしてきた手法です。

具体的な事例

三目並べ（Tic-Tac-Toe）

三目並べは状態空間が小さいため、ミニマックス法でゲーム木を完全に探索できます。最適にプレイすると必ず引き分けになることが証明されており、ミニマックス法の学習用として最適な題材です。

チェスAI「ディープブルー」

1997年にチェス世界チャンピオンを破ったIBMのディープブルーは、ミニマックス法をベースとした探索エンジンを搭載していました。毎秒2億局面を評価する専用ハードウェアと、グランドマスターの知識を組み込んだ評価関数を組み合わせることで、深い探索を実現しました。

オセロ・将棋プログラム

オセロや将棋のAIプログラムでも、ミニマックス法（とその改良版であるαβ法）は長年にわたって中核的な技術として使用されてきました。近年はディープラーニングとの組み合わせ（例：AlphaZero）が主流になりつつありますが、ミニマックス法の考え方は依然としてゲームAIの基本です。

G検定での出題ポイント

試験対策のポイント ミニマックス法はG検定で頻出のテーマです。以下の点を押さえましょう。
  • MAX層（自分の手番で最大値を選ぶ）とMIN層（相手の手番で最小値を選ぶ）の違いを正確に理解する
  • ゲーム木における評価値の伝搬の仕組みを図で説明できるようにする
  • 計算量がO(b^d)であり、複雑なゲームでは全探索が不可能であることを理解する
  • 評価関数の役割（局面を数値で評価する）を理解する
  • αβ法がミニマックス法の改良であることを関連づけて理解する
  • 二人零和有限確定完全情報ゲームという前提条件を押さえる