KI-Entwicklung am Beispiel des Dicey Dungeons-Spiels

Ungefähr einen Monat lang löste ich eines der schwierigsten technischen Probleme meines neuen Spiels, Dicey Dungeons - eine verbesserte KI für die endgültige Veröffentlichung des Spiels. Es war eine ziemlich interessante Arbeit, und vieles davon war neu für mich, deshalb habe ich beschlossen, ein wenig darüber zu schreiben.

Zunächst erkläre ich: Ich bin kein Experte für Computertheorie, sondern nur einer von denen, die genug Programmieren studiert haben, um Videospiele zu erstellen. Danach habe ich mein Training abgeschlossen und nur das genommen, was ich brauchte. Normalerweise kann ich meine Probleme selbst lösen, aber ein echter Programmierer würde meine Entscheidungen höchstwahrscheinlich nicht gutheißen.

Ich habe versucht, einen Artikel auf einem ausreichend hohen Abstraktionsniveau zu schreiben, damit die Grundideen auch Nicht-Programmierern klar waren. Aber ich bin kein Experte in solchen Dingen, daher können meine Erklärungen der Theorie falsch sein. Schreiben Sie mir dazu in den Kommentaren zum Original, ich werde gerne Änderungen vornehmen!

Beginnen wir mit der Erklärung der Aufgabe!

Herausforderung

Falls Sie Dicey Dungeons noch nicht gespielt haben, erzähle ich Ihnen kurz etwas über das Spiel: Dies ist ein Rollenspiel mit Deckbuilding, in dem jeder Feind eine Reihe von Waffenkarten hat, die unterschiedliche Aktionen ausführen. Außerdem würfeln sie! Dann rüsten sie diese Würfel, um Schaden zu verursachen oder verschiedene Statuseffekte zu erzeugen oder um zu heilen oder sich gegen Schaden und dergleichen zu verteidigen. Hier ist ein einfaches Beispiel dafür, wie ein kleiner Frosch ein großes Schwert und einen kleinen Schild benutzt:


Ein komplizierteres Beispiel: Dieser Alleskönner hat einen Schraubenschlüssel, mit dem Sie zwei Würfel zusammenlegen können (dh 3 + 2 ergeben 5 und 4 + 5 ergeben 6 und 3). Er hat auch einen Hammer (Hammer), der dem Spieler einen "Schock" -Effekt auferlegt, wenn Sie sechs auf ihn anwenden, und einen Erbsenschützen (Erbsenschütze), der wenig Schaden anrichtet, aber dann einen "Countdown" hat dort gilt es für mehrere Züge.


Eine weitere wichtige Komplikation: Das Spiel hat Statuseffekte, die die Fähigkeiten der Gegner verändern. Das wichtigste davon ist Schock, der Waffen nach dem Zufallsprinzip deaktiviert. Der Schock kann durch Verwendung eines zusätzlichen Würfels und „Brennen“ entfernt werden, wodurch die Würfel in Brand gesetzt werden. Während die Würfel brennen, können sie verwendet werden, aber jede Verwendung kostet 2 Gesundheitspunkte. Das macht ein kluger Handwerker, wenn ich all seine Waffen und Würfel schockiere und verbrenne:


Natürlich gibt es noch viel mehr im Spiel, aber um eine allgemeine Vorstellung zu bekommen, reicht dies aus.

Unsere Aufgabe: Wie kann die KI die beste Aktion für ihren Zug auswählen? Wie kann er herausfinden, welche der brennenden Würfel gelöscht werden sollen, welcher Würfel zur Schocklinderung verwendet werden soll und welcher für wichtige Waffen aufbewahrt werden soll?

Wie zuvor

Lange Zeit hatte die KI in Dicey Dungeons nur eine Regel: Er betrachtete alle Waffen von links nach rechts, bestimmte den besten Würfel, der für ihn verwendet werden konnte, und verwendete ihn dann. Das hat super geklappt, aber es gab Ausnahmen. Also habe ich neue Regeln hinzugefügt.

Zum Beispiel habe ich den Schock bewältigt, indem ich mir alle Waffen angesehen habe, die keinem Schock ausgesetzt waren, und ausgewählt habe, welchen Würfel ich verwenden würde, wenn der Schock entfernt wurde, und diesen Würfel dann als "reserviert" für die Zukunft markiert. Ich habe mit brennenden Würfeln wie diesen gearbeitet: Ich habe geprüft, ob ich genug Gesundheit habe, um sie zu löschen, und zufällig ausgewählt, ob ich das tun soll.

Ich fügte Regel für Regel für alles hinzu, was ich mir vorstellen konnte, und als Ergebnis bekam ich eine KI, die zu funktionieren schien! Tatsächlich ist es erstaunlich, wie gut sich diese Verflechtung verschiedener Regeln gezeigt hat - die KI in Dicey Dungeons trifft möglicherweise nicht immer die richtige Entscheidung, war aber immer zumindest akzeptabel. Zumindest für ein Spiel, das sich noch in der Entwicklung befindet.

Aber im Laufe der Zeit begann das System, ständig neue Regeln hinzuzufügen, aus allen Nähten zu knacken. Die Leute haben Exploits entdeckt, die KI dazu gebracht haben, sich dumm zu verhalten. Mit dem richtigen Ansatz könnten Sie beispielsweise einen der Bosse überlisten, damit er den Spieler niemals angreift. Je mehr Regeln ich hinzufügte, um die Situation zu korrigieren, desto seltsamer wurden Dinge - einige Regeln gerieten in Konflikt mit anderen, Grenzfälle tauchten auf.

Eine der Lösungen bestand natürlich darin, neue Regeln hinzuzufügen, jede Aufgabe einzeln zu betrachten und neue if-Konstrukte zu erstellen, um sie zu verarbeiten. Aber ich denke, dass ich auf diese Weise einfach die wahre Lösung des Problems beiseite geschoben habe. Die Einschränkung des Systems bestand darin, dass es nur eine Frage betraf: "Was wird mein nächster Schritt sein?" Sie schaute nie nach vorne und versuchte nicht vorzuschlagen, was aus einer bestimmten intelligenten Kombination entstehen könnte.

Also habe ich beschlossen, wieder von vorne zu beginnen.

Klassische Lösung

Versuchen Sie, nach Informationen über KI für Spiele zu suchen, und wahrscheinlich werden Sie als Erstes auf eine klassische Lösung stoßen - die Erstellung eines Minimax- Algorithmus. Hier ist ein Video darüber, wie es bei der Entwicklung von KI für Schach verwendet wird:


Die Minimax-Implementierung lautet wie folgt:

Zunächst erstellen wir die einfachste, abstrakte Version unseres Spiels, in der alle erforderlichen Informationen für einen bestimmten Zeitpunkt im Spiel enthalten sind. Wir werden es ein Board nennen . Im Falle von Schach sind dies die aktuellen Positionen aller Figuren. Im Fall von Dicey Dungeons ist dies eine Liste von Würfeln, Waffen und Statuseffekten.

Dann erstellen wir eine Wertefunktion , die misst, wie gut das Spiel für eine bestimmte Spielkonfiguration, dh für ein bestimmtes Brett, spielt . Beispielsweise wird im Schach ein Brett, auf dem sich die Figuren in ihrer ursprünglichen Position befinden, mit 0 Punkten bewertet. Das Brett, auf dem Sie den Bauern Ihres Gegners gegessen haben, hat einen Wert von 1 Punkten, und das Brett, auf dem Sie Ihren eigenen Bauern verloren haben, hat einen Wert von -1 Punkten. Und das Brett, auf dem wir den Gegner schachmatt gesetzt haben, wird mit einer unendlichen Anzahl von Punkten bewertet, oder so ähnlich!

Dann simulieren wir von diesem abstrakten Brett aus alle möglichen Bewegungen, die wir machen können, was uns neue abstrakte Bretter gibt. Dann simulieren wir den Abschluss aller möglichen Bewegungen auf diesen Brettern und so weiter, so viele Schritte wie Sie möchten. Hier ist eine hervorragende Illustration einer ähnlichen Lösung von freecodecamp.org :


Wir erstellen ein Diagramm aller möglichen Züge, die beide Spieler ausführen können, und wenden eine Wertefunktion darauf an, um den Spielverlauf zu bewerten.


Und darin unterscheidet sich Dicey Dungeons von Minimax: Minimax stammt aus der mathematischen Theorie der Spiele und wurde entwickelt, um die beste Reihe von Zügen der Welt zu finden, bei denen der Gegner versucht, seine Punktzahl zu maximieren. Der Algorithmus wird so genannt, weil er die Verluste des Spielers minimiert, wenn der Gegner spielt, um seine Gewinne zu maximieren.

Aber was passiert in den Dicey Dungeons? Eigentlich ist es mir egal, was mein Gegner tut. Damit das Spiel spannend wird, reicht es für die künstliche Intelligenz aus, logische Schritte zu unternehmen - um den besten Weg zu finden, die Würfel auf Waffen anzuwenden, damit der Kampf fair ist. Mit anderen Worten, für mich ist nur „max“ wichtig, ohne „mini“.

Das heißt, damit die AI Dicey Dungeons einen guten Zug machen können, reicht es mir, diese Grafik möglicher Züge zu erstellen, das Brett mit der höchsten Punktzahl zu finden und dann die Züge zu machen, die zu diesem Punkt führen.

Die leichte Bewegung des Feindes

Kommen wir zu den Beispielen! Schauen wir uns den Frosch noch einmal an. Wie kann sie entscheiden, was als nächstes zu tun ist? Woher weiß sie , dass die gewählte Aktion die beste ist?


Tatsächlich hat sie nur zwei Möglichkeiten. Platziere 1 auf dem breiten Schwert und 3 auf dem Schild oder mache das Gegenteil. Sie entscheidet offensichtlich, dass es besser ist, 3 statt 1 zu setzen. Aber warum? Weil sie alle möglichen Ergebnisse studiert hat:


Wenn Sie 1 auf das Schwert setzen, erhalten wir 438 Punkte. Wenn Sie 3 darauf setzen, erhalten wir 558 Punkte. Großartig! Wenn ich also Schwert 3 platziere, bekomme ich mehr Punkte. Das Problem ist gelöst.

Woher kommen diese Brillen? Das Bewertungssystem in Dicey Dungeons berücksichtigt derzeit die folgenden Aspekte:

• Schaden: Der wichtigste Faktor sind 100 Punkte für jeden verursachten Schadenspunkt.
• Gift: Ein wichtiger Statuseffekt, den die KI für fast genauso wichtig hält wie den Schaden - 90 für jedes Gift.
• Erstellen anderer Statuseffekte: z. B. Schock, Brennen, Schwächen usw. Jeder von ihnen kostet 50 Punkte.
• Bonusstatus-Effekte: Das Hinzufügen positiver Statuseffekte wie Verteidigung und dergleichen zum Spieler selbst kostet jeweils 40 Punkte.
• Einsatz von Waffen: Die Verwendung einer beliebigen Art von Waffe kostet 10 Punkte, denn wenn nichts anderes gelingt, muss die KI nur versuchen, alles zu verwenden.
• Countdown-Reduzierung: Um einige Waffentypen zu aktivieren (z. B. für Pea Shooter), reicht der Gesamtbetrag der Würfel gerade aus. Daher erhält die KI 10 Punkte für jeden Countdown-Punkt, den sie reduziert.
• Punkte auf Würfeln: Die KI erhält 5 Punkte für jeden nicht verwendeten Punkt auf den Würfeln, d. H. 1 kostet 5 Punkte und 6 kostet 30 Punkte. Dies geschieht, damit die KI keine Würfel verwenden möchte, die Sie nicht benötigen, sodass ihre Bewegungen den menschlichen sehr ähnlich werden.
• Dauer: KI verliert 1 Punkt pro Spielzug, daher haben lange Züge etwas weniger Wert als kurze. Dies geschieht so, dass die KI bei zwei Bewegungen, die ansonsten gleichwertig sind, die kürzeste auswählt.
• Behandlung: Es kostet nur 1 Punkt für einen wiederhergestellten Gesundheitspunkt, denn obwohl ich möchte, dass die KI dies für wichtig hält, habe ich meine Gesundheit nicht wirklich überwacht. Es gibt immer Dinge zu tun und wichtiger!
• Bonuspunkte: Sie können zu jeder Bewegung hinzugefügt werden, um die KI zu etwas zu zwingen, was er sonst niemals getan hätte. Sehr mäßig verwendet.

Und schließlich gibt es zwei Sonderfälle: Wenn dem angegriffenen Ziel die Gesundheit ausgeht, kostet es eine Million Punkte. Wenn die Gesundheit mit der KI endet, kostet sie minus eine Million Punkte. Dies bedeutet, dass sich die KI niemals versehentlich selbst tötet (z. B. indem sie den Würfel mit sehr geringer Gesundheit auszahlt), oder dass sie niemals einen Zug verpasst, in dem sie den Spieler töten kann.

Diese Zahlen sind nicht ideal - nehmen Sie zum Beispiel die aktuell offenen Ausgaben: 640 , 642 , 649 , aber das ist nicht sehr wichtig. Selbst annähernd genaue Zahlen reichen aus, um die KI zu mehr oder weniger korrekter Arbeit anzuregen.

Schwierigere Bewegungen des Feindes

Der Froschkoffer ist so einfach, dass selbst mein schrecklicher Code alle Optionen in nur 0,017 Sekunden herausfinden kann. Aber dann wird die Situation komplizierter. Schauen wir uns noch einmal das Beispiel des Alleskönners an.


Der Entscheidungsbaum ist „etwas“ komplizierter:


Leider tritt selbst in relativ einfachen Fällen ziemlich schnell ein Komplexitätsschub auf. In diesem Fall erhalten wir in unserem Diagramm 2.670 Knoten, die untersucht werden müssen, und dies dauert viel länger als im Fall eines Frosches - vielleicht ein oder zwei Sekunden.

Dies ist größtenteils auf die kombinatorische Komplexität zurückzuführen. Beispielsweise spielt es keine Rolle, welche der beiden Methoden wir verwenden, um den Schock zunächst zu lindern. Der Algorithmus betrachtet dies als zwei separate Lösungen und erstellt für jede einen vollständigen Baum von Verzweigungslösungen. Als Ergebnis erhalten wir einen Zweig, dessen Vervielfältigung völlig unnötig ist. Es gibt auch ähnliche kombinatorische Probleme bei der Auswahl von Blöcken zum Einlösen, zum Entfernen von Schocks von Waffen und beim Verfahren für deren Verwendung.

Aber selbst wenn wir solche unnötigen Zweige finden und optimieren (was ich bis zu einem gewissen Grad tue), wird es immer einen Punkt geben, an dem die Komplexität aller möglichen Permutationen von Lösungen zu riesigen, langsamen Entscheidungsbäumen führt, deren Bewertung unendlich lange dauern wird. Dies ist also das erste ernsthafte Problem dieses Ansatzes. Hier ist noch einer:


Hauptschlüssel. Teilt den Würfel in zwei Teile.

Diese wichtige Art von Waffen (und ähnliche) verursacht KI-Probleme, da das Ergebnis ihrer Verwendung ungewiss ist . Wenn ich eine Sechs drauf lege, kann ich fünf und eins oder vier und zwei oder vielleicht zwei Dreifache bekommen. Ich werde das erst wissen, wenn ich es tue. Daher ist es sehr schwierig, einen Plan zu erstellen, der dies berücksichtigt.

Glücklicherweise hat Dicey Dungeons eine großartige Lösung für diese beiden Probleme!

Moderne Lösung

Die MCTS-Methode (Monte Carlo Tree Search) ist ein probabilistischer Entscheidungsalgorithmus. Im Folgenden finden Sie ein etwas seltsames Video, das das Prinzip der Entscheidungsfindung nach der Monte-Carlo-Methode dennoch sehr gut erklärt:


Anstatt jede mögliche Bewegung zum Diagramm hinzuzufügen, überprüft MCTS die Sequenzen zufälliger Bewegungen und verfolgt dann diejenigen, die sich als besser erwiesen haben. Dank einer Formel namens Upper Confidence Bound kann er auf magische Weise bestimmen, welche Zweige des Entscheidungsbaums die „vielversprechendsten“ sind:


Diese Formel habe ich übrigens einem sehr nützlichen Artikel über die Suche nach Bäumen mit der Monte-Carlo-Methode entnommen . Frag mich nicht, wie es funktioniert!

Das Erstaunliche an MCTS ist, dass wir, um die beste Lösung zu finden, normalerweise nicht alles dumm durchsuchen müssen und dasselbe abstrakte Board / Move-Simulationssystem wie bei Minimax verwenden können. Das heißt, wir verwenden beide Algorithmen. Dies ist genau das Schema, das ich in Dicey Dungeons verwendet habe. Zunächst versucht sie, eine vollständige Bereitstellung des Entscheidungsbaums abzuschließen, was normalerweise nicht viel Zeit in Anspruch nimmt und zum besten Ergebnis führt. Wenn der Baum jedoch zu groß erscheint, verwenden wir wieder MCTS.

MCTS hat zwei sehr coole Funktionen, die perfekt für Dicey Dungeons sind:

Erstens arbeitet die Methode ideal mit Unsicherheit. Da es immer wieder ausgeführt wird und Daten aus jedem Lauf sammelt, lasse ich es einfach undefinierte Bewegungen simulieren, beispielsweise mit einem Hauptschlüssel, auf natürliche Weise, und nach vielen Läufen erstellt die Methode einen ziemlich korrekten Bereich von Punkten, die als Ergebnis dieser Bewegung erhalten werden.

Zweitens kann er mir eine Teillösung geben. Wenn Sie mit MCTS arbeiten, können Sie so viele Simulationen durchführen, wie Sie möchten. Wenn es endlos ausgeführt wird, konvergiert es theoretisch zu genau den gleichen Ergebnissen wie Minimax. Wichtiger für mich ist jedoch, dass ich mit MCTS in begrenzter Zeit eine gute Lösung finden kann. Je mehr Suchvorgänge wir durchführen, desto besser wird die „Lösung“ gefunden. Bei Dicey Dungeons reichen jedoch oft nur einige hundert Suchvorgänge aus, die einen Bruchteil einer Sekunde dauern.

Interessante verwandte Themen

So entscheiden die Feinde in den Dicey Dungeons, wie sie dich töten sollen! Ich möchte dieses System zur nächsten Version des Spiels v0.15 hinzufügen!

Woher kommen die Grafiken, die ich gezeigt habe, auch auf Twitter:


Ich habe sie erstellt, indem ich einen Exporter für GraphML geschrieben habe , ein Open-Source- Grafikdateiformat , das von vielen verschiedenen Tools gelesen werden kann. (Ich habe das ausgezeichnete yEd verwendet , das ich sehr empfehlen kann.)

Ein Teil der Lösung für dieses Problem bestand darin, der KI die Simulation von Bewegungen zu ermöglichen, was an sich schon ein interessantes Rätsel ist. Als Ergebnis habe ich ein Action-Scripting-System implementiert. Jetzt, wo die Gegner verschiedene Arten von Waffen benutzen. Sie führen diese kleinen Skripte aus:


Diese kleinen Skripte werden vom hscript- Parser und Ausdrucksinterpreter basierend auf haxe ausgeführt. Dieser Teil war schwer zu implementieren, aber der Aufwand hat sich gelohnt: Das Spiel war sehr praktisch für die Erstellung von Mods. Ich hoffe, dass die Leute nach der Veröffentlichung des Spiels mit diesem System ihre eigenen Waffen entwickeln können, das heißt, sie können dem Spiel fast alles hinzufügen, was sie sich vorstellen können. Da die KI klug genug ist, um alle auf sie übertragenen Aktionen zu bewerten, können die Feinde außerdem herausfinden, wie sie die von den Spielern erstellten modifizierten Waffen verwenden können!