Mein Name ist Andrey Rybalka, ich nehme am russischen AI Cup unter dem Spitznamen Lama teil und ich werde Ihnen noch einmal sagen , wie man kein Macbook gewinnt. Glücklicherweise bin ich eine erfahrene Person - mit diesen Händen habe ich nicht einmal 7 Stücke gewonnen.

Die diesjährige Aufgabe war also ein Platformer / 2D-Shooter, für den man einen Bot schreiben musste. Das Spiel sah so aus:

Der Bot sah so aus:

Wenn Sie daran interessiert sind, wie Bild Nr. 2 in Bild Nr. 1 gespielt wird, klicken Sie bitte unter Katze.

Wenn Sie nicht teilgenommen und andere Artikel nicht gelesen haben, empfehle ich Ihnen, zunächst zu sehen, wie die Dynamik auf der Website oder in der Tube aussieht:

Turniersystem

Für den Anfang sind mehr als 2 Wochen für die Programmierung vorgesehen. Dann beginnt die erste Runde. Es dauert 2 Tage und die 300 besten gehen weiter. Nach der Runde ändern sich die Spielregeln (jetzt kontrollieren wir zwei Charaktere gleichzeitig) und es wird eine weitere Woche gegeben, nach der die zweite Runde vergeht. Dann sind die Regeln wieder kompliziert (jetzt spielen wir auf viel komplexeren Karten), es wird eine weitere Woche gegeben und schließlich spielen wir das Finale.

Aber das ist nicht das Ende. Nach dem Finale gibt es eine weitere Woche, an deren Ende der Sandkasten einfach stoppt, und die 6 besten, ausgenommen die Sieger des Finales, werden ebenfalls ausgezeichnet. Der grundlegende Unterschied zwischen dem Sandbox-Finale und dem Meisterschaftsfinale besteht darin, dass in der Sandbox Spiele in einem zufälligen Format erstellt werden und nicht nur im Format der aktuellen Runde.

Teilnahmegeschichte

Wo ohne? Sie können überspringen, wer nicht interessiert ist. Der technische Teil wird niedriger sein.

Beta-Testwoche und erste Runde

Wie es scheint, habe ich am Tag nach dem Start des Open Beta-Tests mit dem Programmieren begonnen. Aber persönlich war es für mich etwas demotivierend, dass die Organisatoren dieses Mal im Gegensatz zur Vergangenheit beschlossen, wieder von der Praxis des Publizierens eines Pseudocodes eines Simulators abzurücken. Unter den Teilnehmern waren sicherlich diejenigen, die gerne einen Simulator durch Reverse Engineering schreiben, aber ich bin nicht einer von ihnen, und mir war es langweilig, dies zu tun. Da dies nicht meine erste Meisterschaft war, wusste ich, dass ich mich früher oder später beteiligen würde, aber aus dem oben beschriebenen Grund wurde ich zu spät beteiligt. Infolgedessen konnte ich mich, was einige Teilnehmer in den ersten Tagen taten, zwingen, in nur eineinhalb Wochen fertig zu werden. Als Ergebnis habe ich 5 Tage vor der ersten Runde die erste Codezeile des Bots geschrieben. Kurz gesagt, zu Beginn der ersten Runde war ich noch nicht fertig und die Runde verlief ohne meine Teilnahme. Ich entschied, dass ich mich durch Durchwahl direkt in die zweite Runde begeben würde.

Zweite Runde

Zu diesem Zeitpunkt habe ich bereits in vollem Umfang programmiert, durchschnittlich 4 bis 6 Stunden pro Tag. Einige Tage vor dem Start der zweiten Runde habe ich die erste Version des Bots hochgeladen. Sie stieg sofort zügig auf und stieg schnell in die Top-10-Sandkästen. Dann begann die Runde, wo ich den fünften Platz belegte.

Final

Ich verbrachte den ersten Abend der letzten Woche (von vier, weil ein Start für Freitag geplant war), um den Weg zu finden. Es gab noch viele Ideen, aber worauf man sich konzentrieren sollte und welche der Ideen möglicherweise das größte Ergebnis bringen würde, war nicht klar. Deshalb habe ich zunächst versucht, das zu verbessern, was die meisten Niederlagen verursachte. Am Dienstag und Mittwoch waren dies Verbesserungen beim Zielen und Schießen sowie bei der Kontrolle der Erste-Hilfe-Ausrüstung.

Dann sah ich, dass etwas passiert war, mit dem ich lange gerechnet hatte, aber ich hoffte, dass dies nicht passieren würde - einige Gegner begannen, Minen aktiv zu nutzen.

Tatsache ist, dass die Organisatoren während der OBT auf den Vorschlag der Teilnehmer eingegangen sind und eine der Spielmechaniken geändert haben. Im Allgemeinen ist dies natürlich gut, wenn die Teilnehmer angehört werden. Aber gerade diesmal war das Vorhandensein von Rückmeldungen ein grausamer Scherz. Kurz gesagt, die Organisatoren ermöglichten die Detonation von Minen mit einem Schuss.

Das ist an sich logisch. Wenn ich eine Mine wäre und sie auf mich schießen würden, würde ich auch explodieren. Das Problem ist jedoch, dass wir nach Punkten gespielt haben und Punkte nicht nur für Tötungen, sondern auch für Schäden vergeben wurden. So stellte sich heraus, dass Sie, wenn Sie dem Feind nahe genug kommen, Minen unter sich platzieren und auf ihn schießen, sowohl den Feind als auch sich selbst mit einer Explosion töten. Es ist unmöglich auszuweichen. Sie bekommen beide 1000 Punkte für beide Charaktere, die sterben, aber Sie bekommen auch Punkte für Schaden. Wenn der Feind gesund war, erhalten Sie 1000 Punkte für das Töten und 100 für den Schaden und den Feind - nur 1000.

Zwar wussten alle Bescheid, doch oben setzte bis zuletzt fast niemand Minen ein. Ich weiß nicht wie andere, aber persönlich habe ich es nicht benutzt, nur weil ich die ungewollte Fehleinschätzung nicht missbrauchen wollte. Aber wie sie in einem Film sagten, wusste ich, dass wir früher oder später zu diesem Müll übergehen werden.

Kurz gesagt, mitten in der Nacht von Mittwoch auf Donnerstag habe ich mich selbst gestört. Rein situativ, nichts fortgeschrittenes. Nur nach dem Prinzip, dass mein Charakter es verdient, sich selbst zu töten, und das kann er auch. Wie die Praxis gezeigt hat, planten einige andere Teilnehmer den Einsatz von Minen im Voraus, so dass sie einen fortgeschritteneren Selbstmord einführten, planten jedoch strategisch, ihn kurz vor dem Finale auszulösen. Infolgedessen stellte sich heraus, was passiert ist - Platz 9 im Finale wie auch im letzten Jahr.

Sandbox-Finale

Nach dem Finale verließ ich die Stadt für die Ferien. Eine Woche später kehrte er zurück und am ersten Abend, buchstäblich in 2-3 Stunden Arbeit, wurden die Minen stark verbessert, worüber ich im technischen Teil mehr schreiben werde. Die restlichen Änderungen betrafen hauptsächlich die Bearbeitung von Fehlern und die Vervollständigung der Evaluierungsfunktion. Kurz gesagt, ein wenig Programmierung und viele Tests.

Technischer Teil

Entweder die Geschwindigkeit von Java oder der Krümmungsradius der Hände, sondern beide zusammen ließen mich wieder nicht mit einer reinen Simulation zurechtkommen. Daher sind die Bewegung, das normale Schießen und die Installation von Minen von mir getrennt.

Simulation

Mit den Augen eines Bots sah die Welt so aus:

Auf dem Video denke ich, und so ist alles ungefähr klar. In der oberen linken Ecke befindet sich das Debug der Auswertungsfunktion. Sie können sehen, woraus der Score jeder Flugbahn besteht. Gelbe Silhouetten (zum Beispiel um 2:30 Uhr) - dies sind die gleichen Flugbahnen in 9 Richtungen, um die sie niedriger sein werden. Linien von Pfeilen irgendwo ab 2:50 sind eine Suche nach einem Weg (rot - zum Feind, grün - zum Verbandskasten, gelb-grün - zur Waffe, blau - zur Mine). Die grünen Quadrate am Ende des Videos sind meine PVS-Kacheln, die von der ausgewählten Kachel aus sichtbar sind. Die roten Punkte in ihrer Mitte zeigen an, woher die umgekehrte Sichtbarkeit stammt.

Zeichenbewegungen simulieren ohne Mikrotechnik. Aufzählungsflüge auch, aber bei ihnen verwende ich mehrere Hacks, so dass Situationen weniger wahrscheinlich sind, in denen die Kugel bei vollem Häkchen den Charakter „durchläuft“, ohne ihn zu berühren, obwohl sie ihn mit Mikrotik hätte berühren sollen. Wenn Sie zum Beispiel darüber nachdenken, kann die beschriebene Situation nur an den Ecken auftreten:

Bei Tick 1 befindet sich die Kugel an Position 1, bei Tick 2 an Position 2. Ohne Mikrotik - Boris-Meerrettich - bekommt man, mit Mikrotik - Ohrschuss. Zu diesem Zweck muss sich die Position des Aufzählungszeichens in Teilstrichen 1 und 2 auf einer anderen Seite befinden als mindestens eine der Seiten des Zeichens oder der Kachel (ein Minze-Rechteck). Auf diese Weise ist es möglich, eine Kugel ohne Mikrotechnik zu simulieren, bis im obigen Bild die Bedingung old_bullet.x > character_left_side.x != new_bullet.x > character_left_side.x ist. In diesem old_bullet.x > character_left_side.x != new_bullet.x > character_left_side.x sollten Sie dieses Häkchen genauer analysieren .

Dann berechnete ich bei jedem Tick die Flugbahnen aller fliegenden Kugeln neu, bevor sie mit der Wand kollidierten, und speicherte ihre Position in jedem Tick im Array, sodass Sie in der Simulation schnell nach Kollisionen mit ihnen suchen konnten.

Für eine Panzerfaust berechnete ich nach dem Aufprall auf eine Mauer mathematisch ohne Mikrotechnik den genauen Aufprallpunkt, um das Epizentrum der Explosion korrekt zu berechnen.

Außerdem füllte ich mit jedem Tick das Array dodge_trajectories - simulierte die Bewegung jedes Charakters, einschließlich der Feinde, in 8 Richtungen für 25 Ticks (gelbe Silhouetten im Video des Visualizers, nachdem das Kontrollkästchen für den möglichen Traj aktiviert wurde. Zum Beispiel um 2:30 Uhr). Und wie bei Kugeln behielt er bei jedem Tick alle möglichen Positionen bei. Es wurde dann an vielen Orten verwendet, von denen ich einige erwähnen werde.

Ich habe die PVS auch im Voraus nach Kacheln berechnet. Für jede Zelle habe ich eine Liste mit Kacheln erstellt, deren Mitte darin zu sehen ist. Es wurde durch Raytracing berechnet. Dies ist im Video vom Visualizer am Ende zu sehen. Grüne Quadrate sind Kacheln, die von der ausgewählten Zelle aus sichtbar sind. Die roten Punkte in ihrer Mitte zeigen an, woher die umgekehrte Sichtbarkeit stammt.

Suche nach einem Weg

Wird durch den Dijkstra-Algorithmus gemäß Wegpunkten implementiert. Die Kachel, auf der Sie stehen können, wurde als Wegpunkt betrachtet. Die Anpassung des Algorithmus für den 2D-Plattformer ist eigenständig und daher aus Optimierungsgründen auf Krücken aufgebaut. Aber es hat schnell genug funktioniert: Ich habe zuvor Dijkstra (ich habe nicht herausgefunden, wie man es richtig sagt) von jedem Thema auf der Ebene zu jedem Plättchen erstellt. Ich habe nur Straßen gebaut, die über eine Zwei-Wege-Geländefähigkeit verfügen. Dies war notwendig, damit man später sehr schnell von jedem Plättchen zu jeder Erste-Hilfe-Ausrüstung / Waffe / Mine gelangen konnte. Es war möglich, diese Einschränkung aufzuheben, aber in der Praxis hielt ich es für vernünftiger, Zeit für andere Dinge zu verwenden, da diese Einschränkung nicht viel Schaden anrichtete.

Außerdem zählte ich jedes Mal, wenn ich auf ein anderes Plättchen mit einem beliebigen Charakter (meinem und dem des Feindes) wechselte, für ihn den Weg zum nächsten Feind, zur Erste-Hilfe-Ausrüstung sowie zur Mine und zu den Waffen, falls er sie noch brauchte.

Auf meinem Heimcomputer dauerte bei einem Spiel mit 1000 Ticks die gesamte Pfadsuche insgesamt etwa 100 ms.

Wenn der Pfad einen Feind oder Freund kreuzt, füge ich einfach ein paar Dutzend Einheiten zu seinem Gewicht hinzu. Wenn es also einen relativ kurzen Umweg gibt oder wenn es danach rentabler ist, zu einem anderen Objekt zu rennen, werde ich dies tun. Im Video aus dem obigen Visualizer ist dies um 2:55 zu sehen, wo der Weg zum nächsten Feind umgangen wurde, weil Ein gerader Pfad kreuzt das zweite Zeichen.

Suchpfad-Visualisierung:

Durchscheinende violette Quadrate sind Wegpunkte, sie sind auch die Eckpunkte des Graphen. Lindgrüne Pfeile - Kanten ¹ Spalte ²
¹ nicht zu verwechseln mit Rippen, ² Zufälle monarchischer Natur sind zufällig [ca.]

Bewegung

Zwei Charaktere gingen der Reihe nach. Wenn Sie nur dachten - "und jetzt ist es in die Top 10 gekommen?!", Dann haben Sie richtig gedacht. :) Es gab nicht genug Ressourcen, um mit beiden zu laufen. Eine Ausnahme war das Erscheinen einer neuen fliegenden Kugel.

Die Basis für die Auswahl einer Flugbahn ist die Genetik ohne Kreuzung. Aber wenn sich die Genetik letztes Jahr im Fußball perfekt gezeigt hat, dann hat sie dieses Jahr einen sehr kleinen Vorteil gebracht. Meine Experimente zeigten ein sehr nahes Ergebnis sowohl in der Genetik als auch bei zufälligen Suchen. Ich sehe mehrere Gründe dafür, aber der wichtigste scheint mir der folgende zu sein: Im Fußball hatten wir ein festes Ziel - den Ball. Die meiste Zeit war sein Verhalten vorhersehbar - wenn wir eine gute Flugbahn gefunden haben, um den Ball auf das Tor zu schlagen und ihm zu folgen, wird diese Flugbahn nach 20 Zecken wahrscheinlich immer noch gut sein, weil Der Ball kann seinen Weg nicht spontan ändern. Aber dieses Jahr haben wir nicht mit dem Ball gespielt, sondern mit feindlichen Charakteren. Sie änderten ihr Verhalten mit jedem Tick. Die Relevanz der Flugbahn blieb also sehr kurz.

Ich habe aus zwei Gründen immer noch Genetik verwendet:

Ich habe gerade ihren Code vom letzten Jahr kopiert. Es war sogar komisch, wie wenig ich bis auf die Auswertungsfunktion Änderungen vornehmen musste, damit sich der Bot erträglich bewegte. Kurz gesagt, ich habe anderthalb Wochen lang einen Simulator geschrieben und dann ungefähr eine Stunde lang die Logik der Bewegung aus dem letzten Jahr kopiert. In einer weiteren Stunde habe ich eine einfache Schätzung abgegeben, und der Bot begann beim Schießen eines Schnellstarts ziemlich stabil damit zu gewinnen.
Ich liebe anscheinend den Schmerz. Ansonsten kann ich nicht erklären, warum ich wieder in Java geschrieben habe und nicht wie alle normalen Top-Versionen:

Also musste ich alles in jeder Hinsicht tun, damit die Strategie nicht bei jedem ersten Spiel mit einer Auszeit zusammenbrach. Dank der genetischen Herangehensweise konnte ich einen Schnappschuss der Simulation der Welt und der gezählten Punkte speichern und dann bei der Berechnung der nächsten Generationen die Schnappschüsse nur für das erste mutierte Gen deaktivieren.

Das heißt Grob gesagt, wenn ich in der ersten Generation 10 Ticks nach rechts gegangen bin und dann hochgesprungen bin und in der zweiten Generation eine Mutante ausgewertet habe, die 10 Ticks nach rechts gegangen ist und dann runtergesprungen ist, dann ist der Bezugspunkt für die Mutante der zuvor berechnete Schnappschuss der Welt und der Punkte danach 10 Bewegungen nach rechts. Somit habe ich die Kalkulation deutlich reduziert.

Igogo, ein ungefährer Bewegungsalgorithmus:

Wir erzeugen N zufällige Genotypen. Jedes besteht aus M zufälligen Genen. Bei jedem Gen handelt es sich um Action-codierte Nummern: Eine Nummer ist für die Bewegungsrichtung verantwortlich, die zweite für das Springen / Gehen / Abspringen, die dritte für das Grundschießen (nur für die Bewertungsfunktion, der Grundschießalgorithmus wird weiter unten beschrieben), die vierte für die Anzahl der Wiederholungen Aktion. Die Gesamtzahl der Aktionen im Genotyp überschreitet zusammen mit den Wiederholungen nicht die Simulationstiefe - 40 Ticks.
Wir fügen ihnen eine Reihe von hartcodierten Genotypen hinzu: direkte Bewegung in 9 Richtungen (8 Seiten + Stillstand) und ein paar einfache Voreinstellungen, die in der Praxis dazu beigetragen haben, einige typische Situationen im Labyrinth etwas schneller zu überwinden. Zum Beispiel sind dies die Flugbahnen: ⮤ ⮤
Fügen Sie den besten Genotyp aus dem vorherigen Zug hinzu.
Bewerten Sie alles, lassen Sie das M am besten.
Wir schaffen die nächste Generation, in der in jedem Genotyp ein oder mehrere Gene mutiert sind.
Wir fügen sie dem allgemeinen Pool hinzu, der bereits das M-Beste der letzten Generation enthält.
Wir wiederholen ab Punkt 4 noch einige Male.

Bewertungsfunktion

Eigentlich der Ort, an dem die Strategie lebt.

Während der Meisterschaft wurde eine ganze Reihe von Metriken aller Art hinzugefügt (um genau zu sein 57). Einige von ihnen haben das Finale nicht miterlebt. Der andere Teil überlebte, aber vor dem Hintergrund der Inflation des Ergebnisses während der Meisterschaft hatte dies praktisch keinen Einfluss auf das Ergebnis, aber der Rest in der Größenordnung von 20 bis 25 war genau für die Bewegung und das Grundschießen verantwortlich.

Ich werde einige Beispiele für wichtige Metriken in zufälliger Reihenfolge geben:

Strafe für eine Kugel / Panzerfaust-Explosion in mir.
Bonus für Freiheitsgrade. Das heißt für die Anzahl der Richtungen (auf / ab / links / rechts), in die ich mich von der aktuellen Kachel bewegen kann. Je mehr Freiheitsgrade vorhanden sind, desto größer ist die Wahrscheinlichkeit, einer Kugel auszuweichen. Dieser Bonus zwang den Bot, auf Plattformen und Treppen zu bleiben. Der Bonus ist dreimal höher, wenn der Gegner eine Panzerfaust hat.
Strafe für die Entfernung (durch die Suche nach dem Weg) zum nächsten Erste-Hilfe-Kasten; für die durchschnittliche Entfernung (durch die Suche nach dem Pfad) zu allen Erste-Hilfe-Sets; weil der Weg von ihm zu der ihm am nächsten gelegenen Reiseapotheke kürzer ist als der Weg von mir zu seiner (!) Reiseapotheke.
Strafe dafür, dass der Feind meinen Kopf sieht.
Strafe dafür, dass der Feind meine Beine sieht (Punkte 4 und 5 zwangen den Bot, sich hinter Teilschutz zu verstecken).
Angriffsbonus beim Nachladen feindlicher Waffen.
Bonus für Schüsse gemacht.
Strafe für zu viel oder zu wenig Distanz zum Feind. Es hing von mehreren Faktoren ab: der Gesundheit beider, ob die Waffen beider nachgeladen wurden usw.
Bonus für gefährliche Arbeitsbedingungen.
Strafen für den Fallzustand und für den Flugzustand auf dem Sprungfeld (da diese beiden Zustände nicht unterbrochen werden können und daher viel weniger wahrscheinlich sind, dass sie sich der Kugel entziehen).
Der Bonus für die Anzahl der Verbandskästen, die sich auf der anderen Seite von mir befinden, im Vergleich zum Feind (d. H., Wenn sich der Feind zu meiner Rechten befindet, bekomme ich einen Bonus für die Anzahl der Verbandskästen, die sich zu meiner Linken befinden. Dies ergab im Wesentlichen Sinn Runde 1 und 2, in denen der einzige Weg vom Feind zu diesen Verbandskästen durch mich führte).
Bonus für den Weg zum Feind, zur Erste-Hilfe-Ausrüstung (wenn ich verwundet bin), zu einer Mine (wenn ich weniger als zwei habe), zu Waffen (wenn es keine gibt).
Strafe für die Nähe der Mauern, falls der Feind eine Panzerfaust hat. Genauer gesagt habe ich überlegt, wie viele Zecken die feindliche Rakete, wenn sie sie abfeuert, in die Nähe der Mauer fliegen wird, und auf dieser Grundlage wurde die Zone in der Nähe der Mauer, aus der es unmöglich ist, der Explosion zu entkommen, als gefährlich eingestuft und ich erhielt eine Geldstrafe dafür, dass ich darin war.
Neujahrsbonus.

Bullet Evasion

Aus den oben genannten Gründen geschieht dies automatisch

Zielen

Es ist viel los. Das vielleicht wichtigste ist ein einfacher und effektiver Algorithmus, der entscheidet, ob ich eine Waffe auf den Feind richten soll (weil das Zielen die Verbreitung von Waffen erhöht):

Wir betrachten den Winkel zwischen (last_angle - min_spread) und (last_angle + max_spread).
Wir schießen die Strahlen von der Mitte meines Charakters zu den beiden Ecken des feindlichen AABB , die der Senkrechten am nächsten liegen. Wenn einer von ihnen außerhalb des Bereichs liegt (last_angle - min_spread) ... (last_angle + max_spread), wird dieser Bereich abgeschnitten.
Wir betrachten den Winkel zwischen diesen Strahlen.
Teilen Sie die erste zweite Ecke durch die erste, wir erhalten Deckung (Coverage). Stellt die aktuelle Wahrscheinlichkeit in Prozent dar, dass sich die Flugbahn des abgefeuerten Geschosses mit der des Gegners schneidet.
Wir simulieren eine Aktion, bei der das Zielen auf einen Feind mit einer Änderung der Streuung einhergeht.
Wiederholen Sie die Schritte 1..4 für die neue Menge [last_angle, min_spread, max_spread]. Aus diesem Grund überlegen wir uns, welche Berichterstattung wir anstreben.
Als Ergebnis haben wir die aktuelle Abdeckung sowie die vorhergesagte Abdeckung für den Fall, dass wir die Waffe auf den Feind richten. Wenn die geschätzte Abdeckung größer als die aktuelle ist, zielen wir ab.

Demo 2 Punkte:

Wenn die Linien grün sind, fällt der Feind vollständig in den Zielbereich. Orange - teilweise rot - fällt überhaupt nicht.

Aber ich ziele normalerweise nicht auf den Bauch des Feindes, sondern auf einen optimaleren Punkt.

Wenn für eine Pistole und ein Sturmgewehr der Feind in der Luft ist, überlege ich, wie viele Zecken die Kugel ihre aktuelle Position erreichen wird, dann entnehme ich aus dem dodge_trajectories Array, das oben beschrieben wurde, alle möglichen Positionen durch diese Anzahl von Zecken, dodge_trajectories alle 8 Positionen und berücksichtige beim Zielen dass der Feind an diesem gemittelten Punkt ist.

Wenn er auf dem Boden steht, ziele ich "auf den Kopf", basierend auf den Überlegungen, dass er nur nach oben springen kann, so dass ein Schuss in den Kopf viel schwieriger auszuweichen ist als ein Schuss in den Bauch und noch schwieriger in die Beine.

Für eine Panzerfaust nehme ich ebenfalls 8 mögliche Positionen durch so viele Zecken ein, wie die Rakete den Feind erreicht. Für sie baue ich einen Kegel (genauer gesagt einen Kreisabschnitt), der all diese Positionen beschreibt, und innerhalb dieses Kegels sortiere ich die Trajektorien mit einigen Schritten. Für jede Flugbahn simuliere ich einen Raketenflug sowie eine Explosion im Falle eines Treffers in der Wand. Die Flugbahn, in der der Feind am wenigsten ausweichen kann, benutze ich zum Zielen.

Sogar in einigen Fällen, wenn ich vom Sprungbrett stürze und fliege (d. H. Wenn der Feind nicht unterbrechen kann), betrachte ich einfach den Abfangpunkt durch die Kugel des Feindes, indem ich das System der Bewegungsgleichungen löse. Der Code wurde von seinem eigenen Hockey-Bot aus dem Jahr 2014 kopiert, wo er zum Abfangen des Pucks verwendet wurde. :)

Unter anderem habe ich in bestimmten Situationen das Zielen abgebrochen, wenn sich für die nächsten 10 Ticks eine Position auf meinem Weg befindet, in der sich der Strahl von der Mitte dieser Position in Richtung des aktuellen letzten Winkels mit dem Feind schneidet. Dies ermöglichte es mir, mit Bewegung zu zielen, ohne den Winkel zu ändern und daher die Streuung zu erhöhen.

Schießen

Das Grundschießen wurde in die gefundene Flugbahn eingenäht und war rein situativ. Aber auch jeder Tick, den mein Bot versuchte zu berechnen, ob es Sinn macht, jetzt zu schießen, und wenn ja, schoss er. Z.B:

wenn der Feind nicht garantiert ausweichen kann;
wenn die Deckung über einem festen Wert lag.

Wenn es sich bei meiner Waffe um eine Panzerfaust handelte, simulierte ich im Falle eines sofortigen Schusses mit einigem Schritt alle möglichen Flugbahnen innerhalb der Ausbreitung. Und wenn das Ergebnis zeigt, dass der potenzielle Nutzen den potenziellen Schaden übersteigt, habe ich geschossen. Ich bewertete den Vorteil anhand von 4 Metriken in absteigender Reihenfolge der Wichtigkeit für mich und den Feind: garantierter Tod (mein oder der Feind), möglicher Tod, garantierter Schaden, möglicher Schaden. Wenn es mindestens eine Flugbahn gab, in der ich mich garantiert umgebracht und möglicherweise nur den Feind getötet habe, habe ich nicht geschossen.

Es gab noch andere Schecks. Zum Beispiel könnte ich einen Schuss stornieren, wenn die potenzielle Reichweite im nächsten Tick meiner Flugbahn höher ist als in der aktuellen.

Im Allgemeinen sagte mir die Logik, dass das grundlegende Schießen ausgeschaltet werden sollte, aber Tests zeigten das Gegenteil. Ich kann mir nicht vorstellen warum.

Minen

Zum Zeitpunkt des Finales steckten sie noch in den Kinderschuhen: Ich habe jede Zecke angekreuzt, was passieren würde, wenn ich jetzt je nach Gesundheit des Gegners 1 oder 2 Minen platziere und sie erschieße. Wenn es mir garantiert ist, den Feind zu töten und wenn es für mich von Vorteil ist (entweder nach Punkten oder weil nur der Feind sterben wird), habe ich es getan.

Nach dem neuen Jahr, als ich von einer Reise zurückkam, schrieb ich am ersten Abend den Algorithmus, der mich an 2-4 Stellen in der Tabelle brachte. Der Algorithmus war einfach: Ich habe nur jeden Tick simuliert, was passieren würde, wenn ich sofort in den Berserker-Modus wechseln und auf den Feind rennen würde, um ihn so schnell wie möglich mit einer Mine in die Luft zu jagen. Für den Feind simulierte ich ein einfaches Ausweichen mit den gleichen Ausweichstrecken: Ich nahm drei Strecken, die den Abstand zu mir vergrößerten. Wenn ich mich zum Beispiel links vom Feind befand, analysierte ich drei Fälle: Der Feind rennt nach rechts davon; der Feind läuft nach rechts und springt; rennt nach rechts und springt nach unten. Wenn ich in allen drei Fällen garantiert Zeit hatte, ihn mit einer Mine zu töten, und er garantiert nicht in der Lage war, Minen vor mich zu legen, tat ich es.

Außerdem konnte der Algorithmus auf der Ebene der Schnellstartstrategie springen oder springen - einfach basierend auf dem Unterschied in der Y-Koordinate.

Infolgedessen endete auf den endgültigen Karten fast jedes Spiel mit weniger als 1000 Ticks und Selbstbeschuss meiner beiden Charaktere.

Pazifismus

Um zu sehen, wie effektiv meine Minen waren, entschloss ich mich, meine zuvor auf dem Telegrammkanal getroffene Annahme zu überprüfen , dass es im Finale möglich war, einen Platz an der Spitze einzunehmen, ohne zu schießen. Also habe ich nur das Schießen in meinem Bot genommen und ausgeschaltet, mit Ausnahme eines Minenschusses. Das einzige ist - um die Wertung nicht zu verlieren, wurde dieser Modus nur aktiviert, wenn ich genug Minen hatte, um den Feind zu töten.

Kurz gesagt, mein Bot ist Pazifist geworden. Um seinen Frieden und seine Demut zu demonstrieren, schaute er nicht einmal auf den Feind (siehe Video). Na ja, er hat manchmal Minen geschossen, denken Sie. Ich habe nicht auf Gegner geschossen! Und wenn sie gleichzeitig starben - was können Sie tun, ein tragischer Unfall?

Im Allgemeinen habe ich diese Version auf die Seite hochgeladen, 4 Spiele mit jeweils den dann Top 3 erstellt und ...

... haben jeweils 3 von 4 Spielen gewonnen. Im Allgemeinen ist es seltsam, dass die Nachbarn mitten in der Nacht nicht gekommen sind, um sich über mein homerisches Lachen zu beschweren. :)

Bewundern Sie sich:

Wenn ich diese 2-3 Stunden vor dem Finale und nicht danach verbringe, würde dieser Artikel vielleicht erklären, wie man ein MacBook gewinnt und nicht, wie man es auf alle Fälle vermeidet, wer weiß. Leider kennt die Geschichte die Konjunktivstimmung nicht.

Testen

Im Allgemeinen habe ich alle Änderungen so oft getestet, dass das Ergebnis statistisch signifikant war. Genauer gesagt sollte die Untergrenze des Konfidenzintervalls 50% überschreiten. Für das Finale der Sandbox wählte das Skript die Koeffizienten aus. In früheren Jahren habe ich Genetik ausprobiert, aber es hat schlecht funktioniert - für ein normales Ergebnis musste man zu viele Spiele spielen. Diesmal habe ich also nur einen Koeffizienten nach dem anderen geändert und 200 Spiele gewonnen. In den Fällen, in denen das Ergebnis gut war, führte ich zusätzliche Tests durch. Kurz gesagt, ließ über Nacht zwei Dutzend Koeffizienten und hatte ein Ergebnis am Morgen.

Abschließend

Das hat irgendwie alles mit Trauer in zwei Hälften geklappt.

In den letzten Tagen vor dem Ende des Sandkastens verbrachte ich die meiste Zeit auf dem zweiten Platz in der Tabelle, aber ein paar Stunden vor dem Ende des Sandkastens hatte ich kein Glück und startete eine Reihe von Spielen nach den Regeln der Runden 1 und 2, während Meine Strategie orientierte sich am besten an den Regeln des Finales. Zum Beispiel gibt es hier von 13 Spielen nur 1 nach den endgültigen Regeln. Also habe ich auch meine Gewinnquote in diesen Spielen viel schlechter als üblich herausgefunden. Im Allgemeinen ist der allmächtige Zufall:

Infolgedessen verlor ich zu viele Spiele, verlor meinen ganzen Vorteil und fiel von 2 auf 4 Plätze und hatte keine Zeit, mich zu erholen, weil die Meisterschaft vorbei war. Es ist gut, dass der Sandkasten nicht den ersten Platz in der Gewinnerliste verloren hat.

Ich möchte mich noch einmal bei Mail.ru Group für diese nächste wundervolle Meisterschaft bedanken. , , , ( 1100 ). — , . , . , , , !

, . , , . " 8 ".

Über die Unveränderlichkeit: Geschichte des 9. Platzes des russischen AI Cup 2019