Minimax-Algorithmus
# Minimax-Algorithmus

Der Minimax-Algorithmus ist ein Algorithmus, der im Bereich der künstlichen Intelligenz und der Spieltheorie verwendet wird.

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 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

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.

