Es war Mittwoch, es gab ein gewöhnliches langweiliges Treffen bei der Arbeit. Der Designer kratzte sich am Ohr und der Tester vergrub sich am Telefon. Vor dem Fenster fuhr ein Auto an, und ich erhielt einen Brief am Telefon - der
russische AI Cup 2018 begann. Ungefähr niemand ahnte etwas, und in diesem Moment wusste ich bereits genau, was ich in den nächsten anderthalb Monaten tun würde.
Hallo allerseits, mein Name ist
Andrey Tokarev und ich möchte meine Erfahrungen mit der Teilnahme am
russischen AI Cup 2018 teilen.
Was ist das?
Der Russian AI Cup ist ein jährlicher Wettbewerb für künstliche Intelligenz, der seit 2012 stattfindet. Hier müssen Sie einen Algorithmus schreiben, der jemanden oder etwas steuert, und diese jemand oder etwas konkurrieren miteinander. In diesem Jahr war es notwendig, Roboter beim Fußballspielen zu steuern.
Ich hatte bereits Erfahrung in solchen Wettbewerben. Insbesondere habe ich am russischen AI Cup 2016 (ohne Preis) und am Mini AI Cup 2018 (2. Platz) teilgenommen.
Lass uns gehen
Zuerst habe ich meine Klassen der Spielwelt erstellt, Objekte, einen 2- und 3-dimensionalen Vektor aus früheren Wettbewerben genommen und alles in das Git-Repository hochgeladen. Natürlich können Sie Objekte aus dem Sprachpaket verwenden, aber es gibt keine Vektoren, sie können nicht geändert werden, und es ist in der Tat bequemer, Ihre eigenen Klassen zu verwenden. Was ich nicht umgeschrieben habe, ist die Arena-Klasse, sie passte mir so wie sie ist, und es bestand keine Notwendigkeit, sie zu ändern.
Simulation
Hier haben wir eine Spielwelt und was können wir dagegen tun?
Aber es stellt sich nichts heraus, bis wir die Spielwelt simulieren können und nicht einmal feststellen können, ob der Ball in ein leeres Netz fliegt. Also
schreiben wir die Simulation ab. Der Simulationscode ist nicht Teil des Sprachpakets, sondern wird in einer Sprache bereitgestellt, die ich nicht kenne. Die C-Syntax ist jedoch ähnlich, sodass die erforderlichen Funktionen kopiert, eingefügt und definiert werden und die Sim zu 90% bereit ist. Wo ich meine Hände regieren musste, habe ich es sorgfältig versucht, da Fehler hier teuer sein können und es schwierig sein wird, sie zu fangen. Ich habe immer noch ein paar Fehler gemacht, aber es hat mich ein wenig Blut gekostet.
Es wurde sofort klar, dass es bei Verwendung einer ehrlichen Simulation (100 Mikroticks) nicht ausreicht, 100 Optionen mit einer Mikrotik zu berechnen, als eine Option mit 100 Mikrotiks. Ich habe noch 2 Mikrotik gelassen, damit die Diskrepanz nicht zu groß war.
Strategie-Grundlagen
Wir haben also eine Spielwelt und können deren Veränderung simulieren. Also, was kommt als nächstes?
Es gibt verschiedene Ansätze. Wenn es nur wenige mögliche Züge gibt und die Tiefe nicht sehr groß ist, können Sie sie mit brutaler Gewalt ausführen: Sortieren Sie alle Züge, auch die Rückzüge des Gegners, sie haben wieder ihre eigenen Züge ... d. H. Minimax Wenn es viele Bewegungen gibt, können Sie diese künstlich begrenzen. Sie können beispielsweise Richtungen ein Vielfaches von 15 Grad einschlagen, zu jedem 10. Tick springen und denselben Minimax verwenden. Dieser Ansatz scheint mir jedoch geeignet zu sein, wenn das Ergebnis nicht zu empfindlich für kleine Änderungen der Bewegungen ist. Hier führt eine Abweichung von einem Grad in Richtung des Roboters nach der Kollision zu großen Abweichungen.
Das andere Extrem, wenn wir ohne erschöpfende Suche Bewegungen ausführen, ist eine Art Heuristik. Dieser Ansatz mag praktikabel sein, aber es ist sehr schwierig, einen starken Fußballspieler mit reinen Heuristiken zu schaffen.
Die Kombination der beiden Methoden sieht jedoch vielversprechend aus: Sie können sich zuerst in eine zufällige Richtung bewegen und dann das Spiel mit einer Heuristik beenden, die bis zum Ball läuft und zur richtigen Zeit springt. Dieselbe Heuristik in Kombination kann verwendet werden, um die Bewegungen des Gegners vorherzusagen. Früher habe ich im Wettbewerb bereits etwas Ähnliches verwendet, und diese Methode hat sich mehr oder weniger nicht als schlecht erwiesen.
Und so schreiben wir Heuristiken (im RAIK-Ovsky-Jargon kluger Kerl oder einfach nur klug)!
Da ich das Ergebnis so schnell wie möglich sehen wollte, wurde smartgay in Eile geschrieben und es stellte sich als ziemlich dumm heraus (selbst der Code ist beschämend). Ich habe gerade die Zeit berechnet, nach der der Roboter den Ball fangen konnte, basierend auf der aktuellen Geschwindigkeit des Balls und der maximalen Geschwindigkeit des Roboters und bin bis zu dem Punkt gelaufen, an dem sich der Ball zu diesem Zeitpunkt befinden würde (Kollisionen wurden nicht berücksichtigt). Er wusste nicht, wie man springt und berücksichtigte nicht einmal die Höhe des Balls, er konnte leicht unter dem Ball laufen, und wenn sich der Ball zu schnell wegbewegte, rannte er im Allgemeinen in die entgegengesetzte Richtung. Da smart nicht springen konnte, ließ ich ihn zuerst in einem festen Abstand vom Ball springen, und wenig später fiel die Wahl des Momentes des Sprunges auf die Schultern eines großen Zufalls! Das Fehlen einer rationalen Wahl eines Sprunges stellte sich als großer Nachteil heraus, aber dazu später mehr. Aber im Allgemeinen sah ein sauberer Smart nicht schlecht aus und erzielte manchmal sogar Tore, obwohl auch in ihren eigenen Toren.
Als nächstes benötigen wir eine Bewertungsfunktion (OF).
Das anfängliche OF sah folgendermaßen aus: (1000 - Tick) * Ziel + Ball.z + eine Funktion der relativen Position des Roboters und des Balls, so dass er zum Ball läuft, auch wenn er ihn nicht erreichen kann. Hier kann das Ziel -1,0,1 sein, abhängig davon, ob es ein Ziel gibt und für wen, und das Häkchen ist das Häkchen vom Beginn der Simulation, an der das Ziel stattgefunden hat. Das Letzte ist, dass der Roboter das Ziel nicht ständig verschiebt.
Jetzt lassen wir den Roboter in zufälliger Richtung eine zufällige Anzahl von Ticks laufen, dann übertragen wir die Kontrolle auf den Smart, der ihn zum Ball führt, in einem zufälligen Moment springt er und
trifft den Ball verfehlt. Darüber hinaus ist es besser, nicht in die Mitte des Balls zu laufen, sondern mit einer zufälligen Verschiebung um eine kleine Strecke, damit der Roboter in einem Winkel schlagen kann.
Die Simulation dauerte eine feste Zeit von 2 Sekunden und am Ende wurde das OF aufgerufen. Ein solches Szenario wurde für jeden Roboter mehrmals wiederholt und das beste anhand der Bewertung ausgewählt.
Bisher hat diese Strategie einen schwerwiegenden Nachteil: Sie hat kein Gedächtnis - bei jedem Tick wird alles von Grund auf neu berechnet, was bedeutet, dass die Strategie ein Ziel bei einem Tick sehen und beim nächsten nicht finden kann. Dies ist nicht der Fall, Sie müssen es beheben - wir speichern die beste Option für jeden Roboter und verwenden sie im nächsten Tick wieder. Auch jetzt wissen Roboter über die Angelegenheiten des anderen Bescheid, zum Beispiel, wenn der erste den Ball schlagen wird, läuft der zweite nicht hinter dem Ball her, sondern versucht, einen Pass zu bekommen.
Torhüter
Wir brauchen einen Torhüter. Mein Torhüter unterschied sich grundlegend vom Angreifer darin, dass er aktiviert wurde, wenn sich der Ball einer bestimmten Entfernung zum Tor näherte, sonst würde er einfach zu seinem Basispunkt zurückkehren.
Zusammenfassung
Jetzt haben wir eine gute Grundstrategie, die alles Notwendige kann und auf die in Zukunft aufgebaut werden kann.
Vielleicht scheint alles, was oben beschrieben wurde, einfach und logisch zu sein, aber ehrlich gesagt gab es zu Beginn des Wettbewerbs kein so klares Bild der Strategie, die näher am Ende erschien, und es dauerte zwei Wochen, um dies umzusetzen, und dies ist 1/3 des Wettbewerbs.
Ein bisschen über das Testen
Im Laufe der Zeit treten immer weniger Grale auf, die die Kraft des Spiels verdoppeln, und wir müssen Änderungen auswählen, die eine Steigerung der Ziele um + 10-20% bewirken. Und dann stellt sich heraus, dass so kleine Gewinne nicht so einfach zu identifizieren sind. Für ein gründliches Ergebnis benötigen Sie Hunderte von erzielten Toren. Bei einer Torhäufigkeit von einmal pro Minute sind dies viele, viele Stunden Spielzeit. Aus diesem Grund habe ich fast keine Strategien auf dem Server getestet, sondern lange lokale Tests mit früheren Versionen durchgeführt. Aber selbst das lokale Testen einer Änderung für einen halben Tag wäre nicht sehr praktisch. Deshalb habe ich einen kleinen "Trick" angewendet - ich habe abgeschnittene Strategien getestet. Wenn ich zum Beispiel auf einem Server mehr als 50 Optionen pro Roboter und dann nur 10 lokal ausgewählt habe, konnte ich Tests in einer tolerierbaren Zeit ausführen.
Verbesserungen
Als nächstes werde ich die wichtigsten Verbesserungen und ihre Bewertung in der folgenden Form beschreiben: Um wie viel Prozent erzielt die neue Version mehr Tore als die alte. Das heißt, Wenn zum Beispiel ein neuer den alten mit einer Punktzahl von 120: 100 schlägt, sind es + 20%, wenn er zweimal mehr Punkte erzielt, sind es + 100%.
- Ihr Torhüter muss Tore schlagen. Wenn er keinen Erfolg hat, geben Sie ihm mehr Zeit und erhöhen Sie die Anzahl der Optionen auf x10. + 15%
- Manchmal, wenn der Torhüter den Ball schlägt, geht er in den freien Flug und während er Zeit hat, an seinen Platz zurückzukehren, erzielen sie bereits ein Tor. Unmittelbar nach dem Schlagen des Balls versuchen wir, ihn an seinen Platz zurückzubringen und das Häkchen, zu dem er zurückgekehrt ist, mit einem kleinen negativen Koeffizienten zur Bewertung hinzuzufügen. + 20%
- Ein zusätzlicher Tritt auf den Ball vor dem Tor eines anderen erhöht die Chance auf ein Tor. Dafür geben wir im OF einen Bonus. + 60%
- Experimentiere mit Nitro! Bis zur ersten Runde waren noch ein paar Tage übrig, aber ich beschloss, Nitro im Voraus zu testen. Intuitiv schien es mir, dass Nitro das Gameplay stark beeinflussen würde, da man mit einem Panzer an die Decke springen oder über das gesamte Feld fliegen kann. Zunächst habe ich gelernt, wie man Nitro nur für den Angreifer und selbst dann nur in der Luft verwendet, aber ich habe die Pakete noch nicht gesammelt. Nitro wurde während des Fluges in der nun zufälligen nun dreidimensionalen Richtung eingesetzt. Das Ergebnis war, gelinde gesagt, nicht sehr, ich schaffte es nicht, mehr als + 20% zu quetschen, und die Verwendung von Nitro am Boden brachte keine Ergebnisse. Daher wurde das Problem mit Nitro vorübergehend beiseite gelegt, obwohl ich von diesem Moment an versuchte, Tests mit eingeschaltetem Nitro durchzuführen.
- Zu viel Randomismus! Zufällig ist natürlich gut, er gibt manchmal Tricks, an die man nicht einmal denken kann, aber andererseits ist die Wahrscheinlichkeit, dass alles zusammenfällt, sehr gering, wenn zu viel von ihm vorhanden ist. Und ich hatte zu viel davon. Ich beschloss, den Moment des Sprunges auf die analytische Basis zu übertragen. Da es keine horizontale Beschleunigung in der Luft gab (vergessen Sie Nitro), war es einfach, den Moment des Treffens des Roboters und des Balls (t1) und die Höhe des Balls in diesem Moment (h1) zu berechnen. Jetzt berechnen wir die Zeit (t2), nach der sich der Roboter auf einer Höhe von h1 befindet. Springen Sie jetzt. Hier erhalten wir eine quadratische Gleichung, wenn es keine Lösung gibt oder t2 <t1, dann springen wir früh, sonst springen wir.
Das Ergebnis schockierte mich ein wenig und schraubte den richtigen Sprung sowohl zum Stürmer als auch zum Torhüter. Die Tests zeigten + 200%, d.h. Die neue Version schlug die alten 3 Mal in Toren, der echte Gral! Es war der 17. Januar, nachdem die Strategie auf den Server hochgeladen worden war, gewann sie in einer Siegesserie von 20 Spielen eine Bewertung von 200+ und führte eine Weile die Sandbox an.
- Wir bringen dem Torhüter das Spielen bei. Bis mein Torhüter aktiviert wurde, stand er wie eine Säule. Leichter Seitengang: x = ball.x / 4 ergab einen leichten Anstieg.
- Der Gegner darf nicht vorhergesagt, sondern angenommen werden! Als ich durch die Spiele schaute, bemerkte ich, dass ich oft ein Tor bekomme, nachdem der Torhüter den Ball direkt auf den Gegner geschlagen hat und er spontan ein Tor für mich erzielt. Um den Ball unter Umgehung des Gegners zu treffen, müssen Sie zunächst bestimmen, wo er sich auf dem n-ten Tick befinden kann. Natürlich werden wir Nitro nicht berücksichtigen. Ich konnte die Geschwindigkeit des Roboters noch analytisch bestimmen, es scheint den Schnittpunkt zweier Kreise zu geben. Aber er konnte das zugängliche Gebiet nicht bewältigen. Nun, zur Hölle mit ihm, wir sind Programmierer (nicht durch Ausbildung), lassen Sie die Maschine für uns zählen. Teilen Sie die Ebene in n Richtungen, bewegen Sie den Roboter in jede Richtung. Die Endpunkte sind die Eckpunkte des Polygons, das die Reichweite bestimmt.
Wie benutzt man es? Ich habe einen Tick hinzugefügt, bei dem der Gegner den Ball zum ersten Mal berühren kann, mit einem guten Koeffizienten im OF. Da jetzt kein bestimmtes Szenario von Aktionen, sondern eine bestimmte Reichweite für den Gegner in Betracht gezogen wurde, entfernte ich die Roboter des Feindes, sobald sie mit dem Boden in Kontakt kamen.
Ergebnis + 40%. Darüber hinaus hat dieser Ansatz zwei große Vorteile: Das Entfernen feindlicher Roboter im ersten beschleunigt die Simulation, und dies ermöglicht es wiederum, mehr Optionen zu sortieren, und im zweiten müssen wir uns nicht um die Kontrolle des Gegners kümmern. Fazit: Gewinn!
- Dumme Fehler, aber was ohne sie. Der offizielle Simulator enthält zwei Zeilen:
if abs(ball.position.z) > arena.depth / 2 + ball.radius: goal_scored()
Ich weiß nicht wer wie, aber ich habe die abs () Funktion so wie sie ist belassen, aber vergebens. Die abs-line () (nicht zu verwechseln mit std :: abs ()) nimmt ganzzahlige Werte an, was bedeutet, dass Dezimalstellen abgeschnitten werden. In der Praxis bedeutet dies, dass ich das Tor nur aufgezeichnet habe, wenn der Ball bereits einen vollen Meter hinter der Torlinie war. Ersetzen Sie abs () durch fabs ()! Dies ist nicht das erste Mal, dass diese abs () mich im Stich gelassen hat.
- Wieder Nitro. Die zweite Runde rückte näher und es gab keinen Ort, an dem der normale Gebrauch von Nitro aufgeschoben werden konnte. Er optimierte seine Verwendung, berücksichtigte die Definition eines Sprungs, erlaubte die Verwendung des Torhüters und begann absichtlich, Pakete durch den Torhüter zu sammeln.
- Kommen wir zurück zur Simulation. Ich habe bereits gesagt, dass 100 Optionen mit einer Mikrotik rentabler sind als eine Option mit 100 Mikrotik. Dies ist wahr, aber dies bedeutet nicht, dass mit einem Mikrotik alles in Ordnung ist, ohne zusätzliche Maßnahmen waren die Diskrepanzen ziemlich ernst und dies verhinderte das professionelle Fußballspielen. Um die Genauigkeit der Simulation zu verbessern, habe ich die folgenden Methoden angewendet:
- Während des Sprunges zwei zusätzliche Mikrotik.
- Wenn wir viele Mikrotiken kombinieren, ist es beim Bewegen korrekter, die Durchschnittsgeschwindigkeit zu verwenden und nicht die endgültige.
- Mit der binären Suche finden wir das Häkchen, in dem die Kollision auftritt, und führen zwei Untertaktiken durch: eine vor der Kollision, die andere nach der Kollision. (Ich habe die Kollision des Balls mit einer ebenen Fläche nicht berücksichtigt, da mir die Diskrepanz unbedeutend erschien.)
- Das Laufen auf einer gekrümmten Oberfläche verursachte immer noch große Unstimmigkeiten, und manchmal verfehlte der Torhüter dies. Als mein Torhüter sich auf einer gekrümmten Oberfläche befand, verwendete ich 10 Mikrotik.
Im Durchschnitt wurden etwa 1,4 Mikrotiks pro Zecke erhalten, und die Genauigkeit war nahezu ideal. Natürlich habe ich diese Optimierungen nicht auf einmal vorgenommen, sondern nach und nach. Ich weiß nicht, wie sehr sie die Kraft des Spiels beeinflusst haben, aber ich denke, das ist sehr wichtig.
Was haben wir?
Dank einer Vielzahl von signifikanten Verbesserungen wuchs die Strategie im Ranking stetig und erreichte vor der zweiten Runde fast den historischen Meilenstein - 5000 Elo Rating - und gewann selbstbewusst an Boden.
Manchmal kann man nicht einmal glauben, welche Kombinationen zufällig auftreten. Vielen Dank an die freundliche Community anonym für den Fund.Letzte Woche
In Verbindung mit einer so guten Marge erlaubte ich mir, keine kleinen Verbesserungen zu verfolgen, sondern nach etwas Globalerem zu suchen, insbesondere im Hinblick auf 3x3-Spiele. Experimente, die auf ein Teamspiel abzielen oder einen dritten Spieler in eine besondere Rolle bringen oder dem Torhüter beibringen, während des Scheiterns auszugehen, scheiterten jedoch. Die ganze Woche wurde fast ohne Erfolg verbracht. Trotzdem lag ich einige Tage vor dem Finale immer noch an der Spitze der Rangliste.
Und jetzt, am letzten Tag vor dem Finale, verliere ich gegen einen, dann gegen einen anderen und sogar gegen einen dritten Konkurrenten. Wenn Sie nichts hinzufügen, können Sie ohne Preis bleiben. Die ganze Woche ist nichts passiert. Was kann ich am letzten Tag tun? Die Stimmung war - zumindest aufgeben.
Auferstehung
Nachdem ich ein paar verlorene Spiele gesehen hatte, bemerkte ich, dass jeder
wie Ziegen auf Nitro springt, den Ball in die Luft passt, aber meiner kann ihn nicht bekommen. Ich habe das Einfachste versucht, was zu diesem Verhalten führen kann - ich habe die Höhe des Balls zum Zeitpunkt des Aufpralls mit einem festen Koeffizienten im OF addiert. Ergebnis + 50%, wow! Inspiriert vom Ergebnis begann ich, die Parameter intensiv zu verdrehen (was ich während des gesamten Wettbewerbs vernachlässigte), fügte neue Suchoptionen hinzu und fügte am Ende Zeitkontrolle hinzu, wodurch ich die Zeit maximal nutzen konnte, ohne mein Leben zu riskieren. Am Ende des Tages stellte sich heraus, dass + 150-200%, d.h. Die neue Version schlug die vorherige fast dreimal in Toren! Ja, ja, genau das, was fast eine Woche vor dem Finale auf dem ersten Platz zusammenbrach und eine beispiellose Bewertung von 5000+ in der Geschichte der Meisterschaft erreichte. Auf dem Server wurde die Strategie einige Stunden vor dem Finale erfolgreich getestet. Danach bereitete ich es für den endgültigen Start vor: Deaktivierte Zusicherungen, fügte Divisionsprüfungen auf Null hinzu, lud es erneut auf den Server hoch und schaltete mich in den Standby-Modus.
Letzter Teil Eins
Der erste Teil des Finales fand nachts statt. Ich verfolgte die Ergebnisse, bis ich einschlief und früh morgens aufstand. Es wurden 3 Wellen gespielt (in einer Welle spielt jede mit jeder), ich verlor nur ein Spiel gegen
TonyK und da Anton immer noch manchmal gegen andere Spieler verlor, lag ich mit einem Vorsprung von 7 Punkten an der Spitze (2 Punkte für den Sieg). Eine ziemlich ernsthafte Lücke für 3 Wellen, aber nicht genug zum Entspannen.
Am letzten Tag hatte ich natürlich nicht vor, etwas Ernstes zu tun, sondern die Parameter zu verdrehen. Es wurden einige Änderungen vorgenommen, aber da alles in Eile getestet wurde, war ich mir nicht einmal ganz sicher, ob der Effekt positiv war. Im Allgemeinen betrug der Anstieg 0-20%. Aber Anton fügte deutlich hinzu und begann zumindest nicht schlechter als ich zu spielen.
Nichts zu tun, ich musste senden, was ist, und auf Glück und einen Vorrat an Punkten hoffen.
Letzter Teil Zwei
Glücklicherweise wurden die Spiele so sortiert, dass die Anführer zunächst untereinander spielten, sodass kein Grund zur Sorge bestand. Das allererste Spiel war gegen TonyK. Das Glück war auf meiner Seite, ich gewann den ersten Kampf sowie alle anderen Spiele in dieser Welle, während TonyK einen weiteren Punkt verlor. Eine Lücke von 10 Punkten für zwei Wellen bis zum Ende ist fast unmöglich zu spielen, jetzt war es möglich, sich zu entspannen.
Endergebnis: 352 Siege und 2 Niederlagen (beide von Anton), 1. Platz mit einem Vorsprung von 12 Punkten.
Danke und anderer Müll
Im Allgemeinen hat mir die Aufgabe dieses Jahres sehr gut gefallen, sie war „für mich“ (die Simulation gehört mir und die Dreidimensionalität macht mir keine Angst) und die Spiele waren spektakulär. Ich finde es interessant, nicht nur die Teilnehmer zu beobachten.
Ich möchte den Organisatoren für den wunderbaren Wettbewerb danken.
Ich möchte mich auch bei allen Teilnehmern bedanken, insbesondere bei Anton Kozlovsky (
TonyK ) für den Wettbewerb im Finale, Ivan Tyamgin (
Tyamgin ) für den Wettbewerb im Sandkasten und Alexey Dichkovsky (
Commandos ) für die Unterlassung der Teilnahme und damit für eine Erhöhung meiner Gewinnchancen.
Viel Glück an alle im nächsten RAIK!