Komplexe Spiel-KI für rundenbasierte Strategiespiele

26

Ich recherchiere für ein rundenbasiertes Strategiespielprojekt und suche nach guten Ressourcen zu diesem Thema. Das Spiel ist ein typisches Kriegsspiel, in dem Länder gegeneinander kämpfen, Einheiten aufstellen und diese Einheiten auf einer sechseckigen Karte bewegen, sich gegenseitig angreifen usw. können.

Mich interessiert besonders, wie die KI von Civilization V organisiert ist! Laut Wikipedia verwendet das Spiel vier verschiedene KI-Systeme für verschiedene Ebenen der KI des Spiels:

  • taktische KI steuert einzelne Einheiten
  • Die operative KI überwacht die gesamte Kriegsfront
  • Die strategische KI verwaltet das gesamte Reich
  • Die große strategische KI setzt langfristige Ziele und bestimmt, wie das Spiel gewonnen werden soll

Konzeptionell sieht es so aus, als wäre es sehr sinnvoll, eine komplexe KI zu erreichen, und es macht mich neugierig, herauszufinden, wie diese verschiedenen KI-Systeme funktionieren (und zusammenarbeiten). Die taktische KI ist wahrscheinlich am einfachsten zu verstehen, da sie die Entscheidungsfindung für eine einzelne Einheit (Bewegen, Angreifen, Reparieren, Zurückziehen usw.) übernimmt, aber ich denke, die anderen KI-Systeme sind dort, wo es wirklich interessant wird. Was macht zum Beispiel die operative KI und wie macht sie das? Ich bin mir sicher, dass dies die bestgehüteten Geheimnisse von Firaxis Games sind, aber es wäre cool, eine Diskussion darüber zu beginnen, um mehr darüber zu erfahren.

Auch wenn jemand gute Bücher kennt, die sich mit rundenbasierter Strategiespiel-KI befassen, wäre es gut zu wissen. Offensichtlich ist dies ein spärlich besetztes Thema im Web. Ich habe "Programming Game AI by Example" erhalten, aber in diesem Buch geht es mehr um die Verhaltens-KI einzelner Agenten als um eine hochrangige zielorientierte KI.

BadmintonCat
quelle

Antworten:

19

Obwohl ich dem ersten Absatz von DampeS8N zustimme (dh, die KI des Spiels muss nur so schlau sein, dass der Spieler denkt, dass sie schlau ist), muss diese Frage meines Erachtens noch etwas genauer erörtert werden. Die verwendeten Datenstrukturen könnten FSMs für alle Ebenen sein, aber das beantwortet nicht wirklich die Frage, wie die einzelnen Systeme funktionieren.

Haftungsausschluss: Ich habe die Civilization-Spiele kaum gespielt, daher ist mein Verständnis des Gameplays eingeschränkt. Bei offensichtlichen Fehlern bitte ich um Entschuldigung. Bitte korrigieren Sie mich, und ich werde gerne bearbeiten.

Ich werde Zitate aus dem ursprünglichen IGN-Artikel nehmen .

1. Taktische KI

Auf der untersten Ebene nutzt die taktische KI die vorhandenen Kräfte, um einen Kampf auf lokaler Ebene zu gewinnen.

Dies ist wahrscheinlich der Standardteil des Subsystems. Es gibt unbegrenzte Möglichkeiten, dies durch die Verwendung von FSMs, Verhaltensbäumen (oder sogar durch zufällige Aktionen, je nach Schwierigkeitsgrad der KI) zu erreichen.

Da es sich jedoch um ein rundenbasiertes Spiel handelt, das dem Risiko ähnelt, ist es meiner Meinung nach wahrscheinlicher, dass jeder Einheit eine Punktzahl zugewiesen wird. Abhängig von verschiedenen Variablen (Zugehörigkeiten, Geländeboni usw.) sind an diese Punktzahl Multiplikatoren angehängt.

Das Ergebnis wird dann folgendermaßen berechnet:

If (AI unit score >> (much greater) enemy unit score) Then Completely destroy enemy unit
If (AI unit score > (somewhat greater) enemy unit score) Then Partially destroy enemy unit
If (AI unit score < (somewhat less) enemy unit score) Then Partially destroy AI unit
If (AI unit score << (much less) enemy unit score) Then Completely destroy AI unit

Es ist sinnvoll, dass die KI versucht, diese Punktzahl im Kampf zu maximieren.

Addiere einen Epsilon-Wert (zB kleine zufällige Chance auf Misserfolg / Erfolg) und du hast eine ziemlich anständig aussehende KI (niemand will einen perfekten Gegner, das macht einfach keinen Spaß!).

2. Operative KI

Einen Schritt weiter wählt die operationelle KI die zu bekämpfenden Kämpfe aus und stellt sicher, dass die erforderlichen Kräfte verfügbar sind.

Ich denke, dazu gibt es ein paar Punkte:

  • Bewertung der Stromstärke
  • Verstärkung der Einheiten
  • Bewerten, welche Kämpfe zu wählen / zu vermeiden sind

Aktuelle Stärke auswerten - Das schreit mir nur nach Influence Map . Es kann leicht auf einem Hex-Raster dargestellt werden. Da dieses Subsystem kampforientiert ist, können die Einflusswerte für die Stärkewerte jeder Einheit in der Nähe repräsentativ sein. Wenn Sie eine massive Armee haben, die sich auf ein kleines Gebiet mit Sechsecken konzentriert, ist der Einflusswert sehr groß und die operationelle KI berücksichtigt dies bei der Bewertung der Kämpfe, die ausgewählt werden sollen. Vergessen Sie nicht, dass auch die Einflusswerte der gegnerischen Armeen berechnet werden. Auf diese Weise kann die operative KI potenzielle eingehende Bedrohungen vorhersagen.

Verstärkung von Einheiten - Indem die KI Informationen über gegnerische Fraktionen von der Einflusskarte erhält, kann sie feststellen, welche Einheiten der größten Bedrohung ausgesetzt sind. Die KI kann dann nahegelegenen Einheiten den Befehl erteilen, die bedrohten Parteien zu verstärken.

Bewertung, welche Kämpfe zu wählen / zu vermeiden sind - Hier können einige Situationen auftreten. Wenn die KI erkennt, dass eine Einheit bedroht ist UND es keine Einheiten in der Nähe gibt, die ihr helfen könnten, a) beschließen Sie, die Einheit zu opfern (wenn es sich nur um eine geringe Infanterie handelt, anstelle eines unersetzlichen Generals) oder b) bestellen Sie die Einheit zurückziehen. Umgekehrt könnte die KI, wenn sie eine schwache feindliche Einheit in der Nähe einer Armee entdeckt, die Einheiten anweisen, diesen Feind auszuschalten.

Hier ist ein anständiges Dokument , das Einflusskarten in Echtzeit-Strategiespielen verwendet.

3. Strategische KI

Die strategische KI bewegt sich noch weiter nach oben und verwaltet das Imperium als Ganzes. Sie konzentriert sich darauf, wo Städte gebaut werden und was mit ihnen zu tun ist.

"Wo soll ich eine Stadt bauen?" klingt nur nach Positionsbewertung. Schachprogramme und andere Spiele bestimmen damit, ob eine bestimmte Position wünschenswert ist. Beispielsweise:

Verhexung A: In der Nähe von Ressourcen, im Hochland, in der Nähe von Verbündeten, in der Nähe des Feindes

Die Positionsbewertungsfunktion könnte diese drei Faktoren wie folgt annehmen:

Score = Proximity to resources (closer yields a higher score) + 
terrain elevation (higher yields higher score) + 
proximity to allies (closer is better) + 
proximity to enemies (farther is better)

Und welches Sechseck die höhere Punktzahl hat, wird der Ort sein, an dem die Stadt gebaut wird. Weitere Informationen zu Auswertungsfunktionen finden Sie hier .

Ich gehe davon aus, dass die strategische KI auch eine Reihe von vorgefertigten Pseudostrategien im Spiel hat, abhängig von der Art des Sieges, den die KI anstrebt.

4. Große strategische KI

An der Spitze der Leiter befindet sich die große strategische KI, die entscheidet, wie das Spiel gewonnen wird.

Ich denke, dies ist wahrscheinlich das einfachste und es macht den Eindruck, dass es beeindruckender ist, als es wirklich ist. In einem solchen Spiel wird es nur eine begrenzte Anzahl von Siegertypen geben. In dem Artikel wird ein Eroberungssieg erwähnt, vorausgesetzt, es gibt auch Bündnissiege usw. Es könnte so einfach sein, einen der Typen zufällig auszuwählen und ihn dann an die anderen Systeme weiterzugeben.

EDIT: Natürlich könnte, wie von DampeS8N hervorgehoben, die Art der Karte die beste Siegbedingung vorgeben. In diesem Fall könnte sie von den Designern oder einer Art Bewertungsfunktion unter Berücksichtigung verschiedener Variablen fest codiert werden.

Zusammenfassung
Ich denke, was wirklich wichtig an dieser Art von System ist, ist, dass die Subsysteme so geschichtet sind, dass sie eigentlich nicht viel miteinander kommunizieren müssen. Es scheint sich um eine Top-Down-Architektur zu handeln, bei der die Komponenten lose miteinander verbunden sind. Vom technischen Standpunkt aus gesehen ist es klar und flexibel und lässt sich wahrscheinlich von Emergent Behavior und / oder Subsumption Architecture inspirieren .

Ich entschuldige mich wirklich für die Länge dieses Beitrags, er hat sich in ein Biest verwandelt :(

Wie auch immer, ich hoffe es hilft!

Ray Dey
quelle
2
"Ich denke, das ist wahrscheinlich das einfachste von allen, und es macht den Eindruck, dass es beeindruckender ist, als es wirklich ist." Ich wäre mir nicht sicher. Es gibt einen Unterschied zwischen der bloßen Entscheidung, einen Eroberungssieg anzustreben, und der Entscheidung, wem der Krieg erklärt werden soll, ob wir überfordert sind und um Frieden bitten müssen, welches Ziel am schwächsten anzugreifen ist, welche Einheiten wir bauen und erwerben müssen die richtigen strategischen Ressourcen unserer Armee stärker zu machen, einen Weg zu finden zwei Feinde zu führen , sie zu bekämpfen usw. Diese Phase ist viel komplizierter , als Sie ihm Kredit für geben.
Nicol Bolas
1
Wow, und ich dachte, meine Antwort würde langsam lang. LOL. Gute Show.
DampeS8N
1
Eine bemerkenswerte Sache ist, dass Civ absolut keine einfachen Siegbedingungen hat. Es gibt viele Möglichkeiten zu gewinnen. Wunder bauen, Wissenschaft vorantreiben, Eroberung, Diplomatie usw. Die Auswahl der richtigen Optionen ist oft sehr schwierig und kann sich je nach den Bedingungen auf der Karte ändern. Sie werden beispielsweise feststellen, dass jemand, den Sie gerade kennengelernt haben, in der Wissenschaft weit vor Ihnen liegt, und Sie müssen diesen Weg verlassen und sich mit einem neuen zufrieden geben. Oft hängt der Erfolg davon ab, dass Sie Ihre Optionen so lange wie möglich offen halten.
DampeS8N
@NicolBolas es mag durchaus komplexer sein, aber alle Punkte, die Sie angesprochen haben, scheinen Verantwortlichkeiten für die unteren Ebenen der KI zu sein. Entscheiden, wem der Krieg erklärt werden soll -> Operativ. Welches Ziel ist am schwächsten anzugreifen -> Operational / Tactical. Richtige Ressourcen beschaffen -> Operativ / Strategisch. Dies ist völlig vermutet, aber es wäre sinnvoll, wenn die unteren Systeme für die spezifischen Strategien verantwortlich sind, um die niedrigste Kopplungsstufe zu gewährleisten.
Ray Dey
1
@RayDey: Die höchste Ebene der KI muss in Sachen Ressourcenbeschaffung involviert sein, weil sie entscheiden muss, wie sie beschafft werden soll. Die Diplomatie könnte es bekommen. Das Erweitern auf die Ressource könnte es bekommen. Die Operationsebene ist nicht der richtige Ort, um zu entscheiden, ob man sich im Gegensatz zu anderen Taktiken darum streiten soll. Kopplung ist eine Notwendigkeit für ein Spiel wie Civilization; Alles wirkt sich auf alles in diesem Spiel aus. Sie können keine effektive KI haben, die Entscheidungen ohne viel Kopplung trifft. Obwohl das erklären könnte, warum die KI von Civ V ... nicht besonders hell ist;)
Nicol Bolas
9

Im Allgemeinen sollte KI in Spielen nicht als „komplex“ angesehen werden. Es geht darum, mit möglichst geringem Aufwand das zu erreichen, was Sie wollen. Der Name des Spiels ist Emergence.

In diesem Fall ist Ihre grundlegende Konzeptualisierung falsch. Diese 4 Systeme müssen überhaupt nicht zusammenarbeiten. Sie müssen nur so aussehen wie sie. Sie können auch viel weniger sein, als Sie denken, dass sie sein müssen.

Sie haben auch die Reihenfolge der Schwierigkeitsgrade umgekehrt. Die härteste Komponente der Zivilen KI ist die taktische KI, dicht gefolgt von der Operativen. Strategisch ist wahrscheinlich sehr einfach, und die große KI ist wahrscheinlich noch einfacher.

Die Kommunikation zwischen Komponenten ist mehr wie ein System von Grunzgeräuschen und weniger wie echte Kommunikation. Von High Level zu Low Level würde es so aussehen:

Grand AI

den Zustand der Karte einschätzen. Angesichts des Wissens der KI (das alles sein könnte oder nur das, was sie hätte, wenn sie ein Spieler wäre), entscheidet sie, welches Endziel am schnellsten zu erreichen ist. Es ist wahrscheinlich eine Finite-State-Maschine , die einige Zahlen knirscht und ein Ziel auswählt. Möglicherweise ist es etwas Exotischeres; ein genetischer Algorithmus oder möglicherweise ein Bayes-basierter Doohickey . Es brummt dann eine Botschaft wie "mehr Wissenschaft" nieder.

Strat AI

Dann wird untersucht, welche Informationen verfügbar sind, um mit diesen zu arbeiten. Es geht darum, dieses allgemeine Ziel zu erreichen, aber auch um detailliertere Aspekte des Spiels. Führe ich krieg Habe ich hungernde Menschen? bald. Es ist wahrscheinlich auch eine Finite-State-Maschine , möglicherweise eine Fuzzy-Logik (die in Wirklichkeit nur eine Weiterentwicklung einer FSM ist). Nehmen wir an, es handelt sich um eine einfache FSM. Die obigen Fragen werden in einer Reihenfolge gestellt, in der anhand bestimmter Kriterien entschieden wird, dass in dieser Runde verschiedene Dinge geschehen müssen. Ich bin im Krieg, verteile Geld für die Ausbildung von Soldaten. Meine Leute hungern, bauen hier einen Getreidespeicher, anstatt etwas Wissenschaftliches zu bauen.

Die Auswahl der Einheiten, die gebaut werden sollen, kann Teil von Strat AI oder Op AI sein, je nachdem, wie wir die Dinge aufteilen.

Op AI

wird die Einheiten, die verfügbar sind, nehmen und sie zuweisen, um in verschiedene Fronten des Krieges zu bewegen. Es wird die Gesamtform des Konflikts bestimmen, in die sich neue Einheiten begeben, sobald sie eingesetzt werden. Es ist wahrscheinlich auch ein FSM. Es kann sein, dass der Feind an Front A mit schwachen Einheiten gegen Unit B angreift und dort mehr Einheiten Bs sendet, als an die andere Front, die gegen Unit B stark ist. Es werden allgemeine Befehle an die Einheiten im Allgemeinen ausgegeben. Angriff nach Belieben. Rückzug. Bald.

Taktische KI

ist einheitenspezifisch. Jeder Gerätetyp reagiert unterschiedlich auf die allgemeine Reihenfolge. Eine Einheit, die zum Selbstmord bestimmt ist, kann einen Rückzugsbefehl ignorieren. Einheiten, die Trottel sind, können sich auch dann zurückziehen, wenn sie zum Kampf aufgefordert werden. Civ ist in solchen Dingen normalerweise sehr sparsam. Im Allgemeinen folgen alle Einheiten in Civ ihren Befehlen. In Anbetracht der größeren Ordnung, in der sie sich befinden, sind sie (siehe Muster hier?) Ein FSM. Bin ich verletzt Ich sollte mich zurückziehen und gesund werden. Habe ich an diesem Ort einen Vorteil? Attacke. Bin ich zu nah dran um anzugreifen? Zieh dich zurück. Und die Komplexität dieses FSM muss nicht viel größer sein als diese drei Dinge, um effektiv und überzeugend wie intelligent zu sein.

Kann dies verbessert werden?

Ja natürlich. Die Frage ist, ob die Spieler es merken werden. Und 99% der Zeit werden sie nicht.

Nun, das ist alles Entscheidungsfindung AI. Hier sind andere KI-Subsysteme im Spiel. Es gibt einen A * - oder einen anderen Pfadfindungsalgorithmus, mit dem Einheiten den kürzesten Pfad zu einem Ort finden können. Es gibt Algorithmen, um den besten Ort zu finden, um neue Städte zu gründen. Bald. Es gibt oft Gruppen mit KI, und oft sind sie wirklich komplexer als der denkende Teil der KI. Tatsächlich ist der Code zum Finden der Antworten auf die Fragen, die der FSM stellen muss, oft um Größenordnungen komplexer als der FSM selbst. Wie genau entscheidet man das?

DampeS8N
quelle
Doohicky aus Bayes - großartig
Brian Broom