🎣 🤐 ♀️ Mein Bot für den Russian AI Cup 2019 🖕🏿 🐊 👸

Es ist einfach so passiert, dass diese Meisterschaft für mich die erste war, bei der ich einen würdigen Platz einnehmen konnte, für den ich mich nicht schäme. Deshalb habe ich beschlossen, den Artikel jetzt auch zu schreiben. Der Weg, den ich zu diesem Ort gegangen bin: 1192. Platz in der Meisterschaft des 13. Jahres, 241. Platz in der Meisterschaft des 17. Jahres, 91. Platz in der Meisterschaft des 18. Jahres und schließlich 16. (und 5. Platz) e in den Sandkasten) legen.

Allgemeine Gedanken

Ich glaube, dass einer der Hauptgründe für die relativ erfolgreiche Leistung bei RAIC eine Änderung des Ansatzes zur Erstellung Ihrer Strategie war.

Früher habe ich versucht, sofort etwas Großes und Kompliziertes zu schreiben, ohne Zwischenschritte, und die erste Version konnte erst zwei Wochen nach Beginn der Meisterschaft ausgefüllt werden, aber in der Vergangenheit konnte ich sie nicht die ganze Zeit einplanen und die erste Version wurde erst nach dem Finale ausgefüllt .

All dies führte dazu, dass andere Teilnehmer zwar ihre Lebensstrategien testen konnten, ich aber immer noch keine vorgefertigte, wenn auch schlechte Lösung hatte. Als es möglich war, etwas auszufüllen, stellte sich heraus, dass der gewählte Ansatz nicht funktioniert oder schlecht funktioniert, und da viel Zeit und Mühe investiert wurde, war es nicht möglich, ihn radikal zu ändern.

Deshalb habe ich beschlossen, diesmal anders zu machen. Aufgrund der Erfahrungen mit früheren Beteiligungen habe ich festgestellt, dass der Startbot trotz seiner Primitivität recht rational geschrieben wurde. Bei der Entwicklung können Sie langsam neue Funktionen hinzufügen und testen und sofort die Strategien anderer Teilnehmer überprüfen. Insbesondere war ich überzeugt, diesen Ansatz des letztjährigen Artikels von T1024 auszuprobieren.

Ich habe auch selbst entschieden, dass je komplexer der Ansatz ist, desto weniger effektiv ist er in meinen Händen. Zum Beispiel ist es nicht sinnvoll, Genetik zu verwenden, wenn eine umfassende Suche möglich ist. Wenn weniger Optionen ausgewählt werden können, aber alle oder mehr als die Genetik, ist es besser, die erste Option zu wählen. Plus vom Lesen von Commando-ArtikelnIch kam zu dem Schluss, dass bestimmte Optimierungen für die Aufgabe immer effektiver sind als der allgemeine Algorithmus.

Trotzdem war ich auch jetzt noch drei oder vier Tage zu spät, bevor ich die erste Version des Bots ausfüllen konnte, zu dieser Zeit befanden sie sich bereits im Sandkasten im Krieg.

Was habe ich zu diesem Zeitpunkt gemacht? Ich habe einen Simulator geschrieben, dessen Wichtigkeit ich aus früheren Meisterschaften gelernt habe. Anders als im letzten Jahr, als der Pseudocode des Simulators sofort verfügbar war, mussten in diesem Jahr alle Mechaniken aus der Dokumentation gelesen werden. Glücklicherweise war die Spielmechanik als Ausgleich nicht ganz kompliziert und unkompliziert, so dass ich keine besonderen Probleme hatte.

Frühe Versionen

Nachdem ich einen fertigen, wenn auch krummen, groben Simulator in der Hand hatte, war das erste, was ich tat, die Ausweichmanöver zu vermasseln (Dodge-Funktion). Da ich mich diesmal entschlossen habe, so einfach wie möglich zu handeln, wurden die Ausweichmanöver so einfach wie möglich gemacht. Wir überprüfen die Bewegung in neun Richtungen (4 axial, 4 diagonal und an Ort und Stelle) und prüfen, in welche dieser Richtungen das Gerät den geringsten Schaden erleidet.

Der Rest der Funktionalität des Bots blieb fast vollständig wie bei Quickstart. Die Zielbezeichnung war auch so primitiv wie möglich - eine Kette von Wenns, die die für die Einheit am besten geeignete Aktion auswählen: für den Feind, vom Feind über das Erste-Hilfe-Set bis hin zu Waffen usw.

Überraschenderweise ermöglichte dieser Ansatz, der allmählich komplizierter wurde, aber sein Wesen nicht veränderte, es, vor der ersten Runde fast an die Spitze zu gelangen (sobald der Bot sogar auf dem zweiten Platz im Sandkasten war) und im Allgemeinen irgendwo um die ersten zehn Plätze zu bleiben.

Trotzdem konnte dies nicht ewig dauern und der Bot musste verbessert werden. Es gab jedoch keine Ahnung, was und wie verbessert werden sollte. Alle Versuche, etwas an der Strategie zu ändern, führten dazu, dass sie die alte Version verlor. Kleinere Änderungen wurden vorgenommen, aber nichts weiter.

Der Mangel an Ideen führte dazu, dass ich in Runde 1 und 2 29 bzw. 19 Plätze belegte und obwohl ich ins Finale ging, wurde klar, dass etwas radikal geändert werden musste. Vor dem Finale (und nach dem Finale) wurden die meisten wesentlichen Änderungen vorgenommen.

Bereits irgendwo in der Mitte der Meisterschaft habe ich versucht, mit intelligenteren Bewegungen zu experimentieren, aber alle Versuche waren erfolglos. Die ursprüngliche Idee war, die Richtung zu wählen, in der der Unterschied zwischen der Chance, seinen Bot auf den Feind und den Feind auf seinem Bot zu treffen, maximal war. Für dieses Experiment habe ich fast die gesamte Zeit für das Finale aufgewendet, mit einem Ergebnis von Null.

Für die endgültigen mehrstufigen Karten erwies sich der Bot daher als völlig unvorbereitet. Die If-Kette lieferte relativ gute Ergebnisse auf einstufigen Karten aus Runde 1 und 2, erwies sich jedoch als ungeeignet für mehrstufige Karten des Finales. Ich hatte auch kein Navigationssystem für komplexe Karten, da es auf einfachen Karten möglich war, vom Startcode zu wechseln.

— .

Die gesamte Zündsteuerung erfolgt in der AimHelper-Funktion.

Alles, was unten beschrieben wird, impliziert, dass das Ziel die sichtbare feindliche Einheit ist, die dem Bot am nächsten ist.

Es gibt nur drei Arten von Waffen, von denen jede ihren eigenen Ansatz erfordert. Es ist besser, nur öfter mit einem Maschinengewehr zu schießen, besser mit einer Pistole zu zielen, und dann ist es wichtig, mit einem Raketenwerfer zu schießen, um dem Feind mehr Schaden zuzufügen als Ihnen selbst.

Anfangs gab es überhaupt kein Zielen, der Bot zielte nur auf die Mitte der Einheit. Später wurde eine Vorhersage der Bewegung der Einheit hinzugefügt, wenn sie sich in einem unkontrollierten Flug befindet (Stürze oder Fliegen vom Jumppad). Dazu habe ich einfach die Bewegung der Einheit simuliert, bis die Entfernung, die die Kugel für N Zecken fliegen kann, der Entfernung zur Einheit entspricht.

Beim Testen gegen den Startbot bemerkte er seine sehr unangenehme Angewohnheit, ständig auf und ab zu springen, und wenn der Bot immer auf das Zentrum des Feindes zielte, führte dies dazu, dass sich der Anblick ständig bewegte und die Ausbreitung sehr schnell auf das Maximum anstieg. Zur Gegenwirkung wurde ein Code hinzugefügt, der prüft, ob die Trefferchance mit dem aktuellen Zielwinkel besser oder gleich der Trefferchance mit einem neuen Zielwinkel ist. Dann ändern wir den Punkt, an dem wir zielen, nicht und erhöhen die Streuung nicht.

Beim Schießen war es schwieriger, eines der Hauptprobleme des Startbots war, dass er nicht überprüfte, ob er sich mit einer Explosion berühren würde. Aus irgendeinem Grund mochte ich den Raketenwerfer am meisten von allen drei Arten von Waffen, und deshalb war es die erste Priorität. Es war notwendig, dem Bot beizubringen, sich selbst nicht zu untergraben.

Die HitChance-Funktion wurde geschrieben, die den Schusssektor der Einheit in N Strahlen aufteilte und jeden Strahl auf eine Kollision mit einem Ziel überprüfte. Bei einem Treffer wurde auch die AOE der Explosion überprüft, wenn es sich um einen Raketenwerfer handelt. Trefferchance = Anzahl der Treffer durch Strahl oder Explosion / Anzahl der Strahlen.

Dies ermöglichte es uns, die statische Chance zu bestimmen, uns selbst und den Feind zu treffen, berücksichtigte jedoch nicht, dass der Feind selbst aktiv ausweichen konnte. Es gab andere Probleme, zum Beispiel berücksichtigte die Funktion nicht das zufällige Brennen in Minen.

Dies war genug, um gegen nicht so listige Feinde zu kämpfen, aber gegen Spitzen, die Kugeln gut ausweichen, lieferte die Funktion kein adäquates Ergebnis. Ein neuer Ansatz war erforderlich.

Die HitPredict-Funktion unterteilt den Schusskegel auch in N Strahlen. Statt jedoch erneut zu senden, verwenden wir eine Simulation, bei der jeweils eine Kugel in eine der Richtungen abgefeuert wird und geprüft wird, ob der Feind ausweichen kann.

Um die Ausweichmanöver zu überprüfen, wird auch die Dodge-Funktion verwendet, die der Bot für sich selbst verwendet hat, jedoch mit sehr viel verkürzter Simulationszeit und der Anzahl der Mikrotik. Diese Bewertungsmethode erwies sich als ziemlich genau, aber zu pessimistisch. Wenn Sie nur es verwenden, schießt der Bot zu selten.

In der ersten Version gab die Funktion nur die Trefferchance von 0-1 zurück, später wurde die Berechnung des durchschnittlichen HP-Werts des Ziels sowie die Chance hinzugefügt, durch Treffer zu töten.

Am Ende arbeiteten beide Funktionen zusammen. Die HitPredict-Funktion wurde bis zu vier Mal verwendet, eine für jede Einheit. Das Ergebnis der Berechnung jeder Funktion wurde in Geschwindigkeit umgewandelt, was zeigte, wie profitabel / gefährlich es ist, gerade zu schießen. Werte addiert. Wenn der Gesamtwert kleiner als Null war, wurde die Aufnahme blockiert. Für den Raketenwerfer war es notwendig, dass die Geschwindigkeit größer als Null war.

Es wurde möglich, sicherer zu schießen, wenn ein Verbündeter das Schießen blockiert oder in die AOE eines Raketenwerfers gerät. Sie können ihn in den Rücken schießen, da Sie wissen, dass der Verbündete entweder Zeit zum Ausweichen hat oder es für uns einfach von Vorteil ist, zu schießen. Zum Beispiel werden wir eine Einheit verlieren, aber wir werden zwei auf einmal wegnehmen.

Für den Raketenwerfer war der Ansatz ebenfalls effektiv. Ein Schuss zum richtigen Zeitpunkt ist viel effektiver als zwei Schüsse, wenn die Trefferchance Null ist. In dieser Form war das Schießen im Finale und dies erlaubte den 16. Platz.

Nun die Chips, die nach dem Finale hinzugefügt wurden.

Genaues Zielen: Wenn der Winkel zwischen dem aktuellen und dem gewünschten Visier nicht zu groß ist, richten wir das Visier auf eine Datenrate, um die Streuung nicht zu erhöhen.

Informationswinkel für die Pistole: Seltsamerweise ist der Chip sehr einfach, kam aber vorher nicht in den Sinn. Das Verbot zu schießen, wenn der Streufaktor (Streuung / maximale Streuung) größer als 0,6 ist, lieferte den Prozentsatz der Siege im 1x1-Modus in 3: 1 gegen die Version, die auf die Waffen-CD geschossen hat. Die Reduzierung des Faktors auf 0,3 ergab den gleichen Prozentsatz an Siegen gegen die Version mit dem Parameter 0,6. Somit erwies sich eine der einfachsten Optimierungen als eine der effektivsten.

Visualisierung der Funktionsweise der HitPredict-Funktion, die Trajektorien, auf denen der Treffer garantiert ist, sind rot markiert.

Navigation

Bis zum Finale der Navigation gab es überhaupt kein Wort. Es wurde ein leicht verbesserter Algorithmus vom Startbot aus verwendet, und dies war im Allgemeinen ausreichend.

Daher hatte der Bot bei komplexen Karten eine sehr schwere Zeit. Es wurde dringend ein dringender BFS-Suchalgorithmus geschrieben, der nach einem Pfad suchte, ohne dessen physische Erreichbarkeit einfach durch Kacheln zu berücksichtigen. Damit der Bot den gefundenen Weg passieren konnte, wurden verschiedene Krücken verwendet. All dies funktionierte sehr schief und manchmal funktionierte es überhaupt nicht, aber dennoch konnte der Bot irgendwie an Waffen und Erste-Hilfe-Sets gelangen und nicht sofort springen.

Nach dem Finale wurde die Navigation erheblich verbessert und verhielt sich nach meinen Beobachtungen noch effizienter als viele Teilnehmer mit besseren Algorithmen für die Pfadsuche.

Arbeitsprinzip: Der Bot sucht auf dem Weg innerhalb des 5x5-Quadrats, das von der Mitte des Bots aus sichtbar ist, nach der Zelle, die am weitesten entfernt ist, und folgt bis zu diesem Punkt.

Trotzdem blieb es bis zum Ende ein unglaublich krückenhafter Code, der nur auf den endgültigen Karten funktionierte und auf andere, komplexere Karten fiel.

Grün markierter Weg gefunden diykstroy. Der Bot folgt dem mit einem weißen Quadrat markierten Punkt.

Bewegungs- und Schätzfunktion

Vor dem Finale gab es keine Bewertungsfunktion, stattdessen wurde eine Kette von Wenns verwendet, die den Bot in der Reihenfolge ihrer Priorität gemäß den gegebenen Bedingungen auf das Ziel setzte. Das erste war zum Beispiel die Suche nach Waffen, wenn der Bot keine hat, dann die Suche nach einem Erste-Hilfe-Kasten, wenn wir verletzt sind usw.
Dies funktionierte auf einfachen Karten, obwohl es schief war, da sich die Prioritäten sehr stark änderten und verschiedene zusätzliche Faktoren nicht berücksichtigten.

Daher wurde dennoch eine Bewertungsfunktion geschrieben.

Hauptparameter

Einheitsgesundheit, der größte Bonus.
. — , — .
— , . (1 — / . ), , . , , .
. , , .
, , , .
.
, .
.
Ein großer Bonus, wenn wir den Feind mit Selbststrahlung berühren können.

Die letzten beiden Parameter waren nicht im Finale.

Alle diese Boni werden für jeden Tick berechnet, summiert und der Gesamtwert gemittelt. Darüber hinaus gibt es geschätzte Parameter, die für jede Richtung einmal berechnet werden.

Bonus für die Bewegung zum nächsten Feind.
Bonus für den Wechsel zum nächsten Erste-Hilfe-Kasten. Je weniger Gesundheit wir haben, desto stärker ist der Bonus.
Bonus für den Wechsel zur nächsten Waffe, wenn wir keine Waffe haben, oder für den Wechsel zu einer Waffe mit einer höheren Priorität als der Bot.
Bonus für den Wechsel zur Beutebox min, wenn der Bot weniger als zwei davon hat.
Bonus für den Wechsel zum Erste-Hilfe-Kasten, der dem Feind am nächsten liegt, wenn wir näher am Erste-Hilfe-Kasten sind als der Feind.
Der interessanteste Bonus. Es wurde nach dem Finale hinzugefügt. Ermöglicht es Ihnen, zu verhindern, dass der feindliche Bot behandelt wird. Beobachtungen zufolge erwies es sich als recht effektiv.

Anmerkungen

Die Simulationstiefe beträgt 30 Ticks.
Das Verhalten feindlicher Bots wird nicht simuliert. Das Spiel ist sehr dynamisch und es ist sehr schwierig und nicht besonders notwendig, die Bewegung des Feindes angemessen vorherzusagen. Es könnte nützlich sein, wahnsinnige Selbstmorde zu vermeiden, aber es wurde nie getan.
Um Probleme beim Ausweichen von Kugeln auf dem Spielfeld zu vermeiden, simulieren wir mit einer Qualität von 100 Mikrotik pro Tick (wie im Spiel), andernfalls reduzieren wir sie auf 5.
Möglicherweise stellen Sie fest, dass kein Dämpfungskoeffizient angewendet wird. Vielleicht war das ein Fehler.

Die alte Verschiebungsoption befindet sich in MoveHelperOld, die neue in MoveHelper.

Mein Bot (rechts) bewacht das Erste-Hilfe-Set

Minen

Über Minen muss gesondert berichtet werden. Wenn es anfangs kein sehr wichtiges Gameplay-Element war, sollte es wichtige Punkte abbauen. Nach dem Betatest wurde die Fähigkeit, Minen zu explodieren, plötzlich hinzugefügt, wenn sie von einer Kugel oder Explosion getroffen wurden. Darüber hinaus war es möglich, die Mine im selben Tick zu setzen und zu untergraben.

Das heißt, wenn Sie nur zwei Zecken ausgeben, können Sie jede feindliche Einheit mitnehmen. Der Feind erhielt 1000 Punkte für unseren Tod, aber wir erhielten 1000 + seiner Gesundheit zum Zeitpunkt des Abrisses für seinen Tod. Wenn Sie dies zweimal wiederholen, können Sie sich mit sehr hoher Wahrscheinlichkeit einen Sieg sichern.

Der Exploit erwies sich als so stark, dass ein Teilnehmer, der in der Gesamtwertung irgendwo auf dem 15. Platz lag, unerwartet auf den 4. Platz im Finale abrutschte, einfach aufgrund eines kompetenten Kamikaze.

(Der Unterschied besteht darin, dass es in der allgemeinen Rangliste sowohl einfache als auch komplexe Karten gibt. Bei einfachen Karten funktioniert Selbstmord schlechter.)

Im Endeffekt verwendete die Strategie Minen, verwendete jedoch keine absichtliche Selbstdetonation. Nach dem Finale, als um zusätzliche Preise gekämpft wurde, wurde das TryPlantMine2-Modul hinzugefügt, das den Demoman implementiert. Aufgrund von Fehlern im Code war das Modul zunächst nicht besonders effizient, aber in der neuesten Version war es möglich, alles zu reparieren, und die Strategie stieg sofort steil an. Es kam zu dem Punkt, dass sie sogar in die Top 3 flog, obwohl sie dann etwas ausrutschte.

Arbeitsprinzip: Wenn wir in einer Position sind, in der Sie eine Mine platzieren können und nicht später als fünf Zecken schießen können, simulieren wir drei Optionen: Einfach abschießen, eine Mine setzen und schießen, zwei Minen und schießen. Für Feinde und Verbündete simulieren wir Bewegungen mit derselben Ausweichfunktion und prüfen, ob sie aus der Explosionszone herausspringen können, bevor wir sie untergraben können (nicht sicher, wie viel sie benötigt wurden). Bei jeder Option prüfen wir, wie vorteilhaft es für uns ist, Punkte zu sammeln. Wenn wir schwarze Zahlen schreiben, werden wir untergraben (auf diese Weise können wir untergraben werden, selbst wenn wir wissen, dass zwei unserer Einheiten und ein Feind sterben, aber wir werden trotzdem gewinnen).

Die Auswirkung der Selbstuntergrabung auf die Wertung

Ergebnisse

Einfache Lösungen können oft effektiver sein als komplexere, aber dies hat seine eigenen Grenzen. Mit diesem Ansatz können Sie ziemlich hohe Werte erreichen, aber dann in die Falle tappen, wenn das Potenzial zur Verbesserung der Strategie bereits ausgeschöpft ist und ohne radikale Änderungen die Stärke der Strategie nicht erhöht werden kann. Für die Zukunft sollten Sie über eine Zwischenoption nachdenken.

Fazit

Im Allgemeinen hat mir diese Meisterschaft gefallen, obwohl ich voreingenommen bin, weil es das erste Mal ist, dass ich einen Platz einnehme. Trotzdem wurde in diesem Jahr viel auf einer höheren Ebene realisiert, ohne auch nur meine subjektiven Gefühle zu berücksichtigen.

Zum ersten Mal war es möglich, im Telegramm mit einer Person zu kommunizieren, die für den technischen Teil verantwortlich ist und die alle Fragen umgehend beantwortete, wofür sie sich bedankt.
Zum ersten Mal war im Localranner ein normaler integrierter Visualizer vorhanden. Zuvor mussten Sie zum Ausgeben von Debugging-Grafiken eigene Grafiken schreiben.
Schließlich wird anstelle des unbequemen und fehlerhaften Dienstprogramms Repeater die Schaltfläche "Spiel wiederholen" im LAN hinzugefügt.

Von den Minuspunkten ist natürlich ein großer Exploit bei Minen.

Und ich hoffe, dass meine Erfolge in dieser Meisterschaft nicht zufällig sind und dass ich beim nächsten Mal zumindest einen Platz retten und noch besser eine höhere Position einnehmen kann (Träumen ist nicht schädlich).

Der Bot-Code kann auf dem Github angezeigt werden: github.com/silentnox/CodeSide

Mein Bot für den Russian AI Cup 2019