Mini ai cup 2 oder fast AgarIO - was könnte man tun, um zu gewinnen?

Hallo allerseits! Dieses Mal möchte ich darüber schreiben, wie ich es geschafft habe, den Mini AI Cup 2 Wettbewerb zu gewinnen. Wie in meinem letzten Artikel wird es praktisch keine Implementierungsdetails geben. Diesmal war die Aufgabe weniger umfangreich, aber dennoch gab es viele Nuancen und kleine Dinge, die das Verhalten des Bots beeinflussten. Selbst nach fast dreiwöchiger aktiver Arbeit am Bot gab es daher noch Ideen zur Verbesserung der Strategie.



Unter dem Schnitt viele Gifs und Verkehr.

Die hartnäckigen werden es herausfinden, der Rest wird entsetzt davonlaufen (aus den Kommentaren zu dem kurzen komprimierten Teil).

Diejenigen, die zu faul sind, um viel zu lesen, können zum vorletzten Spoiler des Artikels gehen, um eine kurze, kurze Beschreibung des Algorithmus anzuzeigen , und dann können Sie von vorne mit dem Lesen beginnen .

Link zur Quelle auf dem Github .

Werkzeugauswahl

Wie beim letzten Mal habe ich viel Zeit gebraucht, um darüber nachzudenken, wo ich anfangen soll. Die Wahl fiel unter anderem auf zwei Sprachen: Java, mir vertraut und schon seit Studienzeiten in C ++ ganz vergessen. Aber da es mir von Anfang an so schien, als ob das Haupthindernis für das Schreiben eines guten Bots weniger die Entwicklungsgeschwindigkeit als vielmehr die Produktivität der endgültigen Lösung wäre, fiel die Wahl dennoch in C ++.

Nach der erfolgreichen Erfahrung, meinen eigenen Visualizer zum Debuggen des Bots in früheren Wettbewerben zu verwenden, wollte ich auch diesmal nicht auf einen verzichten. Aber der Visualizer, den ich für QW for CodeWars für mich selbst geschrieben habe, sah für mich nicht nach einer idealen Lösung aus, und ich entschied mich für diesen Visualizer. Es wurde ebenfalls unter CodeWars hergestellt, erforderte jedoch keine ernsthafte Verarbeitung für die Verwendung in diesem Wettbewerb. Die relative Einfachheit der Verbindung und die Bequemlichkeit, das Rendern an einer beliebigen Stelle im Code aufzurufen, spielten für ihn eine Rolle.

Nach wie vor wollte ich unbedingt jeden Tick im Spiel debuggen - die Fähigkeit, eine Strategie in einem beliebigen Moment des getesteten Spiels auszuführen. Da der Plug-in-Visualizer dieses Problem nicht lösen konnte, fügte ich mit Hilfe des # ifdef-Paares (in das ich auch die für das Rendern verantwortlichen Codeteile eingewickelt habe) jedem Tick das Speichern der Context-Klasse hinzu, die alle erforderlichen Werte der Variablen aus dem vorherigen Tick enthielt. Im Kern war die Lösung ähnlich wie in Code Wizards, aber diesmal war der Ansatz nicht so spontan. Nachdem Sie das gesamte Spiel simuliert hatten, wurden Sie aufgefordert, die Nummer des Spielticks einzugeben, der neu gestartet werden muss. Informationen über den Status von Variablen vor diesem Tick wurden aus dem Array entnommen sowie die von der Eingabestrategie empfangene Zeile, sodass ich die Bewegungen meiner Strategie in beliebiger Reihenfolge spielen konnte.

Starten Sie

An dem Tag, an dem die Regeln geöffnet wurden, kam ich nicht vorbei und schaute am ersten Abend, was uns erwartet. Er zögerte nicht, sich über das json-Eingabeformat zu empören (ja, es ist praktisch, aber einige Teilnehmer lernen bei solchen Wettbewerben neue oder längst vergessene alte YPs, und es ist nicht besonders angenehm, mit json-Parsing zu beginnen), schaute sich die seltsame Formel der Bewegung an und begann irgendwie, den Rahmen der Zukunft zu bilden Strategien (um den Artikel in Zukunft zu verstehen, ist es nützlich, die Regeln zu lesen). 2 Tage lang schrieb ich eine Reihe von Klassen wie Ejection, Virus, Player und andere, las json, verband eine Einzeldateibibliothek zum Protokollieren ... Und am Abend der Eröffnung einer Sandbox ohne Rating hatte ich bereits eine Strategie in Kraft und wiederholte im Prinzip fast die Grundlinie in C ++, aber deutlich viel größerer Code.

Und dann ... fing ich an, Optionen herauszufinden, wie man sie entwickelt. Gedanken zu dieser Zeit:

• Die Suche nach Weltstaaten kann nicht auf Werte reduziert werden, die Minimax und Modifikationen überwältigen können.
• Potenzielle Felder sind gut, aber sie beantworten schlecht die Frage, wie die Welt die nächsten n Zecken verändern wird.
• Genetik und ähnliche Algorithmen werden funktionieren, aber nur 20 ms werden pro Strich angegeben, und die Berechnungstiefe wäre auf den ersten Blick wünschenswert, mehr als die Empfindungen mit dem GA verarbeitet werden können. Ja, und Sie können mit der Auswahl der Mutationsparameter „glücklich bis ans Ende“ spielen.

Ich habe mich definitiv für eines entschieden: Wir müssen eine Simulation der Welt machen. Können ungefähre Berechnungen eine kalte und genaue Berechnung „schlagen“? Solche Überlegungen veranlassten mich natürlich, den Code zu untersuchen, der für die Simulation der Welt auf dem Server verantwortlich sein sollte, da er diesmal zusammen mit den Regeln öffentlich zugänglich gemacht wurde. Schließlich gibt es nichts Besseres als Code, der die Regeln der Welt genau beschreiben sollte?

Also dachte ich genau nach, bis ich anfing, den Code zu studieren, der unsere Bots auf dem Server und lokal testen sollte. In Bezug auf die Verständlichkeit und Korrektheit des Codes war zunächst nicht alles sehr gut, und die Organisatoren begannen zusammen mit den Teilnehmern, ihn aktiv zu verarbeiten. Während des Betatests (einige Tage danach) waren die Änderungen in der Spiel-Engine sehr gravierend und viele nahmen erst an dem Moment teil, in dem sich die Test-Engine nicht stabilisiert. Aber am Ende haben sie meiner Meinung nach auf eine gut funktionierende Engine für ein Spiel gewartet, das für das Wettbewerbsformat sehr gut geeignet ist. Ich begann auch keine ernsthaften Ansätze zu implementieren, bis sich der lokale Läufer stabilisierte, und in der ersten Woche wurde in meinem Bot nichts Vernünftigeres getan, außer dem angeschraubten Visualizer.

Am Vorabend des ersten Wochenendes im Telegramm bildeten die Organisatoren eine separate Gruppe, in der davon ausgegangen wurde, dass die Leute in der Lage sein würden, den Gebietsschema-Läufer zu korrigieren und zu verbessern. Ich habe auch an der Arbeit am Motor der Welt teilgenommen. Nach Diskussionen in diesem Chat stellte ich als Test zwei Pull-Anfragen an das Gebietsschema des Läufers: Anpassen der Essformel (und kleiner Änderungen in der Reihenfolge des Essens) an die Regeln und Zusammenführen mehrerer Teile zu einem Agaric unter Beibehaltung der Trägheit und des Massenschwerpunkts ). Dann begann ich darüber nachzudenken, wie man eine vernünftige Kollisionsphysik in diesen Code einfügt, weil die Physik, die zu dieser Zeit in der Spielwelt vorhanden war, sehr unlogisch funktionierte. Da die Kollisionen zwischen den beiden Agarics in den Regeln nicht beschrieben wurden, fragte ich die Organisatoren nach Kriterien, nach denen meine Implementierung einer solchen Logik akzeptabel wäre. Die Antwort lautete: Agarics bei einer Kollision sollten „weich“ sein (dh sie könnten ein wenig ineinander laufen), während die Logik einer Kollision mit den Wänden nicht berührt werden sollte (dh die Wände sollten die Agarics einfach stoppen, aber nicht wegschieben). Und meine nächste Pull-Anfrage war eine ernsthafte Änderung der Physik.


Ich möchte auch diese Pull-Anfrage hervorheben, die den verwirrenden Code mit der Statusanalyse und einer großen Anzahl gefundener (und potenzieller) Fehler erheblich zu etwas viel Verständlicherem reduziert hat.

Eine Simulation schreiben

Nachdem ich den Runner-Gebietsschema-Code in eine vernünftige Form gebracht hatte, begann ich allmählich, den Weltsimulationscode vom Runner-Gebietsschema auf meinen Bot zu übertragen. Zuallererst war es natürlich ein Code zur Simulation der Bewegung von Agarics und gleichzeitig ein Code zur Berechnung der Physik von Kollisionen. Es dauerte ein paar Abende, um den neu gestalteten Code vor dem Umschreiben von Fehlern zu bewahren (die Logikübertragung erfolgte überhaupt nicht durch Kopieren des Codes) und ungefähre Schätzungen, wie tief die Berechnungen durchgeführt werden sollten.

Die Bewertungsfunktion für jeden Tick in diesem Moment war +1 für das Essen, das ich esse, und -1 für das gegnerische Essen sowie etwas größere Werte für das Essen der Agarics des anderen. In den Konstanten für das Essen anderer Agarics gab es anfangs einen Unterschied zwischen dem Essen meines Gegners, meines Gegners (und natürlich einer sehr hohen Geldstrafe für das Essen meiner letzten Agarika durch den Gegner) sowie zwei verschiedenen Gegnern voneinander (nach ein paar Tagen wurde der letzte Koeffizient 0). Zusätzlich zur Gesamtgeschwindigkeit für alle vorherigen Ticks der Simulation wurde jeder Tick mit 1 + 1e-5 multipliziert, um meinen Bot zu ermutigen, zumindest etwas früher nützlichere Aktionen auszuführen, und am Ende der Simulation wurde die Geschwindigkeit für den letzten Tick als Bonus hinzugefügt, ebenfalls sehr gering . Um die Bewegung von Agarics zu simulieren, wurden Punkte am Rand der Karte mit einem Schritt von 15 Grad von den arithmetischen Mittelkoordinaten aller meiner Agarics ausgewählt, und ein Punkt wurde ausgewählt, wenn die Bewegung simuliert wurde, für die die Schätzfunktion den größten Wert angenommen hat. Und schon mit einer so scheinbar primitiven Simulation und einer damals einfachen Einschätzung hat sich der Bot ganz sicher in den Top 10 etabliert.


Am Freitag- und Samstagabend wurde eine Simulation der Verschmelzung von Agarics, eine Simulation der „Untergrabung“ von Viren und das Erraten der TTF des Gegners hinzugefügt. Der TTF des Gegners war ein ziemlich interessanter berechneter Wert, und es war möglich zu verstehen, zu welchem ​​Zeitpunkt der Gegner einen Split machte oder zum Virus gelangte, indem nur der Moment eines unkontrollierten Fluges erfasst wurde, der von einer sehr kleinen Anzahl von Zecken mit einer großen Viskosität bis zum Flug durch die gesamte Karte dauern konnte. Da Agaric-Kollisionen zu einem leichten Überschuss ihrer Höchstgeschwindigkeit führen können, habe ich zur Berechnung des TTF des Gegners überprüft, ob seine Geschwindigkeit in zwei Ticks hintereinander wirklich der Geschwindigkeit entspricht, mit der Sie im Freiflug zwei Ticks hintereinander erhalten können (im Freiflug flogen Agarics streng gerade und mit Verlangsamung jeder Zecke genau gleich der Viskosität). Dadurch wurde die Möglichkeit von Fehlalarmen fast vollständig ausgeschlossen. Außerdem habe ich beim Testen dieser Logik festgestellt, dass eine größere TTF immer einer größeren ID des Agarics entspricht (von der ich später überzeugt war, als ich den Explosionscode auf den Virus übertrug und den Split verarbeitete ), was sich ebenfalls lohnte.

Nachdem ich mir die konstanten Teilungen in den Top 3 angesehen hatte (die es ihnen ermöglichten, Lebensmittel auf der Karte signifikant zu sammeln), fügte ich dem Bot als Test einen permanenten Teilungsbefehl hinzu, wenn sich im Sichtradius kein Feind befand, und fand meinen Bot am Sonntagmorgen in der zweiten Zeile der Bewertung. Das Verwalten einer Handvoll kleiner Agarics hat das Ranking erheblich verbessert, aber es war viel einfacher, sie zu verlieren, wenn Sie auf einen Gegner stoßen. Und da die Angst, von meinen Agarics gefressen zu werden, sehr bedingt war (die Strafe galt nur für das Essen in einer Simulation, aber nicht für die Annäherung an einen Gegner, der essen konnte), wurde als erstes eine Strafe für die Kreuzung mit einem Gegner hinzugefügt, der essen konnte. Und diese Einschätzung wirkte wie ein Bonus für die Verfolgung eines Gegners. Nachdem ich den CPU-Verbrauch mit meiner Strategie überprüft hatte, entschied ich mich, eine weitere Simulationsrunde hinzuzufügen, wenn die Aufteilung beim ersten Häkchen erfolgte (diese Logik musste natürlich auch vom Runner-Gebietsschema auf meinen Code übertragen werden), und dann verlief die Simulation genauso wie zuvor . Diese Art von Logik war nicht sehr gut geeignet, um auf den Feind zu "schießen" (obwohl sie sich manchmal zufällig zu einem sehr geeigneten Zeitpunkt spaltete), aber sie war sehr gut, um schneller Lebensmittel zu sammeln, was das ganze Top zu dieser Zeit tat. Solche Änderungen ermöglichten es uns, die nächste Woche in die erste Zeile des Ratings einzutragen, obwohl die Marge nicht signifikant war.

Zu dieser Zeit war dies völlig ausreichend, das „Rückgrat“ der Strategie wurde ausgearbeitet, die Strategie sah ziemlich primitiv und erweiterbar aus. Was mir aber wirklich aufgefallen ist, war der CPU-Verbrauch und die allgemeine Codestabilität. Daher waren hauptsächlich die Abende des nächsten Arbeitsteils der Woche der Verbesserung der Genauigkeit von Simulationen (die der Visualizer sehr geholfen hat), der Stabilisierung des Codes (Valgrind) und einigen Optimierungen der Arbeitsgeschwindigkeit gewidmet.

Lass uns weitermachen

Meine nächste gesendete Strategie, die ein deutlich besseres Ergebnis zeigte und den Gegnern (zu diesem Zeitpunkt) vorausging, enthielt zwei wesentliche Änderungen: Hinzufügen eines potenziellen Feldes zum Sammeln von Lebensmitteln und Verdoppeln der Anzahl von Simulationen, wenn sich ein Gegner mit einem unbekannten TTF in der Nähe befindet.

Das potenzielle Feld für das Sammeln von Lebensmitteln in der ersten Version war recht einfach und bestand im Wesentlichen darin, sich an Lebensmittel zu erinnern, die aus der Sichtbarkeitszone verschwunden waren, das Potenzial an den Orten zu verringern, an denen sich der feindliche Bot befand, und in meiner Sichtbarkeitszone auf Null zu setzen (mit anschließender Wiederherstellung alle n Zecken gemäß den Regeln). Dies schien eine nützliche Verbesserung zu sein, aber in der Praxis war der Unterschied meiner subjektiven Meinung nach entweder gering oder gar nicht vorhanden. Beispielsweise übersprang der Bot bei Karten mit hoher Trägheit und Geschwindigkeit häufig das Essen und versuchte dann, dorthin zurückzukehren, während er viel Geschwindigkeit verlor. Wenn er sich jedoch entschied, die Geschwindigkeit beizubehalten und das ausgelassene Essen einfach ignorierte, würde er deutlich mehr essen.


Ein völlig anderer subjektiver Nutzen stellte sich als doppelte Simulation des Feindes mit verschiedenen TTFs heraus - dem minimal und maximal möglichen (falls ich die TTF nicht für alle sichtbaren Agarics auf der Karte kenne). Und wenn mein Bot früher dachte, dass der feindliche Haufen von Agarics ein Ganzes werden und sich langsam bewegen würde, dann wählte er jetzt das schlimmste der beiden Szenarien und riskierte nicht, dem Feind nahe zu sein, von dem er weniger weiß, als er möchte.

Nachdem ich einen signifikanten Vorteil erlangt hatte, versuchte ich ihn zu erhöhen, indem ich eine Definition des Punktes hinzufügte, an dem der Gegner seine Agarics anweist, sich zu bewegen, und obwohl dieser Punkt in den meisten Fällen ziemlich genau berechnet wurde, verbesserte dies allein die Ergebnisse des Bots nicht. Nach meinen Beobachtungen wurde es noch schlimmer als der Fall, als sich die Agarics des Gegners einfach in die gleiche Richtung und mit der gleichen Geschwindigkeit bewegten, als hätte der Gegner nichts getan, sodass diese Änderungen bis zu besseren Zeiten in einem separaten Gitarrenzweig gespeichert wurden.


Es gab auch Versuche, die Bewertungsfunktion auf die Bewertung der gewonnenen Masse zu übertragen, Versuche, die Funktion der Bewertung der Gefahr des Gegners zu ändern ... Aber auch hier wurden alle derartigen Änderungen der Gefühle noch schlimmer. Das einzige, was bei der Beurteilung der Gefahr aus der Nähe zum Feind nützlich war, war eine weitere Leistungsoptimierung sowie die Ausweitung dieser Schätzung auf einen viel größeren Radius als den Schnittradius mit dem Feind (im Wesentlichen die gesamte Karte, jedoch mit einer quadratischen Abnahme, wenn auch leicht vereinfacht). Anwesenheit des Gegners in fünf oder mehr Radien im Bereich von 1/25 der maximalen Gefahr, gefressen zu werden). Die letzte ungeplante Änderung führte auch dazu, dass meine Agariks große Angst hatten, sich einem wesentlich größeren Feind zu nähern, und im Falle ihrer überlegenen Größe eher dazu neigten, sich dem Gegner zu nähern. Es stellte sich also als erfolgreicher und nicht ressourcenintensiver Ersatz für den für die Zukunft geplanten Code heraus, der für die Angst vor einem Angriff eines Gegners durch Spaltung verantwortlich sein sollte (und ein wenig Hilfe bei einem solchen Angriff für mich später).

Nach langen und relativ erfolglosen Versuchen, etwas zu verbessern, kehrte ich wieder zur Vorhersage der Bewegungsrichtung des Gegners zurück. Ich habe beschlossen, es zu versuchen, wenn es nicht nur darum geht, die Dummy-Rivalen zu ersetzen, sondern es mit der minimalen und maximalen TTF-Option zu tun - zweimal simulieren und die beste auswählen. Aber dafür könnte die CPU nicht ausreichen, und in vielen Spielen meines Bots könnten sie sich aufgrund eines unersättlichen Appetits einfach vom System trennen. Daher habe ich vor der Implementierung dieser Option eine ungefähre Definition der aufgewendeten Zeit hinzugefügt und bei Überschreitung der Grenzwerte begonnen, die Anzahl der Simulationsbewegungen zu verringern. Durch Hinzufügen einer Doppelsimulation des Feindes für den Fall, dass ich den Ort kenne, an den er sich bewegt, erhielt ich erneut eine ziemlich ernsthafte Erhöhung der meisten Spieleinstellungen, mit Ausnahme der ressourcenintensivsten (mit hoher Trägheit / niedriger Geschwindigkeit / niedriger Viskosität), die auf eine starke Abnahme der Tiefe zurückzuführen ist Simulationen könnten noch schlimmer werden.

Vor dem Start der 25-km-Tick-Spiele wurden zwei weitere nützliche Verbesserungen vorgenommen: die Strafe für das Beenden der Simulation weit entfernt von der Kartenmitte sowie das Erinnern an die vorherige Position des Gegners, wenn er die Sichtlinie verlassen hat (sowie das Simulieren seiner Bewegung zu diesem Zeitpunkt).Die Implementierung der Strafe für die Endposition des Bots in der Simulation war ein vorberechnetes statisches Gefahrenfeld mit einer Gefahr von Null in einem Radius, der etwas größer als die Hälfte der Länge des Spielfelds ist und schrittweise erhöht wird, wenn Sie sich vom Spielfeld entfernen. Die Anwendung der Geldstrafe dieses Feldes an den Endpunkten der Simulation erforderte fast keine CPU und verhinderte zusätzliche Läufe in die Ecken, wodurch der Feind manchmal vor Angriffen bewahrt wurde. Und das Auswendiglernen mit anschließender Simulation von Rivalen ermöglichte es uns größtenteils, zwei manchmal manifestierte Probleme zu vermeiden. Das erste Problem wird im folgenden GIF dargestellt. Das zweite Problem war, dass, wenn ein größerer Feind aus dem Sichtfeld verloren ging (zum Beispiel nach der Verschmelzung seiner Teile), es möglich war, sich „erfolgreich“ zu vereinigen und zusätzlich einen bereits gefährlichen Gegner zu füttern.


Außerdem wurden den Punkten am Rand der Karte Bewegungssimulationen hinzugefügt: zu jedem Agarik der Rivalen und innerhalb eines Radius der arithmetischen mittleren Koordinate meiner Agariki alle 45 Grad. Der Radius wurde auf Durchschnitt von den arithmetischen Mittelkoordinaten meiner Agarics eingestellt.

Letzte Vorbereitung

Zum Zeitpunkt der Eröffnung der Spiele für 25.000 Ticks und des Einzugs ins Finale hatte ich einen soliden Vorsprung, aber ich hatte nicht vor, mich zu entspannen.

Zusammen mit den neuen 25.000 Spielen kam die Nachricht: Die Spiele im Finale werden ebenfalls 25.000 sein, und das Zeitlimit der Strategie für Zecken ist etwas länger geworden. Nachdem ich die Zeit ausgewertet hatte, die meine Strategie unter den neuen Bedingungen für das Spiel verbringt, entschied ich mich, eine weitere Version der Simulation hinzuzufügen: Wir machen alles wie gewohnt, aber während der Simulation unterwegs teilen wir uns auf. Dies erforderte unter anderem die Verwendung der im vorherigen Schritt gefundenen Simulation, jedoch mit einer Verschiebung von 1 Zug (wenn wir beispielsweise festgestellt haben, dass 7 Ticks vom aktuellen geteilt werden, dann Im nächsten Zug wiederholen wir dasselbe, aber wir werden den Split bereits im 6. Zug durchführen. Dies führte zu aggressiven Angriffen auf Rivalen, verbrauchte jedoch etwas mehr Strategiezeit.


Alle weiteren Verfeinerungen bezogen sich ausschließlich auf die Effizienz der Simulationen bei fehlendem TL: Optimierung der Reihenfolge des Trennens bestimmter Teile der Logik in Abhängigkeit von der verbrauchten CPU. In den meisten Spielen sollte dies nichts ändern, aber etwas Richtigeres zu finden, funktionierte dann nicht.

Anstelle einer Schlussfolgerung

Im Allgemeinen erwies sich der Start dieses Wettbewerbs als ziemlich geölt, aber in den ersten eineinhalb Wochen wurde die Aufgabe mit Hilfe der Teilnehmer in eine ziemlich spielbare Form gebracht. Anfangs war die Aufgabe sehr unterschiedlich, und die Wahl des richtigen Lösungsansatzes schien keine triviale Aufgabe zu sein. Noch interessanter war es, Wege zu finden, um den Algorithmus zu verbessern, ohne die Grenzen des CPU-Verbrauchs zu überschreiten. Vielen Dank an die Organisatoren für den Wettbewerb und für die Erstellung der weltweiten Quellcodes für Open Access. Letztere haben natürlich zu Beginn ihre Probleme erheblich verschärft, aber den Teilnehmern das Verständnis des Geräts des Weltsimulators erheblich erleichtert (wenn nicht zu sagen, was dies im Prinzip ermöglicht hat). Besonderer Dank für die Möglichkeit, einen Preis zu wählen! Der Preis war also viel nützlicher :-) Warum brauche ich ein anderes MacBook?