Anfangs hatte ich keine Pläne für einen Artikel, insbesondere über das Sprechen auf einer Konferenz. Aber es gab eine Konferenz. Und nachdem ich darüber gesprochen hatte, hatten die Zuschauer Fragen zur Umsetzung einiger technischer Probleme. Und so stellte sich Wort für Wort heraus - ein Artikel.
Live-Aufnahme unter dem Link .
Haftungsausschluss: Dieser Artikel ist ein Versuch, einige dieser Fragen zu beantworten. Ich freue mich, wenn neue Fragen auftauchen, auf die ich Gelegenheit habe, selbst etwas Neues zu lernen. Und ja, dieser Artikel ist in keiner Weise ein Versuch, das Klirren von Kupferrohren zu spüren.
Beginnen wir also am Anfang dieser Geschichte. Im Frühjahr 2018 kündigte mail.ru einen Programmierwettbewerb an, der auf dem Agairo- Spiel basiert. Die Essenz des Wettbewerbs ist die Schaffung eines Spielbot.
Wettbewerbsregeln unter diesem Link . Um sich kurz zu fassen und die Regeln in eigenen Worten zu skizzieren, müssen Sie einen Bot erstellen, um in Agairo zu spielen. Zu einer Zeit ein beliebtes Internet-Spiel (in dem Sinne, dass es über den Browser gestartet wird), dessen Essenz darin besteht, Ihre jüngeren Brüder zu essen und vor größeren davonzulaufen. Sie steuern ein Farbrad in einem begrenzten zweidimensionalen Raum. Um das Gameplay in diesem Bereich zu erstellen, gibt es neben Ihrem Kreis noch andere Kreise, die von anderen Spielern entsprechend gesteuert werden. Es gibt Nahrung (farbige Punkte) für das Wachstum, zusätzliche Hindernisse werden in Form von „Viren“ eingeführt, eine Kollision, bei der Ihr Kreis in kleinere aufgeteilt wird, was den Spielprozess teilweise erschwert, da kleine größere essen und größere sicherer sind.
Ich werde ein Bild von einer Variante des Spiels für Wettbewerbe geben
Mit Spieler meinen wir nicht den Bot-Entwickler, sondern den Bot selbst.
Die Organisatoren des gesamten Wettbewerbs behielten das ursprüngliche Konzept des Spiels bei, fügten jedoch eine Reihe von Neuerungen hinzu. Das Hauptproblem ist die Einschränkung der Überprüfung des Bots und die Einführung eines einfachen physikalischen Gesetzes namens Trägheit. Die Physik hat die Physik schon lange durchlaufen, daher ist Trägheit nicht nur mit uns verbunden, sondern auch mit Größen wie Masse, Geschwindigkeit und Beschleunigung. Wir brauchen nichts anderes aus der Welt der Physik.
Ich hoffe, der literarische Teil hat genug Aufmerksamkeit geschenkt und es ist Zeit, sich der technischen Komponente des Wettbewerbs zuzuwenden und daran teilzunehmen.
Haftungsausschluss 2: Ich bin mir ziemlich sicher, dass das, was unten beschrieben wurde, dünner, eleganter und intelligenter gemacht werden könnte, aber wie es passiert ist, ist passiert.
Schreiben Sie also das Rezept und die Hauptzutaten auf, sie sind nicht alle neu, aber Sie können Ihre eigenen nach Ihrem Geschmack hinzufügen.
Aufgabe: Erstellen Sie einen Bot, der Agairo alleine spielen kann.
Die Hauptidee: Verwenden Sie neuronale Netze (im Folgenden als neuronales Netz, neuronales Netz (NN) bezeichnet) als Steuerelement des Bots.
Hauptproduktionswerkzeuge: Microsoft Visual Studio und c # mit einem reibungslosen Übergang zu c ++.
Dann ist es für den Autor am wichtigsten, seinen Leser auszuwählen oder zu verstehen, für den ich schreibe. Er weiß, was neuronale Netze und genetische Algorithmen sind und wie er dies alles im Detail beschreiben kann.
Das ist alles, ich habe meinen Leser ausgewählt, mein Leser weiß das alles, aber nicht so gut, um es in der Praxis anzuwenden.
Während ich diesen Artikel schreibe, werde ich mich daher an einfache Formen wie ein Neuron und eine Aktivierungsfunktion erinnern.
Zur Visualisierung verwende ich handgezeichnete Bilder, die wie folgt gelesen werden sollten: Wenn Sie dort Fehler sehen, schreiben Sie, zeichnen Sie auf die richtigen.
Alles ist also bereit, an den Pfad der Softwarekonstruktion des Bots gesendet zu werden. Fangen wir an:
Wir nehmen den Zyklus, oder besser gesagt, die Organisatoren des Wettbewerbs haben ihn für uns als Beispiel für einen einfachen Bot vorbereitet. Lassen Sie uns tiefer gehen und das Archiv für den Wettbewerbsteilnehmer über diesen Link aus dem Repository herunterladen. Die Organisatoren haben versprochen, dass der Wettbewerbsserver aktiv sein wird, und nach seiner Fertigstellung können wir diese Wörter überprüfen. Wir öffnen das Archiv und wählen eine Programmiersprache, die für uns verständlich ist.
Die Dokumentation des Wettbewerbs beschreibt auch die Kommunikationstechnologie des Kunden (lesen Sie unseren Bot) und des Servers eines Rechenzentrums, das irgendwo in der Tiefe lebt. Kurz gesagt, die Kommunikation erfolgt über die Konsolenleitung, indem Befehle daraus geschrieben und gelesen werden.
Das Zauberwort Serialisierung sollte hier erwähnt werden: Es packt Ihre Daten in ein Format, das der Serializer versteht, und die Fähigkeit, diese Daten mithilfe des Serializers wieder in das Programm einzulesen. Es gibt viele Serializer. Das einfachste sequentielle Format zum Schreiben in die txt-Datei ist ebenfalls ein Serializer, aber einfach. Was wir über Serializer wissen müssen, ist, dass sie existieren und in Bezug auf die API nahezu transparent sind. Die Organisatoren haben dies höchstwahrscheinlich verstanden und daher enthält das Beispiel ihres Bots alle notwendigen Anweisungen für die Arbeit mit dem Serializer. In unserem Fall war es JSON .
Für den Bot nach dem Serializer sieht die Spielwelt wie eine Reihe von Daten aus, die zu Beginn des genannten Zyklus empfangen wurden. Daten über die Spielwelt werden vom Server entsprechend dem Radius der Ansicht begrenzt, der den 4 Radien des Bots entspricht. Denken Sie daran, dass der Bot ein Kreis ist. Und der Kreis um den Kreis ist der äußere Rand der Überprüfung, obwohl der äußere Kreis leicht in Richtung der Bewegung des Bots relativ zur Mitte des Bots voreingenommen ist, aber dies kann in unserem Fall vernachlässigt werden.
Und so haben wir einen Zyklus, das Maß für den Zyklus ist Zecke, wie viele Zyklen vergangen sind, so viele Zecken sind gelaufen. Höchstwahrscheinlich werden wir uns nicht mehr an diesen Tick erinnern, aber er wird eine Reihe wichtiger Einschränkungen und Vereinfachungen mit sich bringen: Die Berechnungszeit wird nicht nur durch einen einzelnen Tick, die Zeit einer Iteration des Zyklus, sondern auch durch die Gesamtberechnungszeit begrenzt, nach deren Ablauf der Spielserver Ihren Bot vom Management trennt. Kreuzen Sie es an und geben Sie dem Bot Befehle. Wir werden es als ein Quantum der Spielzeit betrachten, Tick ist eine unteilbare Zeitdauer in der Spielwelt. Daraus ergeben sich Pluspunkte. Da das Häkchen standardmäßig gleich 1 ist, ist es einfacher, Geschwindigkeiten, Beschleunigungen und andere Werte zu berechnen. In allen Formeln multiplizieren wir mit 1, anstatt eine Art Kurvenzeit t = 0,0015 Sekunden zu verwenden. Fehler in diesen Operationen sind ebenfalls minimal.
Alles oben Genannte ähnelt einem Film, es scheint, dass das Bild auf dem Bildschirm lebhaft und bewegend ist, aber tatsächlich werden uns 25 verschiedene Bilder pro Sekunde gezeigt, und unser Gehirn betrachtet dies nur als ausreichende Frequenz für eine vollständige Wahrnehmung der Dynamik des Videos. So sieht der Bot die Welt in Zeitintervallen. Tick ist ein Rahmen der Spielwelt.
Das neuronale Netzwerk funktioniert auch entsprechend den Zecken.
Das Bild beginnt sich von der Seite des Bots zu klären:
Der Server sendet die verarbeiteten Daten über die Welt an den Bot-> Tick Start-> Der Bot empfängt die Daten -> verarbeitet sie-> sendet die Bot-Verwaltungsbefehle an den Server-> Der Server liest die Daten-> Ende des Ticks und dann in einem nahezu unendlichen Kreis oder einer Schleife 45000 Ticks im Finale Das Spiel ist eine ziemlich bedeutende Figur.
Wichtiger Hinweis: Sie können Tick überspringen und erhalten nichts dafür. Es gibt Fälle von Servern, in denen jeder Tick dem Server etwas mitteilen muss, damit der Server den Bot nicht in einem Hang des Steuerungsprogramms verdächtigt.
Der Autor hat beschlossen, den Server nicht viel zu berühren, aber ich muss ein paar Worte dazu sagen. Auf dem Server befindet sich ein Modell der Spielwelt, das entsprechend Berechnungen und Aktionen ausführt. Das Serverprogramm enthält die folgenden Blöcke:
- Berechnung von Bot-Kollisionen (Verarbeitung von Kollisionen mit den Grenzen der Spielwelt, wer wen gegessen hat, Bot-Bot oder Bot-Essen oder eine Kollision mit einem Virus usw.)
- Berechnung der Bot-Physik (Bot-Bewegung, Änderungen der Bot-Geschwindigkeit gemäß Bot-Befehlen oder aufgetretenen Kollisionen)
- Berechnungen bezogen sich auf das Teilen oder Kombinieren von Bots, wenn möglich, das Hinzufügen von Nahrungsmitteln und anderen Funktionen, um die Spielwelt zu erhalten.
- und natürlich das Senden und Empfangen von Daten an Bots auf Gaming-Ticks.
Ein solcher Server wird als "Befehl" bezeichnet. Das heißt, alle Aktionen werden auf der Serverseite ausgeführt, wodurch Probleme bei der Datensynchronisierung behoben werden. Der Kunde (lesen Sie den Bot) erhält nur ein fertiges Bild der Welt, wie seine anderen Rivalen, hier wird die Gleichheit der Positionen der Bots erreicht, es gibt keine Prioritäten und Warteschlangen. Auch hier tritt eine Änderung der Koordinaten des Bots auf dem Server auf. Beispielsweise gibt der Bot einen Befehl zum Verschieben und erkennt erst beim nächsten Tick seine neuen Koordinaten, die nicht immer mit dem Team übereinstimmen, als Option als Hindernis in Form einer Wand der Spielwelt.
Bild von der Website des Veranstalters
Wir haben das Lesen von Daten mit dem Bot und dem Verwaltungsserver herausgefunden. Schauen wir uns nun die Tiefen des Bot-Geräts an.
Wie der Leser wahrscheinlich bereits verstanden hat, wird es nur wenige Wörter und viel Arbeit geben oder umgekehrt.
Der Bot wird von einem neuronalen Netzwerk gesteuert. Kurz und geräumig, aber nicht ganz klar wie.
Die Wahl eines neuronalen Netzwerks und die Technik für dessen Implementierung.
Im Moment entscheiden wir, dass das neuronale Netzwerk für uns eine Black Box ist, die einen Eingang und einen Ausgang hat.
Die Eingabe und Ausgabe für uns sind eindimensionale Arrays mit einer Dimension von N = 16 für die Eingabe und einer Dimension von M = 4 für die Ausgabe.
Da die Natur des künstlichen neuronalen Netzwerks grob aus dem natürlichen neuronalen Netzwerk kopiert wird, wäre es gut, wenn wir die Struktur der Eingabedaten den natürlichen näher bringen würden. In der Natur sind dafür verschiedene Sensoren verantwortlich. Halten Sie sich also an die Bot-Sensoren.
Die folgende Option wurde experimentell ausgewählt (das Bild ist auf 8 Sensoren und ein neuronales 4x3-Netzwerk vereinfacht, aber dies soll meinen Leser nur verwirren):
Das Sichtfeld des Bots ist in gleiche (möglicherweise sogar ungleiche) Sektoren unterteilt. Jeder Sektor liefert ein Signal an einen der Eingänge des neuronalen Netzwerks. Wenn wir also den Bereich um den Bot in 16 Sektoren unterteilen (360/12 = 22,5 Grad Sektorübersicht), erhalten wir 16 Eingaben des neuronalen Netzwerks. Typischerweise wird ein Signal im Bereich von -1 bis 1 an den Eingang eines neuronalen Netzwerks angelegt. Daher müssen die Eingangssignale normalisiert werden.
Die Rationierung wird vereinfacht, indem das Gesamtsignal durch seinen maximal möglichen Wert geteilt wird. Es ist natürlich möglich, eine dynamische Normalisierung durchzuführen, dh jedes Mal nach dem Maximum zu suchen und den Signalwert auf seine Norm zu bringen, aber wir werden den Maximalwert in Form einer Konstanten festlegen, die der maximalen Anzahl von Objekten in einem Sektor entspricht, und ihn während der Arbeit am Bot nicht ändern.
Die Signale können entweder positiv oder negativ sein. Wir sind uns einig, dass der Signalwert von 0 bis 1 ein positives Motiv für unseren Bot ist (Lebensmittel, Lebensmittel in Form eines kleineren Bots). Ein negativer Signalwert von -1 bis 0 ist ein negatives Motiv für den Bot (Wand) Spielwelt, ein weiterer größerer Bot).
Zeichnen
Ein Signal aus einem Sektor ist eine normalisierte Größe, die aus der Summe einzelner Signale besteht. Jedes einzelne Signal hat, wie gesagt, ein Vorzeichen und eine Größe. Die Größe des Signals ist als proportionale Funktion der Entfernung definiert. Der minimale Abstand ist die Kreisgrenze des definierenden Bots, der maximale Abstand ist der Rand der Sichtbarkeit des Bots. Wenn wir beispielsweise ein positives Signal von Lebensmitteln erhalten, die nur in maximaler Entfernung in den Sektor gelangen, ist das Signal schwach und steigt an, wenn sich der Bot dem Lebensmittel nähert.
Sensoren in Form von Sektoren waren für diesen Fall am besten geeignet, aber es kann einfach Sondenantennen geben, hier ist die Fantasie auf Ihrer Seite. Natürlich hat der Autor verschiedene Optionen für die Aufteilung in Sektoren von 4 bis 72 Sektoren ausprobiert, aber die Praxis hat gezeigt, dass das neuronale Netzwerk in 16 Sektoren recht erfolgreich trainiert ist und bereit ist, den Bot auch mit vier Sektoren zu steuern. Hier zeigt sich die Flexibilität der Natur des neuronalen Netzwerks.
Schließlich wurde das Wort Neuronales Netztraining gesprochen. Im Moment haben wir jedoch entschieden, dass das neuronale Netzwerk eine Black Box mit Ein- und Ausgabe ist. Da wir die Eingabedaten analysiert haben, müssen wir noch ein paar Worte über die Ausgabedaten oder Signale dieser Box sagen, was mit ihnen zu tun ist und wie sie zu verarbeiten sind.
Wir setzen die Dimension des Ausgangssignals auf 4. Diese Zahl ist eine Manifestation des Dualismus von kartesischen Koordinaten und Polar. Der Autor hat die Natur des Wissens seines Lesers nicht vergessen und erinnert ihn daher mit seiner Zeichnung an einmal gut erworbenes Wissen.
Daher verwendeten die Serverentwickler logischerweise die Polarkoordinaten, um die Spielwelt zu simulieren, und stellten den Bots und ihren Entwicklern höflich kartesische Koordinaten zur Verfügung. Daher musste der Autor eine Seite in diesem Koordinatensystem auswählen. Für ein neuronales Netzwerk ist ein Polarkoordinatensystem verständlicher, das nur die Größe (Leselänge) des Vektors und den Winkel seiner Abweichung enthält. Schließlich verstehen Sie auch die Wörter „rechts abbiegen“, anstatt zwei Schritte entlang der Ordinate und drei Schritte entlang der Abszisse zu bewegen.
Daher sind 4 Ausgangssignale, dies sind 2 Signale zum Erhöhen oder Verringern des Winkels des Geschwindigkeitsvektors des Bots, und 2 weitere erhöhen oder verringern die Größe des Geschwindigkeitsvektors.
Aber da der Spielserver darum gebeten hat, Befehle zur Steuerung des Bots in kartesischen Koordinaten zu geben, sind ein paar Formeln für die Übersetzung von Polarkoordinaten in kartesische Koordinaten und all diese Schande an ihren Stellen aufgetaucht (dies ist ein Pseudocode ähnlich c #).
float rotate1 = outputs[0]; float rotate2 = outputs[1]; float speed1 = outputs[2]; float speed2 = outputs[3]; if (rotate1 > 0.65 && rotate2 < 0.65) angle = angle + 35 * PI / 180; if (rotate1 < 0.65f && rotate2 > 0.65) angle = angle - 35 * PI / 180; if (speed1 > 0.65 && speed2 < 0.65) speed = speed + 2; if (speed1 < 0.65 && speed2 > 0.65) speed = speed - 2; dx = speed * Cos(angle); dy = speed * Sin(angle);
Signale sind vorhanden, genau wie bei einem Bot. Es scheint, dass sie ihm Eingangssignale gegeben haben, aber am Ausgang ist etwas nichts wert: Es steht oder bewegt sich zufällig.
Also kam es dazu, die Black Box zu öffnen und hinein zu schauen.
Fortsetzung folgt.
Aber vor der neuen Teaser-Serie:
Der lila Bot im neuronalen Netzwerk spielt in Local Runner gegen die Standard-Bots, die die Organisatoren standardmäßig eingenäht haben.