Minimax-Algorithmus

Der Minimax-Algorithmus ist ein Algorithmus zur Ermittlung der Spielstrategie für Spiele bei denen zwei gegnerische abwechselnd Züge ausführen (z.B. Schach Go Reversi Dame Mühle oder Vier Gewinnt).

Im Gegensatz zu Würfelspielen sind die Spiele nicht vom Zufall abhängig im Gegensatz Karten- und Ratespielen sind sie offen d.h. jeder Spielsituation sind jedem der beiden Spieler Zugmöglichkeiten des jeweiligen Gegenspielers bekannt.

Aus diesem Grund läßt sich die Strategie für das jeweilige Spiel mit dem ermitteln. Die optimale Strategie ist dann gefunden sie zum (bestmöglichen) Ergebnis eines Spielers führt man von optimaler Spielweise des Gegner ausgeht. einige Spiele wie das so genannte Nimm-Spiel lässt sich eine optimale Strategie auch ohne Minimax berechnen.

Inhaltsverzeichnis

1 Algorithmus 2 Bewertungsfunktion 3 Suchbaum-Beispiel 4 Anmerkungen 5 Iterative deepening 6 Pseudocode 7 Variante: Der NegaMax Algorithmus

Algorithmus

• Jeder Spielposition (Brettstellung) ist ein Zahlwert zugeordnet:
  • Positionen die günstig für Spieler A seien große Zahlen zugeordnet
  • Positionen die günstig für Spieler B kleine Zahlen.
  • Spieler A maximiert also den Zahlwert Laufe des Spiels Spieler B minimiert ihn.
• Der Algorithmus baut einen Suchbaum (s.u.) der alle Folgepositionen der aktuellen Position enthält alle Folgepositionen der Folgepositionen usw. Bis zu bestimmten Tiefe.
• Für die Blätter des Suchbaums wird eine Bewertung bestimmt.
• Die Bewertung wird nun von den zur Wurzel übertragen:
  • Ist Spieler A am Zug so einer Position der Maximalwert der Bewertungen aller zugeordnet.
  • Ist Spieler B am Zug so einer Position der Minimalwert der Folgepositionsbewertungen zugeordnet.
  • Das ganze geschieht rekursiv bis die Wurzel des Spielbaums erreicht
• Je nachdem welcher Spieler am Zug entscheidet sich der Algorithmus für den Zug Folgeposition mit minimaler oder maximaler Bewertung.

Bewertungsfunktion

Bei fast allen anderen Spielen ist zu rechenaufwendig. Deshalb begnügt man sich damit Suchbaum nur bis zu einer vorgegebenen Suchtiefe Die Bewertungsfunktion wird modifiziert sehr gute Spielpositionen A erhalten sehr hohe Werte sehr gute für B erhalten sehr niedrige Werte. Zur der Werte bedient man sich Heuristiken zur Schätzung.

Die steigende Rechenleistung von Computern und Programme haben mittlerweile dazu geführt dass selbst so komplexen Spielen wie Schach heutzutage die Menschen ohne Mühe vom Computer geschlagen werden Die dabei verwendete Strategie beruht im Wesentlichen dem Minmax-Algorithmus.

Suchbaum-Beispiel

Die Knoten der Ebenen 1 und entsprechen Spielsituationen in denen Spieler A am ist d.h. hier wird jeweils der Max-Wert untergeordneten Knoten ermittelt.

Die Knoten der Ebene2 entsprechen Spielsituationen denen Spieler B am Zug ist d.h. wird jeweils der Min-Wert der untergeordneten Knoten

Auf der Blätterebene werden die Knotenwerte über die Bewertungsfunktion ermittelt.

Im Bild sind Kanten ( = ) die zum Max-Wert führen rot gekennzeichnet. die zum Min-Wert führen sind blau gekennzeichnet.

Anmerkungen

• Das Minimax-Verfahren ist im Kern vom Spiel unabhängig d.h. z.B. Schach und Reversi den selben Algorithmus.
• Schnittstellen zum speziellen Spiel sind lediglich beiden folgenden Programmteile:
  • Welche Züge sind in einer konkreten möglich?
  • Wie wird eine Spielsituation numerisch bewertet?
• Neben dem Minimax-Verfahren kann ein Spiel spielspezifische Verfahren anwenden z.B. vorberechnete Bibliotheken für

Der Minimax-Algorithmus benötigt einerseits abhängig von Suchtiefe extrem viel Zeit andererseits steigt in Regel bei höherer Suchtiefe auch die Qualität Suchergebnisses.

Es existieren daher verschiedenen optimierte Varianten

• variable Suchtiefe: wenn nur noch wenige pro Spielsituation existieren z.B. weil sich nur wenige Spielsteine auf dem Spielfeld befinden kann Suchtiefe erhöht werden (und umgekehrt).
• dynamische Suchtiefe: wenn sich die Zahlenwerte einer Stelle des Suchbaums von Ebene zu stark ändern kann die Suchtiefe lokal erhöht (und umgekehrt).
• die Alpha-Beta-Suche kann verwendet werden.

Eine wesentliche Zeitersparnis ergibt sich durch der bisher untersuchten Stellungen und deren Bewertung. eine Stellung durch verschiedene Zugfolgen von der erreicht braucht nicht jedes Mal wieder der darunter liegende Suchbaum durchsucht werden.

Iterative deepening

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

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

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 Züge Zug simulieren if restTiefe <= 1 keineFolgezügeMehrMöglich then zugWert :=  bewertungsFunktion  else zugWert :=  minWert ( restTiefe - 1 )  Zug-Simulation zurücksetzen if zugWert > ermittelt begin ermittelt := zugWert doNext := nummer Zuges /* für das Hauptprogramm */ end return ermittelt  end maxWert   function minWert ( restTiefe ) returns number  var ermittelt zugWert : number  begin  ermittelt := + unendlich für alle Züge Zug simulieren if restTiefe <= 1 keineFolgezügeMehrMöglich then zugWert :=  bewertungsFunktion  else zugWert :=  maxWert ( restTiefe - 1 )  Zug-Simulation zurücksetzen if zugWert < ermittelt ermittelt := zugWert end return ermittelt  end minWert   

Variante: Der NegaMax Algorithmus

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

Bücher zum Thema Minimax-Algorithmus

Dieser Artikel von Wikipedia unterliegt der GNU FDL.