Wie kann man beweisen, dass in jedem Unterabschnitt die Strategie im Minimax-Algorithmus am optimalsten ist?

Question

Die Frage ist, wie der Titel schon sagt.

Ich weiß, dass der Minimax-Algorithmus dies für ein 2-Personen-Spiel tut (angenommen, wir wollen den Gewinn von A maximieren):wenn A an der Reihe ist, nehmen wir das Maximum der untergeordneten Werte, weil wir den Gewinn von A maximieren, und wenn B an der Reihe ist, nehmen wir das Minimum der untergeordneten Werte, weil wir den Gewinn von B minimieren wollen.

Ich glaube jedoch nicht, dass die obige Logik beweist, dass jedes Teilproblem, die Strategie, im Minimax-Algorithmus die optimalste ist.Irgendwelche Hinweise oder Lösungen zu der von mir vorgeschlagenen Frage?Wenn die obige Logik dies tut, könnten Sie sie dann näher erläutern?

Answer 1

Der Anspruch, den minimax hat, ist:Minimax gibt die optimale Strategie, wenn der andere Spieler auch die gleiche Strategie verwendet.

Basis:Für ein Blatt im Spielbaum gibt es nur eine Strategie, die minimax offensichtlich wählt, und sie ist optimal - da es die einzige ist.
Hypothese:minimax wählt optimale Strategie für ein Tiefenspiel d.
Beweis:

Schauen wir uns ein Spiel mit Tiefe an d+1.Es gibt offensichtlich 2 mögliche Szenarien:

1. Es ist an der Reihe - das ist max Phase.In diesem Fall bewertet minimax aus allen möglichen Zügen, die wir ausführen können, rekursiv den Min-Max-Wert für jede dieser Strategien und liefert uns das optimale Ergebnis für ein 'Teilspiel', in dem wir diesen Zug gewählt haben.Jedes dieser Teilspiele ist von Tiefe d, und aus der Induktionshypothese ist es optimal.
   Da dies die maximale Phase ist, wählt der Min-Max-Algorithmus das Maximum, das für uns die optimale Lösung ist.
2. Der Gegner ist an der Reihe - das ist min Phase.Ähnlich wie bei der obigen Logik teilt Minimax den Fall auf alle möglichen Züge auf, die der Gegner ausführen kann, und bewertet deren Ergebnis.Aus der Induktionshypothese sind Bewertungen optimal, und wir wählen das Minimum aus ihnen - was der Gegner gewählt hätte und die optimale Strategie für ihn ist (und nehmen an, dass der Gegner für jeden Schritt des Weges optimal wählt) - also Der Gegner wählt die minimale Bewertung, die unseren Gewinn minimiert und damit seinen Gewinn maximiert.

QED

Darauf basierend können Sie einen weiteren Anspruch von minimax schließen - der von der Strategie zurückgegebene Wert ist nicht geringer als das, was Sie tatsächlich erhalten (unabhängig von der Strategie des Gegners).Dies kann durch Induktion sehr ähnlich wie oben nachgewiesen werden.

Richtlinie:

Basis:Nur eine Strategie, und Sie geben sie zurück, wenn der 'Baum' tatsächlich ein Blatt ist.
Anspruch:von minimax zurückgegebener Wert für das Tiefenspiel d ist eine Untergrenze für alle Spiele, die ab diesem Level gespielt werden, wobei Sie nach Minimax gewählt haben, und keine Einschränkung für den Gegner.
Beweis:

Schauen wir uns das Spiel der Tiefe an d+1.

1. Wenn Sie an der Reihe sind, haben Sie das Maximum aus allen Blättern gewählt, da Sie haben Sie hier die Wahl.Jedes Blatt garantiert Ihnen (Induktion hypothese) mindestens einen Wert und durch Auswahl des Maximums von ihnen - sie garantieren auch den gewählten Wert.
2. Wenn der Gegner an der Reihe ist, haben Sie keine Kontrolle über die Wahl.Sie können nur sicher sein, dass er sich für einen Zug entscheiden wird, keine Ahnung, welchen.Für alle möglichen Züge erhalten Sie jedoch ein neues 'Teilspiel' mit Tiefe d, wo die Induktionshypothese gilt.Der Gegner kann einen dieser Züge wählen, sodass Sie garantieren können, dass Sie nach diesem Zug einen Wert von mindestens haben min{game after opponent move}, was genau das ist, was die Min-Phase zurückgibt.

QED.

Answer 2

Sie können nicht nachweisen, dass Minimax den Gewinn des Spielers maximiert, da Minimax nicht versucht, den Gewinn des Spielers zu maximieren.

Welcher Minimax ist auf minimieren der mögliche verluste ;Das heißt, seine Entscheidungen sind konservativ und nehmen das schlechteste Szenario an (optimales Spiel vom anderen Spieler).Versuchen Sie, diese einzuweisen;Sie finden es viel einfacher.