Der letzte Teil.
In den vorherigen Kapiteln ( Teil 1 , Teil 2 , Teil über die GPU ) haben wir die Bedingungen des Wettbewerbs, das neuronale Netzwerk und den genetischen Algorithmus angesprochen. Fahren wir also fort.
Bevor Sie fortfahren, gibt es einen Link zu GitHub mit dem Quellcode für das Programm in C ++ und zur Unterstützung des Titels des Artikels - eine ausführbare Datei unter Windows im Ordner bin , die dem Bildschirm von saree ziemlich ähnlich ist. Im Keller des Artikels organisierte er die „Hall of Fame“ vergangener Meisterschaften.
Wir haben uns also für die Architektur des Programms entschieden, die aus zwei separaten Teilen (Programmen) besteht, wobei der Teil nur das neuronale Netzwerk und das Kommunikationsprotokoll mit dem Spielserver der Wettbewerbsorganisatoren (dem Spielbot selbst) enthält und der Hauptteil aus den folgenden Blöcken besteht:
Kurz zu jedem der Teile.
Physik-Motor. Basierend auf dem Physikberechnungsmodul aus den offiziellen Quellen, überarbeitet für die GPU und hinzugefügt Bot-Sensor-Berechnungen, Fitnessfunktionen, Bot-Kollisionen. Der Quellcode entfernte Viren und Botversuche, um den instabilen Teil des Programms zu teilen. Deshalb habe ich meine Fehler nicht geteilt.
Neuronales Netz. Wir haben das letzte Mal ausführlich genug darüber gesprochen, einschließlich der Implementierung im Code, daher gehe ich davon aus, dass auch hier viel klar ist, zumal es keine besonderen Fragen von Lesern gab.
Genetischer Algorithmus. Es gab Lücken in der Berichterstattung über die Umsetzung. Jetzt werde ich es höchstwahrscheinlich wiederholen, aber es ist einfacher, es noch einmal zu wiederholen.
Ich erinnerte mich sehr an die Präsentationsfolie. Daher blieb die Hauptfrage: Wie kann man die Evolution bewegen? Hierzu wurde die Fitnessfunktion erfunden. Das Hauptziel der Fitnessfunktion ist die Auswahl von Genotypen für die Übertragung von der aktuellen Population von Bots zur nächsten.
Wie ist die Wahl der Fitnessfunktion höchstwahrscheinlich klar geworden. Die Frage der Überfahrt blieb bestehen.
Es gibt verschiedene grundlegende Methoden der Kreuzung, mehr zum Link . Das Grundprinzip ist jedoch der zufällige Austausch von Genen zwischen elterlichen Genotypen. In der Regel werden zwei Elternteile ausgewählt, es gibt auch verschiedene Methoden zur Auswahl von Eltern aus einer Population, der Link kann detaillierter gelesen werden. Obwohl die Auswahl der Eltern zufällig getroffen wird, steigt die Wahrscheinlichkeit, einen bestimmten Elternteil auszuwählen, proportional zu seiner Fitnessfunktion.
Als nächstes wird die Mutationsfunktion auf den fertigen Genotyp angewendet.
In unserem Fall ändert der Algorithmus von Zeit zu Zeit ein beliebig ausgewähltes Gen in ein zufälliges Gen, mit anderen Worten, eines der Gewichte des neuronalen Netzwerks ändert sich in ein zufälliges.
Wir haben eine neue Population und die weitere Entwicklung führt zum gewünschten Ergebnis. Es gibt mehrere Punkte, den ersten: Je mehr Bots in der Population vorhanden sind, desto schneller findet der genetische Algorithmus die optimale Lösung oder konvergiert zur Lösung (das optimale Gewichtsverhältnis im neuronalen Netzwerk). Wenn ein Bot beispielsweise 1000 Gene hat, erweitert sich der Suchraum mit einer Population von 3000 Bots erheblich, verglichen mit einer Population von 300 Bots. Ein weiteres Problem tritt auf: Wenn Sie alle 3000 Bots in die Arena freigeben, die für 4-8 Bots ausgelegt ist, sind die Bots höchstwahrscheinlich physisch überfüllt. Wenn sie etwas lernen, ist dies definitiv kein Spiel in Agario. Daher gibt es zwei Möglichkeiten, um die Überbevölkerung der Arena zu vermeiden: die erste, bei der mehrere Bots aus der Bevölkerung ausgewählt werden und in der Arena gegeneinander antreten, und zwar so oft, bis wir Spielstatistiken für jeden Bot sammeln. Das zweite, zu dem der Autor gegangen ist, ist der Start mehrerer Arenen parallel, beispielsweise 50-300, alles hängt von der Leistung eines bestimmten Computers ab, und parallel dazu nimmt die gesamte Population von Bots an Wettbewerben teil. Die Population kann mit ihren Fitnessfunktionen und Identifikatoren in Subpopulationen unterteilt werden (entspricht der Anzahl der Arenen) und dann Genotypen zwischen Subpopulationen austauschen. Oder stellen Sie sich alles als eine große Population von Bots vor, die in verschiedenen Arenen spielen. Der Autor hat beide Optionen ausprobiert, jedoch in der Quellversion mit einer einzigen Population von Bots. Der Parameter im Depth ist die Arenanummer.
Also erklärte er die Grundprinzipien des Aufbaus eines Programms. Wer live sehen will, heißt auf dem Link zum Github willkommen .
Wenn Sie es nicht starten können, wird ein kurzes Video diesen Moment aufhellen:
Ankündigung: Im August wird mail.ru einen weiteren AI Mini Cup organisieren, die offizielle Ankündigung wurde noch nicht als wahr angesehen. Aber nach Informationen aus den Telegrammen der Gruppe ist die Basis des Wettbewerbs wieder die Physik-Engine, etwas über Autos. Daher kurz über die Prinzipien der Erstellung eines Bots, diejenigen, die natürlich interessiert sein werden:
Hier, wie bei unserer Fußballmannschaft, ist es ratsam, die Gruppe zu verlassen, das Finale ist ein separates Lied. Lassen Sie die Finalisten über die Siege schreiben, aber unsere Hauptbeteiligung.
Das klarste und einfachste:
Schreiben Sie mehr verschiedene Bedingungen in den Hauptteil des Bot-Codes, zum Beispiel wenn (Loch) -> springen usw. Einfache Bedingungen sind zu Beginn der Meisterschaft wirksam, dann wird die Komplexität der Bots zunehmen und der Vorteil bedingter Lösungen wird verschwinden.
Und so die vielversprechendste Methode in vielen strategischen Spielen:
PP-Methode ( oder potenzielle Felder ). Die Idee ist schön, die Suche nach Maximum oder Minimum in einer dynamischen Umgebung. Ein Raster der ausgewählten Dimension wird auf dem gesamten Spielfeld oder nur auf dem Gebiet um den Bot erstellt. Dies hängt alles vom Umfang des Bots ab. Als nächstes betrachten wir an jedem Knotenpunkt dieses Gitters die Abstände zu den für uns interessanten Objekten oder als Option sofort Potentiale, die positiv (Anziehung, das ist das, was für den Bot interessant ist) und negativ (Gefahr für den Bot) sein können. Dementsprechend werden die Potentiale am Punkt summiert und wir erhalten die Gesamtpotentiale an jedem Punkt des Gitters. Potentialfeld. Der Bot kann je nach Aufgabe nur das kleinste oder größte Potenzial auswählen. Grundsätzlich sind potenzielle Felder 2D-Implementierungen, obwohl 3D cool aussehen wird, aber es wird eine Menge Ressourcen für Berechnungen geben.
Das Schwierigste:
Die beiden Hauptimplementierungen sind die Brute-Force- Methode oder die Monte-Carlo-Methode . Jeder von ihnen ist das Thema eines separaten Artikels, aber je nach Sensation sind es diese Methoden, die Sie zum Finale führen. Wenn es sich um eine These handelt, kann der Bot nicht nur auf die aktuelle Zeit oder Vergangenheit schauen, sondern wenn er möchte, kann er in die Zukunft schauen, ein Trichter (Kegel) möglicher Ergebnisse erscheint hier und je weiter der Bot sehen möchte, desto mehr Optionen erscheinen. Zum Zeitpunkt Tick Zero entscheidet sich der Bot beispielsweise für eine von acht Richtungen. Bei Schritt Tick + 1 in jeder der acht neuen Koordinaten hat er die Möglichkeit, erneut in acht Richtungen zu gehen. Es ist notwendig, mögliche feindliche Bewegungen während dieser Zeit zu berücksichtigen. Jedes mögliche Ergebnis der Berechnungen bringt einen möglichen Nutzen oder Schaden mit sich. Basierend darauf bewegt sich der Bot in eine der Richtungen. Und weiter geht eine solche Berechnung in der Tiefe der Zukunftsform mit jedem Tick. Die Tiefe der Bewegungsansichten wird durch die möglichen Ressourcen des Computers bestimmt. Daher tritt bei kleinen Computerressourcen das Problem auf, diese Berechnungen zu optimieren.
Über die Quelle, wenn Interesse besteht, werde ich die Kommentare zum Code bearbeiten, während ich ihn so angelegt habe, wie er war.
In der Quelle werden die Signale des aktuellen Ticks und des vorherigen Ticks an den Eingang des Neurons gesendet, es wurde dank des Lesers interessanter: tongohiti für die Idee.
Für diejenigen, die sich an die These über die anfängliche Verteilung von Gewichten im neuronalen Netzwerk erinnern, ist die Xavire-Initialisierung ein interessantes Thema.
Vielen Dank für Ihre Aufmerksamkeit. Treffen Sie mich bei KI-Wettbewerben.
Verwandte Artikel von Teilnehmern, aber erster Exkurs :
Sie saß auf dem Boden
Und sortierte den Stapel von Briefen
Und wie gekühlte Asche
Ich nahm sie in meine Hände und warf sie.
Nahm vertraute Blätter
Und es war wunderbar, dass sie sie ansah,
Wie Seelen von oben aussehen
Auf ihnen ein verlassener Körper ...
Oh, wie viel Leben war hier
Irreversibel erfahren!
Oh, wie viele traurige Minuten
Liebe und Freude getötet! ..
Meine Strategie beim Russian AI Cup 2017
Geschichte der Teilnahme (und fast des Sieges) am jährlichen Wettbewerb Russian AI Cup 2016
Siegesgeschichte beim jährlichen russischen AI Cup 2015
Russischer AI Cup 2014: Siegerstrategie
Goldmedaille beim Russian AI Cup 2013 - wie das alles war
Der Weg zur Silbermedaille beim russischen AI Cup 2012