Game-AITutorial

Programmieren von KIs für 4×4 TicTacToe – Part 4 – Eine Experten-KI


Im letzten Post haben wir den MinMax-Algorithmus kennen gelernt. Dieser Algorithmus würde ohne jegliche Anpassungen bereits genug sein, um eine KI zu erstellen, die perfekt spielt. Da dieser Ansatz uns garantiert diejenige nächste Aktion zu nehmen, die immer in einem Sieg (oder im kleinsten Übel) endet, egal wie gut der Gegner spielt. Dasselbe Prinzip klappt daher auch bei komplexeren Spielen.

Dennoch gibt es eine Schattenseite des Algorithmus. Er findet zwar die beste Aktion, aber schafft das indem er alle zukünftigen Zustände anschaut/erzeugt. Stell dir nur einmal vor wir würden das für das aller erste “X” auf einem leeren Feld machen. Der Algorithmus geht dann durch insgesamt

  • 16 Anfangszustände
  • 15 weitere Zustände pro Anfangszustand (–> 16*15)

Insgesamt gibt es damit rund 16 x 15 x 14 x 13 x … (bzw. 16!) Zustände zu checken, was ausgeschrieben 20.922.790.000.000 Zustände sind. Es dauert natürlich enorm lange alle diese Zustände zu überprüfen (auch wenn in der Realität weniger Zustände überprüft werden müssen, da vier X/O bereits genug sind um das Spiel zu beenden). Dennoch wenn die KI keine zwei Stunden “überlegen” soll, dann ist das sicher nicht die endgültige Lösung.

Eine mögliche Lösung wäre es bei einer vorgegebenen Tiefe den MinMax-Algorithmus abzubrechen. Dadurch wäre ein Kompromiss zwischen Performance und guten Spielzügen möglich. Den Zustandsbaum aber einfach bei einer bestimmten Tiefe abzuschneiden, ist nicht möglich. Es fehlt dadurch dann natürlich das “Endergebnis”. Stell dir vor wir legen uns auf eine maximale Tiefe von zwei fest. Dann könnte dieser Baum entstehen:

Das heißt theoretisch funktioniert dieser Ansatz natürlich schon, aber man sieht, dass es auch Situationen gibt, in welchen der Algorithmus nicht mehr weiß wie gut/schlecht der jeweilige Zweig ist, weil eine Aussage über den Endzustand fehlt. Dadurch kann man die Nummer natürlich auch nicht mehr schrittweise mit min/max bestimmen. Und genau aus diesem Grund benutzen wir eine Heuristik, um die Qualität des Zustands zu bestimmen.

Wann immer wir einen Zustand auf maximaler Tiefe erreichen, dieser aber kein Endzustand ist, benutzen wir eine Heuristik zum Schätzen des Zustandwerts (bzw. manchmal wendet man der Einfachheit halber auf alle Zustände die Heuristik an). Wir haben uns bereits klar gemacht, dass Heuristiken lediglich die echte Welt annähern. Deshalb kann die Benutzung von Heuristiken natürlich zu nicht-optimalen Entscheidungen/Aktionen führen, selbst wenn der ganze Baum durchgerechnet wird. Aber es ist eine gute und effiziente Möglichkeit, um die Qualität eines Zustandes zu bestimmen, egal ob er Endzustand ist oder nicht.

Wir wenden einmal beispielhaft folgende Heuristik mit MinMax auf unser Beispiel an:

  • Falls der Gegner drei O in einer Reihe/Spalte/Diagonale hat, verringere den Wert des Zustands um 10
  • Je mehr X in einer Reihe/Spalte/Diagonale desto besser: Addiere für jedes X in Spalte/… eins auf die Board-Value (vorausgesetzt es ist mindestens eine freie Zelle in dieser Reihe/Spalte/…)
  • Falls der Gegner vier O in einer Reihe/… hat, verringere den Wert des Zustands um 1000

Diese Heuristik gibt Zuständen, in welchen der Gegner maximal zwei Zeichen in einer Reihe/Spalte/… gesetzt hat den höchste Wert. Dadurch wird die KI sehr früh schon versuchen Fallen und ähnliches zu blocken. Konkret entsteht damit beim MinMax-Algorithmus Schritt für Schritt die nachfolgenden Bilder:





Im nächsten Schritt werden wir uns eine KI basteln, die noch härter zu schlagen ist als unsere MinMax-KI. Dafür müssen wir uns jedoch im nächsten Post ein paar Grundlagen zur Monte-Carlo Simulation anschauen. Zum Abschluss noch eine KI mit MinMax-Algorithmus aber ein bisschen anderer Heuristik:

Open in new window

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.