Minimax-Algorithmus
[vi[pl:Algorytm min-max]]Der Minimax-Algorithmus ist ein Algorithmus zur Ermittlung der optimalen Spielstrategie für Spiele bei denen zwei gegnerische Spieler abwechselnd Züge ausführen (z.B. Schach, Go, Reversi, Dame, Mühle oder Vier Gewinnt).
Im Gegensatz zu Würfelspielen sind die genannten Spiele nicht vom Zufall abhängig, im Gegensatz zu Karten- und Ratespielen sind sie offen, d.h. in jeder Spielsituation sind jedem der beiden Spieler alle Zugmöglichkeiten des jeweiligen Gegenspielers bekannt.
Aus diesem Grund läßt sich die optimale Strategie für das jeweilige Spiel mit dem Minimax-Verfahren ermitteln. Die optimale Strategie ist dann gefunden, wenn sie zum (bestmöglichen) Ergebnis eines Spielers führt, wenn man von optimaler Spielweise des Gegner ausgeht. Für einige Spiele, wie das so genannte Nimm-Spiel, lässt sich eine optimale Strategie auch direkt ohne Minimax berechnen.
| Table of contents |
|
2 Bewertungsfunktion 3 Suchbaum-Beispiel 4 Anmerkungen 5 Pseudocode |
Bei fast allen anderen Spielen ist dies zu rechenaufwendig.
Deshalb begnügt man sich damit, den Suchbaum nur bis zu einer vorgegebenen Suchtiefe aufzubauen.
Die Bewertungsfunktion wird modifiziert, sehr gute Spielpositionen für A erhalten sehr hohe Werte,
sehr gute Spielpositionen für B erhalten sehr niedrige Werte.
Zur Ermittlung der Werte bedient man sich Heuristiken zur Schätzung.
Die steigende Rechenleistung von Computern und bessere Programme haben mittlerweile dazu geführt, dass selbst bei so komplexen Spielen wie Schach heutzutage die meisten Menschen ohne Mühe vom Computer geschlagen werden können. Die dabei verwendete Strategie beruht im Wesentlichen auf dem Minmax-Algorithmus.
Die Knoten der Ebenen 1 und 3 entsprechen Spielsituationen, in denen Spieler A am Zug ist,
d.h. hier wird jeweils der Max-Wert der untergeordneten Knoten ermittelt.
Die Knoten der Ebene2 entsprechen Spielsituationen, in denen Spieler B am Zug ist,
d.h. hier wird jeweils der Min-Wert der untergeordneten Knoten ermittelt.
Auf der Blätterebene werden die Knotenwerte jeweils über die Bewertungsfunktion ermittelt.
Im Bild sind Kanten ( = Spielzüge ), die zum Max-Wert führen, rot gekennzeichnet.
Kanten, die zum Min-Wert führen, sind blau gekennzeichnet.
Es existieren daher verschiedenen optimierte Varianten, z.B.
Algorithmus
Der Algorithmus funktioniert folgendermaßen:
Bewertungsfunktion
Eine ideale Bewertungsfunktion ordnet einer Stellung den Wert +1 zu, wenn Spieler A gewinnt und den Wert -1, wenn Spieler B gewinnt und 0 bei Unentschieden. Kann man von sämtlichen Spielpositionen den Suchbaum bis zur maximalen Tiefe aufbauen (bis zur Endstellung, wo man sieht, wer gewinnt), so spielt der Algorithmus ein perfektes Spiel. Allerdings ist in der Praxis der vollständige Aufbau eines Suchbaums nur bei sehr einfachen Spielen wie Tic-Tac-Toe möglich.Suchbaum-Beispiel
Das Bild oben zeigt einen einfachen Baum mit Suchtiefe 3.Anmerkungen
Der Minimax-Algorithmus benötigt einerseits abhängig von der Suchtiefe extrem viel Zeit,
andererseits steigt in der Regel bei höherer Suchtiefe auch die Qualität des Suchergebnisses.Pseudocode
Hauptprogramm (Auszug):
var doNext : number
dummy := maxWert ( gewünschte suchTiefe )
Zug doNext ausführen
function maxWert ( restTiefe ) returns number
var ermittelt, zugWert : number
begin
ermittelt := - unendlich
für alle möglichen Züge
Zug simulieren
if restTiefe <= 1 or keineFolgezügeMehrMöglich
then zugWert := bewertungsFunktion
else zugWert := minWert ( restTiefe - 1 )
Zug-Simulation zurücksetzen
if zugWert > ermittelt then begin
ermittelt := zugWert
doNext := nummer des Zuges /* für das Hauptprogramm */
end
end
return ermittelt
end maxWert
function minWert ( restTiefe ) returns number
var ermittelt, zugWert : number
begin
ermittelt := + unendlich
für alle möglichen Züge
Zug simulieren
if restTiefe <= 1 or keineFolgezügeMehrMöglich
then zugWert := bewertungsFunktion
else zugWert := maxWert ( restTiefe - 1 )
Zug-Simulation zurücksetzen
if zugWert < ermittelt then ermittelt := zugWert
end
return ermittelt
end minWert
