Minimax

Die Annahme

Bei einem Spiel wie Schach oder Tic-Tac-Toe genügt es nicht, einen Weg zum Ziel zu finden — ein Gegner wirkt entgegen. Minimax rechnet deshalb mit dem ungünstigsten Fall: Der eigene Zug wird so gewählt, dass das Ergebnis auch dann noch am besten ist, wenn der Gegner anschließend seinen besten Zug macht. Die Herangehensweise heißt adversariale Suche, von lateinisch adversarius, „Gegner".

Die Berechnung

Das Verfahren baut den Spielbaum bis zu den Endstellungen auf und bewertet diese (Sieg, Niederlage, Unentschieden). Von dort rechnet es rückwärts: An den Knoten, an denen man selbst zieht, wird der größte Wert der Nachfolger übernommen; an den gegnerischen Knoten der kleinste. So wandert die Bewertung Ebene für Ebene nach oben, bis der Wert des besten Zugs in der aktuellen Stellung feststeht.

Die Grenze der Vollständigkeit

Vollständig durchrechnen lässt sich das nur bei kleinen Spielen. Tic-Tac-Toe hat rund eine halbe Million Stellungen und ist damit vollständig lösbar; Schach hat schätzungsweise 10 hoch 40 legale Stellungen. In der Praxis bricht das Verfahren deshalb nach einer festen Tiefe ab und schätzt die erreichten Stellungen mit einer Bewertungsfunktion — bei Schach etwa nach Materialwert und Stellungsmerkmalen.

Zwei Probleme des Abbruchs

Wer mitten im Spiel abbricht, urteilt über eine Momentaufnahme. Steht die eigene Dame gerade ungedeckt, sieht die Stellung gut aus, obwohl sie im nächsten Zug verloren geht — deshalb rechnet man unruhige Stellungen weiter, bis nichts mehr geschlagen wird (Ruhesuche). Und ein unabwendbarer Verlust lässt sich durch Zwischenzüge über den Suchhorizont hinausschieben, sodass er unsichtbar bleibt; das ist der Horizonteffekt.

Einordnung

Minimax bewertet erschöpfend und exakt, ist aber teuer. Das Alpha-Beta-Pruning liefert dasselbe Ergebnis bei deutlich weniger Aufwand. Für Spiele mit sehr großem Verzweigungsfaktor wie Go, wo auch keine gute Bewertungsfunktion von Hand zu finden war, hat sich stattdessen die Monte-Carlo-Baumsuche durchgesetzt.