ミニマックス（Minimax、時にMinmax、MM、鞍点とも呼ばれる）は、人工知能、決定理論、組合せゲーム理論、統計学、哲学において用いられる決定規則である。これは、最悪のシナリオ（最大損失）における潜在的な損失を最小化することを目的とする。利得を扱う場合、これは「マキシミン」と呼ばれ、最小利得を最大化することを指す。元々は複数プレイヤーのゼロサムゲーム理論のために定式化され、プレイヤーが交互に手を打つ場合と同時に手を打つ場合の両方を扱うが、より複雑なゲームや、不確実性の下での一般的な意思決定にも拡張されている。
この概念は、一方のプレイヤーの利得が他方の損失となる敵対的設定において中心的な役割を果たす。そのような文脈では、ミニマックスは保守的な戦略を提供する。すなわち、相手は常に自分にとって最悪の行動を選ぶと仮定し、保証された利得を最大化する手を選択する。この原理は、機械学習や深層学習における多くのアルゴリズム、特に生成モデルの訓練や堅牢なシステムの設計の基盤となっている。
ゲーム理論の基礎
ゲーム理論において、マキシミン値とは、他のプレイヤーの行動を知らずにプレイヤーが確実に得られる最高の値であり、同義的には、他のプレイヤーがプレイヤーの行動を知っている場合に、そのプレイヤーに受け取らせることができる最低の値である。形式的な定義は、v_i_underline = max_{a_i} min_{a_{-i}} v_i(a_i, a_{-i}) であり、ここで i はプレイヤーのインデックス、a_i はプレイヤー i の行動、a_{-i} は他の全プレイヤーの行動、v_i はプレイヤー i の利得関数である。
マキシミン値の計算は最悪ケースのアプローチを用いる。すなわち、プレイヤーの各可能な行動について、他の全員の可能な行動を調べ、最悪の組み合わせ（最小値を与えるもの）を決定する。そして、この最小値が可能な限り高くなるような行動を選択する。例えば、行プレイヤーが T、M、B を選択でき、列プレイヤーが L または R を選択できる2人ゲームを考え、利得が表に示されているとする。行プレイヤーは T をプレイすることで少なくとも2の利得を保証できる（B は −100 のリスクがあり、M は −10 を生じ得る）ため、v_row_underline = 2 となる。列プレイヤーは L をプレイすることで少なくとも0を確保できる（R は −20 のリスクがある）ため、v_col_underline = 0 となる。両者がマキシミン戦略（T、L）をプレイする場合、利得ベクトルは (3, 1) となる。
プレイヤーのミニマックス値とは、他のプレイヤーがプレイヤーの行動を知らずに、そのプレイヤーに受け取らせることができる最小の値であり、同義的には、他のプレイヤーの行動を知っている場合にプレイヤーが確実に得られる最大の値である。その形式的定義は、v_i_overline = min_{a_{-i}} max_{a_i} v_i(a_i, a_{-i}) である。ゼロサムゲームでは、各プレイヤーについてミニマックス値はマキシミン値と等しくなり、ミニマックス定理へとつながる。
ミニマックス定理とゼロサムゲーム
1928年にジョン・フォン・ノイマンによって証明されたミニマックス定理は、有限で2人のプレイヤーからなるゼロサムゲームにおいて、混合戦略を用いる場合、マキシミン値がミニマックス値と等しくなることを述べている。この定理は均衡分析の基礎を提供する。そのようなゲームでは、ゲームの価値は、両プレイヤーが最適にプレイした場合の期待利得である。この定理は、プレイヤーが少なくともこの値を保証でき、相手がこの値以下に抑えることができることを保証する。
同時手ゲームでは、この概念は混合戦略に拡張され、プレイヤーは純粋な行動に対してランダム化する。ミニマックス定理は、混合戦略における鞍点の存在を保証する。鞍点とは、どちらのプレイヤーも一方的に逸脱することで利得を改善できない戦略の組である。この結果は、敵対的例が同様の最悪ケース原理を用いて分析されるニューラルネットワークの訓練において基礎的である。
人工知能への応用
AIにおいて、ミニマックスはゲームや敵対的シナリオにおける意思決定に広く用いられている。典型的な例は、チェス、チェッカー、三目並べなどの2人ターン制ゲームのためのミニマックスアルゴリズムである。このアルゴリズムは、相手が最適にプレイすると仮定して、ゲーム木を再帰的に評価する。各ノードで、プレイヤーは自分の最小利得を最大化する手を選択し、相手はプレイヤーの最大利得を最小化する手を選択する。これはしばしばアルファ・ベータ枝刈りと組み合わせて計算複雑性を削減する。
大規模言語モデルやトランスフォーマーアーキテクチャでは、ミニマックス原理は敵対的訓練に現れ、モデルは最悪ケースの摂動に対して堅牢になるよう訓練される。例えば、生成的敵対ネットワーク（GAN）はミニマックス目的関数を用いる。生成器は、識別器が本物と偽物を区別する能力を最小化しようとし、識別器はその精度を最大化しようとする。この敵対的プロセスは、深層学習におけるミニマックスの直接的な応用である。
拡張と変種
ミニマックスは、バックギャモンのような偶然性を含むゲーム（期待ミニマックスを用いる）や、不完全情報ゲーム（反実仮想後悔最小化などの技法を用いる）を含む、より複雑なゲームに拡張されている。強化学習では、ミニマックスはロバスト制御やマルチエージェント設定で用いられ、エージェントは最悪ケースの相手行動を考慮しなければならない。この概念は最適化や統計学にも現れ、ミニマックス推定量は最大リスクを最小化する。
コンピュータチェスや他のゲームプレイAIでは、アルファ・ベータ枝刈りを用いたミニマックスは依然として中核的な技法であるが、OpenAIやGoogle DeepMindのような現代のシステムは、ミニマックス的な目的関数を組み込んだ機械学習アプローチを用いることが多い。この原理は、不確実性の下での行動選択において、意思決定者が最悪ケースの損失を最小化する選択肢を選ぶ決定理論にも関連する。
歴史的背景と関連概念
ミニマックス規則はゲーム理論と決定理論にルーツを持ち、ジョン・フォン・ノイマンやオスカー・モルゲンシュテルンなどの数学者による貢献がある。これは、最適化における鞍点の概念や、非ゼロサムゲームにおけるナッシュ均衡と密接に関連する。哲学では、ミニマックスは合理性やリスク回避の議論に用いられる。
現代のAIでは、ミニマックスはしばしばベイズ決定理論と対比される。ベイズ決定理論は最悪ケースの仮定ではなく事前確率を用いる。ミニマックスは保守的である一方、ベイズ法はより柔軟であり得る。これらの選択は、確率的情報の利用可能性に依存する。AI研究では、ミニマックスは、特に敵対的環境における意思決定アルゴリズムを評価するためのベンチマークとして残っている。
関連項目
- アルファ・ベータ枝刈り
- ゲーム理論
- ゼロサムゲーム
- 敵対的機械学習