ミニマックス

マキシミン値とは、他のプレイヤーの行動を知らなくてもプレイヤーが確実に得られる最高値であり、言い換えれば、他のプレイヤーがプレイヤーの行動を知っている場合に、プレイヤーに強制的に受け取らせることができる最低値です。正式な定義は次のとおりです。^{[ 3 ]}

${\displaystyle {\underline {v_{i}}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i})}}$

どこ：

• iは対象となるプレイヤーのインデックスです。
• ${\displaystyle -i}$は、プレイヤーiを除く他のすべてのプレイヤーを表します。
• ${\displaystyle a_{i}}$これはプレイヤーiが取った行動です。
• ${\displaystyle a_{-i}}$他のすべてのプレイヤーが行った行動を示します。
• ${\displaystyle v_{i}}$はプレイヤーiの価値関数です。

プレイヤーの最大最小値の計算は、最悪のケースを想定したアプローチで行われます。プレイヤーの可能な行動ごとに、他のプレイヤーの可能な行動をすべてチェックし、最悪の行動の組み合わせ、つまりプレイヤーi に最小値を与える組み合わせを決定します。次に、この最小値が可能な限り最大になるように、プレイヤーiが取るべき行動を決定します。

例えば、2人プレイのゲームを考えてみましょう。1人目のプレイヤー（「行プレイヤー」）はT、M、Bの3つの手からいずれかを選択でき、2人目のプレイヤー（「列プレイヤー」）はLまたはRの2つの手からいずれかを選択できます。両者の手の組み合わせの結果は、利得表で表されます。

${\displaystyle {\begin{array}{c|cc}\hline &L&R\\\hline T&3,1&2,-20\\M&5,0&-10,1\\B&-100,2&4,4\\\hline \end{array}}}$

（各セル内の最初の数字は行プレイヤーの配当、2番目の数字は列プレイヤーの配当を表します。）

例として、純粋戦略のみを考慮します。各プレイヤーを順番にチェックします。

• 行のプレイヤーはTをプレイすることができ、これにより少なくとも2（Bをプレイするのはリスクがあるが、報酬につながる可能性がある）−100、Mをプレイすると、−10）。したがって：${\displaystyle {\underline {v_{row}}}=2}$。
• 列プレイヤーはLをプレイして少なくとも0 ( Rをプレイすると、${\displaystyle -20}$したがって：${\displaystyle {\underline {v_{col}}}=0}$。

両プレイヤーがそれぞれの最大最小戦略を実行する場合${\displaystyle (T,L)}$ペイオフベクトルは${\displaystyle (3,1)}$。

プレイヤーのミニマックス値とは、他のプレイヤーがそのプレイヤーの行動を知らない状態で、そのプレイヤーに強制的に受け取らせることができる最小値です。言い換えれば、他のプレイヤーの行動を知っている場合に、そのプレイヤーが確実に得られる最大の値です。正式な定義は次のとおりです。^{[ 3 ]}

${\displaystyle {\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}}$

定義は最大最小値の定義と非常によく似ています。最大値演算子と最小値演算子の順序が逆になっているだけです。上記の例では次のようになります。

• 行のプレイヤーは、最大で4の値を取得できます(他のプレイヤーがRをプレイした場合) または5（相手プレイヤーがLをプレイした場合）、したがって：${\displaystyle {\overline {v_{row}}}=4\ .}$
• 列プレイヤーは最大値1を取得できます（他のプレイヤーがTをプレイした場合）。1（Mの場合）または4（Bの場合）。したがって：${\displaystyle {\overline {v_{col}}}=1\ .}$

すべてのプレイヤーiについて、最大最小値は最大で最小最大値である。

${\displaystyle {\underline {v_{i}}}\leq {\overline {v_{i}}}}$

直感的に言えば、マキシミン戦略では最大化が最小化の後に行われるため、プレイヤーiは他のプレイヤーが何をするかを知る前に自分の価値を最大化しようとします。一方、ミニマックス戦略では最大化が最小化の前に行われるため、プレイヤーiは他のプレイヤーが何をしたかを知っている状態で自分の価値を最大化できるので、はるかに有利な立場にあります。

表記を理解するもう1つの方法は、右から左に読むことです。

${\displaystyle {\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}=\min _{a_{-i}}{\Big (}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}{\Big )}}$

最初の結果セット${\displaystyle \ v_{i}(a_{i},a_{-i})\ }$両方に依存する${\displaystyle \ {a_{i}}\ }$そして${\displaystyle \ {a_{-i}}\ .}$まず私たちは疎外する${\displaystyle {a_{i}}}$から${\displaystyle v_{i}(a_{i},a_{-i})}$最大化することによって${\displaystyle \ {a_{i}}\ }$（あらゆる可能な値に対して）${\displaystyle {a_{-i}}}$一連の限界的な結果を生み出す${\displaystyle \ v'_{i}(a_{-i})\,,}$これは、${\displaystyle \ {a_{-i}}\ .}$次に最小化します${\displaystyle \ {a_{-i}}\ }$これらの結果に関して。（最大最小値の場合とは逆。）

常にそうであるように、${\displaystyle \ {\underline {v_{row}}}\leq {\overline {v_{row}}}\ }$そして${\displaystyle \ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,}$両プレイヤーがミニマックス戦略を実行した結果得られる利得ベクトル、${\displaystyle \ (2,-20)\ }$の場合${\displaystyle \ (T,R)\ }$または${\displaystyle (-10,1)}$の場合${\displaystyle \ (M,R)\,,}$同様に、報酬ベクトルに対して順位付けすることはできない${\displaystyle \ (3,1)\ }$両プレイヤーがそれぞれ最大最小戦略を実行した結果である。

2人ゼロサムゲームでは、ミニマックス解はナッシュ均衡と同じである。

ゼロサムゲームの文脈では、ミニマックス定理は以下と同等である。^{[ 4 ]}

有限個の戦略を持つすべての2人ゼロサムゲームにおいて、各プレイヤーに対して値Vと混合戦略が存在し、

（a）プレイヤー2の戦略を考慮すると、プレイヤー1 にとって可能な最良の利得はVであり、 

（b）プレイヤー 1の戦略を考慮すると、プレイヤー2にとって可能な最良の利得は−Vである。

言い換えれば、プレイヤー1の戦略は、プレイヤー2の戦略に関係なく、プレイヤー1にV の利得を保証し、同様にプレイヤー2は−Vの利得を保証できます。ミニマックスという名前は、各プレイヤーが相手プレイヤーの最大利得を最小化することに由来します。このゲームはゼロサムゲームであるため、各プレイヤーは自身の最大損失も最小化します（つまり、自身の最小利得を最大化します）。値のないゲームの例も参照してください。  

AとBが同時に行動するゼロサムゲームの次の例は、マキシミン解を示しています。各プレイヤーが3つの選択肢を持ち、表に表示されているAの利得行列（「プレイヤーAの利得行列」）を考えます。Bの利得行列は、符号が反転した同じ行列であると仮定します（つまり、選択肢がA1とB1の場合、BはAに3を支払います）。すると、最悪の結果が1を支払うことになるため、 Aのマキシミン選択はA2になります。一方、 Bの単純なマキシミン選択は、最悪の結果が支払いなしとなるため、B2になります。しかし、この解は安定していません。BがAがA2を選択すると信じている場合、 Bは1を得るためにB1を選択します。次に、AがBがB1を選択すると信じている場合、 Aは3を得るためにA1を選択します。そして、BはB2を選択します。最終的に、両方のプレイヤーが選択の難しさに気づきます。したがって、より安定した戦略が必要です。     

いくつかの選択肢は他の選択肢によって支配されるため、排除することができます。AはA3を選択しません。なぜなら、Bが何を選択しても、A1またはA2のどちらかがより良い結果を生み出すからです。BはB3を選択しません。なぜなら、Aが何を選択しても、B1とB2の組み合わせがより良い結果を生み出すからです。

プレイヤーA は、確率1/6で A1 を、確率 5/6 で A2 を選択することで、期待支払額が1/3を超えることを回避できます。Bが B1 を 選択した場合、A の期待利得は 3 × 1/6 − 1 × 5/6 = − + 1/3 となり、B が B2 を選択した場合は−2 × 1/6 + 0 × 5/6 = − + 1/3 となります。同様に、Bは、確率 1/3 で B1を、確率2/3 で B2を選択するという ランダム化戦略 を 用いる ことで、 Aが何を選択し て も、少なくとも1/3の期待利得を確保できます 。 これらの混合 ミニ マックス戦略はこれ以上改善できず、安定して い ます。

ゲーム理論では、マキシミンとミニマックスはしばしば区別される。ミニマックスは、ゼロサムゲームにおいて、相手の最大利得を最小化することを意味する。ゼロサムゲームでは、これは自身の最大損失を最小化し、自身の最小利得を最大化することと同義である。

「マキシミン」とは、非ゼロサムゲームにおいて、自身の最小利得を最大化する戦略を表すために一般的に用いられる用語である。非ゼロサムゲームにおいては、これは一般的に相手の最大利得を最小化することとは異なり、またナッシュ均衡戦略とも異なる。

ミニマックス値は、繰り返しゲームの理論において非常に重要である。この理論における中心的な定理の一つであるフォーク定理は、ミニマックス値に基づいている。

ミニマックスアルゴリズム^{[ 5 ]}は、 n人ゲーム（通常は2人ゲーム）で次の手を選択するための再帰アルゴリズムです。ゲームの各局面または状態には値が関連付けられています。この値は局面評価関数によって計算され、プレイヤーがその局面に到達することがどれほど良いかを示します。プレイヤーは、相手の可能な次の手によって生じる局面の最小値を最大化する手を選択します。の番になると、Aはそれぞれの合法的な動きに値を与える。

考えられる割り当て方法の一つは、 Aの特定の勝利を+1、Bの勝利を-1とすることです。これは、ジョン・H・コンウェイによって開発された組み合わせゲーム理論につながります。別の方法としては、ある手の結果がAの即時勝利であれば正の無限大を、Bの即時勝利であれば負の無限大を割り当てるというルールを用いる方法があります。その他の手の結果がAに与える値は、Bのそれぞれの手の結果が与える値の最大値となります。's possible replies. For this reason, A is called the maximizing player and B is called the minimizing player, hence the name minimax algorithm. The above algorithm will assign a value of positive or negative infinity to any position since the value of every position will be the value of some final winning or losing position. Often this is generally only possible at the very end of complicated games such as chess or go, since it is not computationally feasible to look ahead as far as the completion of the game, except towards the end, and instead, positions are given finite values as estimates of the degree of belief that they will lead to a win for one player or another.

This can be extended if we can supply a heuristic evaluation function which gives values to non-final game states without considering all possible following complete sequences. We can then limit the minimax algorithm to look only at a certain number of moves ahead. This number is called the "look-ahead", measured in "plies". For example, the chess computer Deep Blue (the first one to beat a reigning world champion, Garry Kasparov at that time) looked ahead at least 12 plies, then applied a heuristic evaluation function.^[6]

The algorithm can be thought of as exploring the nodes of a game tree. The effective branching factor of the tree is the average number of children of each node (i.e., the average number of legal moves in a position). The number of nodes to be explored usually increases exponentially with the number of plies (it is less than exponential if evaluating forced moves or repeated positions). The number of nodes to be explored for the analysis of a game is therefore approximately the branching factor raised to the power of the number of plies. It is therefore impractical to completely analyze games such as chess using the minimax algorithm.

The performance of the naïve minimax algorithm may be improved dramatically, without affecting the result, by the use of alpha–beta pruning. Other heuristic pruning methods can also be used, but not all of them are guaranteed to give the same result as the unpruned search.

A naïve minimax algorithm may be trivially modified to additionally return an entire Principal Variation along with a minimax score.

The pseudocode for the depth-limited minimax algorithm is given below.

関数minimax(node, depth, maximizingPlayer)は、 depth = 0またはnode が終端ノードの場合、 node のヒューリスティック値 を返します。maximizingPlayerの場合、 値 := −∞ 各子ノードに対して value := max(value, minimax(child, depth − 1, FALSE)) それ以外の場合 は値 を返す（*プレイヤーを最小化する*） value := +∞ 各子ノードに対して value := min(value, minimax(child, depth − 1, TRUE)) 戻り値

(* 初回呼び出し *) minimax(origin, depth, TRUE)

ミニマックス関数は、リーフノード（終端ノードおよび最大探索深度のノード）に対してヒューリスティック値を返します。非リーフノードは、子孫リーフノードから値を継承します。ヒューリスティック値は、最大化プレイヤーにとってのノードの好ましさを測定するスコアです。したがって、最大化プレイヤーにとって勝利などの好ましい結果をもたらすノードは、最小化プレイヤーにとってより好ましいノードよりも高いスコアを持ちます。終端（ゲーム終了）リーフノードのヒューリスティック値は、最大化プレイヤーにとっての勝利、敗北、または引き分けに対応するスコアです。最大探索深度の非終端リーフノードについては、評価関数がノードのヒューリスティック値を推定します。この推定の精度と探索深度によって、最終的なミニマックス結果の精度と正確さが決まります。

ミニマックス法は、コード内で2人のプレイヤー（最大化プレイヤーと最小化プレイヤー）を別々に扱います。${\displaystyle \ \max(a,b)=-\min(-a,-b)\ ,}$ミニマックス法は、多くの場合、ネガマックス法に簡略化できる。

プレイ中のゲームでは、各プレイヤーが各ターンに最大2つの手しか取れないと仮定します。アルゴリズムは右側のツリーを生成します。ここで、円はアルゴリズムを実行しているプレイヤー（最大化プレイヤー）の手を表し、四角は対戦相手（最小化プレイヤー）の手を表します。前述のように、計算リソースの制限により、ツリーは4手先までしか読み取れ ません。

アルゴリズムは、ヒューリスティック評価関数を使用して各リーフノードを評価し、図に示す値を取得します。最大化プレイヤーが勝利する動きには正の無限大が割り当てられ、最小化プレイヤーが勝利する動きには負の無限大が割り当てられます。レベル 3 では、アルゴリズムは各ノードについて、子ノードの値の最小値を選択し、それを同じノードに割り当てます (たとえば、左のノードは「10」と「+∞」の間の最小値を選択し、値「10」を自身に割り当てます)。次のステップであるレベル 2 では、各ノードについて、子ノードの値の最大値を選択します。ここでも、値は各親ノードに割り当てられます。アルゴリズムは、ルートノードに到達するまで、子ノードの最大値と最小値を交互に評価し続け、ルート ノードで最大の値を持つ動き (図では青い矢印で示されています) を選択します。これが、プレイヤーが最大損失を最小化するために行うべき動きです。 

ミニマックス理論は、他のプレイヤーが存在しないものの、決定の結果が未知の事実に依存する意思決定にも拡張されています。例えば、鉱物探査を行うという決定にはコストがかかり、鉱物が存在しない場合は無駄になりますが、存在すれば大きな利益が得られます。一つのアプローチは、これを自然とのゲームとして捉え（「自然による動き」を参照）、マーフィーの法則や抵抗主義と同様の考え方を用いて、二人のゼロサムゲームと同じ手法で、期待される最大損失を最小化するアプローチを取ることです。

さらに、偶然性（例えばサイコロ）が要素となる2人対戦ゲーム向けに、期待値ミニマックス木が開発されている。

古典的な統計的決定理論では、推定量があります${\displaystyle \ \delta \ }$パラメータを推定するために使用される${\displaystyle \ \theta \in \Theta \ .}$また、リスク関数も仮定します。${\displaystyle \ R(\theta ,\delta )\ .}$通常は損失関数の積分として指定される。この枠組みでは、${\displaystyle \ {\tilde {\delta }}\ }$を満たす場合、ミニマックスと呼ばれます。

${\displaystyle \sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\ \sup _{\theta }\ R(\theta ,\delta )\ .}$

意思決定理論の枠組みにおける代替基準としては、事前分布が存在する場合のベイズ推定量が挙げられる。${\displaystyle \Pi \ .}$推定器がベイズ的であるのは、平均リスクを最小化する場合である。

${\displaystyle \int _{\Theta }R(\theta ,\delta )\ \operatorname {d} \Pi (\theta )\ .}$

ミニマックス意思決定の重要な特徴は、非確率的であることです。期待値や期待効用を用いた意思決定とは異なり、様々な結果の確率について仮定を置かず、起こりうる結果をシナリオ分析するだけです。そのため、他の意思決定手法とは異なり、仮定の変化に対して頑健です。この非確率的アプローチには、ミニマックス後悔理論や情報ギャップ意思決定理論など、様々な拡張が存在します。

さらに、ミニマックス法は順序尺度（結果を比較して順位付けする）のみを必要とし、間隔尺度（結果に「どれだけ良いか悪いか」が含まれる）は必要とせず、モデル化された結果のみを使用して順序尺度データを返します。ミニマックス分析の結論は、「最悪のケースは（結果）であり、これは他のどの戦略よりも悪くないため、この戦略はミニマックスである」となります。これに対し、期待値分析の結論は「この戦略はℰ（X）= nをもたらす」という形式です。したがって、ミニマックス法は順序尺度データに適用でき、より透明性が高いと言えます。