Hallo allerseits, mein Name ist Olya. Vor zwei Wochen endete ein weiterer Wettbewerb bei CodinGame - ein Wettbewerb zum Programmieren von Bots für das Spiel. Ich bin in die Top 300 der Welt-Bestenliste gekommen, deshalb möchte ich Ihnen sagen, warum Wettbewerbe cool sind und meine Geheimnisse teilen. Ivan Spaceorc , der in die Top 100 des gleichen Wettbewerbs kam, wird ebenfalls Geheimnisse teilen.
Sie lernen, wie Sie erfolgreich an KI-Programmierwettbewerben teilnehmen können.
Was ist CodinGame?
codameame.com ist eine Bildungsplattform für Entwickler aller Altersgruppen und Ausbildungsstufen. Sie können in 26 Sprachen schreiben: von C # und Python bis Bash und Haskell. Das Coolste ist, dass die Aufgaben dort nicht langweilig und unverständlich sind, sondern echte Spiele mit einer guten GUI:
Ein Wettbewerb ist ein 10-tägiger Wettbewerb, der alle paar Monate stattfindet. Jeder kann teilnehmen, es ist nicht notwendig, Finalist von ACM ICPC zu sein. Um ganz nach oben zu gelangen, müssen Sie natürlich zumindest die für künstliche Intelligenz typischen Algorithmen verstehen.
Aber um ein paar Abende mit Interesse zu verbringen, reicht das Grundwissen aus. In jedem Wettbewerb gibt es einen vorgefertigten Code zum Lesen der Eingabedaten. Es bleibt nur, die Regeln zu lesen, unprätentiös zu schreiben, wenn - sonst - und in die Schlacht!
Code von Kutulu
"Cthulhu Code" ist der letzte Wettbewerb, der vom 15. bis 25. Juni stattfand. Um die Handlung und den Zweck herauszufinden, reicht eine Beschreibung aus:
PH'NGLUI MGLW'NAFH CTHULHU R'LYEH WGAH'NAGL FHTAGN
Was für immer lügen kann, ist überhaupt nicht tot. Und der Tod stirbt in einem mysteriösen Zeitalter.
Sie und Ihr Forscherteam haben das Grab von Cthulhu entdeckt. Dies ist die schlimmste Entscheidung in Ihrem Leben, weil er nicht bereit war aufzuwachen und jetzt hungrig nach Ihrem Tod ist. Aber die Krypta ist ein echtes Labyrinth und du erinnerst dich nicht, wo der Ausgang war ... Wenn er noch da ist!
Oh ... und es scheint, dass Cthulhu nicht allein war und jetzt schickt er die Tiefen für dich.
Versuchen Sie, am längsten am Leben zu bleiben, aber denken Sie daran, dass Sie allein nicht lange durchhalten werden ...
Die Regeln
Ich sage gleich , anstatt eine Textbeschreibung der Regeln zu lesen, können Sie sich ein Video der Analyse der Regeln und der grundlegenden Taktiken von Tinsane ansehen :
Ansonsten lesen Sie weiter.
Karte
Im Spiel gehen vier Spieler auf der generierten Karte - genauer gesagt, der Graph der miteinander verbundenen Zellen. Mehr auf der Karte laufen feindliche Schergen, deren Ziel es ist, die Spieler einzuholen und zu erschrecken.
Charaktere
- Der Forscher ist einer der Spieler. Geht in eine beliebige Richtung auf eine Zelle. Es hat Superkräfte, aber dazu später mehr.
- Vanderer ist ein grünes Monster. Erscheint alle 5 Runden von zuvor bekannten Punkten auf der Karte. Es erzeugt über 3–6 Züge, sucht nach dem nächsten Spieler und beginnt mit der Verfolgung. Geht nur ein Feld pro Runde. Wenn er in N Schritten niemanden gefangen hat, verschwindet er von der Karte.
- Slasher - ähnlich wie der Tod mit einer Sense. Erscheint anstelle eines Spielers, dessen Gesundheit unter 200 Punkte gefallen ist, und bleibt bis zum Ende des Spiels auf der Karte. "Sieht" einen Spieler, wenn sich keine Wände zwischen ihnen befinden. Wenn das Ziel in 2 Zügen nicht aus den Augen verloren wird, springt der nächste Zug an die Stelle, an der der Spieler zuletzt gesehen wurde.
Überleben
Wenn der Wanderer oder Slasher mit dem Spieler die Zelle betritt, verliert der Spieler 20 Gesundheit. Außerdem verlieren die Spieler in jeder Runde ohne Grund eine bestimmte Menge an Gesundheit. Wenn sich jedoch lebende Forscher im Umkreis von zwei Zellen befinden, geht etwas weniger Gesundheit verloren.
Forscher Supermächte
- PLAN - Erhöht die Gesundheit in 5 Runden um 2 Punkte. Wenn andere Forscher in den Aktionsradius fallen, erstreckt sich der Effekt auf sie und der Ersteller des Effekts erhält jeweils +2 Gesundheit. Sie können 2 Mal pro Spiel verwenden.
- YELL - macht dem Spieler in der nächsten Zelle Angst. Die für die nächste Runde geplante Aktion wird zu WAIT (der Spieler bleibt einfach stehen). Es ist nützlich, wenn der Wanderer den Feind verfolgt und Sie ihn ersetzen möchten.
- LICHT - beleuchtet Zellen in einem Radius von 5, Sie können 3 Mal pro Spiel verwenden. Hilft, die Wanderer abzuschrecken: Wenn sie den Weg zum nächsten Ziel zählen, zählt jede beleuchtete Zelle als 4.
Ende des Spiels
Ein Spieler stirbt, wenn seine Gesundheit auf Null fällt. Nach 200 Zügen verlieren die überlebenden Spieler schneller an Gesundheit und das Spiel endet fast sofort.
Wettbewerbsentwickler geben den Spielern die Regeln, aber erfolgreiche Spieler gehen zu Github und lesen den Schiedsrichtercode .
Taktik
Ich muss sofort sagen, dass ich nicht bei Null angefangen habe. Am 16. Juni veranstaltete Kontur in sieben Städten Coding-Hubs - Treffen für diejenigen, die über den Wettbewerb diskutieren und Spaß in einer angenehmen Umgebung haben möchten ( Foto ).
Ich habe die Prüfung an der Universität bestanden und bin nicht zum Hub in Jekaterinburg gekommen, aber ich habe den Bonus der Organisatoren genutzt - das Starter-Kit. Es ist in zwei Sprachen verfügbar - C # und TypeScript - und implementiert bereits die gesamte Infrastruktur: die Logik zum Lesen des Spielstatus in jeder Runde sowie Klassen, die das Spiel selbst charakterisieren (wie Status und mögliche Aktionen), und einige zusätzliche (z. B. ein benutzerdefinierter Timer). . Ich konnte sofort anfangen, das Interessanteste zu schreiben - mein Gehirn bot Forscher.
Eine der Führerinnen des Hubs in Jekaterinburg ist Vanya Dashkevich ( Spaceorc ). Er sitzt seit mehr als einem Jahr auf CodinGame, hat an sieben Wettbewerben teilgenommen und in fünf die Top 100 der Welt erreicht:
Ich erfuhr von Wanja die Einzelheiten der Entscheidung, die ihm den 64. Platz in der Weltrangliste einbrachte, und verglich seine Entscheidung mit meiner.
[1] Komm zu den Hubs: Dort kannst du Links zu Starter-Kits erhalten, die Regeln diskutieren, Taktiken entwickeln und interessante Leute treffen.
Dass zu Beginn des Wettbewerbs, am Ende, der Algorithmus zur Auswahl des nächsten Zuges gleich aussieht:
- Generieren Sie alle Aktionen, die dem Bot zur Verfügung stehen.
- Wenden Sie sie auf den aktuellen Status an.
- Bewerten Sie die Ergebnisse dieser Schritte.
- Wählen Sie die beste.
Verfügbare Aktionen generieren
Ollisteka : Bereits in diesem Schritt begann ich, Heuristiken anzuwenden - ich stellte mich anstelle dieses Forschers vor und entschied, was gut sein würde und was nicht. Kann ich zur nächsten freien Zelle gehen? Fügen Sie einen solchen Zug hinzu. Ich habe noch einen unbenutzten Plan und es gibt keinen Wanderer oder Slasher in der Nähe, der mich in der nächsten Runde angreifen wird. Hinzufügen.
Nach dem gleichen Schema fielen LIGHT und YELL in die Liste der möglichen Aktionen, aber ihre Verwendung senkte mich nur in der Rangliste. Daher habe ich sie immer noch aus der endgültigen Implementierung entfernt.
[2] Hab keine Angst, Fantasie einzubeziehen: Für den Anfang reichen einfache Heuristiken und ein paar bedingte Operatoren aus.
Schlaganfallanwendung
Das Anwenden eines Zuges auf einen Spielzustand wird als Simulation bezeichnet. Das Vorhandensein von Simulationen ermöglicht es Ihnen, fortgeschrittene KI-Programmiertechniken zu verwenden: Minimax , genetische Algorithmen , Monte-Carlo-Baumsuche und andere.
Ollisteka : Dieser Schritt bezieht sich auf meine "Untersimulation". "Nedo" - denn nachdem ich gegangen bin, sollte der Rest der Spieler gehen, die Feinde sollten gehen oder wieder erscheinen. Ich war jedoch zu faul, um eine vollständige Simulation für vier Spieler und eine große Anzahl von Feinden mit nicht trivialer Logik durchzuführen. Daher habe ich meine Gesundheit nur geändert, je nachdem, ob ich alleine oder in einer Gruppe war, und bin in dieser Runde nicht auf einen Wanderer gestoßen.
spaceorc : Mein üblicher Ansatz in letzter Zeit waren zwei Schritte:
- Sie kommen auf irgendeine Weise auf die Bühne, wenn die Organisatoren alle Regeln öffnen und die Quelle des „Schiedsrichters“ auf Github ablegen.
- Sie nehmen den Schiedsrichter und schreiben, während Sie ihn ansehen, eine Simulation.
Die Simulation ist vollständig, mit allen Nuancen, aber unwirksam. Normalerweise wette ich auf die Geschwindigkeit und Tiefe der Suche ... Mit einer vollständigen Simulation können Sie jedoch viele Spiele lokal ausführen und verschiedene Strategien vergleichen. Ich habe die vollständige Simulation mit CodinGame getestet - ich habe die Positionen der Schergen vorhergesagt, wusste, wie die Rivalen gefallen sind (dh der nächste Schritt), und habe die Diskrepanzen herausgefunden. Als die vollständige Simulation fertig war, begann ich, eine schnelle zu schreiben - um dies einfach zu tun und eine funktionierende zu haben.
[3] Willst du an die Spitze? Sie müssen die Regeln herausfinden und eine Simulation schreiben.
Simulation von Gegnern
spaceorc : Schrieb Monte Carlo Tree Search, aber es spielte sich schlechter ab, weil zu wenig Zeit zum Sortieren blieb. Im Allgemeinen kam dieser Ansatz mehr oder weniger nur in Ultimate Tic-Tac-Toe zu mir. Die Gegner spielten auf die gleiche Weise - Simulation pro Zug plus Punktzahl, meine Züge - MCTS und spielen bis zum Ende durch. Auf diese Weise konnten in 50 ms etwa 50 Spiele bis zum Ende simuliert werden. Dies ist nicht genug für MCTS, also habe ich es ausgeschnitten und bin zur ursprünglichen Idee zurückgekehrt.
Infolgedessen wurde eine schnelle Simulation unvollständig:
- hörte auf, die Wanderer weiter als 8 Zellen von mir entfernt zu betrachten;
- hat aufgehört, die Wanderer zu laichen, weil sie bereits in 5 Zügen laichen, und dies ist ungefähr meine Suchtiefe.
Aufgrund dessen hat die Suchtiefe zugenommen. Ich habe auch versucht, nur Bewegungen (ohne YELL, LIGHT, PLAN) meiner Gegner zu simulieren, aber es stellte sich als schlimmer heraus.
Bewertungsfunktion
Die Bewertungsfunktion hilft bei der Auswahl der besten aller verfügbaren Züge. Es nimmt den Status des Spiels bei der Eingabe und gibt auf der Ausgabe eine Zahl mit einer Schätzung an - je größer es ist, desto besser ist der Status des Spiels für den aktuellen Spieler.
Ollisteka : Welche Parameter wurden in meine Bewertung einbezogen:
- die Gesundheit meines Forschers;
- Wanderer:
- Wenn er wahrscheinlich beim nächsten Schritt hierher kommt, ist dies ein schlechter Schritt.
- Wenn ich mit ihm auf der gleichen Linie bin, dann ist es umso besser, je weiter er von ihm entfernt ist.
- Wenn er mich auch jagt, ist die Entfernung noch wichtiger.
- freie Zellen herum, um nicht in eine Sackgasse zu geraten;
- andere Forscher, denen es besser ist, in der Nähe zu bleiben;
- aktueller PLAN: Wenn meine Gesundheit unter 230 fällt, ist eine Behandlung eine gute Idee.
Irgendwann habe ich versucht, die Slashers zu bewerten, aber als ich sie entfernte, wurde ich auf ein paar Dutzend Plätze in der Rangliste angehoben. Wenn ich ihre Logik besser ausarbeiten würde, würden sie vielleicht mehr Gutes tun.
Infolgedessen könnte meine Einschätzung kleiner sein, aber wie sie sagen, funktioniert es - nicht anfassen.
spaceorc : Ich habe versucht, mit Bewertungsfunktionen herumzuspielen , aber es hat nicht sehr gut geklappt ... Im Allgemeinen haben einige derjenigen, die sich in der Rangliste als deutlich höher als ich herausstellten, nicht so viel durchgemacht, sondern gute Funktionen für die Bewertung entwickelt. Damit bin ich nicht fertig geworden. Meine abschließende Bewertungsfunktion umfasste:
- die Anzahl der Punkte (die Tour, auf der gestorben ist + Gesundheit);
- Krähe ;
- Entfernung zu ausländischen Forschern.
[4] Experiment: Ändern Sie die Koeffizienten der Parameter der Bewertungsfunktion, fügen Sie neue Parameter hinzu und löschen Sie die alten.
Den besten Zug wählen
Wir sortieren die Züge in absteigender Reihenfolge, nehmen den ersten und verwenden ihn.
Optimierung
Um einen Platz in den Top 100 zu kämpfen, reicht eine gute Bewertungsfunktion und eine vollständige Simulation nicht aus. Je schneller der Bot arbeitet, desto mehr Spiele werden in einer Zeitscheibe simuliert. Je mehr Spiele, desto wahrscheinlicher ist es, dass der aktuelle Zug am optimalsten ist. Je optimaler der Zug, desto höher der Platz in der Rangliste.
Ollisteka : Ich habe die Tatsache ausgenutzt, dass die Karte in Form eines Diagramms dargestellt werden kann. Ich habe die Längen aller Pfade von Zelle zu Zelle im Voraus berechnet und nicht jedes Mal Zeit damit verbracht.
spaceorc : Bei CodinGame funktionierte die Simulation schnell und machte in 50 ms mehrere Zehntausende von Bewegungen. Aufgrund dessen:
- Bitmasken und unsicherer Code.
- Explorer - int, Wanderer - int, Slasher - int.
- Alle veränderlichen Zustände passen in 128 Bytes, sodass alles sehr schnell funktioniert.
- Die Koordinate ist Byte, da die größte Karte 222 freie Zellen hatte.
- Die Warteschlange muss sein - var queue = stackalloc byte [255].
- Vorberechnung von Wegen, Entfernungen und anderen Dingen.
Ich habe es in letzter Zeit die ganze Zeit gemacht, es ist sehr gut. Übrigens schreibe ich immer viele Tests für eine solche Simulation, ohne die sie einfach nicht debuggt werden kann.
[5] Willst du um einen Platz in den Top 100 kämpfen - entferne ineffizienten Code.
Was es dazu führte
Ollisteka : Während des gesamten Wettbewerbs blieb mein Bot stetig in den Top 300. Irgendwann war ich sogar auf dem 84. Platz in der Weltrangliste, aber dann habe ich eine neue Version festgelegt und bin nicht zurückgekommen. ¯ \ (ツ) / ¯ Nachdem ich den 290. Platz belegt habe, bin ich aus drei Gründen sehr glücklich:
- Dies ist der erste Wettbewerb, an dem ich voll teilgenommen habe, da ich in der Vergangenheit zu beschäftigt mit dem Studium war.
- Ich mochte das Spiel selbst - es war klar, wie man spielt und was man tut, um zu gewinnen.
- Weltbeste 15% - das klingt cool :)
Es war offensichtlich, dass Sie eine vollständige und schnelle Simulation durchführen müssen, um an die Spitze zu gelangen. Aber ich wollte das nicht, also habe ich der Bewertungsfunktion nur Parameter hinzugefügt und die magischen Konstanten geändert.
spaceorc : Ich bin ziemlich zufrieden mit dem Ergebnis, ich bin in die Top 100 gegangen ... Trotzdem musste ich mehr an der Bewertungsfunktion arbeiten, es stellte sich heraus, dass eine starke Tendenz zur Simulation bestand. Und am Ende bin ich ein bisschen müde, meine Fantasie war nicht genug ...
Abschließend
Schauen Sie sich CodinGame an und versuchen Sie es! Im Juli versprechen sie einen neuen Wettbewerb - kommen Sie zu den Hubs, wir werden die Bots zusammen codieren.
Nützliche Links:
UPD Danke dbf für den Kommentar: Code of Kutulu wurde in den Mehrspielermodus hochgeladen . So können Sie das im Artikel gewonnene Wissen in die Praxis umsetzen! :) :)