Entwicklung einer listigen KI in einem taktischen Spiel, das auf Heuristiken und Mutationen basiert

In taktischen Spielen ist KI sehr wichtig. Wenn KI als „künstlicher Idiot“ angesehen wird, kann das Spiel durch erstaunlichen Multiplayer, Handlung, Atmosphäre und Grafik gerettet werden (dies ist ungenau). Die Lösung liegt auf der Hand: Machen Sie eine gute KI, was könnte das Problem sein?


Im Detail. Im Folgenden sind meine Schritte zum Aufbau einer starken KI mit Charakter aufgeführt. Nicht super stark [ 1 ], aber in der Lage, schnell lokal in einem gefräßigen Browser eines mittelschwachen PCs zu arbeiten. Ich habe den Ansatz von Expertensystemen unter Verwendung einer Reihe von Heuristiken und Mutationen angewendet. Es werden 15 Schritte der schrittweisen Transformation der KI beschrieben, wobei jeder der Schritte zu spüren ist.

Kurzbeschreibung

In einem experimentellen Browsergame basiert die KI auf der Erzeugung vieler möglicher Zustände - den Ergebnissen des aktuellen Zuges. (Aufgrund der Spielspezifikationen und der Bequemlichkeit werden diese resultierenden Zustände im Artikel je nach Kontext entweder Turn-Szenarien oder KI-Strategien genannt .) Dann werden die Szenarien des Kurses mutiert. Gemäß den erhaltenen Szenarien werden die Schätzungen des "Erfolgs" berechnet. Am erfolgreichsten und von einem Computer-Spieler durchgeführt.

Beispielsweise werden drei Strategien generiert:

1. Laufen Sie hektisch vorwärts und greifen Sie alle an, die den Arm hochdrehen. Punkte des Endzustands: 37000 Punkte.
2. Greife Bogenschützen aus sicherer Entfernung an, während sich der Rest in den Ecken versteckt. 45000 Punkte.
3. Alle ziehen sich zurück, gruppieren sich und verstecken sich vor Feinden. Wenn Sie einen Feind aus sicherer Entfernung verletzen können, greifen Sie an. 18000 Punkte.
4. In diesem Fall wird die 2. Strategie ausgewählt.

Nun, alles scheint Standard zu sein. Nicht wirklich.

Der gesamte Zellstoff ist, wie die Skripte generiert werden und wie der Wertkoeffizient des Skripts berechnet wird. In einem von ihnen auferlegen, und das Ergebnis wird Sie traurig machen.

Spielregel

Der Spieler und die KI haben anfangs 6 identische Einheiten an den Ecken. Jedes Team wechselt sich abwechselnd mit allen Einheiten gleichzeitig ab. Optionen für den Fortschritt jeder Einheit:

• einen Zug überspringen;
• bewege dich und überspringe;
• Bewegen Sie sich und greifen Sie an ( Sie können und müssen manchmal Ihre eigenen angreifen ).

Das Spielfeld und die Zusammensetzung des Teams werden prozedural generiert ( dh zufällig, jedoch mit Durchgängigkeitsprüfungen und akzeptablem "Takt" ). Einheitentypen:

1. Fighter F, Nahkampfeinheit mit der größten Überlebensfähigkeit, dem größten Schaden und der größten Mobilität. Eine Art Panzer + Schaden.
2. Bogenschütze A, der niedrigste Schaden, aber der Angriff erfolgt in einer geraden Linie in einer Entfernung von 1-7.
3. Zauberer W stirbt mit einem Schlag eines Kämpfers, aber der Angriff erfolgt in einer Entfernung von 1-5 in einer geraden Linie durch alle Einheiten.

Das Spielfeld ist immer 10 * 10 groß.

Mögliche Felder auf der Karte:

• Erde - legt keine Einschränkungen fest.
• Wand - durch sie kann man weder schießen noch passieren.
• Wasser - es ist unmöglich, es zu passieren, aber ein Bogenschütze kann hindurchschießen (ein feuriger Magier kann es nicht ).

Das Spiel ist vollständig bestimmt, das heißt, es enthält kein Zufallselement (100% Trefferchance, kein kritischer Schaden usw.). Es ist auch ein Spiel mit vollständigen Informationen, dh Rivalen wissen zu jeder Zeit alles über den Zustand der Truppen des jeweils anderen. Wie bei Dame.

KI ist stärker als ein Fleischspieler, aber letzterer auf der ersten Ebene hat ein Handicap in Form einer Einheit. Am 3. hat der Spieler im Gegenteil ein Handicap von einer Einheit und es ist viel schwieriger zu gewinnen (ich habe ungefähr 15% der Siege in dieser Phase). Dann kommt die eher zufällige Version von Game +.


Das Spiel wurde auf nativem Javascript entwickelt: auf Divs und CSS-Stilen, und dies war die unglücklichste mögliche Lösung [ 2 ]. Dies ist ein Browsergame. Der Motor wurde nicht benutzt. Das einzige Ziel des Projekts ist es, einen starken Computerspieler „mit Charakter“ zu schaffen und diesen Charakter zu ändern (Berechnung von Cyborgs, aggressiven Orks, tückischen Elfen, dummen Zombies).

Um den "Computerstil" des Feindes zu reduzieren, wurden einige Tricks angewendet:

• Der Spieler wartet nach seinem Zug nicht, bis die KI über seinen Zug nachdenkt. Der Feind beginnt „sofort“, seine Bewegungen auszuführen ( in Wirklichkeit ist dies eine Illusion ).
• Der Computerspieler steuert die Einheiten auch mit seinem Cursor ( und dies ist auch eine Illusion, der Cursor fliegt nur zur gleichen Zeit wie die Einheitenanimationen ).
• KI kann heimtückische Köder verwenden, um einen Kampf zu erzwingen ( alles ist fair ).

Und was ist so kompliziert?

Auf den ersten Blick scheint alles einfach zu sein: Sie können einfach alle Optionen aller Züge sortieren und die beste auswählen. Aber sehr bald wird klar, dass alles sehr schwierig ist.
Eine vollständige Aufzählung ist aufgrund des kombinatorischen Explosionseffekts [ 3 ] nicht möglich. Dies besteht darin, dass die Komplexität der Berechnungen mit zunehmender Anzahl der in den Szenarien überprüften Elemente exponentiell zunimmt. Als nächstes werde ich beschreiben, was dies in meinem speziellen Spiel bedeutet.

Erstens, weil In jeder Runde gehen die Teameinheiten alle auf einmal , dann kann ihre Reihenfolge unterschiedlich sein. Und mit 6 Einheiten im Team solcher Kombinationen wird 720 (1 * 2 * 3 * 4 * 5 * 6). Wenn es mehr Einheiten geben wird, wird es eine große Anzahl von Kombinationen geben (bei 7 - 5040, bei 8 - 40320 ...). Wenn Sie das maximale Ergebnis nicht berücksichtigen, riskiert der Spieler, das Vergnügen in Erwartung des nächsten Zuges für 5-10 Minuten auszuprobieren ( und wenn er hartnäckig ist, wird die Verzögerung auf Millionen von Jahren anwachsen, nicht jeder wird leiden ). Aufgrund dieser Eigenschaft ist meine KI zu Beginn des Kampfes weniger effektiv als am Ende. Gegen Ende ist bereits die Hälfte des Teams gestorben.


Zweitens kann sich jede Einheit zu verschiedenen Punkten der Karte bewegen . Kämpfer mit einem Bewegungsbereich von 4 können 1-41 verschiedenen Positionen ähneln. Für Zauberer und Bogenschützen mit einer Bewegung in 3 beträgt die mögliche Anzahl von Zügen 1-25. Zum Beispiel kann die Zusammensetzung des Teams sein: 4 Kämpfer, 1 Magier und 1 Bogenschütze. Wir erhalten die Summe der verschiedenen Kombinationen von Zügen für diesen Gegenstand: 41 * 41 * 41 * 41 * 25 * 25 = 1766100625. In der Realität gibt es aufgrund gegenseitiger Schnittpunkte und unpassierbarem Gelände weniger Kombinationen, aber in einer seltenen Situation mit „Streuung auf der Karte“ wird die Anzahl der Kombinationen sein nähere dich dieser Zahl.

Drittens kann jede Einheit nach der Bewegung eine Bewegung überspringen oder in eine von vier Richtungen angreifen. Das heißt, wir haben 5 mögliche endgültige Aktionen pro Einheit. Gesamtkombinationen: 5 ^ 6 = 15625.

Gesamtkombinationen: 720 * 1766100625 * 15625 = 19868632031250000.

Und in jeder gültigen Kombination müssen die Punkte des resultierenden Zustands berechnet werden. Die Bewertungsfunktion umfasst: Nachahmung von Bewegungen, Angriff, Verursachen von Schaden, Tod von Einheiten und Zählen der verbleibenden Trefferpunkte von Überlebenden. Natürlich ist die Anzahl der Kombinationen überbewertet, weil Unter realen Bedingungen nimmt die Variabilität aufgrund der Grenzen und Hindernisse auf der Karte ab, es handelt sich jedoch immer noch um eine unerträgliche Anzahl von Kombinationen. Und das alles passiert schließlich in einem normalen Browser.

Wie wird es gemacht?

Um ein ähnliches Problem zu lösen, wurde ein heuristischer Ansatz verwendet, dessen verallgemeinerter Algorithmus wie folgt beschrieben werden kann:

1. Generieren Sie verschiedene Szenarien basierend auf vordefinierten Strategien (~ 20 Teile).
2. Solange Zeit bleibt, mutieren Sie die Skripte und lassen Sie die profitabelsten übrig.
3. Wählen Sie am Ende das Szenario mit der höchsten Bewertung aus.
4. Führen Sie den ersten Zug der Einheit aus dem Skript aus, aber gehen Sie den Rest nicht. Starten Sie die Animation des ersten Zuges und verbessern Sie die Skripte für die verbleibenden Einheiten, während die Animation angezeigt wird.
5. Wiederholen Sie dies für die verbleibenden Einheiten ab Schritt 1.

Die heuristische Methode ist eine Methode, die funktionieren kann (nach McConnell [ 4 ]). Mehr und strenger auf Wikipedia [ 5 ].

Die wichtigsten Punkte in diesem Algorithmus sind: Szenarioerstellung, Mutationen und die korrekte Bewertung der Rentabilität des Staates. Jeder dieser Punkte verwendet seine eigenen lokalen Heuristiken. Trotzdem wurden nach Möglichkeit Algorithmen mit einem garantiert optimalen Ergebnis verwendet, beispielsweise A * zum Auffinden des Pfades [ 6 ].

Der evolutionäre Ansatz, den ich verwendet habe, kann nicht als vollwertiges Gen bezeichnet werden [ 7 ], weil Ich habe nur Mutationen und das Überleben des „Stärksten“ von ihm verwendet und die Einflusskoeffizienten der einzelnen Heuristiken manuell angepasst. Algorithmen zur Bildung von Populationen und Kreuzen wurden nicht verwendet. Nach der Mutation überlebt nur eine: entweder eine Mutante oder ein Elternteil.



Ich habe aufgrund der Art des Problems keine neuronalen Netze [ 8 ] verwendet. Erstens aufgrund der Komplexität ihrer erfolgreichen Implementierung in einem sich ständig ändernden Umfeld (das Aufkommen neuer Mechaniken, Fähigkeiten, Fertigkeiten). Zweitens aufgrund der Komplexität ihrer kontrollierten Personalisierung (wenn Sie zwei Verhaltensweisen vornehmen möchten: schnelles Suworow und vorsichtiges Kutuzow [ 9 ]).

Die Entwicklung eines künstlichen Idioten zur künstlichen Intelligenz

0) Zunächst wurden in der KI nur 3 Strategien mit zufälligen Bewegungen eingeführt. { Schwierigkeit des Spiels # 0 }. Die Zustandsbewertung war nur eine Zufallszahl. Und da KI nicht das einzige Entwicklungselement ist, musste ich mich lange mit dem Verhalten verrückter Fische abfinden.

1) Bei der Berechnung der Bewertung der Strategie wurden dann die Überprüfungen der verbleibenden Einheiten und ihres Lebens mit der KI und dem Spieler hinzugefügt. { Schwierigkeit des Spiels # 10 }. Für eine tote Einheit erhielt das Team 0 Punkte. Für völlig gesunde X-Punkte (zum Beispiel 100.000 für Kämpfer F, 70.000 für Bogenschütze A, 85.000 für Zauberer W). Für die Verwundeten wurden 50% des Kernwerts und die restlichen 50% im Verhältnis zu den verbleibenden Leben des Maximums berechnet. Dank dessen war es für die KI rentabler, Feinde zu töten, und wenn er nur verletzen konnte, wählte er Gegner mit weniger Leben - verletzlicher.

Zufällige Bewegungen wurden bedeutungsvoller - KI gab manchmal etwas zurück.

2) Dann wurde eine aussagekräftigere Startstrategie hinzugefügt:
max_agro - Alle Soldaten rannten so nah wie möglich an die Feinde heran und versuchten , so viel Schaden wie möglich zuzufügen . { Schwierigkeit des Spiels # 20 }. Eine Strategie verwendete die ursprüngliche Zugreihenfolge der Einheit, die zweite ging in umgekehrter Reihenfolge vor.

AI begann sich in taktischen Spielen wie der primitivste künstliche Idiot zu verhalten. Und ziemlich oft wird eine solche KI in taktischen Spielen verwendet. Es ist beliebt wegen seiner Zuverlässigkeit und Einfachheit. Dieser kann sogar gewinnen - aber sehr selten.

Genau so sieht KI-Verhalten im fehlgeschlagenen Spiel Master of Monsters - Disciples of Gaia aus, was es mühsam macht, darin zu spielen [ 10 ].


3) Dann wurden Strategien hinzugefügt, die möglichen Schaden durch Feinde während der Bewegung berücksichtigen und diejenigen Bewegungen auswählen, die zur geringsten Gefahr führten - vorzugsweise Null. { Schwierigkeit des Spiels # 30 }. Und die KI wurde sofort übermäßig feige und vermied jegliche Nähe zum Feind - es ist besser wegzulaufen als anzugreifen und zu verletzen, weil der Feind mehr Veränderung geben kann!

Daher begann die Bewertung der Bedingungen auch, den möglichen Schaden für den Feind zu berücksichtigen. Strafpunkte aus potenziellem Schaden durch Feinde wurden mit einem abnehmenden Koeffizienten von 0,20 berechnet (der Koeffizient wurde ständig neu konfiguriert ). Dies zwang die KI, bei der Wahl zwischen Angriff oder Flug eine aggressive Option zu wählen, da sie fünfmal mehr Punkte als der Flug brachte. Aber die KI blieb noch lange feige, denn um in eine Situation der Wahl zu gelangen, sollte der Feind bereits in Reichweite sein, und die KI selbst wird sich mit solchen Einschätzungen niemals zuerst angreifen. Das heißt, es wird nicht zur Annäherung gehen. Natürlich wird sich der Spieler betrogen fühlen, weil die KI unendlich viel Geduld hat und für immer vor der Gefahr davonlaufen kann, was den Spieler zur Aggression zwingt.

Es ist zu beachten, dass solche Berechnungen möglicher Schäden ohne die Verwendung eines Caches sehr lang sind. Eine vollständige Fehleinschätzung einer Strategie ohne Optimierungen dauerte zunächst 700 Millisekunden. Aber ich habe eine Begrenzung für den gesamten Verlauf einer Einheit ~ 4000 ms! Nach Optimierungen und verbrauchten Caches verringert sich diese Zeit mit sehr ähnlichen Strategien auf 20 Millisekunden ( leider kann der Cache aufgrund des kombinatorischen Explosionseffekts nicht alle im Voraus berechnet werden, sodass nicht immer 20 ms erreicht werden ).

Als ich die Berechnungstechnologie mit der Vorhersage mehrerer Züge vor mir einführte, dauerte die Berechnungszeit für eine Tiefe von nur 2 Zügen (Feind und KI) bereits +700 Millisekunden. In diesem Fall wird die Optimierung verwendet, indem die "schwachen" Zweige abgeschnitten werden. Wenn wir hierfür die primitive max_agro-Strategie verwenden, betrug der Zeitanstieg +30 Millisekunden, und das Caching hat diesen Unterschied fast nicht verringert ( da die Position auf der Karte völlig neu war ).

Infolgedessen habe ich 5 verschiedene Ansätze zur Entwicklung dieses Ansatzes gemacht, aber am Ende habe ich ihn komplett aufgegeben, weil Mutationen mit Heuristiken ergaben bessere und schnellere Ergebnisse.

4) Die folgenden Strategien zielten darauf ab, die anfängliche Vielfalt der Strategien zu erweitern:
far_attack_and_hide - Einheiten versuchen, so weit wie möglich vom Feind entfernt anzugreifen. Wenn sie nicht angreifen, verstecken sie sich vor jedem Angriff.

close_group_flee - Einheiten ziehen sich aus dem Kampf zurück und gruppieren sich so nah wie möglich beieinander. Wenn Sie den Feind gleichzeitig sicher angreifen können, greifen Sie an.
{ Schwierigkeit des Spiels # 40 }.

Dies verbesserte den Prozess des Kampfes selbst, aber der Beginn des Kampfes war für die KI immer unrentabel: Es zog sich ständig zurück, aber es konnte in den Angriff gelockt und abgeschreckt werden, so dass die KI-Gruppe in mehrere kleine Gruppen aufgeteilt wurde, die separat zerstört werden konnten.

5) Dann ist es Zeit für Mutationen . { Schwierigkeit des Spiels # 50 }.

Der Mutationsalgorithmus war sehr einfach:

• Beim Durchlaufen der ausgewählten Strategien wurde eine Kopie der Strategie erstellt.
• in dieser Kopie wurde eine Mutation des Kurses gemacht;
• Wenn der Zug ungültig wurde, wurde er gemäß einer der Standardstrategien auf mindestens einen gültigen korrigiert.
• Punkte der mutierten Strategie wurden berechnet;
• Wenn der Mutant mehr Punkte hatte, ersetzte der Mutant seinen Elternteil.

Gleichzeitig haben Außenstehende die Strategie nicht gelöscht und sich auch an Mutationen beteiligt, weil Es war immer eine spürbare Wahrscheinlichkeit für eine sehr erfolgreiche Reihe von Mutationen.

Zunächst wurde der primitivste Mutationstyp implementiert: 1 bis 3 Bewegungen wurden durch zufällige ersetzt, die Reihenfolge der Bewegungen blieb gleich. Während einer Iteration von Berechnungen wurden durchschnittlich etwa 5 bis 15 Mutationen für jede Strategie erstellt. Darüber hinaus war im Durchschnitt jede fünfte Mutation rentabler und ersetzte die Strategie der Eltern.

6) Heuristischer Köder . { Schwierigkeit des Spiels # 60 }.

Diese Heuristik wiederholte die Taktik, mit der ich die KI dazu verleitete, mit einer Einheit anzugreifen, um sie einzeln zu töten. Dieser Trick wurde auch der KI beigebracht.

Dazu wird bei der Berechnung von Punkten für den Zustand der Strategie geprüft, ob der aktuelle Zustand der Situation des Köders entspricht:

• Es kann nur ein KI-Soldat angegriffen werden.
• Nur ein Feind kann eine gekrochene Einheit angreifen.
• Die Einheit des Computerspielers muss nach diesem Angriff überleben.
• Mindestens zwei Einheiten des Computers können als Reaktion darauf angreifen. Je mehr solche Bestrafungseinheiten, desto mehr Punkte für die Heuristik.

Der Effekt erwies sich als ausgezeichnet: Es wird für den Spieler einfacher, den Kampf selbst zu beginnen. Darüber hinaus ist es für den Spieler meistens immer noch rentabler, sich auf diesen Köder zu setzen, da er nach einem Gegenangriff mit seinem gesamten Kader auf die KI fallen kann ( dies ist der Fall, wenn er vorher vernünftig gruppiert ist ). Und dort werden alle kompetenten lokalen taktischen Entscheidungen alles lösen.


7) Dann fiel mir auf, dass sich KI-Kämpfer ständig wie Kakerlaken zerstreuen . { Schwierigkeit des Spiels # 70 }. Außerdem könnten sich Soldaten in einer Ecke verstecken oder in enge Tunnel gehen, in denen die KI bei der Sortierung möglicher Angriffe stark an Wirksamkeit verloren hat.
Daher wurden der Bewertungsfunktion Heuristiken zur Schätzung der Entfernungen zwischen Einheiten und Kartentopographie mit den folgenden Annahmen hinzugefügt:

• Je näher die Verbündeten "im Durchschnitt" beieinander sind, desto besser (die Einheiten begannen sich seltener in verschiedene Teile der Karte zu zerstreuen).
• Je näher die KI-Soldaten den „durchschnittlichen“ Soldaten des Feindes sind, desto besser (ich brauchte eine offensive KI).
• Je größer der maximale Abstand zwischen zwei Verbündeten ist, desto schlechter. Gleichzeitig wird eine Entfernung von 4 nicht bestraft, und alles, was größer ist, wird exponentiell bestraft (dies hat aufgehört, Soldaten in gefährdete Reihen zu ziehen).
• Wenn ein KI-Soldat nicht in mindestens zwei Runden rennen und den Feind angreifen kann, muss er mit einer Geldstrafe belegt werden (dies zwingt ihn, voranzukommen, aber nicht selbst angegriffen zu werden).
• Wenn sich innerhalb eines Radius von 2 Schritten vom Soldaten zu viele Sperrpositionen befinden, wird eine Geldstrafe verhängt (seltener stießen sie auf Tunnel).
• Wenn sich ein Soldat am Rand der Karte befindet, wird er noch härter bestraft. Infolgedessen nahm die Manövrierfähigkeit der KI stark zu Eine Einheit kann von einem offenen Bereich zu einer viel größeren Anzahl von Positionen laufen als von einer Ecke oder einem Tunnel.

8) Dann ist es Zeit, Strategien zu erweitern. { Schwierigkeit des Spiels # 80 }. Ich konnte keine vollständige Aufzählung der möglichen Reihenfolge der Einheitenbewegungen hinzufügen, aber ich konnte ihre Bewegungen nach Typ auflisten: Kämpfer, Bogenschütze, Zauberer. Daher erschienen Strategien für die Abfolge von Zügen der Form W_A_F: zuerst gehen alle Zauberer, dann alle Bogenschützen, dann alle Kämpfer.

Somit wurden 6 neue Strategien hinzugefügt: W_A_F, W_F_A, A_W_F, A_F_W, F_A_W, F_W_A. Sie haben nicht alle Probleme gelöst, aber die Qualität des Spiels erheblich verbessert.

9) Ich hatte Mutationen, aber sie waren von geringem Nutzen. { Schwierigkeit des Spiels # 90 }. Meist verbesserten sie schwache Strategien, während erfolgreiche sich selten verbesserten. Daher wurden die Mutationen modifiziert und jedes Mal funktionierte eine der zufälligen Arten von Mutationen:

• 1 bis 3 Bewegungen wurden durch zufällige ersetzt, die Reihenfolge der Züge blieb gleich (alter Weg);
• Tauschen Sie die Bewegungsreihenfolge von zwei zufälligen Einheiten aus. Lassen Sie sie unverändert, auch wenn sie nicht optimal sind. Wenn die Bewegung nicht wiederholt werden kann, wird sie zufällig durch eine der üblichen Strategien in einen gültigen Zustand versetzt.
• Vertauschen Sie die Reihenfolge der Züge zweier zufälliger Einheiten und erzählen Sie ihre Züge erneut. Alle fehlgeschlagenen Bewegungen in nachfolgenden Einheiten werden durch zufällige konventionelle Strategien repariert.

Die Einführung dieser Mutationen begann ernsthaft die Unmöglichkeit zu kompensieren, alle Kombinationen von Einheitenbewegungen vollständig aufzuzählen. Obwohl er aufgrund seiner Zufälligkeit keine Garantie dafür gibt, dass ein Coup in der verfügbaren begrenzten Zeit gefunden wird.

10) Dann wurden weitere halbzufällige Strategien hinzugefügt . { Schwierigkeit des Spiels # 100 }. Die Reihenfolge der Züge wurde zufällig generiert und die Züge selbst wurden nach den folgenden Prinzipien ausgewählt (um ihre Bedeutung zu verringern):

• maximalen Schaden zufügen;
• als Reaktion so wenig Schaden wie möglich nehmen;
• Gehen Sie Ihren Feinden so nahe wie möglich.

Ich habe hier keine spürbare Verbesserung gesehen, aber das Projekt ist bereits so weit fortgeschritten, dass jede Verbesserung zu weniger spürbaren reproduzierbaren Effekten führt.

11) Ich hatte die krassen Fehler der KI satt, als er meine Soldaten angriff, während er mit seinem Zauberer angriff, aber gleichzeitig seine Verbündeten verwundete. { Schwierigkeit des Spiels # 110 }. Obwohl er vorher tatsächlich mit ihnen herumlaufen und sie aus der Schusslinie entfernen konnte. Daher wurde eine hart generierte Strategie mit manuellen Überprüfungen erstellt :

• Wenn es einen Zauberer gibt, dann finde einen Ort, an dem er maximalen Schaden zufügt.
• Wenn es an diesem Ort oder auf dem Weg des Streiks Verbündete gibt, erinnere dich an sie.
• Erstens gehen alle Verbündeten, an die sie sich erinnern, und können keine vom Zauberer reservierten Positionen einnehmen (dh den Weg frei machen).
• der Zauberer geht;
• Die restlichen Einheiten gehen.

Die Strategie lässt sich leicht in Worten beschreiben, ist aber für die Programmierung cool.

12) Manchmal " flüchteten " Einheiten kurz vor Beginn der Feindseligkeiten in die Büsche . { Schwierigkeit des Spiels # 120 }. Infolgedessen konnten zu Beginn des Angriffsaustauschs eine oder sogar zwei Einheiten zu weit von militärischen Operationen entfernt sein und den Verbündeten nicht helfen. Wenn dies passierte, war mir fast garantiert, dass ich die KI schlagen würde. Wenn es nicht passiert ist, habe ich oft verloren. Ich habe dies beseitigt, indem ich eine neue Heuristik eingeführt habe, um die resultierenden Punkte der Strategie zu bewerten. Für jede Einheit wurde eine Überprüfung durchgeführt:

1. Wenn die Einheit in diesem Zug angegriffen hat, erhielt sie +1500 Punkte.
2. Wenn Sie nicht angegriffen haben, wurden die Positionen berechnet, von denen aus die Feinde den Verbündeten Schaden zufügen konnten. Zählen Sie weiter, wenn mehr als 0 solcher Positionen vorhanden sind (N> 0).
2.1. Wenn eine Einheit keine Position erreichen und schlagen kann (n = 0), erhält sie eine Strafe von -1000 Punkten.
2.2. Wenn eine Einheit alle Positionen erreichen kann, erhält sie +1200 Punkte.
2.3. Wenn eine Einheit bis zu bestimmten Positionen angreifen kann, erhält sie + (n / N) * 1000 Punkte.

Dies hat den „Zusammenhalt“ der KI-Einheiten erheblich verbessert. Leider tauchten Fälle von „einem Deserteur“ auf, als eine der verwundeten Einheiten es vorzog, sich in einer verlorenen Situation hinter dem Rücken ihrer Kameraden zu verstecken, anstatt einen Beitrag zu leisten, indem sie den Feind angriffen. Es sah lächerlich aus, wenn der Computer nur noch 2 Einheiten hatte und der Spieler 3 oder mehr. Eine zusätzliche Korrekturheuristik ist die folgende Regel:

IF ("   ,   " AND "    3 ") THEN "      " 

13) Am Ende der Einführung der Strategien hatten sie bereits weniger als 25 Stück. { Schwierigkeit des Spiels # 130 }.

Die Mutation jedes einzelnen von ihnen ist zu teuer geworden. Daher wurde beschlossen, die erfolglosesten zu entfernen und nur 8 Stück zu belassen. Von Anfang an wollte ich diesen Ansatz nicht in der Erwartung verwenden, dass die Mutation von Außenstehenden zu einem unerwartet hervorragenden Ergebnis führen kann, anstatt nur zu einem guten. Die Eingabe dieser Verarbeitung führte letztendlich zu einer Verbesserung des KI-Spiels.

14) Zu Beginn gab es noch eine interessante Überarbeitung. Zunächst wurde der Wert des Szenarios als Differenz der Punktesumme berechnet:

 _ = _ - _ 

Aber nach mehreren Verbesserungen fiel mir ein, dass dies nicht die beste Lösung ist, weil dann sind für AI die Situationen "2 Soldaten gegen 1 einzelnen Soldaten" und "4 Soldaten gegen 3 Soldaten" gleich. Daher wurden Punkte als Verhältnis berechnet:

 _ = _ / _ 

Die Änderung ist gering und das Ergebnis ist sehr ernst. Ohne Änderung war der Preis eines Fehlers mit erhöhtem Risiko immer der gleiche. Nach der Verfeinerung begann die KI gegen Ende des Kampfes weniger nachlässig zu riskieren, was sie deutlich stärkte.

Ich möchte darauf hinweisen, dass all diese Verbesserungen schrittweise eingeführt wurden, wenn auch in der angegebenen Reihenfolge, aber viele von ihnen wurden verbessert, verarbeitet und aufgrund von Fehlern in einer chaotischeren Reihenfolge korrigiert. Es gab mehr als 100 echte Iterationen.

So spielt die endgültige KI { Schwierigkeitsgrad des Spiels # 9999 }:

AI geht sofort und verschwendet keine Zeit mit Nachdenken

Um die Berechnungen selbst zu beschleunigen, wurden Optimierungsalgorithmen aktiv in Form von Partitionen verschachtelter Schleifen in sequentielle Schleifen ( Reduzierung der Komplexität ) und der Einführung mehrerer Arrays mit zwischengespeicherten vorläufigen Berechnungen ( und anschließender Optimierung dieser Caches ) verwendet. Nach meinen Schätzungen könnten weitere Optimierungen zu einer doppelten (oder sogar größeren) Geschwindigkeitssteigerung führen, dies würde jedoch zu einer ungerechtfertigten Erhöhung der Zeitkosten und einem weiteren noch größeren Verlust der Lesbarkeit des Codes führen.

Die Haupttechnologie der Hochgeschwindigkeit sind vorläufige Berechnungen während der Ausfallzeit. Diese Methode besteht darin, den Prozess in zwei Teile zu unterteilen: die Berechnungen selbst und die Animation der Berechnungsergebnisse:

• Berechnungen des Verlaufs der ersten Einheit beginnen unmittelbar nach dem Zug des Spielers, während ein Fenster herausfliegt, in dem der Zug des Gegners beginnt. Und das sind bis zu 4 Sekunden, die der Spieler nicht als leere Erwartung wahrnimmt.
• Die Berechnungen des zweiten und der nachfolgenden Züge beginnen, wenn die Animation des Verlaufs der letzten Einheit erst beginnt (dh wenn der KI-Cursor gerade seine Bewegung beginnt). Und die Zeit aller Animationen beträgt bereits 4,5 Sekunden. Es wäre zwar richtiger, dies nicht die Berechnung des nächsten Schrittes zu nennen, sondern die Verbesserung der bereits entwickelten früheren Strategie und die Suche nach einer neuen, weil Bei jeder Iteration werden die Bewegungen des gesamten Teams berechnet.
• Wenn sich die animierende KI zu beweglichen Einheiten bewegt, fliegt der KI-Cursor, der vorgibt, auf sie zu klicken. Der Cursor fliegt so schnell wie möglich, damit der Komfort der Verfolgung erhalten bleibt. Darüber hinaus konnte durch Hinzufügen eines Cursors nicht nur die Rechenzeit von 2 Sekunden auf 4,5 Sekunden erhöht werden, sondern auch der Fortschritt des Computers für eine Person komfortabler angezeigt werden.
• Die Zugzeit des Spielers wird ebenfalls nicht verschwendet. Solange der Spieler denkt, werden fast keine Berechnungen durchgeführt, so dass zu diesem Zeitpunkt mögliche Caches für den zukünftigen Zug des Computergegners intensiv berechnet werden.

Um zu verhindern, dass all dies im Browser zurückbleibt und mit einem relativ stabilen FPS arbeitet, werden die Berechnungen vom Worker ( Web Worker ) asynchron durchgeführt [ 11 ].

Auf diese Weise wollte ich das nervige Wartefenster „Computer-Spaziergänge“ loswerden. Solch ein unangenehmer Würfel ist in vielen guten Spielen zu finden, zum Beispiel bei Xenonauts [ 12 ]. Ich glaube, dass ich dieses Problem bewältigen konnte.


Daher verbringt die KI immer die gleiche Zeit damit, über ihren Umzug nachzudenken - unabhängig von ihrer Komplexität. Ein sehr merkwürdiges Merkmal dieses Ansatzes ist, dass je stärker der Spieler einen Computer hat, desto mehr KI-Mutationen Zeit zum Aussortieren haben und daher umso stärker und leistungsfähiger der Computer des Spielers ist. Ich habe diesen Effekt zuerst entfernt, indem ich die Laufzeit festgelegt und die Geschwindigkeit des Computers vorberechnet habe. Allerdings habe ich dann diese Fixierung entfernt, weil Besitzer von leistungsstarken Computern können so mit "ihrem" Computer kämpfen, anstatt mit dem durchschnittlichen.

Was ist das Ergebnis und was sind die Nachteile

Somit weiß der resultierende Computergegner, wie man würdig kämpft und nutzt die Versehen eines Spielers gut aus und macht nicht zu viele seiner eigenen. Trotzdem kenne ich alle Merkmale seiner Arbeit, wenn auch mit Spannung, aber ich besiege ihn fast immer (unter gleichen Bedingungen). Aber ich möchte das Gegenteil: Selbst wenn ich über seine Eigenschaften Bescheid weiß, verliere ich fast immer gegen ihn. KI ist alles andere als ideal, da die von mir verwendeten Heuristiken zu einer synergistischen Überlappung von "Fehlern meiner Wahrnehmung" führen. Diese Fehler sind:

1. Aufgrund der Unvollkommenheit und Unvollständigkeit meiner eigenen Strategie kenne ich nicht alle besten Strategien und kann sie daher nicht identifizieren und im Spiel umsetzen.
2. Effizienzverlust (was nicht so ideal ist) von ausgearbeiteten Heuristiken bei der Übertragung auf Programmcode. Zum Beispiel meine menschliche Heuristik: „Einheiten bleiben in der Nähe, aber nicht zu nahe, um doppelten Schaden durch Magier zu vermeiden und nicht in engen Passagen stecken zu bleiben.“ Diese Heuristik hilft mir, die KI zu besiegen, aber wenn ich sie meinem Computergegner beibringe, muss ich eine qualitative Beschreibung in eine algorithmische mit quantitativen Schätzungen übersetzen, und hier ist Datenverlust möglich.
3. Gegenseitige Konflikte zwischen Heuristiken. Wenn zu viele Heuristiken vorhanden sind, beginnen sie sich allmählich zu überlappen. Infolgedessen kann eine unerwartete Verstärkung aufgrund einer versteckten Doppelzählung oder einer teilweisen Verdoppelung auftreten. Oder irgendeine Art von Heuristik wird aufhören, irgendetwas zu beeinflussen, weil sein Beitrag wird durch große konkurrierende Koeffizienten vollständig blockiert.
4. Enge Zeitbeschränkungen und schrittweise Verbesserungen der gewählten Strategien führen dazu, dass der erste Schritt immer weniger durchdacht ist. Dies bedeutet, dass ein erfolgloser erster Zug die offensichtlich effektiveren Züge der verbleibenden Einheiten des Teams blockieren kann. Dies drückt sich in der Tatsache aus, dass der erste Kämpfer F, anstatt sich zu entfernen, den Feind ironisch angreifen kann und dann sein Verbündeter W seinen eigenen verletzen muss, um den Feind zu erledigen.

Vollwertige genetische Algorithmen würden es höchstwahrscheinlich ermöglichen, optimalere Koeffizienten in der Heuristik auszuwählen, anstatt sie mit dem Auge abzugleichen. Dies ist jedoch bereits eine Aufgabe für zukünftige vollwertige Projekte - ich möchte nicht lange an einem Prototyp hängen bleiben. Ich bin sehr zufrieden mit der aktuellen KI: Sie ist umsichtig, ein wenig heimtückisch, ziemlich aggressiv und erlaubt dem Spieler nicht, sich trocken zu besiegen ( in Wirklichkeit ist es äußerst selten, dies zuzulassen ).

Zusätzliche Funktionen

Mit dieser Implementierungsmethode können Sie zusätzliche Boni in der Spieleentwicklung erzielen ( in vielerlei Hinsicht aus Sicht des Entwicklers und seiner brennenden Bedingungen ):

1. Das Erscheinen neuer Mechaniken im Spiel wird die Stärke des Computerspielers nicht zerstören, obwohl es ihn im Vergleich zum Spieler allmählich schwächt. Diese Schwächung kann durch die Einführung zusätzlicher Heuristiken ausgeglichen werden. Damit dies nicht zu fortschreitenden Ressourcenausgaben führt, können diese neuen Heuristiken nur angewendet werden, wenn diese neuen Mechaniken im aktuellen Kampf vorhanden sind.
2. Wirklich intelligente Schwierigkeitsgrade . Grundsätzlich bestimmt der Schwierigkeitsgrad, welche Boni ein Computerspieler als Ressourcen erhält ( mehr Gold zu Beginn oder ein Bonus im Bergbau ) oder wie viel seine Soldaten schlagen ( + 50% Schaden ). Es funktioniert, aber Sie können die KI ein wenig weniger intelligent machen, indem Sie einige Heuristiken schrittweise deaktivieren, wenn die Komplexität abnimmt.
3. In der Fortsetzung des zweiten Absatzes können Sie verschiedene Rassen / Fraktionen von Computergegnern erstellen: Nur aggressive Strategien funktionieren für Orks; in Massen von Zombies rennen nur die Primitiven „vorwärts und greifen an“; und Cyborgs nutzen die volle Kraft der KI. Dank dieses Spielers muss vor dem Angriff nicht nur die Anzahl der Gegner, sondern auch deren Intelligenz bewertet werden.

All dies klingt vielversprechend, aber Sie sollten sich daran erinnern, dass all dies auf dem Papier schön ist und in einem echten Spiel möglicherweise nicht funktioniert, sich als uninteressant oder sogar für den Spieler unsichtbar herausstellt. Dies ist jedoch ein guter Grund zum Experimentieren.

Wo zu fühlen

Sie können die Leistung dieser KI im taktischen KI-Rumpelbrowser testen. Testperson “kostenlos auf Websites wie itch.io [ 13 ]. Der GET-Parameter ai (Werte von 0 bis 140 in Schritten von 10) verringert die Komplexität der KI.

Nach meinen Erwartungen wird es für Sie sehr, sehr schwierig sein, KI zu gleichen Bedingungen zu besiegen. Auch nachdem man sich an die Spielregeln gewöhnt hat. Ich empfehle, dieses Spiel als Prototyp zu betrachten, was es im Wesentlichen ist (es enthält keine Musik, Sounds und keinen Preis ).

Bitte hinterlassen Sie Ihre Meinung in den Kommentaren zur Interessantheit der KI, Tipps und Kritik zur möglichen Implementierung der KI mit verschiedenen Lehrmethoden. Wenn Sie sich plötzlich für meine anderen Forschungsergebnisse interessieren, können Sie hier mein Konto abonnieren.

Referenzliste

1. DeepMind - Artikel über Habré .
2. HTML5-Spiele: Canvas vs. SVG vs. div on stackoverflow .
3. Kombinatorische Explosion - Wikipedia .
4. Der perfekte Steve McConnell-Code ist Habr .
5. Heuristische Methoden - Wikipedia .
6. A * - Red Blob-Spiele .
7. Der genetische Algorithmus. Fast das Schwierige - Habr .
8. Acht erstaunliche Spiele mit künstlicher Intelligenz von der Firma Google - Habr .
9. Ganz kurz über Suworow und Kutusow .
10. Meister der Monster - Schüler von Gaia - Rückblick auf IGN .
11. Eine detaillierte Erklärung der JavaScript-Spielschleifen und des Timings .
12. Xenonauten und ein langer AI-Standby-Bildschirm .
13. KI taktisches Grollen. Testperson - auf itch.io.