🍧 🔉 😓 Fortsetzung der Teilnahme (und des Sieges) am russischen AI Cup 2019 🗽 🐭 🌕

Hallo allerseits, mein Name ist Andrey Tokarev , und ich möchte noch einmal meine Erfahrungen mit der Teilnahme und dem Sieg am russischen KI-Pokal teilen .

Wenn jemand es nicht weiß, ist der russische KI-Pokal (im Folgenden RAIK) eine Programmiermeisterschaft für künstliche Intelligenz, bei der wir (oder besser gesagt unser Programm) einen oder mehrere Charaktere (Einheiten) kontrollieren müssen, die miteinander konkurrieren. In diesem Jahr war das Spiel ein zweidimensionaler Plattformer, der an Computerspiele der frühen 90er Jahre erinnerte, und die Einheiten waren bewaffnete Männer, die dieselben Männer des Feindes töten sollten. Mehr dazu lesen Sie in der Ankündigung.

Dieses Mal gab es kein Treffen, als die Tagesordnung für den Start der RAIK kam. Kommen wir also gleich zum Punkt.

Erster Blick

Also habe ich die Regeln durchgesehen und das Spiel ausprobiert. Der erste Eindruck war - was hier zu tun? Da die Einheiten keine Trägheit hatten und die Anfangsstufen ohne geschlossene Zyklen waren, konnte der Feind immer an uns festhalten, wenn er wollte, und sich dagegen zu verteidigen, war unmöglich. Und in dieser Situation sind die Möglichkeiten sehr begrenzt. Sie werden Kugeln nicht ausweichen. Aber meine ersten Befürchtungen haben sich nicht erfüllt, obwohl der Zufallsfaktor hoch war, erwiesen sich die Regeln als ziemlich spielbar.

Ich begann mich nicht sofort zu entwickeln, ein paar Tage ~~fielen~~ mir ~~zum Narren~~beschlossen zu reflektieren. Ich habe mir nichts Besonderes ausgedacht. Es ist klar, dass Sie Kugeln ausweichen, Erste-Hilfe-Sets verfolgen und den Feind nach Möglichkeit nicht ein Erste-Hilfe-Set nehmen lassen müssen. Es gab noch einen vagen Plan, strategisch vorteilhafte Positionen zu finden, und dreht sich um diese, aber es war nicht ganz klar, wie diese Positionen zu unterscheiden waren.

Start

Auf geht's. Aus Gewohnheit konvertiere ich die Datenobjekte im Sprachpaket in meine eigenen Datenstrukturen. Ja, es dauert einige Zeit, aber nicht sehr viel, aber ich bekomme mehr Flexibilität, arbeite in einer vertrauten Umgebung und während ich konvertiere, ist es besser zu verstehen, wie die Spielwelt funktioniert. Natürlich nicht auf einmal, aber nach Bedarf. Zum Beispiel habe ich die Minen erst wieder aufgebaut, als mich die politische Situation bei der Meisterschaft gezwungen hat, extreme Maßnahmen zu ergreifen. Ich habe ungefähr die Logik von Smartgayev kopiert und nur einen Scheck für das Vorhandensein einer Mauer zwischen mir und dem Feind hinzugefügt. Ich habe nachgesehen, sie scheinen gut zu laufen, also können wir davon ausgehen, dass wir eine Spielwelt haben.

Simulation

Jetzt gehen wir zum beliebtesten Zeitvertreib aller RAIK-Teilnehmer über: Wir schreiben eine Simulation! Nach dem Lesen des Meisterschafts-Chats wurde klar, dass das Schreiben einer genauen Simulation schlecht ist. Also habe ich sofort für die Genauigkeit getroffen. Es stellte sich heraus, dass es trotz eines einfachen Rückpralls von der Decke eine Diskrepanz innerhalb des Teakholzes gab. Es war natürlich möglich, mehrere Tage daran zu basteln und die Genauigkeit deutlich zu erhöhen, aber erstens ist nicht bekannt, welchen Gewinn dies bringen würde. Zweitens war ich zu ungeduldig und wollte wie immer das Ergebnis so schnell wie möglich sehen. Also beschloss ich, die Strategie selbst zu schreiben, und dachte, ich würde meine Simulationskurve dann gegebenenfalls korrigieren. Im Nachhinein muss ich sagen, dass ich mich vielleicht geirrt habe.
Es würde sich lohnen, die Simulation sofort wieder normal zu machen, und so mussten dort bis zum Ende der Meisterschaft Korrekturen vorgenommen werden, und dennoch blieb sie schief.

Strategiebasis

Dann gehen wir zum Standardszenario nach: wir erzeugen die Reihenfolge der Aktionen der Einheit ~~Roboter~~ simulieren eine Änderung in der Spielwelt und legt sie alle mit dem Eingang der Bewertungsfunktion (OF). Wenn es im Fußball (letztjähriges Turnier) ineffektiv war, dem Ball mit einer völlig zufälligen Anzahl von Spielern nachzulaufen (es gibt zu wenig Chancen, den Ball zu treffen, insbesondere aus dem richtigen Winkel), gibt es kein solches Problem. Grundsätzlich brauchen wir eine Simulation für zwei Dinge: Kugeln ausweichen und den Weg finden. Ein paar völlig zufällige Aktionsszenarien reichen aus, um Kugeln auszuweichen. Mehrere Dutzend Szenarien funktionieren auch für die Suche nach einem Weg mehr oder weniger, zumindest auf nicht so schwierigen Karten.

Übrigens die Suche nach dem Weg - es ist klar, dass das Zählen bis zum Ende nicht immer möglich ist, daher müssen Sie in der Lage sein, die Entfernung zu bestimmen. Mit der gleichen Simulation könnte man zeitliche Entfernungen mehr oder weniger genau berechnen. Aber hier habe ich es auch vereinfacht, nur die Abstände entlang eines rechteckigen Gitters gezählt. Diese Vereinfachung hatte natürlich einige Konsequenzen für komplexe Karten. Manchmal waren meine Einheiten bei der Suche nach Waffen immer noch verwirrt, während der Feind bereits anfing zu schießen. Diese Vorfälle waren zwar ziemlich selten.

Die Wahl des Ziels war recht einfach: Während es keine Waffen gibt, gehen wir zu Waffen, wenn es Waffen gibt, gehen wir zum Feind, und wenn es wenig "Gesundheit" gibt, gehen wir zum Medizinschrank. Bei Erste-Hilfe-Sets und Waffen wurden Objekte ausgeschlossen, die sich als Ziel näher am Feind befanden. Aus irgendeinem Grund stand für mich die Priorität der Waffen an erster Stelle der Maschine.

Die erste Bewertungsfunktion bestand aus zwei Komponenten: Gesundheit (nicht meine, sondern eine Einheit) mit einem großen Koeffizienten und die Entfernung zum Ziel mit einem kleinen Koeffizienten.
Jene. Es wurde eine Route gewählt, die nicht unter die Kugeln fällt, sondern sich gleichzeitig dem Ziel so schnell wie möglich nähert. Es ist wichtig, sich die beste Route zu merken, die für den nächsten Tick gefunden wurde. Andernfalls kann es vorkommen, dass wir eine gute Option finden, diese aber beim nächsten Tick nicht herausgeben.

Wir gehen nach vorne und die ersten Verbesserungen

Bei den Schlachten war klar, dass es fast unmöglich war, aus großer Entfernung in ihn einzudringen, wenn der Feind ein normales Ausweichen hatte. Dies ist eine Verschwendung von Kugeln. Also habe ich eine einfache Bedingung für das Schießen hinzugefügt: Schieße nur, wenn der Feind näher als 7 Meter ist. Wenn der Abstand sehr groß ist, lohnt es sich außerdem, ihn wieder aufzuladen, auch wenn nur eine Kugel im Clip fehlt. Diese beiden einfachen Bedingungen haben einiges hinzugefügt.

Dies war die erste Version, die ich gesendet habe. Am selben Tag wurde mir klar, dass eine Waffe rentabler ist als ein Maschinengewehr. Außerdem fügte er dem OB eine weitere Entfernung zum Feind hinzu, falls der Schuss nicht bald kommt. So versuchte er beim Nachladen, Abstand zu halten.

Der Start war recht erfolgreich. Ich kann mich nicht erinnern, wie hoch die Strategie vor dem Zurücksetzen (irgendwo um die ersten drei bis fünf) im Ranking gestiegen ist und nach dem Zurücksetzen zuversichtlich gestiegen ist.

Die Hauptverbesserung in der nächsten Version war auf den Versuch zurückzuführen, Erste-Hilfe-Sets zu kontrollieren. Auch hier war alles einfach: Die Entfernung zwischen den Erste-Hilfe-Sets zu mir und dem Feind wurde berechnet, und wenn sie ungefähr gleich waren, wurde angenommen, dass das Erste-Hilfe-Set gezogen wurde und somit derjenige, dem es näher ist. Dies wurde von der Bewertungsfunktion berücksichtigt. Jene. Theoretisch versuchte die Einheit, sich so zu positionieren, dass so viele Erste-Hilfe-Sets wie möglich verdeckt wurden. In der Theorie natürlich, aber nicht in der Praxis.

Danach habe ich lange Zeit keine Updates mehr gesendet. Zu meiner Überraschung erreichte die Strategie zuerst den 1. Platz und kam dann immer noch um mehr als 100 Punkte davon. Wahrscheinlich dachten alle, ich würde etwas Cooles schneiden, und ich war schockiert, wie diese elende Strategie in die Höhe schoss. Elend, denn es gibt eine ungeschickte Kontrolle über Erste-Hilfe-Sets, es gibt zwei Wenns zum Schießen, aber im Grunde ist dies ein einfaches Ausweichen und eine Bewegung, die auf einer Simulationskurve basiert.

Testen

Ich möchte darüber separat sprechen, weil Das richtige Testen ist ein sehr wichtiger Teil der Entwicklung, und viele Teilnehmer scheinen diesen Aspekt zu ignorieren. Unfall wird von Menschen intuitiv missverstanden.

Angenommen, wir führen einen Test durch und nach 40 Spielen sehen wir eine Punktzahl von 27:13 zugunsten des neuen. Das ist alles, wir haben den Gral gefunden, den Test abgebrochen und die Änderungen akzeptiert. Selbst bei gleichen Kräften besteht eine Wahrscheinlichkeit von ungefähr 2% für eine solche Situation.

Ein weiteres Beispiel: Wir starten 100 Spiele und akzeptieren die Änderungen, wenn die Punktzahl 55:45 oder mehr beträgt. Mit einer Wahrscheinlichkeit von 2,8% kann eine Version auf diese Weise spielen, die in Wirklichkeit mit der gleichen Punktzahl verlieren sollte. Ein paar Prozent des Fehlers scheinen nicht sehr groß zu sein, aber wenn 90% unserer Änderungen nicht erfolgreich sind, bedeutet dies, dass jede vierte akzeptierte Änderung nicht erfolgreich ist. Selbst 100 Spiele sind also immer noch ein mittelmäßiger Test, aber weniger - überhaupt nichts.

Natürlich kann das Starten mehrerer hundert Spiele eine unanständige Zeit in Anspruch nehmen. Es gibt verschiedene Möglichkeiten, Sie können nachts Tests durchführen, im Hintergrund fahren, Serverzeit mieten oder die Strategie schnell umsetzen :) Meine ersten Versionen funktionierten durchschnittlich 5 Sekunden lang irgendwo. zum Spiel, so viel Glück damit.

Wenn die Strategie langsam ist, können Sie abgeschnittene Versionen lokal steuern - beispielsweise weniger Suchvorgänge, weniger Mikro-Ticks. Ich habe dies im Fußball verwendet (vorheriger RAIK), es wurden keine Probleme festgestellt. Vielleicht geht die Qualität irgendwo verloren, aber auf jeden Fall ist es rentabler, als bei 20 Spielen nach Änderungen zu suchen.

Verbesserungen

Dieses Mal werde ich die Verbesserungen der Zahlen nicht bewerten. Erstens waren sie alle klein (weniger als 20%) und daher ungenau. Zweitens mehrdeutig, d.h. Die neue Version könnte die vorherige sicher schlagen und schlechter gegen andere spielen. Und drittens erinnere ich mich einfach nicht an sie.

, . , . , , .
. .. , , . , , -. , . , , . .
, , . , , , , , . , . , .
, ? , , . . , . .

-

Objektiv müssen Sie in die Richtung schießen, in der sich die Matte befindet. Schadenserwartung ist am höchsten. Es ist klar, dass dies analytisch nicht berechnet werden kann und wo Mathematik, wie wir wissen, nicht hilft, hilft die Simulation. Wir schießen in alle möglichen Richtungen und versuchen, dem Feind aus jeder Kugel einzeln auszuweichen. Jedem Pool weisen wir den minimalen Schadenswert zu, den er genau verursacht. Im Fall einer herkömmlichen Kugel ist es entweder 0 oder ihr Schaden, und im Fall einer Rakete gibt es 3 Optionen.

Jetzt kennen wir die Matte. Wenn wir Schäden in jeder Richtung separat erwarten, können wir die Matte leicht berechnen. Warten Sie auf jede Schussrichtung und wählen Sie die beste aus. Es wäre schön, diese Funktion bei der Aufzählung zu verwenden, damit das Gerät korrekt positioniert ist, aber es war zu langsam, um es für jedes Szenario aufzurufen. Es wurde einmal pro Tick für jede Einheit aufgerufen, und jetzt wurde das Schießen nicht nach Entfernung durchgeführt, sondern wenn der erwartete Schaden eine bestimmte Grenze überschritt. Der Anstieg war signifikant, und im Fall der Panzerfaust sah es ziemlich klar aus - jetzt konnte meine sogar irgendwo auf die Wand zielen, um den Feind mit einer Druckwelle zu treffen.

Aufgrund der Tatsache, dass ich diese Funktion nicht in die Suche einfügen konnte, gab es ein Problem, dass die Bedingungen für die Aufnahme bei der Suche und in der Realität unterschiedlich waren. Ich wusste nicht, wie ich dieses Problem lösen sollte, ich musste damit leben.

Danach gab es keine wesentlichen Änderungen mehr, bis ich am letzten Tag das Selbststrahlen einführte. Er fügte eine Strafe hinzu, wenn in dem Moment, in dem der Feind feuerte, kein Sprung mehr vorhanden war, da ein Sturz das Ausweichen erschweren würde. Ich habe versucht, den Weg des Feindes zum Erste-Hilfe-Kasten vorherzusagen, wenn er nur wenige Leben hat, und damit die Kontrolle über sie leicht verbessert. Er selbst fing an, Erste-Hilfe-Sets aus 60% seiner Gesundheit anstatt aus 50% zu suchen. Er fügte den Abstand zwischen seinen in der PF hinzu, damit sie sich nicht gegenseitig störten und die Panzerfaust nicht sofort zwei ausschaltete. Am Ende fügte er einen aggressiven Mod hinzu, falls sich die Situation für eine lange Zeit nicht ändert und ich an Punkten verliere, sonst bleiben meine manchmal stecken.

Ergebnisse

Wie gesagt, ziemlich schnell auf den ersten Platz in der Rangliste gekommen. Mit Ausnahme von kurzen Zeiträumen blieb ich dort bis zum Ende. In den Runden war die Situation etwas schlechter: 4. Platz im ersten, 3. Platz im zweiten. Dies zeigte, dass ich gegen starke Spieler gut gespielt habe, aber gegen schwache nicht stabil genug. Dies zeigt ganz deutlich eines der Spiele der 2. Runde, bei dem mich kostya200300, der damals auf dem letzten Platz war, mit 0 besiegte!

Selbststrahlen

Wie die meisten Teilnehmer war ich von der Möglichkeit einer Selbstexplosion nicht begeistert. Dies erhöhte den bereits beträchtlichen Zufallsfaktor erheblich. Aber es war klar, dass man nicht darauf verzichten konnte. Es stimmt, ich wollte das nicht wirklich und habe es bis zum letzten Tag verschoben. Diese Technik ist recht einfach: Wenn wir auf dem Boden stehen, der Feind sich in einem Radius der Explosion befindet und wir genug (maximal zwei) Minen haben, setzen wir Minen und schießen auf den Boden. Ich habe eine zusätzliche Bedingung gestellt, dass ich nach der Explosion einen klaren Vorteil bekomme, d. H. entweder sofort gewinnen oder mehr Gegner als ihre eigenen töten. Ich dachte, da ich einen hohen Platz anstrebe, ist es unrentabel, eins zu eins zu wechseln. Nun, es ist wie im Schach, wenn man spielt, um zu gewinnen, dann ist es unrentabel, alles hintereinander auszutauschen. So schickte ich meine mit Kamikaze-Fähigkeiten ausgestatteten Krieger in die letzte Schlacht.

Das endgültige

Wie ich bereits schrieb, spricht die Bewertung nur vom Kräfteverhältnis mit den engsten Konkurrenten, und ich hatte keine Stabilität gegenüber schwächeren Rivalen. In dieser Hinsicht war die Eliminierung der Teilnehmer für das Finale für mich ein Chaos. Andererseits führte die massive Verbreitung der terroristischen Ideologie am letzten Tag zu einer weiteren Verbreitung der Kräfteverteilung. Kurz gesagt, trotz der zuversichtlichen Führung in der Rangliste gab es kein Vertrauen in das Finale, es gab nur Hoffnung. Nach der ersten Hälfte des Finales wurde klar, dass der Hauptkampf zwischen mir und Ivan Tyamgin stattfinden wird. Ich führte zu einer kleinen Anzahl von Punkten, während der Rest weit zurückblieb.

In der Pause ~~trödelte~~ ichEr nahm die Selbstdetonation auf - etwas wurde behoben (es stellte sich heraus, dass Minen nicht oben auf der Treppe platziert werden sollten) und fügte einige Gegenmaßnahmen gegen die Detonation hinzu. Und reparierte die Simulation, weil meine bisher an der Ecke klebte.

Der Beginn des zweiten Teils der Endrunde war für mich erfolgreich, die Lücke begann langsam zu wachsen und erreichte ein Maximum von etwa 20 Punkten. Ich entspannte mich sogar ein wenig und anstatt die Ergebnisseite alle 3 Minuten zu aktualisieren, begann ich am Telefon Schach zu spielen. Als ich noch einmal hinschaute, betrug die Lücke bereits etwa 7 Punkte und rollte dann schnell zum 1 .. Ich frage mich, was sie für den 2. Platz geben? 1 Stunde bis zum Ende gibt es wieder eine Lücke. 30 Minuten wird die Lücke katastrophal reduziert. 10 Minuten - nur 3 Punkte! Eine Minute ... der Sieg scheint! Wanja hat mir nur 3 Punkte verloren. Dies liegt innerhalb der zufälligen Streuung. Der Rest liegt 50 Punkte oder mehr zurück.

Über lustige Käfer

Bereits nach dem Finale bemerkte ich, dass sich meine Einheiten in einigen Spielen seltsam verhalten - sie meiden Kugeln nicht, wenn sie sie anscheinend speziell fangen konnten und sogar, als ob sie sie speziell fangen könnten. Es stellte sich heraus, dass ich in der Pause im Finale einen Fehler gemacht hatte - als festgestellt wurde, ob der Feind mich in die Luft jagen konnte, musste berechnet werden, welcher von mir sich im Radius der Explosion befand. Hier habe ich die Koordinaten meiner eigenen und der Einheit eines anderen verwechselt und fälschlicherweise angenommen, dass die Explosion dort stattfinden würde, wo ich bin, und somit garantiert in den Radius der Explosion fallen würde. Die reale Explosion wurde bereits vom richtigen Punkt aus betrachtet, sodass in der Simulation der Feind selbst von mir weg explodieren konnte. Normalerweise fügte es der Schätzung nur eine große Konstante hinzu, aber es hatte keinen wirklichen Einfluss auf irgendetwas. Wenn der Feind jedoch nicht genug Minen hatte, um mich in die Luft zu jagen, stellte sich heraus, dass es für mich rentabel war, eine Kugel zu fangenso dass der Feind bereits genug Minen hatte und ich genau die Ergänzung zur Bewertung bekam. Vielleicht lag es an Schlafmangel oder einer betrunkenen Dose Bier, aber tatsächlich passieren immer Fehler.

Fazit

Das Spiel war zwar nicht so spektakulär wie Fußball, aber aus strategischer Sicht nicht weniger interessant. Der Schwellenwert war relativ niedrig, was sich positiv auf die Teilnehmerzahl auswirkte. Ich habe im Monat der Meisterschaft viele Emotionen erhalten, sowohl Freude als auch Emotionen, und dafür bin ich den Organisatoren dankbar. Ich danke auch allen Teilnehmern, insbesondere Vanya Tyamgina, dass sie mich im Finale nicht gelangweilt haben.

Fortsetzung der Teilnahme (und des Sieges) am russischen AI Cup 2019