Es ist Tradition geworden, dass der Gewinner oder nur ein Spieler nach Sportprogrammwettbewerben einen Artikel über Habré veröffentlicht, um zu erklären, wie großartig es war, an dem Wettbewerb teilzunehmen und als Option, um daran zu gewinnen. Natürlich kann aus seinem Artikel viel für zukünftige Wettbewerbe entnommen werden.
Ich denke jedoch, dass es nur wenige Artikel über die Teilnahme am aktuellen Wettbewerb in der Beta-Testphase gibt. Es ist klar, dass Sie den Entscheidungscode nicht veröffentlichen können. Es ist immer noch nicht bekannt, wie gut diese Entscheidung ist, und vieles ist noch unbekannt, denn dies ist tatsächlich erst der Beginn des Turniers, aber das ist der Reiz. Der Autor gibt dem Leser die Möglichkeit, in einen abfahrenden Zug einzusteigen und eine Neujahrsreise in die Welt der Spielstrategien zu genießen.
Zunächst einmal danke ich Ihnen, dass Sie den Artikel geöffnet haben. Ich möchte sofort ein Geheimnis preisgeben: Dies wird eine Reihe von Artikeln sein, in denen ich hoffe, genetische Algorithmen und neuronale Netze ansprechen zu können. In der Zwischenzeit, wie bereits oben geschrieben, herzlich willkommen zu einem Ausflug zum russischen AI Cup CodeBall.
Link zur Schnellstartseite der Meisterschaft.Unter dem obigen Link kann der Leser die Regeln der Meisterschaft, die Spielregeln selbst und den Hauptteil des mathematischen Apparats finden, der zum Erstellen des Bots erforderlich ist. Auf der Schnellstartseite finden Sie auch Beispiele für bereits geschriebene Bots für verschiedene Programmiersprachen, was den ersten Start erheblich erleichtert.
Beginnen wir mit einem einfachen CodeBall-Meistertitel.
Eine schöne Kombination aus den Wörtern Code und Ball, fast Fußball. Die Regeln und die Logik des Spiels sind ebenfalls ähnlich wie beim Fußball, aber mit jeder Runde werden sie komplizierter. Daher werden wir die Anfangsbedingungen der Spiele als Grundlage nehmen.
Die Essenz des Spiels, wie in einem kürzlich erschienenen Song angegeben: Die Spieler müssen ein Tor erzielen und der Torhüter muss die Bälle schlagen.
Schematisches Spielfeld:
Bitte beachten Sie, dass sich die Bots in der Ebene des XZ-Arenabodens bewegen. Die Y-Achse ist für die Höhe des Spielobjekts verantwortlich.
Auch schematisch Objekte des Spiels (Ball und Bots (die Organisatoren nennen sie Roboter))
Nun etwas Text zur Unterstützung der Bilder. Das Spielfeld ist ein dreidimensionaler geschlossener Raum, weder der Ball noch die Bots können darüber hinausgehen. In diesem Bereich gibt es zwei Bereiche des „Tors“, in denen der Ball von einem der Spieler als erzielt gilt. Damit das Tor gezählt werden kann, muss sich der Ball vollständig hinter den Torlinien befinden (in der Abbildung durch eine gepunktete Linie gekennzeichnet).
Um die Berechnung von Kollisionen (Kollisionen) von Spielobjekten (Arena, Ball, Bots) zu vereinfachen, werden Bots und der Ball als ideale Kugeln (Bälle) betrachtet, die durch die folgenden Werte beschrieben werden: Radius der Kugel, Koordinate des Kugelmittelpunkts, Masse, Geschwindigkeit. Die Arena wird auch durch ideale mathematische Grundelemente beschrieben, so dass auf die Kollisionsberechnung ohne Beteiligung von Polygonen verzichtet wird, was die Aufgabe erheblich vereinfacht. Wenn Sie bis zum Ende durch die Meisterschaftsregeln scrollen, findet der Leser ein Programm auf dem Pseudocode, das nur für die obigen Berechnungen verantwortlich ist. Dieser Pseudocode wird nach geringem Aufwand in die Programmiersprache Ihrer Wahl übersetzt und ist durchaus praktikabel. Aber dazu später mehr.
Ein paar Worte zur Physik der Spielwelt. Um dem Geschehen in der Arena Glaubwürdigkeit zu verleihen, wird die Schwerkraft eingeführt, dh Bots und der Ball werden ständig von der Schwerkraft beeinflusst, die relativ zum Boden der Arena nach unten gerichtet ist. Die anderen Formen der physischen Interaktion wie Reibung oder Winkelgeschwindigkeiten (Rotation) von Objekten wurden von den Organisatoren zugunsten der Einfachheit der Beschreibung der physischen Welt ignoriert. Wenn der Ball gegen die Wände der Arena schlägt, verliert er einen Teil seiner Energie, aber dies erschwert die Welt nicht sehr und es ist von außen verständlich, dass es keine Möglichkeit gibt, eine Perpetual-Motion-Maschine in Form eines Balls zu schaffen.
Um die Welt noch plausibler erscheinen zu lassen, wurde ein Berechnungsschema mit Zecken und Mikrotiks angewendet. In
seinem ersten Artikel ging der Autor ausführlich auf das Konzept der Teakholzspielzeit ein. In diesem Wettbewerb können wir uns die physische Engine in den Quellcodes ansehen, wie er sagte, es wird für uns in Zukunft nützlich sein und feststellen, dass es für die Spieler Tics gibt, und innerhalb der Engine passiert alles in Mikrotik, standardmäßig 100 Mikrotik in einem Tick, was es möglich macht, genauer zu sein Beschreiben Sie Kollisionen von Objekten und vermeiden Sie unangenehme Dinge wie das Versagen von Objekten außerhalb der Arena oder das Versagen von Objekten ineinander, was zu Fehlern in der Interaktion zwischen ihnen führt.
Wir haben die Welt (Arena) und die Spielzeit herausgefunden. Schauen wir uns die Spielobjekte an: Bots und den Ball. Der Ball, den wir bereits aus den Wettbewerbsregeln herausgefunden haben, ist eine Kugel. Kurz gesagt, ein Bot ist eine Kugel mit einem kleineren Radius und einer größeren Masse, der Befehle gegeben werden können: Geben Sie die gewünschte Geschwindigkeit (dies ist ein dreidimensionaler Vektor, der sowohl Richtung als auch Länge oder Größe der Geschwindigkeit enthält) und die Stärke des Sprunges an, wenn der Sprung derzeit aus der Sicht ratsam ist die Logik des Spiels. In dieser Phase des Wettbewerbs wurde eine Vereinfachung eingeführt: Wenn der Bot im Flug ist (die Wände der Arena nicht berührt), kann er keine Befehle zum Ändern der Geschwindigkeit ausführen.
Wir wenden uns dem Schwierigsten zu oder umgekehrt, alles hängt von der Erfahrung des Lesers bei der Arbeit mit dreidimensionalen Vektoren ab. Beschreibung des Standorts von Spielobjekten. Unterstützungsbild
Kommen wir zur Botanik.
Bei jedem Spiel-Tick erhält Ihre Strategie die folgenden Objekte:
Ball:
class Ball: x: Float
und eine Liste von Bots mit Daten für jeden Bot:
class Robot: id: Int player_id: Int is_teammate: Bool
Sie können sofort erkennen, dass es unpraktisch ist, mit diesen Daten zu arbeiten. Es ist wünschenswert, einen Klassen- (Objekt-) 3D-Vektor und einen Klassen-2D-Vektor einzuführen. Viel hängt von der Programmiersprache Ihrer Wahl ab. Normalerweise sind diese Klassen bereits geschrieben und für die gewünschte Programmiersprache leicht im Internet zu finden. Der Autor schreibt jetzt einen Bot in c ++, wird aber versuchen, sich auf Pseudocode zu beschränken. Wenn Sie vollwertige Klassen von Vektoren einführen, bleiben die Operationen der Addition, Subtraktion, Multiplikation, Normalisierung und anderer Vektoroperationen innerhalb der Klasse, was die Arbeit an der Strategie erheblich vereinfacht.
Es gibt auch eine Spielerklasse, die angibt, welche Bots aus der Liste Ihnen gehören, welche:
class Player: id: Int me: Bool
Nachdem Sie Daten über die Spielwelt an die Eingabe Ihrer Strategie übertragen haben, gibt Ihnen die Spiel-Engine die Kontrolle und startet einen Timer für Berechnungen. Die Zeit für Berechnungen ist im Durchschnitt auf etwa 20 Millisekunden für alle Aktionen innerhalb des Ticks begrenzt. Es besteht der Verdacht, dass zu diesem Zeitpunkt auch Zeit zum Deserialisieren der empfangenen Daten und zum
Serialisieren der von Ihrer Strategie an den Server gesendeten Daten enthalten ist. Da die Anzahl der Bots jedoch 4 beträgt (Ihre 2 und 2 Gegner, erhöht sich in der letzten Runde die Gesamtzahl der Bots auf 6), kann die Zeit für diese Operationen vernachlässigt werden.
Es ist Zeit für die Teams.
Zum Beispiel möchten wir dem Bot den Befehl geben, sich auf den Ball zu bewegen. Um den gewünschten Vektor der Geschwindigkeitsrichtung zu finden, muss die Position des Bots von der Ballposition subtrahiert werden. Wir erhalten den Richtungsvektor zum Ball. Dann kann er normalisiert und mit der maximalen Geschwindigkeit des Bots von den Konstanten der Welt multipliziert werden. Auf dem Bild mehr
Wahrscheinlich hat der Leser auf der Folie bemerkt, dass die Berechnungen sowohl für 3D-Vektoren als auch für 2D-Vektoren durchgeführt werden können. Wenn wir die Tatsache berücksichtigen, dass der Bot mehr Zeit auf der Bodenebene der Arena verbringt, hat die Vereinfachung der Berechnungen auf zwei Koordinaten keinen Einfluss auf die Genauigkeit der Berechnungen zum Abfangen des Balls. Natürlich sollten Sie die Höhe des Balls nicht vergessen, aber unter Berücksichtigung der Schwerkraft wird er früher oder später auf den Bot sinken.
Ein Bot-Sprung ist die Addition der vertikalen Geschwindigkeit (vertikale Geschwindigkeit). Die Richtung des Bot-Sprungs stimmt mit der Richtung der aktuellen Bot-Geschwindigkeit überein, wobei eine Komponente entlang der Y-Achse hinzugefügt wird.
Wenn wir den obigen Wörtern eine komplexere Bewegungslogik hinzufügen, können wir das folgende Verhalten von Bots erhalten:
Jetzt hat die Site eine Sandbox, in der Sie die Spiele sehen können, aber nichts fühlt sich an, wenn Sie Ihre Strategie schreiben und ihren Spielen folgen. Es wurde experimentell festgestellt, dass selbst die einfachste Strategie, die aus mehreren zehn Codezeilen besteht, recht gut funktionieren kann.
Von den einfachen Formen von Strategien, die mir in den Sinn kommen, ist die Strategie, einen Bot zuzuweisen, um das Tor zu schützen, den zweiten Bot, um einen Angreifer zu machen. Die Hauptaufgabe des Angreifers besteht darin, den Ball zu jagen und bei Erfolg auf das gegnerische Tor zuzuschlagen. Ein Bot, der als Torhüter spielt, ist normalerweise in seiner Bewegung auf dem Spielfeld eingeschränkt und operiert hauptsächlich im Torraum. All diese Dinge lassen sich leicht mit if-else-Konstrukten der von Ihnen gewählten Sprache beschreiben. In jedem Fall muss mein Leser in dieser Phase eine Strategie entwickeln. Gemäß den Wettbewerbsbedingungen können Sie den Quellcode der Strategie nicht veröffentlichen. Ich denke jedoch, dass es nicht verboten ist, Ansätze zur Gestaltung einer Strategie zu diskutieren.
Es scheint mir, dass die Organisatoren des Wettbewerbs ein interessantes Thema für das Turnier ausgewählt haben, die einzige Seite ist etwas langsam, aber ich hoffe, dass es bald behoben wird.
einige schöne Spielmomente vom Teilnehmer der Meisterschaft:
Ich warte auf Feedback in den Kommentaren zum Artikel, worauf ich näher eingehen soll.
Im nächsten Artikel werde ich versuchen, Methoden zur Vorhersage des Verhaltens des Balls rechtzeitig für ein aussagekräftigeres Botspiel in Ihrer Strategie zu beschreiben.
In der Zwischenzeit herzlichen Glückwunsch zum kommenden Neujahr 2019!
Fortsetzung folgt.