Game-AITutorial

Programmieren von KIs für 4×4 TicTacToe – Part 5 – Monte-Carlo Simulation


Der aktuelle MinMax-Ansatz sieht deutlich vielversprechender aus als unser alter Heuristik basierter Ansatz. Dennoch ist das nur die Spitze des Eisberges! Es gibt Möglichkeiten die Performanz weiter zu steigern! Zum Beispiel indem man den MinMax-Algorithmus, den wir letztes Mal implementiert haben, verbessert (zum Beispiel durch Alpha-Beta-Suche). Dieser Algorithmus ist aber “nur” ein verbesserter MinMax Ansatz. Aus diesem Grund gehen wir auf diesen Ansatz nicht weiter ein.

Stattdessen gehen wir das größte Problem bei der Verwendung von MinMax an: Die Heuristik! Wenn wir eine schlechte Heuristik benutzen, können wir sogar fünf Züge in die Zukunft schauen und bekommen trotzdem grauenhafte Ergebnisse. Auch wenn ganz “OK” funktionierende Heuristiken recht schnell gefunden sind, so ist es doch extrem hart eine sehr gute Heuristik zu finden! Deshalb wäre es natürlich toll, wenn wir die Abhängigkeiten von diesen handgemachten Heuristiken eliminieren. Genau das werden wir mit der Monte-Carlo Simulation erreichen! Das Entfernen der handgemachten Heuristiken hat einen weiteren Vorteil: Wir können nun starke KIs erschaffen ohne selbst groß Ahnung vom Spiel zu haben.

Am Ende des nächsten Posts werden wir eine KI implementieren, die Monte-Carlo Suche benutzt. Aber dazu später mehr, zuerst einmal sehen wir uns die grundlegenden Ideen hinter der Monte-Carlo Simulation an. Monte-Carlo Simulation kann vereinfacht zusammengefasst werden als:

Tu etwas so oft, bis du in der Lage bist die Eintritts-Wahrscheinlichkeiten der Resultate realistisch abschätzen zu können

Diese Aussage ist natürlich sehr generell, aber beinahe jeder hat das Prinzip zumindest ein paar Mal im Leben schon benutzt ohne den Namen zu kennen. Stell dir vor, jemand gibt dir einen Würfel, bei welchem eine der Seiten öfter auftaucht als die Anderen. Du sollst jetzt bestimmen welche Seite das ist.

Diese Frage zu beantworten ist einfach, aber sehr erschöpfend. Alles was man dabei tun muss, ist den Würfe einige tausend Mal zu werfen und zu zählen wie oft welche Seite gezeigt wurde. Wenn man sich noch nicht sicher ist, macht man eben noch ein paar tausend Würfe mehr. Solange bis man erkennt welche Seite häufiger auftaucht als die anderen Seiten (auch “Das Gesetz der großen Zahlen” genannt). Selbst wenn natürlich etwas Unsicherheit übrig bleibt, kann man durch diese Methode fast immer die manipulierte Seite finden.

Exakt dasselbe Konzept wenden wir auf KIs an.

Basierend auf dem aktuellen Zustand werden einige Tausend Spiele gespielt (bis zum Ende) mit zufälliger Zugwahl. In der allerersten Abzweigung, speichert man sich dabei folgende Dinge pro Aktion:

  • Wie oft wurde dieser Zweig besucht
  • Wie oft hat der Zweig zu einem Sieg geführt
  • Wie oft hat der Zweig zu einer Niederlage geführt

Dieser Ansatz unterscheidet sind vom MinMax Ansatz darin, dass man nicht mehr durch alle Zustände, sondern nur noch durch ein paar tausend Zustände/Aktionen gehen muss, um die Gewinnchance zu berechnen. Die Idee hinter diesem Konzept ist, dass wenn man im besten Zweig/mit der besten Aktion startet, man trotzdem insgesamt öfter gewinnt, selbst wenn man nicht alle Zustände angeschaut hat. Denn die Wahrscheinlichkeit in einem Zweig bei zufälligen Zügen zu gewinnen, ist natürlich stark davon abhängig wie oft man allgemein in diesem Zweig gewinnt. Wenn man viele Spiele spielt und immer zufällig eine Aktion auswählt, könnte man sich in folgender Situation wieder finden:

Man sieht, dass wir immer eine zufällige Aktion wählen, selbst im ersten Zweig und zählen nur Werte für den ersten Zweig. In dem oberen Beispiel können wir mit dem Wissen jetzt die nächste beste Aktion herausfinden, welche diejenige mit der höchsten Win-Ration (oder alternativ win+draw – Ratio) ist.

Heute bauen wir jedoch keine KI zum Thema, weil wir im nächsten Post sowieso eine KI bauen, die darauf basiert.

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.