すべてのサブセクション、戦略がミニマックス アルゴリズムで最適であることを証明するにはどうすればよいでしょうか?

Question

質問はタイトルの通りです。

ミニマックス アルゴリズムが 2 人のゲームでこれを行うことはわかっています (A の利益を最大化したいと仮定します)。A の番の場合は、A の利益を最大化するため、子の値の最大値を取得します。B の番の場合は、B の利益を最小化するため、子の値の最小値を取得します。

ただし、上記のロジックは、すべての下位問題、戦略がミニマックス アルゴリズムで最適であることを証明するとは思いません。私が提案した質問に対するヒントや解決策はありますか?上記のロジックが当てはまる場合、それについて詳しく説明してもらえますか?

Answer 1

ミニマックスの主張は次のとおりです。他のプレイヤーも同じ戦略を使用している場合、ミニマックスは最適な戦略を提供します。

ベース:ゲーム ツリーの葉の場合、戦略は 1 つだけあり、ミニマックスが選択するのは明らかであり、それが唯一のものであるため、それが最適です。
仮説:ミニマックスは深みのあるゲームに最適な戦略を選択します d.
証拠:

奥深いゲームを見てみましょう d+1. 。明らかに 2 つのシナリオが考えられます。

1. 出番です - これは max 段階。この場合、私たちが実行できるすべての可能な動きのうち、minimax はそのような各戦略の最小-最大値を再帰的に評価し、この手を選択した「サブゲーム」に最適な結果を与えます。これらのサブゲームはそれぞれ奥が深いです d, 、帰納法仮説から、それは最適です。
   これは最大フェーズであるため、最小-最大アルゴリズムは最大値を選択します。これが私たちにとって最適なソリューションです。
2. 相手の番です - これは min 段階。上記のロジックと同様に、ミニマックスは対戦相手が実行できるすべての可能な動きにケースを分割し、その結果を評価します。帰納仮説から、評価は最適であり、その中から最小限のものを選択します。これが対戦相手が選択したであろうものであり、彼にとって最適な戦略です（そして、対戦相手が道の各ステップで最適な選択をすると仮定します）。相手は最小の評価を選択し、それが私たちの利益を最小化し、結果として彼の利益を最大化します。

QED

これに基づいて、ミニマックスの別の主張を結論付けることができます。つまり、戦略によって返される値は、(相手の戦略に関係なく) 実際に得られる値を下回ることはありません。これは、上記と非常によく似た帰納法によって証明できます。

ガイドライン:

ベース:戦略は 1 つだけで、「木」が実際には葉である場合にそれを返します。
請求:奥行きのあるゲームに対してミニマックスによって返される値 d は、このレベルからプレイされるすべてのゲームの下限であり、ミニマックスに従って選択し、対戦相手に対する制限はありません。
証拠:

奥深いゲームを見てみよう d+1.

1. それがあなたの番なら、あなたはここに選択肢があるので、あなたはすべての葉から最大値を選びました。葉のそれぞれは、少なくともある程度の価値を保証します（誘導仮説）。
2. 相手の番の場合、あなたは選択をコントロールできません。彼が何らかの手を選択することだけは確信できますが、どれになるかはわかりません。ただし、あらゆる可能な動きに対して、深みのある新しい「サブゲーム」が得られます。 d, 、ここで帰納法仮説が成り立ちます。対戦相手はこれらの動きのいずれかを選択できるため、この動きの後、少なくとも の値を持つことが保証できます。 min{game after opponent move}, 、これはまさに最小フェーズが返すものです。

QED.

Answer 2

MiniMAXはプレーヤックの利益を最大にしようとしないため、最小値の利益を最大化することを証明することはできません。

が最小にすることは、損失を最小にすることです。つまり、その決定は保守的であり、最悪のシナリオ（他のプレイヤーによる最適なプレイ）を想定しています。それを証明してみてください。あなたはそれをはるかに簡単に見つけるでしょう。