Der Minimax ist in der Spieltheorie eine Methode, die darauf abzielt, den erwarteten Verlust zu minimieren. Dabei geht der Spieler davon aus, dass die Entscheidung seines Gegners ungünstig ausfällt. Das heißt, das schlimmste Szenario wird vor der Bewegung des Gegners erwartet.
Anders ausgedrückt, die Minimax-Methode besteht darin, die beste Entscheidung zu treffen, vorausgesetzt, dass der andere Spieler das Worst-Case-Szenario für Sie wählt.
Wir müssen berücksichtigen, dass diese Methode in einem Zweipersonenspiel (zwei Spieler) anwendbar ist und dass es sich nicht um ein kooperatives, sondern um ein Nullsummenspiel handelt. Das bedeutet, dass der Gewinn des einen Spielers vom anderen verloren wird und umgekehrt. Folglich wird jeder Agent daran interessiert sein, seinen eigenen Nutzen zu maximieren, auch wenn dies dem anderen schadet.
An dieser Stelle muss auch daran erinnert werden, dass die Spieltheorie ein Zweig der Mathematik und Ökonomie ist, der sich mit Entscheidungen befasst, die die Situation eines Individuums optimieren, wenn Kosten und Nutzen nicht im Voraus festgelegt sind, sondern von den Entscheidungen anderer abhängen.
Minimax-Algorithmus in einem Entscheidungsbaum
Wir sehen, wie die Minimax-Methode in einem Entscheidungsbaum mit mehreren Knoten angewendet wird. Das Spiel beginnt unten und endet mit einem Ergebnis auf der obersten Ebene.
An der Basis des Baumes macht der Gegner den ersten Zug, daher wird das schlechteste Ergebnis erwartet. Auf der zweiten Ebene liegt es dann an Spieler x, der versucht, seinen Gewinn unter Berücksichtigung der zuvor vom Gegner getroffenen Entscheidung zu maximieren.
Auf der dritten Ebene ist wieder der Gegner an der Reihe und so weiter. Wir zeigen ein Beispiel unten.
Beispiel für einen Minimax-Algorithmus
Im folgenden Entscheidungsbaum zeigen wir die Ergebnisse, die Spieler x zu jedem Zeitpunkt des Spiels erzielt hat. An der Basis, auf der ersten Ebene, trifft der Gegner die Entscheidung. Aus diesem Grund werden die Szenarien angegeben, in denen der Spieler -10 verlieren oder 5 gewinnen kann.
Auf der zweiten Ebene liegt es an Spieler x, also wird er seinen Gewinn maximieren. Wenn Sie 10 verlieren oder 1 gewinnen, gewinnen Sie 1. Ebenso gewinnen Sie zwischen 5 oder 7 Gewinnen 7.
Dann ist der Gegner wieder an der Reihe, also werden die Szenarien angegeben, in denen Spieler x das schlechteste Ergebnis hat, -3 und 4, je nach Fall. Schließlich trifft Spieler x zwischen dem Verlust von 3 oder dem Gewinn von 4 die Entscheidung, die letzteres zulässt.
Wir müssen berücksichtigen, dass die Werte jedes Knotens von einer Nutzenfunktion abhängen.
Um den Baum besser zu verstehen, nehmen Sie an, dass die Entscheidung an der Basis über die Verteilung des Produkts liegt. Der Konkurrent (der Gegner) kann die Verteilung auslagern (siehe linke Seite des Baums). In diesem Fall muss er sich zum Beispiel zwischen Dealer A und B entscheiden. Er entscheidet sich also für ersteren, was dazu führt, dass Spieler x 10 verliert (wenn er B wählt, würde Spieler x 12 gewinnen).
Aber vielleicht zieht es der Gegner vor, seine Ware selbst zu verteilen, motorisierte Fahrzeuge zu mieten oder einen Lastwagen zu kaufen. Wählen Sie von beiden Szenarien das erste, das für Spieler x weniger schmeichelhaft ist, da er 5 und nicht 10 gewinnt.