Game-AITutorial

Programmieren von KIs für 4×4 TicTacToe – Part 3 – Der MinMax-Algorithmus


Durch die Verwendung von Daumenregeln haben wir, im letzten Post, bereits eine ziemlich gute KI geschaffen. Dennoch ist es einfach diese KI zu besiegen, wenn man erst einmal verstanden hat, dass sie “Fallen” nicht erkennt. Als Situationen in denen der Spieler seine “X” so platziert, dass es nicht mehr möglich ist mit genau einem “O” den Sieg zu verhindern. Das nachfolgende Bild zeigt eine derartige Situation.

Neben diesem Fakt, wird der ein oder andere sicher auch schon vermuten, dass Heuristik getriebene KIs in komplexeren Spielen wie etwa bei Schach eine schlechte Performance zeigen. Diese Art von KIs sind schnell implementiert und liefern trotzdem Ergebnisse mit denen man einigermaßen etwas anfangen kann im Vergleich zu total zufälligen Zügen. Daher eignen sie sich für schnelle Tests bestens, aber um wirklich herausfordernde Gegner zu schaffen fehlt noch ein klein wenig. In den nächsten zwei Posts sehen wir uns daher an wie man sinnvoll Heuristiken und “Suche” kombinieren kann, um eine Experten-KI zu schaffen.

Der erste Schritt in diese Richtung ist erst einmal sich komplett zu lösen von der “Daumenregeln-Lösung” und das Ganze systematischer anzugehen. Denn ein großes Problem der Daumenregeln ist, dass sie nur begrenzt weit in die Zukunft sehen können, was “Fallen-Situationen” nicht vorhersehbar für die KI macht.

Dieses in die Zukunft schauen kann man relativ einfach erreichen mit einem Algorithmus, der MinMax-Algorithmus genannt wird. Die Grundidee ist dabei, dass der Algorithmus alle möglichen zukünftigen Feldbelegungen durchgeht und diejenige nächste Aktion auswählt, die in jedem Fall zu einem Sieg führt. Das ist wichtig sich zu merken: Der MinMax-Algorithmus sucht diejenige nächste Aktion, die zu 100% einen Sieg bedeutet, egal wie gut der Gegner spielt.
Natürlich gibt es Situationen, in welchen es keine Möglichkeit gibt immer zu gewinnen, egal was der Gegner macht, aber diesen Punkt sehen wir uns später genauer an.

Stellt dir vor du wärst “X” in dieser Situation:

Es ist offensichtlich, dass ein Kreuz in der dritten Reihe und dritten Spalte zu einem Sieg führen. Vielleicht sieht das sogar unsere Heuristik-KI. Aber wir brauchen eine Strategie, um mehr als nur das zu sehen, wir wollen auch weiter in die Zukunft sehen. Aus diesem Grund geht der MinMax-Algorithmus alle vom aktuellen Zustand aus erreichbaren Zustände durch und findet die nächste Aktion mit garantiertem Sieg. Der gesamte Spiel-Baum sieht dabei so aus:

Im nächsten Schritt muss man systematisch die nächste beste Aktion finden, welche einen Sieg bringt. Der Mensch ist ziemlich gut darin, solche Aktionen relativ intuitiv und sofort zu erkennen. Jedoch, wenn der Computer die beste Aktion finden soll, muss man das Ganze etwas systematischer angehen. Genau hier springt der MinMax-Algorithmus ein, welches aus drei grundlegenden Schritten besteht:

  • Weise jedem Endzustand eine Nummer zu (Sieg=+1, Unentschieden=0, Niederlage=-1)
  • Beginnend bei den Endzuständen, wähle die Nummer, die der jeweilige Spieler wählen würde, wenn er perfekt spielen würde
  • Propagiere die Nummer Schritt für Schritt durch den Baum nach oben bis die Ursprungssituation erreicht wurde und sich die beste nächste Aktion ablesen lässt (Die Aktion mit der höchsten Nummer).

Das klingt erst einmal theoretischer und verwirrender als es ist. Ein Beispiel sollte den Algorithmus klar machen. Der Baum nachdem man jedem Endzustand eine Nummer gegeben hat abhängig von Sieg/Unentschieden/Niederlage und mit ein paar Labels – Diese sehen wir uns gleich genauer an – sieht so aus:

Basierend auf diesem Baum soll die nächste beste Aktion gefunden werden. Die Labels an der Seite sagen aus wessen Zug es ist (“X”s bzw. “O”s Zug) und welche Nummer dieser Spieler auswählt. Wenn du X bist und die beste Aktion finden möchtest, nimmst du natürlich die größte Zahl (Max), weil du selbst wählen kannst, welche Nummer du nimmst. Wenn hingegen O am Zug ist, sucht dieser die niedrigste Zahl, weil du als X davon ausgehen musst, dass die niedrigste Zahl (Min) für dich das bestmögliche für O ist. (Denk auch an unsere Annahmen zu Beginn: Beide Spieler spielen immer perfekt!).

Im nachfolgenden wird der entstehende Baum Schritt für Schritt mit dem MinMax-Algorithmus bearbeitet. Im nächsten Post werden wir dann endlich auch eine KI basierend darauf implementieren!





Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.