Minimax-Algorithmus

Der Minimax-Algorithmus ist ein Algorithmus, der im Bereich der künstlichen Intelligenz und der Spieltheorie verwendet wird, er minimiert den möglichen Verlust in einem Worst-Case Szenario mit maximalem Verlust.

Eine mit dem Minimax-Algorithmus berechnete Strategie wird Minimax-Strategie genannt. Sie sichert dem betreffenden Spieler den höchstmöglichen Gewinn, der unabhängig von der Spielweise des Gegners zu erzielen ist. Das aus den Minimax-Strategien beider Spieler gebildete Strategie-Paar bildet ein Nash-Gleichgewicht.

Der Minimax-Algorithmus kann zur Ermittlung der Spielstrategie für endliche Zwei-Personen-Nullsummenspiele mit perfekter Information verwendet werden. Zu diesen Spielen gehören insbesondere Brettspiele wie Schach, Go, Othello, Dame, Mühle und Vier gewinnt, bei denen beide Spieler stets die gesamte Historie der Partie kennen. Auch für Spiele mit Zufallseinfluss wie Backgammon lässt sich der Minimax-Algorithmus auf Grundlage von Erwartungswerten erweitern. In der Regel, aber nicht ausschließlich, wird der Minimax-Algorithmus auf Spiele mit abwechselndem Zugrecht angewandt.

Varianten des Minimax-Algorithmus bilden die Grundlage von Software für Strategiespiele, zum Beispiel Schachprogramme. Die hohe Rechenleistung heutiger Computer hat dazu geführt, dass selbst bei so komplexen Spielen wie Schach Menschen kaum noch eine Chance haben, den Computer zu schlagen.

Bewertungsfunktion

Grundlage des Minimax-Algorithmus ist eine Bewertungsfunktion. Diese misst für jede Position eines Zwei-Personen-Nullsummenspiels die Gewinnaussichten, und zwar aus der Perspektive eines der beiden Spieler, hier in Anlehnung an Schach Weiß.

Eine ideale Bewertungsfunktion ordnet einer Position eines Spiels wie Schach

• den Wert +1 zu, wenn Weiß unabhängig von der Spielweise seines Gegners Schwarz einen Gewinn erzwingen kann,
• den Wert −1, wenn Schwarz einen Gewinn erzwingen kann (entsprechend dem „Gewinn“ in Höhe −1 für Weiß), und
• 0, wenn keiner der beiden Spieler aus eigener Kraft, d. h. unabhängig von der gegnerischen Spielweise, einen Gewinn erzwingen kann.

Für eine konkrete Position ist der zugehörige Wert der Bewertungsfunktion berechenbar, wenn er für alle Positionen bekannt ist, die aus der zu untersuchenden Position durch einen Zug erreichbar sind: Dabei ist es für Weiß optimal, zur Position mit dem höchsten Wert der Bewertungsfunktion zu ziehen (er fungiert daher als Maximierer) und für Schwarz, zur Position mit dem niedrigsten Wert der Bewertungsfunktion zu ziehen (er fungiert als Minimierer). Kann man alle Spielpositionen eines Spiels nacheinander derart untersuchen, so ist die Bewertungsfunktion komplett bekannt, was eine perfekte Spielweise ermöglicht. Allerdings ist dies in der Praxis nur bei sehr einfachen Spielen wie Tic-Tac-Toe möglich.

Bei „richtigen“ Spielen ist diese Vorgehensweise zu rechenaufwändig. Deshalb versucht man, die Bewertungsfunktion durch eine einfacher zu berechnende Variante zu ersetzen, die aber trotzdem möglichst gut die Gewinnaussichten widerspiegelt. Statt der Werte −1, 0 und 1 der idealen Bewertungsfunktion erhalten für Weiß günstige Positionen sehr hohe Werte und für Schwarz günstige Positionen sehr niedrige Werte. Eine solche Schätzung kann durch Heuristiken erfolgen wie z. B. Materialabschätzungen beim Schach auf der Basis von Bauerneinheiten. Verwendet werden diese Schätzungen dann in einer Version der Minimax-Algorithmus, bei der nur diejenigen Positionen untersucht werden, die durch eine beschränkte Zahl von Zügen, Suchtiefe genannt, aus der zu untersuchenden Position entstehen können. Für diese Positionen am sogenannten Horizont fließen dann die Schätzungen der Bewertungsfunktion in den Minimax-Algorithmus ein.

Algorithmus

Der Minimax-Algorithmus ist ein rekursiver Algorithmus. Er ermöglicht es dem am Zug befindlichen Spieler, den optimalen Zug zu bestimmen, vorausgesetzt, dass der Gegner ebenfalls optimal spielt. Er berechnet die Minimax-Entscheidung für den aktuellen Zustand.

Der Minimax-Algorithmus führt eine rekursive Tiefensuche zur Erkundung des gesamten Spielbaums durch. Der Minimax-Algorithmus verwendet die von der Bewertungsfunktion bestimmten Werte für die Endknoten des Baums und verfolgt dann den Baum rekursiv bis zum Wurzelknoten zurück, um den Zug (Nachfolgeknoten) mit dem maximalen Wert zu bestimmen.

Der Algorithmus wählt für den am Zug befindlichen Spieler jeweils die Position (den Knoten) mit dem maximalen Wert und für den Gegenspieler jeweils die Position mit dem minimalen Wert aus.

Beispiel für eine Berechnung mit dem Minimax-Algorithmus

Minimax-Algorithmus: Die Kreise entsprechen den Positionen, in denen der maximierende Spieler Weiß zieht. Die Quadrate entsprechen den Positionen, in denen der minimierende Spieler Schwarz zieht. Gezogen wird entlang der schwarzen Linien (Kanten) nach unten. Die roten Pfeile verdeutlichen die rekursiv von unten nach oben mögliche Berechnung der Werte der Bewertungsfunktion. Konkret markieren die roten Pfeile den jeweils besten Zug, der in der obersten Ebene blau dargestellt ist.

Das Bild rechts zeigt Positionen eines Spiels und die zwischen ihnen möglichen Züge. Der Abbildung liegt die Annahme zugrunde, dass wie beim Schach abwechselnd gezogen wird und es keine Zufallsentscheidungen gibt: Positionen, in denen Weiß zieht, sind als Kreise dargestellt. Positionen, in denen Schwarz zieht, entsprechen den Quadraten. Die möglichen Züge entsprechen den nach unten verlaufenden Linien (Kanten genannt) zwischen den Positionen (Knoten genannt). Insgesamt entsteht dadurch der sogenannte Spielbaum, der hier bis zur Suchtiefe 4 dargestellt ist. Der Teil, der die durchsuchten Positionen umfasst, wird Suchbaum genannt.

Der beste Zug für Weiß wird nun rekursiv bestimmt. Die Positionen mit der Suchtiefe 4 haben die Werte 10, +∞; 5; -10; 7, 5; -∞, -7, -5. Wenn Schwarz in den Positionen mit der Suchtiefe 3 jeweils den optimalen Zug macht, ergibt sich aus Sicht von Weiß nach dem nächster Zug jeweils die Position mit dem minimalen Wert. Im Beispiel sind das die Werte 10, 5; -10; 5, -∞; -7. Weiß wählt in den Positionen mit der Suchtiefe 2 jeweils die Position mit dem maximalen Wert, also 10, -10; 5, -7. Für die zwei Positionen mit Suchtiefe 1, also die Positionen nach dem Zug von Weiß, ergeben sich die Werte -10 und -7. Nach dem besten Zug für Weiß entsteht also die Position mit dem Wert -7.

Die Minimax-Berechnung der Bewertungsfunktion geht aus von den als bekannt vorausgesetzten Werten der unteren Ebene, wobei diese Werte bei einem Schachprogramm durch Heuristiken wie einer Materialbewertung geschätzt werden. Ebene für Ebene werden nun von unten nach oben die (in der Grafik bereits eingetragenen) Werte der Bewertungsfunktion berechnet, wobei sich jeder Wert auf Basis einer optimalen Spielweise des aktuell ziehenden Spielers ergibt: Konkret ist es für Weiß optimal, derart zu ziehen, dass die Position mit dem höchsten Wert erreicht wird. Analog ist es für Schwarz optimal, zur die Position mit dem niedrigsten Wert zu ziehen. Demgemäß markieren die roten Pfeile, wie sich die dargestellten Werte – jeweils korrespondierend zu den optimalen Spielzügen – von unten nach oben, d. h. entgegen der Spielchronologie, berechnen lassen.

Anmerkungen

Der Minimax-Algorithmus ist im Kern vom speziellen Spiel unabhängig, das heißt zum Beispiel Schach und Reversi benutzen denselben Algorithmus. Schnittstellen zum speziellen Spiel sind lediglich die beiden folgenden Programmteile:

• Welche Züge sind in einer konkreten Spielsituation möglich?
• Wie wird eine Spielsituation numerisch bewertet?

Neben dem Minimax-Verfahren kann ein Spiel weitere spielspezifische Verfahren anwenden, beispielsweise vorberechnete Bibliotheken für Eröffnungszüge.

Bei Nicht-Nullsummenspielen, bei denen die Niederlage des Gegners nicht zwangsläufig mit dem eigenen Gewinn zusammenfällt, liefert der Minimax-Algorithmus nicht unbedingt eine optimale Strategie.

Für einige Spiele wie das so genannte Nim-Spiel lässt sich eine optimale Strategie auch durch effizientere Algorithmen der Kombinatorischen Spieltheorie berechnen.

Variante: Der Negamax-Algorithmus

Um den Code zu vereinfachen und jede Position des Suchbaumes gleich behandeln zu können, definiert man, dass jeder Spieler versucht, ein für sich selbst maximales Ergebnis, das heißt maximalen Wert der Bewertungsfunktion, zu erzielen. Dazu muss die Bewertung der Folgestellungen mit $-1$ multipliziert werden (Negation, daher der Name). Damit muss nicht mehr unterschieden werden, ob Weiß oder Schwarz am Zug ist und daher das Maximum oder das Minimum berechnet werden soll, sondern es wird in jeder Stellung immer nur das Maximum der negierten Bewertungen der Folgestellungen berechnet.

Komplexität

Die Laufzeit des Minimax-Algorithmus ist linear bezüglich der Anzahl der zu überprüfenden möglichen Züge. Wenn die Anzahl der möglichen Züge in jeder Stellung etwa gleich ist, hat der Algorithmus also eine Laufzeit, die etwa exponentiell zur Suchtiefe ist. Man beachte, dass in der Theorie bei einem Spiel mit endlich vielen Zuständen die Laufzeit konstant ist, da ab einer gewissen Suchtiefe sich die Laufzeit nicht mehr erhöht. Da bei den meisten Spielen diese Suchtiefe aber niemals realistisch erreicht werden kann, ist es durchaus berechtigt, von einem exponentiellen Wachstum zu sprechen. Andererseits steigt in der Regel abhängig von der numerischen Bewertung bei höherer Suchtiefe auch die Qualität des Suchergebnisses.

Es existieren daher verschiedene optimierte Varianten, zum Beispiel

• Variable Suchtiefe: Wenn nur noch wenige Zugmöglichkeiten pro Spielsituation existieren, etwa weil sich nur noch wenige Spielsteine auf dem Spielfeld befinden, kann die Suchtiefe erhöht werden und umgekehrt.
• Dynamische Suchtiefe: Wenn sich die Zahlenwerte an einer Stelle des Suchbaums von Ebene zu Ebene stark ändern, kann die Suchtiefe lokal erhöht werden und umgekehrt.
• Die Alpha-Beta-Suche kann verwendet werden.

Eine wesentliche Zeitersparnis ergibt sich durch Speicherung der bisher untersuchten Stellungen und deren Bewertungen. Wird eine Stellung durch verschiedene Zugfolgen von der Ausgangsstellung erreicht, braucht nicht jedes Mal wieder der gesamte darunter liegende Suchbaum durchsucht zu werden. In der Praxis verwendet man für diese Speicherung häufig effiziente Hashtabellen.

Iterative Tiefensuche

Speziell bei eingeschränkter Zeit für die Suche (z. B. im Turnierschach) wird iterative Tiefensuche (iterative deepening) verwendet. Dabei wird die Suche, ausgehend von der zu untersuchenden Stellung, wiederholt gestartet und dabei die gewünschte Suchtiefe schrittweise erhöht. Werden die bereits untersuchten Stellungen, wie oben beschrieben, gespeichert, müssen nur die gegenüber der vorhergehenden Suche neu erreichten Stellungen mit der Bewertungsfunktion bewertet werden. Dieses Verfahren wird so lange fortgesetzt, bis die verfügbare Suchzeit überschritten oder ein „hinreichend gutes“ Ergebnis erzielt wurde.

Ohne iterative Tiefensuche wäre beim Überschreiten des Zeitlimits im schlimmsten Fall nur ein einziger Zug untersucht worden, dieser aber bis in sehr große Tiefe. Der nächste Zug, der vielleicht schon nach nur einem einzigen Gegenzug den Gewinn gesichert hätte, wäre gar nicht erst ausprobiert worden.

Implementierung

Hauptprogramm (Auszug):

 gespeicherterZug = NULL;
 int gewuenschteTiefe = 4;
 int bewertung = max(+1, gewuenschteTiefe);
 if (gespeicherterZug == NULL)
    es gab keine weiteren Zuege mehr;
 else
    gespeicherterZug ausführen;

Die normale Variante lautet:

 int max(int spieler, int tiefe) {
    if (tiefe == 0 or keineZuegeMehr(spieler))
       return bewerten();
    int maxWert = -unendlich;
    generiereMoeglicheZuege(spieler);
    while (noch Zug da) {
       fuehreNaechstenZugAus();
       int wert = min(-spieler, tiefe-1);
       macheZugRueckgaengig();
       if (wert > maxWert) {
          maxWert = wert;
          if (tiefe == gewuenschteTiefe)
             gespeicherterZug = Zug;
       }
    }
    return maxWert;
 }

 int min(int spieler, int tiefe) {
    if (tiefe == 0 or keineZuegeMehr(spieler))
       return bewerten();
    int minWert = unendlich;
    generiereMoeglicheZuege(spieler);
    while (noch Zug da) {
       fuehreNaechstenZugAus();
       int wert = max(-spieler, tiefe-1);
       macheZugRueckgaengig();
       if (wert < minWert) {
          minWert = wert;
       }
    }
    return minWert;
 }

Die NegaMax-Variante lautet:

 int miniMax(int spieler, int tiefe) {
    if (tiefe == 0 or keineZuegeMehr(spieler))
       return bewerten(spieler);
    int maxWert = -unendlich;
    generiereMoeglicheZuege(spieler);
    while (noch Zug da) {
       fuehreNaechstenZugAus();
       int wert = -miniMax(-spieler, tiefe-1);
       macheZugRueckgaengig();
       if (wert > maxWert) {
          maxWert = wert;
          if (tiefe == gewuenschteTiefe)
             gespeicherterZug = Zug;
       }
    }
    return maxWert;
 }

Literatur

Jörg Bewersdorff: Glück, Logik und Bluff: Mathematik im Spiel – Methoden, Ergebnisse und Grenzen, Springer Spektrum, 7. Auflage 2018, ISBN 978-3-658-21764-8, doi:10.1007/978-3-658-21765-5, insbesondere Kapitel 2.10.

Siehe auch

• Minimax-Gleichgewicht als Spezialfall des Nash-Gleichgewichts
• Minimax-Regel
• Min-Max-Theorem
• Alpha-Beta-Suche – eine wesentliche Optimierung des Minimax-Algorithmus

Weblinks

• Java-Applet zur Demonstration
• www.javatpoint.com: Mini-Max Algorithm in Artificial Intelligence
• GeeksforGeeks: Minimax Algorithm in Game Theory | Set 1 (Introduction)
• GeeksforGeeks: Minimax Algorithm in Game Theory | Set 4 (Alpha-Beta Pruning)
• freeCodeCamp: Minimax Algorithm Guide: How to Create an Unbeatable AI