Game-AITutorial

Programmieren von KIs für 4×4 TicTacToe – Part 6 – Hardcore KI


In diesem letzten Post der Serie, implementieren wir eine noch etwas klügere KI, welche prinzipiell auch für andere Spiele genutzt werden kann (zumindest das Grundprinzip). Das letzte Mal sahen wir, dass die Monte-Carlo Simulation es uns erlaubt die handgemachte Heuristik los zu werden. Es gibt dennoch eine Kleinigkeit, welche den Ansatz weiter verbessern kann. Wenn wir uns den Spiel-Baum von letztem Mal anschauen, dann haben wir jeden “Start-Move” ungefähr gleich oft gemacht, da wir total zufällig die Aktionen ausgesucht haben. Wenn man jedoch zwei weitere Ideen hinzufügt, wird die Monte-Carlo Simulation noch mächtiger:

  • Benutze eine handgemacht Heuristik, um “gute” Aktionen zu finden
  • Die Anzahl der Siege bestimmt wie gut ein kompletter Zweig ist, selbst während der Simulation

Es wirkt etwas komisch eine handgemacht Heuristik wieder hinzuzufügen, nachdem wir Monte-Carlo doch genau deswegen benutzen, um die Heuristik zu entfernen. Der Unterschied ist jedoch, dass in Monte-Carlo der beste nächste Zug nicht direkt von der gewählten Heuristik abhängt, sondern am Ende immer noch die Anzahl an Siege zählen. Wir benutzten die Heuristik also nur im der Simulation “Tipps” zu geben, welcher nächste Zug der beste sein könnte. Wir simulieren also wie zuvor, indem wir zufällig Züge machen, machen jetzt aber in 10% der Fälle die beste Aktion laut Heuristik. In Pseudo-Code als in etwas das:

Das erlaubt dem Algorithmus gute Aktionen schneller zu finden mit weniger Simulationen. Dadurch wird unsere KI insgesamt “schneller”, weil gute Aktionen früher gefunden werden können. Der zweite Punkt weiter oben ist erst einmal offensichtlich, aber wir können noch etwas mehr davon profitieren als wir es eh schon tun.

Der beste Zweig nach 1000 Spielen ist sehr wahrscheinlich auch der beste Zweig nach 10000 Spielen oder sogar nach 100000 Spielen. Wenn aber zwei Zweige sich nur sehr wenig unterscheiden in der Sieges-Ratio (z.B. 70% vs. 71%), dann ist es sinnvoll sich auf diese zwei Zweige zu konzentrieren. Wir machen also wenn wir zwei solche Zweige gefunden haben, wie bisher auch zufällige mit Heuristiken angereicherte Züge. Dieses Mal jedoch beschränken wir uns nur auf die zwei Züge. Auf diesem Weg nähert sich die Sieges-Chance immer weiter der realen Chance zu gewinnen an und wir können mit immer größerer Sicherheit sagen welches der besser Zweig ist und damit welches die beste nächste Aktion.

Selbst wenn wir erwarten, dass die anderen Zweige immer schlechter sind, sollten wir sie dennoch nicht komplett ausschließen, vielleicht hatten wir ja einfach nur Pech bei den ersten paar Tausend Simulationen. Um diesen Fall auch abzudecken, fügen wir auch hier wieder etwas Zufall ein und nehmen nur in 50% der Fälle den besten Zug (nach Sieges-Chance) als “ersten Zug” und in den anderen 50% einen zufälligen Zug.

Pseudo-Code:

Dadurch, dass die Abschätzung der Sieges-Chance für wenige Simulationen sehr ungenau ist, machen wir erst ein paar Simulationen, um die Sieges/Niederlage Verteilung grob abschätzen zu können, bevor wir uns auf den besten Zweig konzentrieren.

Im Folgenden haben wir eine Monte-Carlo-KI implementiert, welches den besten Sieges-Ratio-Zug benutzt, aber keine Heuristik. Der Code kann natürlich einfach erweitert werden, um auch eine Heuristik, wie beschrieben, mit zu verwenden:

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.