Dies ist die 14-tägige Herausforderung Nr. 3. Thema: Genetische Algorithmen
Diese Herausforderung ist ein bisschen experimentell. Wir wollten herausfinden, was wir mit genetischen Algorithmen herausfordern können. Es mag nicht alles optimal sein, aber wir haben unser Bestes gegeben, um es zugänglich zu machen. Wenn dies klappt, wer weiß, was wir in Zukunft sehen könnten? Vielleicht ein genetischer King of the Hill?
Die Spezifikation ist ziemlich lang! Wir haben versucht, die Spezifikation in "The Basics" zu unterteilen - das absolute Minimum, das Sie benötigen, um mit dem Framework zu spielen und eine Antwort zu senden - und "The Gory Details" - die vollständige Spezifikation mit allen Details zum Controller, auf deren Grundlage Sie arbeiten könnte deine eigene schreiben.
Wenn Sie irgendwelche Fragen haben, können Sie gerne mit uns chatten!
Du bist ein Forscher in der Verhaltenspsychologie. Es ist Freitagabend und Sie und Ihre Kollegen beschließen, Spaß zu haben und Ihre Laborratten für ein kleines Rattenrennen zu verwenden. Nennen wir sie tatsächlich Exemplare , bevor wir uns zu emotional an sie binden .
Sie haben eine kleine Rennstrecke für die Exemplare eingerichtet, und um es interessanter zu machen, haben Sie ein paar Mauern und Fallen und Teleporter über die Strecke gelegt. Jetzt sind deine Exemplare immer noch Ratten ... sie haben keine Ahnung, was eine Falle oder ein Teleporter ist. Sie sehen nur einige Dinge in verschiedenen Farben. Sie haben auch keinerlei Gedächtnis - alles, was sie tun können, ist Entscheidungen auf der Grundlage ihrer aktuellen Umgebung zu treffen. Ich vermute, dass die natürliche Selektion die Exemplare heraussucht, die wissen, wie man einer Falle aus dem Weg geht, die es nicht wissen (dieses Rennen wird eine Weile dauern ...). Lasst die Spiele beginnen! †
† 84.465 Exemplare wurden bei dieser Herausforderung verletzt.
Die Grundlagen
Dies ist ein Einzelspieler-Spiel (Sie und Ihre Kollegen wollten die Bevölkerung nicht verwechseln, also baute jeder seine eigene Rennstrecke). Die Rennstrecke ist ein rechteckiges Gitter, 15 Zellen hoch und 50 Zellen breit. Sie beginnen mit 15 Proben in zufälligen (nicht unbedingt unterschiedlichen) Zellen am linken Rand (wobei x = 0 ). Ihre Proben sollten versuchen, das Ziel zu erreichen, bei dem es sich um eine beliebige Zelle bei x ≥ 49 und 0 ≤ y ≤ 14 handelt (die Proben können die Spur nach rechts überschreiten). Jedes Mal, wenn dies passiert, bekommst du einen Punkt. Sie starten das Spiel auch mit 1 Punkt. Sie sollten versuchen, Ihre Punkte nach 10.000 Runden zu maximieren .
Mehrere Proben können dieselbe Zelle belegen und interagieren nicht.
Jedes Exemplar sieht in jeder Runde ein 5x5-Raster seiner Umgebung (mit sich selbst in der Mitte). Jede Zelle dieses Gitters enthält eine Farbe -1
für 15
. -1
Stellt Zellen dar, die außerhalb der Grenzen liegen. Ihre Probe stirbt, wenn sie sich außerhalb der Grenzen bewegt. Die anderen Farben repräsentieren leere Zellen, Fallen, Wände und Teleporter. Aber Ihr Exemplar weiß nicht, welche Farbe was darstellt, und Sie auch nicht. Es gibt jedoch einige Einschränkungen:
- 8 Farben stehen für leere Zellen.
- 4 Farben repräsentieren einen Teleporter. Ein Teleporter sendet die Probe an eine bestimmte Zelle in seiner 9x9-Nachbarschaft. Dieser Versatz ist für alle Teleporter der gleichen Farbe gleich.
- 2 Farben repräsentieren Wände. Sich in eine Wand zu bewegen ist dasselbe wie still zu stehen.
- 2 Farben repräsentieren eine Falle. Eine Falle zeigt an, dass eine der 9 Zellen in ihrer unmittelbaren Nachbarschaft tödlich ist (nicht unbedingt die Falle selbst). Dieser Versatz ist für alle Überfüllungen derselben Farbe gleich.
Nun zu dieser natürlichen Selektion ... jedes Exemplar hat ein Genom, das eine Zahl mit 100 Bits ist. Neue Exemplare werden durch Kreuzung zweier vorhandener Exemplare und anschließende leichte Mutation des Genoms erzeugt. Je erfolgreicher ein Exemplar ist, desto größer ist seine Reproduktionswahrscheinlichkeit.
Hier ist also Ihre Aufgabe: Sie schreiben eine einzelne Funktion, die als Eingabe das 5x5-Farbraster erhält, das eine Probe sieht, sowie ihr Genom. Ihre Funktion gibt eine Bewegung (Δx, Δy) für die Probe zurück, wobei Δx und Δy jeweils eine von sind {-1, 0, 1}
. Sie dürfen keine Daten zwischen Funktionsaufrufen beibehalten. Dies beinhaltet die Verwendung eigener Zufallszahlengeneratoren. Ihre Funktion wird mit einem gesetzten RNG ausgestattet, das Sie nach Belieben verwenden können.
Die Bewertung Ihres Beitrags ist das geometrische Mittel der Punktzahl auf 50 zufälligen Tracks. Wir haben festgestellt, dass diese Punktzahl einiges an Varianz aufweist. Daher sind diese Ergebnisse vorläufig . Sobald diese Herausforderung endet, wird eine Frist bekannt gegeben. Am Ende der Frist werden 100 Boards nach dem Zufallsprinzip ausgewählt und alle Einsendungen werden auf diesen 100 Boards neu bewertet. Fühlen Sie sich frei, eine geschätzte Punktzahl in Ihre Antwort einzutragen, aber wir werden jede Einreichung selbst bewerten, um sicherzustellen, dass niemand betrügt.
Wir haben Steuerungsprogramme in einer Handvoll Sprachen bereitgestellt. Derzeit können Sie Ihren Beitrag in Python (2 oder 3), Ruby , C ++ , C # oder Java schreiben . Der Controller generiert die Bretter, führt das Spiel aus und stellt einen Rahmen für den genetischen Algorithmus bereit. Sie müssen lediglich die Bewegungsfunktion bereitstellen.
Warten Sie, was genau mache ich mit dem Genom?
Die Herausforderung besteht darin, das herauszufinden!
Da die Exemplare kein Gedächtnis haben, ist alles, was Sie in einer bestimmten Runde haben, ein 5x5-Raster von Farben, die Ihnen nichts bedeuten. Sie müssen also das Genom verwenden, um das Ziel zu erreichen. Die allgemeine Idee ist, dass Sie Teile des Genoms verwenden, um Informationen über die Farben oder das Rasterlayout zu speichern, und Ihr Bot seine Entscheidungen auf der Grundlage der zusätzlichen Informationen, die im Genom gespeichert sind.
Natürlich können Sie dort nichts manuell speichern. Die dort gespeicherten Informationen sind also zunächst völlig zufällig. Der genetische Algorithmus wird jedoch bald diejenigen Exemplare auswählen, deren Genom die richtigen Informationen enthält, während diejenigen, die die falschen Informationen enthalten, getötet werden. Ihr Ziel ist es, eine Zuordnung von den Genombits und Ihrem Blickfeld zu einer Bewegung zu finden, mit der Sie schnell einen Weg zum Ziel finden und die sich konsequent zu einer Gewinnstrategie entwickelt.
Dies sollten genügend Informationen sein, um Ihnen den Einstieg zu erleichtern. Wenn Sie möchten, können Sie den nächsten Abschnitt überspringen und den Controller Ihrer Wahl aus der Liste der Controller unten auswählen (die auch Informationen zur Verwendung dieses bestimmten Controllers enthält).
Lesen Sie weiter, wenn Sie alle wollen ...
Die blutigen Details
Diese Spezifikation ist vollständig. Alle Controller müssen diese Regeln implementieren.
Jede Zufälligkeit verwendet eine gleichmäßige Verteilung, sofern nicht anders angegeben.
Track-Generierung:
- Die Spur ist ein rechteckiges Gitter, X = 53 Zellen breit und Y = 15 Zellen hoch. Zellen mit x ≥ 49 sind Zielzellen (wobei x auf Null basiert).
- Jede Zelle hat eine einzige Farbe und kann tödlich sein oder auch nicht - Zellen sind nicht tödlich, es sei denn, einer der folgenden Zelltypen gibt dies an.
- Es gibt 16 verschiedene Zellenfarben, die von
0
bis beschriftet sind15
und deren Bedeutung sich von Spiel zu Spiel ändert. Stellt außerdem-1
Zellen dar, die außerhalb der Grenzen liegen - diese sind tödlich . - Wähle 8 zufällige Farben . Dies sind leere Zellen (die keine Auswirkung haben).
- Wähle 4 weitere zufällige Farben . Das sind Teleporter. Wählen Sie für zwei dieser Farben einen Versatz ungleich Null in der Nachbarschaft 9x9 (von (-4, -4) bis (4,4) mit Ausnahme von (0,0)). Invertieren Sie für die beiden anderen Farben diese Offsets. Wenn ein Exemplar auf einen Teleporter tritt, wird es sofort um diesen Versatz bewegt.
- Wähle 2 weitere zufällige Farben . Das sind Fallen. Wählen Sie für jede dieser Farben einen Versatz im 3x3-Bereich (von (-1, -1) bis (1,1)). Eine Falle zeigt an, dass die Zelle an diesem Versatz tödlich ist . Hinweis: Die Falle selbst ist nicht unbedingt tödlich.
- Die 2 verbleibenden Farben sind Wände, die die Bewegung behindern. Der Versuch, auf eine Wandzelle zu gelangen, führt dazu, dass die Bewegung stillsteht. Wandzellen selbst sind tödlich .
- Wählen Sie für jede Nicht-Ziel-Zelle des Rasters eine zufällige Farbe. Wählen Sie für jede Zielzelle eine zufällige leere Farbe.
- Bestimmen Sie für jede Zelle am linken Rand der Spur, ob das Ziel innerhalb von 100 Runden erreicht werden kann (gemäß den folgenden Regeln für die Reihenfolge der Runden). Wenn ja, ist diese Zelle eine zulässige Startzelle . Wenn weniger als 10 Startzellen vorhanden sind, verwerfen Sie die Spur und generieren Sie eine neue.
- Erstellen Sie 15 Exemplare mit einem zufälligen Genom und einem Alter von 0 Jahren . Legen Sie jede Probe auf eine zufällige Startzelle.
Turn Reihenfolge:
- Die folgenden Schritte werden der Reihe nach für jede Probe ausgeführt. Die Proben interagieren nicht oder sehen sich nicht und können dieselbe Zelle einnehmen.
- Wenn die Probe 100 Jahre alt ist , stirbt sie. Andernfalls erhöhen Sie das Alter um 1.
- Die Probe erhält ihr Sichtfeld - ein 5x5-Farbraster, das auf der Probe zentriert ist - und gibt eine Bewegung in ihrer 3x3-Nachbarschaft zurück. Bei Bewegungen außerhalb dieses Bereichs wird der Controller beendet.
- Wenn die Zielzelle eine Wand ist, wird der Zug in (0,0) geändert.
- Wenn die Zielzelle ein Teleporter ist, wird die Probe um den Versatz des Teleporters bewegt. Hinweis: Dieser Schritt wird nur einmal und nicht iterativ ausgeführt.
- Wenn die derzeit von der Probe besetzte Zelle (möglicherweise nach Verwendung eines Teleporters) tödlich ist, stirbt die Probe. Dies ist das einzige Mal, dass Proben sterben (abgesehen von Schritt 1.1. Oben). Insbesondere eine neue Probe, die auf einer tödlichen Zelle erscheint, stirbt nicht sofort ab, sondern hat die Chance, die gefährliche Zelle zuerst zu verlassen.
- Wenn die Probe eine Zielzelle belegt, erzielen Sie einen Punkt, verschieben Sie die Probe in eine zufällige Startzelle und setzen Sie ihr Alter auf 0 zurück.
- Wenn sich weniger als zwei Exemplare auf dem Brett befinden, endet das Spiel.
- Erstellen Sie 10 neue Exemplare mit dem Alter von 0 Jahren . Jedes Genom wird (einzeln) durch die folgenden Zuchtregeln bestimmt. Legen Sie jede Probe auf eine zufällige Startzelle.
Zucht:
Wenn ein neues Exemplar erstellt wird, wählen Sie nach dem Zufallsprinzip zwei verschiedene Eltern mit einer Tendenz zu Exemplaren, die weiter nach rechts vorgerückt sind. Die Wahrscheinlichkeit, dass eine Probe ausgewählt wird, ist proportional zu ihrem aktuellen Fitness-Score . Der Fitness-Score eines Exemplars beträgt
1 + x + 50 * Häufigkeit, mit der das Ziel erreicht wurde
Dabei ist x der auf 0 basierende horizontale Index. Exemplare, die im selben Zug erstellt wurden, können nicht als Eltern ausgewählt werden.
Wählen Sie aus den beiden Elternteilen einen zufälligen aus, dem Sie das erste Genomstück entnehmen möchten.
- Wechseln Sie jetzt, während Sie durch das Genom gehen, mit einer Wahrscheinlichkeit von 0,05 die Eltern und nehmen Sie dem resultierenden Elternteil weitere Teile ab.
- Mutieren Sie das vollständig zusammengesetzte Genom: Drehen Sie es für jedes Bit mit einer Wahrscheinlichkeit von 0,01 um .
Wertung:
- Ein Spiel dauert 10.000 Runden.
- Die Spieler beginnen das Spiel mit 1 Punkt (um die Verwendung des geometrischen Mittels zu ermöglichen).
- Jedes Mal, wenn eine Probe das Ziel erreicht, erhält der Spieler einen Punkt.
- Derzeit wird die Einreichung jedes Spielers für 50 Spiele mit jeweils einer anderen zufälligen Spur ausgeführt.
- Der obige Ansatz führt zu mehr Varianz als wünschenswert ist. Sobald diese Herausforderung endet, wird eine Frist bekannt gegeben. Am Ende der Frist werden 100 Boards nach dem Zufallsprinzip ausgewählt und alle Einsendungen werden auf diesen 100 Boards neu bewertet.
- Die Gesamtpunktzahl eines Spielers ist das geometrische Mittel der Punktzahlen dieser einzelnen Spiele.
Die Controller
Sie können einen der folgenden Controller auswählen (da sie funktional gleichwertig sind). Wir haben alle getestet, aber wenn Sie einen Fehler entdecken, den Code oder die Leistung verbessern oder eine Funktion wie eine grafische Ausgabe hinzufügen möchten, senden Sie uns bitte ein Problem oder senden Sie eine Pull-Anfrage auf GitHub! Gerne können Sie auch einen neuen Controller in einer anderen Sprache hinzufügen!
Klicken Sie auf den Namen der Sprache für jeden Controller, um das richtige Verzeichnis auf GitHub aufzurufen, das eine README.md
mit genauen Verwendungsanweisungen enthält .
Wenn Sie nicht mit Git und / oder GitHub vertraut sind, können Sie das gesamte Repository als ZIP von der Startseite herunterladen (siehe Schaltfläche in der Seitenleiste).
Python
- Am gründlichsten getestet. Dies ist unsere Referenzimplementierung.
- Funktioniert sowohl mit Python 2.6+ als auch mit Python 3.2+!
- Es ist sehr langsam. Wir empfehlen, es mit PyPy auszuführen, um eine erhebliche Beschleunigung zu erzielen.
- Unterstützt die grafische Ausgabe mit
pygame
odertkinter
.
Rubin
- Getestet mit Ruby 2.0.0. Sollte mit neueren Versionen funktionieren.
- Es ist auch ziemlich langsam, aber Ruby kann nützlich sein, um eine Idee für eine Einreichung zu erstellen.
C ++
- Benötigt C ++ 11.
- Unterstützt optional Multithreading.
- Mit Abstand der schnellste Controller im Haufen.
C #
- Verwendet LINQ, daher ist .NET 3.5 erforderlich.
- Eher langsam.
Java
- Nicht besonders langsam. Nicht besonders schnell.
Vorläufige Rangliste
Alle Ergebnisse sind vorläufig. Sollte dennoch etwas falsch oder veraltet sein, lassen Sie es mich bitte wissen. Unser Beispielbeitrag ist zum Vergleich aufgeführt, jedoch nicht in Konkurrenz.
Score | # Games | User | Language | Bot
===================================================================================
2914.13 | 2000 | kuroi neko | C++ | Hard Believers
1817.05097| 1000 | TheBestOne | Java | Running Star
1009.72 | 2000 | kuroi neko | C++ | Blind faith
782.18 | 2000 | MT0 | C++ | Cautious Specimens
428.38 | | user2487951 | Python | NeighborsOfNeighbors
145.35 | 2000 | Wouter ibens | C++ | Triple Score
133.2 | | Anton | C++ | StarPlayer
122.92 | | Dominik Müller | Python | SkyWalker
89.90 | | aschmack | C++ | LookAheadPlayer
74.7 | | bitpwner | C++ | ColorFarSeeker
70.98 | 2000 | Ceribia | C++ | WallGuesser
50.35 | | feersum | C++ | Run-Bonus Player
35.85 | | Zgarb | C++ | Pathfinder
(34.45) | 5000 | Martin Büttner | <all> | ColorScorePlayer
9.77 | | DenDenDo | C++ | SlowAndSteady
3.7 | | flawr | Java | IAmARobotPlayer
1.9 | | trichoplax | Python | Bishop
1.04 | 2000 | fluffy | C++ | Gray-Color Lookahead
Credits
Diese Herausforderung war eine enorme gemeinsame Anstrengung:
- Nathan Merril: Hat Python- und Java-Controller geschrieben. Verwandelte das Herausforderungskonzept von einem King-of-the-Hill in ein Rat Race.
- Trichoplax: Spieltest. Arbeitete auf Python-Controller.
- feersum: Schrieb C ++ Controller.
- VisualMelon: Schrieb C # -Controller.
- Martin Büttner: Konzept. Schrieb Ruby-Controller. Spieltesting. Arbeitete auf Python-Controller.
- T Abraham: Spieltesting. Python getestet und C # - und C ++ - Controller getestet.
Alle oben genannten Benutzer (und wahrscheinlich ein paar weitere, die ich vergessen habe) haben zum Gesamtdesign der Herausforderung beigetragen.
C ++ Controller Update
Wenn Sie C ++ mit Visual Studio und Multithreading verwenden, sollten Sie das neueste Update erhalten, da ein Fehler beim Seeding des Zufallszahlengenerators aufgetreten ist, durch den doppelte Boards erstellt werden können.
quelle
'In particular, a new specimen which spawns on a lethal cell will not die immediately, but has a chance to move off the dangerous cell first.'
Antworten:
Blindes Vertrauen - C ++ - scheint in 2000 Läufen über 800 (!) Zu liegen
Farbcodierungsgenom mit einem mysteriösen Track-Feedback und einer wirksamen Wall-Banging-Abwehr
Beispielergebnisse:
Basierend auf dem unfreiwillig langen Test von feersum denke ich, dass 2000 Durchläufe ausreichen, um ein akzeptabel stabiles Ergebnis zu erzielen.
Da mein modifizierter Controller nach jedem Lauf den aktuellen geometrischen Mittelwert anzeigt, habe ich visuell bestätigt, dass die Abweichung über die letzten 50 Läufe relativ gering war (+ - 10 Punkte).
Was bringt diese Tiere zum Ticken?
Anstatt jeder Farbe die gleichen Prioritäten zuzuweisen, berücksichtige ich die folgenden möglichen Werte:
Obwohl ich zu faul bin, es umzubenennen, ist dies eher ein "Gefahrenmelder", der den (vermeintlichen) Ort einer tatsächlichen Falle, einer Mauer, eines Teleporters anzeigt, der darauf wartet, den ahnungslosen Wanderer an einen unangenehmen Ort oder sogar den Eingang eines Toten zu schicken -Ende. Kurz gesagt, ein Ort, an den eine weise Ratte lieber nicht gehen würde.
Gute oder schlechte Gene benötigen zum Speichern nur 2 Bits (zum Beispiel
11
und10
), für Fallen sind jedoch 4 Bits erforderlich (0ttt
wobeittt
einer der möglichen 8 "gefährlichen" Speicherorte angegeben ist).Um jedes Gen konsistent zu halten (dh seine Bedeutung beizubehalten, nachdem es in ein völlig anderes Genom eingemischt wurde, was erfordert, dass sich jedes Farbcodierungsgen an einem festen Ort befindet), werden alle Werte mit 4 Bits codiert (so gut ist codiert wie
11xx
und so schlecht wie)10xx
) für insgesamt 16 * 4 = 64 Bit.Die restlichen 36 Bits werden als "Anti-Wall-Banger" verwendet (dazu später mehr). Die 25 umgebenden Farben werden in einen Index dieser 36 Bits gehasht. Jedes Bit gibt eine bevorzugte vertikale Richtung (aufwärts oder abwärts) an, die verwendet wird, wenn eine mögliche Wahl zwischen zwei Zellen besteht.
Die Strategie ist wie folgt:
Ihr Nagetiere, seht die Feinde eurer Art
Das Schlimmste, was einer Population passieren kann, ist, noch keinen Sieger hervorgebracht zu haben, aber viele Ratten stecken entweder an einer Wand oder in einer endlosen Teleportationsschleife, die nahe genug am Ziel ist, um eine dominante Chance zu haben, für die Zucht ausgewählt zu werden .
Im Gegensatz zu Ratten, die in einer Falle zerquetscht oder in Wände teleportiert werden, werden diese Nagetiere nur im Alter getötet.
Sie haben von Anfang an keinen Wettbewerbsvorteil gegenüber ihren Cousins, die 3 Zellen stecken, aber sie haben genügend Zeit, um Generation für Generation von Cretins zu züchten, bis ihr Genom dominant wird, wodurch die genetische Vielfalt ohne guten Grund stark beeinträchtigt wird.
Um dieses Phänomen abzumildern, besteht die Idee darin, die Nachkommen dieser bösen, bösen Ratten eher daran zu hindern, den Schritten ihrer Vorfahren zu folgen.
Die vertikale Richtungsanzeige ist nur 1 Bit lang (im Grunde genommen "zuerst in dieser Umgebung auf- oder absteigen"), und es ist wahrscheinlich, dass sich einige Bits auf den verfolgten Pfad auswirken. Daher sollten Mutationen und / oder Überkreuzungen a erhebliche Auswirkungen.
Viele Nachkommen werden sich anders verhalten und nicht mit dem Kopf gegen dieselbe Wand stoßen (zwischen den Leichen ihrer verhungerten Vorfahren).
Die Subtilität hier ist, dass diese Anzeige nicht der dominierende Faktor im Verhalten der Ratte ist. Die Farbinterpretation wird in den meisten Fällen immer noch vorherrschen (die Auswahl nach oben / unten ist nur dann von Bedeutung, wenn es tatsächlich zwei "gute" gibt.und was die Ratte als harmlose Farbe ansieht, ist kein Teleporter, der darauf wartet, sie in eine Wand zu werfen.
Warum scheint es zu funktionieren?
Ich weiß immer noch nicht genau warum.
Der absolute Glücksfall, der ein ungelöstes Rätsel bleibt, ist die Trap-Mapping-Logik. Es ist ohne Zweifel der Grundstein für den Erfolg, aber es funktioniert auf seine eigene mysteriöse Weise.
Mit der verwendeten Codierung erzeugt ein zufälliges Genom 25% "gute", 25% "schlechte" und 50% "gefangene" Farbidentifikatoren.
Die "Trap" -Identifikatoren erzeugen wiederum "gute" und "schlechte" Schätzungen in Korrelation mit der 5x5-Umgebung.
Infolgedessen "sieht" eine Ratte an einem bestimmten Ort die Welt als eine Mischung aus stabilen und kontextuellen "go / no go" -Farben.
Wie der recht erfolgreiche Anti-Banging-Mechanismus zu zeigen scheint, ist die gefürchtete Wand (und ihre Cousine die Teleportationsschleife) das schlimmste Element auf der Strecke, aber ich denke, diese sind weitaus weniger verbreitet.
Die Schlussfolgerung ist, dass ein erfolgreiches Programm es vor allem schaffen muss, Ratten zu entwickeln, die in der Lage sind, Positionen zu erkennen, die zu einem langsamen Hunger führen, ohne das Ziel zu erreichen.
Selbst ohne die beiden Farben zu "erraten", die Wände darstellen, scheinen die "Fallen" -Farben zur Vermeidung von Wänden beizutragen, indem eine Ratte einige Hindernisse umgehen kann, nicht weil sie die Wände "sah", sondern weil die "Fallen" -Schätzung diese ausschloss besondere Wandzellen in dieser besonderen Umgebung.
Obwohl die Ratte versucht, sich dem Ziel zu nähern (was dazu führen könnte, dass die "nützlichsten" Fallenindikatoren diejenigen sind, die auf eine Gefahr im Vordergrund hinweisen), denke ich, dass alle Fallenrichtungen ungefähr den gleichen Einfluss haben: eine Falle, die auf eine "Gefahr im Hintergrund" hinweist "2 Zellen vor einer Ratte gelegen" hat den gleichen Einfluss wie eine, die "Gefahr voraus" anzeigt, wenn die Ratte direkt darüber steht.
Warum diese Mischung die Eigenschaft hat, dass das Genom so erfolgreich konvergiert, kann ich leider nicht nachvollziehen.
Ich fühle mich wohler mit der wandschlagenden Abschreckung. Dies funktionierte wie geplant, jedoch weit über meinen Erwartungen (die Punktzahl wurde im Grunde mit vier multipliziert).
Ich habe den Controller stark gehackt, um einige Daten anzuzeigen. Hier sind ein paar Läufe:
Hier tauchte früh eine Rasse von Superratten auf (die Strecke durfte wahrscheinlich geradeaus verlaufen, und einige glückliche Ratten hatten in den ersten Generationen die richtige DNA, um davon zu profitieren). Die Anzahl der Exemplare am Ende ist ungefähr die Hälfte der theoretischen Höchstzahl von 100.000 Ratten, was bedeutet, dass fast die Hälfte der Tiere die Fähigkeit erlangt hat, diese bestimmte Spur auf unbestimmte Zeit (!) Zu überleben.
Natürlich ist die resultierende Punktzahl einfach obszön - wie übrigens auch die Rechenzeit.
Hier können wir die Genomverfeinerung bei der Arbeit sehen. Die Linie zwischen den letzten beiden Genomen ist klar erkennbar. Die guten und schlechten Bewertungen sind am wichtigsten. Die Fallenanzeigen scheinen zu oszillieren, bis sie sich entweder zu einer "nützlichen" Falle stabilisieren oder zu gut oder schlecht mutieren .
Es scheint, dass die Farbgene einige nützliche Eigenschaften haben:
(eine bestimmte Farbe muss auf eine bestimmte Weise behandelt werden).
Jede Farbkodierung kann in ein völlig anderes Genom geworfen werden, ohne das Verhalten dramatisch zu ändern - es sei denn, die Farbe ist tatsächlich (typischerweise) entscheidend eine Mauer oder ein Teleporter, der zu einer Endlosschleife führt).
Dies ist bei einer grundlegenden Prioritätskodierung weniger der Fall, da die Farbe mit der höchsten Priorität die einzige Information ist, die zur Entscheidung über den Verschiebungsort verwendet wird. Hier sind alle "guten" Farben gleich, so dass eine bestimmte Farbe, die der "guten" Liste hinzugefügt wird, weniger Auswirkungen hat.
Die gute / schlechte Kodierung hat nur 2 signifikante Bits von 4 und die Position der Falle kann die meiste Zeit geändert werden, ohne das Verhalten der Ratte signifikant zu verändern.
Ein zu "gut" mutierendes Gen hat entweder nur geringe Wirkung (wenn es beispielsweise einer leeren Zelle entspricht, kann es einen neuen, kürzeren Weg finden, aber das könnte auch die Ratte direkt hineinführen eine Falle) oder eine dramatische (wenn die Farbe eine Wand darstellt, bleibt die neue Ratte sehr wahrscheinlich irgendwo hängen).
Ein Gen, das sich in die "Falle" dreht, entzieht der Ratte entweder eine essentielle Farbe oder hat keine wahrnehmbare Wirkung.
Eine Mutation der Position einer Falle ist nur dann von Bedeutung, wenn tatsächlich eine Falle (oder etwas Schädliches) in Sicht ist, die mit relativ geringer Wahrscheinlichkeit (ich würde so etwas wie 1/3 sagen) vorliegt.
Schließlich schätze ich, dass die letzten 36 Bits nicht nur dazu beitragen, dass Ratten nicht hängen bleiben, sondern auch, dass Ratten gleichmäßiger auf der Strecke verteilt werden, wodurch die genetische Vielfalt erhalten bleibt, bis ein siegreiches Genom entsteht und durch den Farbcodierungsteil dominant wird.
Weitere Arbeit
Ich muss sagen, ich finde diese kleinen Lebewesen faszinierend.
Nochmals vielen Dank an alle Mitwirkenden dieser hervorragenden Herausforderung.
Ich denke darüber nach, den Controller weiter zu schlachten, um signifikantere Daten anzuzeigen, wie die Abstammung einer erfolgreichen Ratte.
Ich würde diese Ratten auch sehr gerne in Aktion sehen, aber dieses C ++ b ** ch einer Sprache macht das Erstellen - geschweige denn das Animieren - von Bildern (unter vielen anderen Dingen) zu einer chaotischen Aufgabe.
Am Ende möchte ich zumindest eine Erklärung des Fallensystems erstellen und möglicherweise verbessern.
Controller-Hacking
Wenn jemand interessiert ist, kann ich die Änderungen, die ich an der Steuerung vorgenommen habe, veröffentlichen.
Sie sind dreckig und billig, aber sie machen den Job.
Ich bin kein GitHub-Fan, also müsste das nur ein Beitrag sein.
quelle
^^v^vvv^^^vv^^v^vvv^v^^vvvv^^^^^^^^^
bedeuten Sie? Den Rest kann ich mir denken, aber ich habe Probleme damit?Harte Gläubige - C ++ - (verbesserte Teleporter): 10.000+ für 2000 Läufe
(Dies ist eine Entwicklung des blinden Glaubens . Vielleicht möchten Sie vor dieser eine weitere Textwand erklimmen.)
Folge IV: Wir orientieren uns an der Startaufstellung
Ergebnisse
Ich wechselte zu g ++ / MinGW und 3 Threads.
Der von GNU generierte Code ist mehr als doppelt so schnell wie der von Microsoft.
Kein Wunder, was mit ihrer entsetzlichen STL-Implementierung.
Teleporter
Der Teleporter-Effekt ist stark positionsabhängig. Bisher war ich froh, einen Teleporter als immer gut (als leeren Raum gesehen) oder immer schlecht (als Mauer gesehen, so dass kein Nagetier ihn jemals nehmen würde) zu betrachten.
Dies ist ein zu grobes Modell.
Ein gegebener Teleporter kann eine Ratte vorwärts treiben, bis einige Zellen vom Ziel entfernt sind, aber sobald er dort ist, kann derselbe Teleporter die Ratte vom Brett werfen.
Ein solcher Teleporter wird höchstwahrscheinlich als passabel eingestuft (da er die Fitness schneller erhöht als beim "Gehen" zu derselben x-Position), Teil des dominanten Genoms werden und fast alle Ratten töten, die ihm als "immer sicher" vertrauen.
Da die Ratten keine Möglichkeit haben, ihre X-Position zu kennen, besteht die einzige Lösung zum Erkennen dieser tückischen Teleporter darin, auf der Grundlage der einzigen verfügbaren Kontextdaten, dh des 5x5-Farbrasters, zu entscheiden, ob sie darauf treten sollen.
Dazu habe ich 4 Arten von Farbgenen definiert:
Die Idee ist, einen Teleporter anhand seiner unmittelbaren 8 Nachbarn zu unterscheiden. Da die Wahrscheinlichkeit, 8 identische Nachbarn an einem bestimmten Ort zu haben, sehr gering ist, sollte dies die Identifizierung einer eindeutigen Instanz jedes Teleporters ermöglichen.
Die 8 Nachbarfarben können zu einer lokalen Signatur kombiniert werden, die für die Position im Labyrinth unveränderlich ist. Leider sind die 8 Nachbarn nur für Zellen sichtbar, die sich im inneren Quadrat des 3x3-Sichtfelds befinden, sodass die Signaturen am Rand des Sichtfelds ungenau sind.
Dies gibt uns jedoch eine konstante kontextbezogene Information in der unmittelbaren Nachbarschaft, die ausreicht, um die Wahrscheinlichkeit zu erhöhen, dass Teleporter erfolgreich navigieren.
Beam- Gene haben ein variables Feld von 2 Bits.
Für eine gegebene lokale Signatur des Teleporters gibt es eine Chance von vier, dass die Strahlzelle als unpassierbar betrachtet wird. Jeder Wert des Feldes wählt eine dieser vier Möglichkeiten aus.
Infolgedessen durchläuft eine Strahlgenmutation auf diesen 2 Bits 4 mögliche kontextbezogene Bedeutungen der Farbe.
Außerdem sind die wichtigsten Farben, die zu erraten sind, noch Wände und Fallen. Das heißt, wir sollten die Erkennung von Teleportern erst zulassen, nachdem die Ratten erfahren haben, wo sich die Mauern und Fallen befinden.
Dies geschieht, indem die lokalen Signaturen nur sparringly aktualisiert werden. Das aktuelle Kriterium für die Aktualisierung einer lokalen Signatur muss in der Nähe einer Farbe liegen, die als potenzieller Teleporter identifiziert wurde.
Die Codierung verwendet 5 Bits pro Farbgen und Gruppentypen, um die 3 niederwertigen Bits für die Codierung eines 0..7-Werts freizugeben:
Jedes Strahlengen hat eine 1/4-Chance, als Block betrachtet zu werden, und eine 3/4-Chance, als leer betrachtet zu werden, sodass 4 Strahlen im Durchschnitt 1 Block und 3 leere Strahlen darstellen.
Der durchschnittliche Anteil, der durch eine zufällige Verteilung von 16 Farben dargestellt wird, ist somit:
Diese Mischung scheint die besten Ergebnisse zu liefern, aber ich bin noch nicht fertig damit, sie zu optimieren.
Genveränderlichkeit
Eines ist sicher: Die für die Darstellung der Gen-Typen gewählten Code-Werte sind kritisch. Das Invertieren zweier Werte kann 2000 Punkte oder mehr kosten.
Auch hier liegt der Grund außerhalb meiner Mathematik.
Ich vermute, dass die Mutationswahrscheinlichkeiten von einem Typ zu einem anderen ausgeglichen sein müssen, da die kumulativen Wahrscheinlichkeiten, wie in einer Markow-Matrix, dazu neigen, die Werte auf die Teilmenge mit den höchsten eingehenden Übergangswahrscheinlichkeiten zu beschränken.
Weg zur Rettung
Durch das Pathing wird die Anzahl der besuchten Zellen drastisch reduziert, sodass nur die Zellen getestet werden können, die am wahrscheinlichsten zum Ziel führen. So werden nicht nur häufige Sackgassen vermieden, sondern falsche Farbcodes werden auch viel häufiger früher entdeckt.
Infolgedessen wird die Konvergenzzeit stark verringert.
Dies hilft jedoch nicht beim Lösen der Karten, bei denen das Genom keine ordnungsgemäße Darstellung der Spur erzeugen kann.
Was tun mit Idioten?
Nachdem ich mir die Strecke visuell angeschaut hatte, verstand ich, warum eine Standardstrategie, die versucht, voranzukommen, auch wenn scheinbar nur Mauern davor sind, in der Tat besser ist als Zurückhalten.
"Mauern" können in Wirklichkeit Teleporter sein, die so viele unglückliche Ergebnisse liefern, dass das Genom sie als Hindernisse ansieht, auf die man niemals treten kann, aber in seltenen Fällen kann eine bestimmte Instanz dieses ungezogenen Teleporters einen positiven (oder zumindest nicht tödlichen) Effekt haben Wenn Sie es nehmen, anstatt sich zurückzuziehen, erhöhen Sie die Chancen, einen Weg zum Sieg zu finden.
Frühe Konvergenz
Mir scheint, die Mutationsrate ist ein bisschen zu niedrig (zumindest für meine Nagetiere).
Die aktuelle Einstellung von 0,01 gibt einer DNA eine Chance von 37%, den Mutationsprozess intakt zu überleben. Durch Ändern des Parameters auf 0,0227 wird diese Wahrscheinlichkeit auf etwa 10% gesenkt.
Ich habe den exakt gleichen Test (mit einer festgelegten Folge von Zufallssamen) mit einer Wahrscheinlichkeit von 10% wiederholt.
Auf vielen Karten wurden aus den vorherigen Fehlern (begrenzte) Erfolge. Andererseits waren enorme Bevölkerungsexplosionen geringer (was den interessanten Nebeneffekt hatte, die Berechnung erheblich zu beschleunigen).
Obwohl die sehr hohen Punktzahlen (über eine Million) seltener vorkamen, war die Anzahl der erfolgreicheren Läufe mehr als ausreichend, um dies auszugleichen.
Am Ende stieg der Mittelwert von 1400+ auf etwa 2000.
Die Einstellung von P auf 5%
ergab dagegen einen Mittelwert von etwa 600. Ich gehe davon aus, dass die Mutationsrate so hoch war, dass sich das Genom der siegreichen Ratten zu oft in weniger effiziente Varianten verwandelte.
Wie funktioniert das?
Mit den hinzugefügten Teleporterdetektoren sank die Anzahl der fehlgeschlagenen Spiele (Punktzahl <10) erheblich.
Bei einem Test mit 2000 Durchläufen gab es nur 1/3 der Fehler.
Das geometrische Mittel stieg nur von 2900 auf 3300, aber diese Zahl spiegelt die Verbesserung nicht wider.
Leere Farben werden häufig als Strahlen und Gefahren erraten (normalerweise 2 bis 5). Das Genom "benutzt" diese Farben, um Wege zu blockieren, die Ratten in Schwierigkeiten bringen würden.
Das Genom ist ziemlich gut darin, Fallen zu erraten (dh wenn Ratten das Ziel erreicht haben, werden in etwa 90% der Fälle Farben erraten, die tatsächliche Fallendetektoren darstellen).
Es werden auch die neuen Strahlencodes für Teleporter verwendet, wenn auch seltener (wahrscheinlich, weil die "tückischen" Teleporter weniger verbreitet sind als Fallen, und andere Strahlen- / Gefahrenfarben entwickeln sich, um den Weg zu den letzten Instanzen dieser Verräter zu blockieren).
Gemessen an der Anzahl der Spiele, bei denen nach 5000 Umdrehungen oder mehr ein Siegergenom entsteht, würde diese neue Rasse meiner Meinung nach erheblich von einer erhöhten Mutationsrate profitieren.
quelle
ColorScorePlayer, vorläufiges Ergebnis ≈ 22
Dies ist der Bot, den Sie in der Herausforderung im GIF sehen.
Dies war unser Testbot während der gesamten Entwicklungsphase. Es verwendet das Genom, um einen Qualitätsfaktor für jede der 16 Farben zu speichern. Dann macht er den Vorwärtszug, der ihn auf die Farbe mit der besten Punktzahl bewegt (und nie weitergeht
-1
). Bei einem Gleichstand wird eine zufällige Bewegung zwischen den verbundenen Zellen ausgewählt.Wir haben diesen Player in alle Controller-Sprachen portiert, sodass er als Beispiel für die Verwendung dient:
Python
Rubin
C ++
C #
Java
Der Spieler punktet ziemlich uneinheitlich. Hier sind 50 Zufallsläufe:
quelle
ColorFarSeeker, C ++ ≈ 74.7
Diese Herausforderung macht wirklich Spaß und ist einfach, wenn Sie es versuchen.
Lassen Sie sich von der langen Beschreibung nicht abschrecken.
Besuchen Sie einfach den GitHub und probieren Sie es aus ... alles wird viel klarer! :)
Der C ++ - Simulator wird aufgrund seiner Geschwindigkeit dringend empfohlen. Auch nachdem ich mein Python-Programm in C ++ übersetzt habe, ist die Python-Simulation noch nicht beendet.
Dies ist eine verbesserte Variante des ColorScorePlayer. Um die 5x5-Ansicht optimal zu nutzen, werden mithilfe einer gewichteten Funktion Schritte in 2 Schritten berücksichtigt. Wenn Sie 1 Schritt voraus gehen, erhalten Sie ein höheres Gewicht, da dies eine unmittelbarere Auswirkung auf das Überleben hat. Bewegen Sie sich 2 Schritte vor Ihnen, erhalten Sie ein geringeres Gewicht.
Versucht sich vorwärts zu bewegen, aber wenn kein sicherer Zug zu sehen ist ... dann versucht es seitwärts ... und wenn alles andere fehlschlägt, bewegt es sich nach dem Zufallsprinzip rückwärts.
Ergebnis:
Es gibt ziemlich viele Einsen ... was ein bisschen deprimierend sein kann, wenn Sie sehen, wie die Konsole eine nach der anderen ausspuckt. Wie ein Planet mit allen Notwendigkeiten für das Leben, aber ohne Anzeichen fortgeschrittener Rattenzivilisationen ...
Dann die gelegentliche Spitze. :)
Hmm ... anscheinend hatte ich Glück für meine erste Serie von Läufen mit einem geometrischen Wert von 300+. Die Punktzahlen schwanken sehr stark. Aber mit mehr Simulatorläufen ist es wahrscheinlich näher an closer 74. (Danke, dass Sie mir beim Simulieren geholfen haben und sein superschnelles Programm)
quelle
Bischof - Python, vorläufige Punktzahl 1.901
Der Bischof bewegt sich immer diagonal, so dass die Hälfte des Brettes auf einer bestimmten Wanderung nicht zugänglich ist. Dies bedeutet jedoch, dass weniger potenzielle Züge codiert werden müssen, sodass jedes einzelne Genomstück einen Zug darstellen kann (der Bischof zieht sich niemals zurück). Welches Bit referenziert werden soll, wird anhand des 3x3-Rechteckblocks vor (rechts) der Probe entschieden. Der beste Zug für eine bestimmte Situation ist immer nur eine Bit-Mutation entfernt.
Dieser Bot lernt zuerst schnell, trifft dann aber häufig eine Decke, bevor er das Ziel erreicht, vermutlich dort, wo eines der folgenden zwei Probleme auftritt:
Code
Trotz dieser Einschränkungen gelingt es dem Bischof in seltenen Fällen gut, wenn einzelne Exemplare jeweils mehrere Runden auf dem Brett absolvieren. Ich hatte gedacht, dass sich ein Exemplar in einer bestimmten Runde nur auf der Hälfte des Bretts bewegen kann (das entspricht nur den schwarzen Quadraten oder nur den weißen Quadraten auf einem Schachbrett). Wie Martin Büttner jedoch betonte, kann ein Teleporter eine Probe von einem schwarzen Quadrat zu einem weißen Quadrat oder umgekehrt bewegen, so dass sie auf den meisten Brettern nicht eingeschränkt werden.
(Es gibt zwei Paare übereinstimmender Teleportertypen und jeder hat eine Wahrscheinlichkeit von 0,5, dass ein Versatz eine Probe in die andere Hälfte des schwarzen und weißen Quadrats verschiebt. Die Wahrscheinlichkeit also, dass eine Tafel nur Teleporter hat, die die Probe auf einen beschränken Die Hälfte des Boards pro Runde beträgt nur 0,25.)
Die Punktzahlen zeigen, dass die gelegentlichen Siege mit langen Phasen des Unterschreitens des Ziels durchsetzt sind:
quelle
Run-Bonus-Spieler: Geometrischer Mittelwert 50,35 (5000-Game-Test)
Dieser Bot bewertet Quadrate anhand ihrer individuellen Farben, basierend auf einem 6-Bit-DNA-Abschnitt wie der Color-Score-Player, jedoch mit einem anderen Zahlensystem. Dieser Bot wurde durch den Gedanken motiviert, dass es ziemlich willkürlich ist, dass eines der Bits den Wert der Punktzahl um 32 ändert, während ein anderes dies nur um 1 tut. Es weist einem Durchlauf von n (n + 1) / 2 den Wert von zu n aufeinanderfolgende 1 Bits. Zusätzlich wird ein Zufallsmechanismus hinzugefügt, um ein Festklemmen zu vermeiden. Es wird ein zufälliger Vorwärtszug mit einer Chance von 1 zu 30 ausgeführt.
Zum Vergleich erzielte der Farb-Score-Spieler in ein paar 1000-Game-Tests 30 bis 35 Punkte. Interessanterweise lag die maximale Spielpunktzahl des Farbspielers im Bereich von 3 bis 5 Millionen, während der maximale Laufbonus nur 200.000 betrug. Der Run-Bonus profitiert vom logarithmischen Durchschnittswertungssystem, indem er eine Punktzahl ungleich Null erhält, die einheitlicher ist.
Das Ausführen von 5000 Spielen dauerte ungefähr 20 Minuten mit 6 Threads auf dem C ++ - Controller.
quelle
StarPlayer | C ++ | Punktzahl: 162 (basierend auf 500 Spieldurchläufen)
Dieser Spieler versucht mit A * den besten Weg nach vorne zu finden. Es weist Gewichte wie ColorScorePlayer zu und versucht, den Weg zum rechten Rand der Ansicht zu finden. Die Implementierung ist nicht die schönste, die ich je gemacht habe, aber zumindest nicht zu langsam.
Musterpartituren:
quelle
WallGuesser - Erzielte 113.266 Punkte in einem 1000-Spiele-Test
Codierung
Ich habe eine wirklich einfache 6-Bit / Farb-Codierung gemacht. Farbe dekodieren [n]
Indem ich die Bits für eine Farbe im gesamten Genom verteile, erhöhe ich die Wahrscheinlichkeit, dass Bits von beiden Elternteilen für jede Farbe verwendet werden.
Bewegung
Ich benutze eine A * -basierte Suche (ich bin mir sicher nicht sehr effizient), um nach dem kostengünstigsten Pfad zu einem der Quadrate am rechten Rand zu suchen. Wenn eine Farbe "gesperrt" ist, wird sie bei der Suche niemals eingegeben. Wenn die Suche keinen Pfad findet, nimmt sie an, dass diese Ratte nicht reproduzierbar ist, und versucht, ihn zu beenden, indem sie einen nach links bewegt.
Reduzierung der Anzahl nicht tauglicher Ratten
Da mein Genom effektiv errät, welche Quadrate Wand- oder Rückwärtsteleporter sind, sind Ratten, die keine Vermutungen haben (keine Farben, die blockiert werden sollen), nicht sehr fit. Um zu versuchen, diese Ratten zu entfernen, wenn keine Farbe als blockiert markiert wird, wird JEDE Farbe als blockiert markiert und die Ratte bewegt sich immer eine nach links.
MACHEN
Derzeit gibt es keine Zufälligkeit im Verhalten, so dass es für Ratten leicht ist, stecken zu bleiben.
quelle
g++ -std=c++11 .\wallguesser.cpp -O2 -o .\wallguesser.exe
. Ich bekomme viele Fehler, aber der erste ist.\wallguesser.cpp:47:19: error: 'dna_t' has no member named 'at' if (d.at(i) == true){
at
um[]
es zu beheben .Die FITTEST - Geometric Mean Score: ~ 922 (2K läuft)
Mein Ansatz ist:
Ich habe über 2000 Parametersätze mit denselben 50 Samen getestet. Die vielversprechendsten Sets wurden ausgewählt und mit 250 identischen Samen bewertet. Diejenigen mit dem höchsten Rang waren der Input für die nächste Testrunde. Also habe ich es geschafft , einen genetischen Algorithmus zu erstellen, um den optimalen genetischen Algorithmus für dieses Problem zu finden, wie vom Benutzer mbomb007 vorgeschlagen .
Das gewünschte Verhalten:
Datenspeichermethoden:
Wir möchten, dass die Spezies Dinge lernt, sich an ihre Umgebung anpasst und die Stärksten werden. Dies funktioniert zwangsläufig nur, wenn das Lernen irgendwie gespeichert werden kann. Das Lernen wird in den 100 DNA-Bits 'gespeichert'. Es ist eine seltsame Art zu speichern, weil wir den Wert unserer DNA nicht ändern können. Wir gehen also davon aus, dass die DNA bereits Informationen über schlechte und gute Züge speichert. Wenn für eine bestimmte Art die richtigen Informationen in ihrer DNA gespeichert sind, bewegt er sich schnell vorwärts und erzeugt mit ihrer DNA viele neue Arten.
Ich fand heraus, dass der geometrische Mittelwert von der Speicherung der Informationen abhängt. Nehmen wir an, wir lesen die ersten 4 Bits der 100 Bits der DNA und möchten diese in einer ganzzahligen Variablen speichern. Wir können dies auf verschiedene Arten tun:
dnarange
Funktion "Eingebaut1011
" Beispiel: Aus 4 Bit wird 1x2 ^ 3 + 0x2 ^ 2 + 1x2 ^ 1 + 1x2 ^ 0 = 15. Mögliche Werte (für 4 Bits): [0, 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]dnaStreakRange
Funktion (unten definiert), Beispiel: 4Bits 1011 werden1x1 + 0x1 + 1x1+ 1x2 = 4
. Mögliche Werte (für 4 Bits): [0, 1, 2, 3, 6, 10]dnaCountRange
Funktion (unten definiert), Beispiel: 4 Bit 1011 werden1x1 + 0x1 + 1x1 + 1x1 = 3
. Mögliche Werte (für 4 Bits): [0, 1, 2, 3, 4]Unterschiede zwischen den Speichermethoden sind:
Priorisieren Sie Lösungen.
Wenn der ColorScorePlayer zwei Vorwärtsbewegungen mit identischen Ergebnissen identifiziert hat, wird eine willkürliche Auswahl getroffen. IMHO sollten Sie niemals die Zufallsfunktion
v.rng.rint()
verwenden . Stattdessen sollten Sie diese Gelegenheit der gleichen Punktzahl als Haken verwenden, um Lösungen für Effekte zweiter Ordnung zu bewerten.Der Effekt erster Ordnung hat die höchste Priorität. Wenn gleiche Werte erreicht werden, hat die Lösung mit der Priorität 2 Vorrang und so weiter. Durch Ändern der Parameter einer Lösung können Sie die Wahrscheinlichkeit des Auftretens gleicher Ergebnisse beeinflussen und auf diese Weise die Gewichtung der Lösungen mit Priorität 1 und 2 ändern.
Umsetzung des gewünschten Verhaltens
Erfahren Sie, welche Farben sicher sind:
threshold = 63/3=21
ist 63 die maximale Punktzahl für 6 Bits und 33% = 1/3 (kann in der obigen Grafik nachgeschlagen werden).Wenn keine guten Züge verfügbar sind, gehen Sie vertikal oder rückwärts:
weightMove
Variable erreicht.Schauen Sie, was dahinter steckt:
x2
undy2
Schleifen), welche Option (über diemainSubScore
Variable) die beste ist . Die am weitesten rechts stehende Spalte in dieser 3x3-Box führt.Fallen identifizieren:
Ich habe die DNA der Spezies mit der höchsten Punktzahl untersucht, als ein beliebiges Spiel unter Verwendung des Speichers a bitsum4 endete (also hat die Farbpunktzahl einen Bereich von [0,4]):
Daraus kann geschlossen werden, dass Mauern und Teleports eine korrekte Punktzahl erhalten. Fallen werden nicht identifiziert, da sie von der Richtung und der Farbe des Ursprungs abhängen, während die Bewertung nach der Farbe des Ziels erfolgt. Es besteht daher ein Bedarf, auch Daten zur Ursprungsfarbe zu speichern, so
v(0,0)
. In einer idealen Welt möchten wir Informationen für 16 Farben x 8 Richtungen x 3 Bits = 384 Bits speichern.Leider sind nur 100 Bit verfügbar, und wir können nicht alle verwenden, da wir für die oben erläuterte Lösung auch etwas Speicher benötigen. Deshalb werden wir 4 Farbbehälter herstellen:
und 4 Bewegungsrichtungsfächer
Wenn die Dezimalpunktzahl 4 oder höher ist (100, 101, 110, 111), wird davon ausgegangen, dass dieser Zelle eine Falle zugeordnet ist. Infolgedessen wird dieser Zug nicht ausgewählt, wenn gleiche Punktzahlen auftreten. Die Identifizierung von Fallen ist also ein Effekt zweiter Ordnung, und das "Sehen, was dahinter steckt" wird eine Lösung mit dritter Priorität sein.
Falsche Vermutungen über die Mauer werden von Trotteln oft in Neugeborene dupliziert:
Einige Arten nehmen fälschlicherweise an, dass Wände gut sind und versuchen, sich ständig zu ihnen zu bewegen, und bleiben deshalb vor Wänden stecken. Sie können auch in Endlosschleifen von Teleportern stecken bleiben. Der Effekt ist in beiden Fällen der gleiche.
Das Hauptproblem ist, dass nach einigen hundert Iterationen einige Gene sehr dominant werden . Wenn dies die „richtigen“ Gene sind, können Sie sehr hohe Punktzahlen erzielen (> 1 Million Punkte). Wenn diese falsch sind, stecken Sie fest, da Sie die Vielfalt brauchen, um die "richtigen" Gene zu finden.
Idioten kämpfen: Lösung 1: Farbumkehr
Die erste Lösung, die ich ausprobiert habe, bestand darin, einen Teil des ungenutzten Speichers zu nutzen, der immer noch sehr vielfältig ist. Nehmen wir an, Sie haben Ihrem Farbspeicher und dem Trap Finding Memory 84 Bit zugewiesen. Die verbleibenden 16 Bits werden sehr unterschiedlich sein. Wir können 2 dezimale 8 Variablen mit Werten im Intervall [0,255] füllen und sie sind homogen, was bedeutet, dass jeder Wert eine Chance von 1/256 hat. Die Variablen werden genannt
inInverse
undinReverse
.Wenn
inInverse
255 ist (eine Chance von 1/256), kehren wir die Interpretation der Farbwerte um . Die Mauer, von der der Trottel annimmt, dass sie sicher ist, wird eine hohe Punktzahl, eine niedrige Punktzahl und wird daher zu einem schlechten Zug. Der Nachteil ist, dass dies auch die 'Rechte'-Gene beeinflusst, so dass wir weniger sehr hohe Punktzahlen haben werden. Darüber hinaus muss sich dieseinInverse
Art vermehren und ihre Kinder erhalten auch Teile der dominanten DNA. Das Wichtigste ist, dass es die Vielfalt zurückbringt.Wenn
inReverse
255 entspricht (eine Chance von 1/256), kehren wir die Reihenfolge der Speicherpositionen der Farbwerte um . Also bevor die Farbe 0 in den Bits 0-3 gespeichert wurde. Jetzt wird Farbe 15 in dieser Position gespeichert. Der Unterschied zuminInverse
Ansatz besteht darin, dass derinReverse
Wille die bisher geleistete Arbeit rückgängig macht. Wir sind wieder am ersten Platz. Wir haben eine Spezies geschaffen, die ähnliche Gene wie zu Beginn des Spiels hat (außer, dass die Falle das Gedächtnis findet).Durch die Optimierung wird geprüft, ob es sinnvoll ist, die
inInverse
undinReverse
gleichzeitig zu verwenden. Nach der Optimierung wurde festgestellt, dass der Score nicht erhöht wurde. Das Problem ist, dass wir eine vielfältigere Genpopulation haben, dies wirkt sich jedoch auch auf die „richtige DNA“ aus. Wir brauchen eine andere Lösung.Morons Fighting: Lösung 2: Hash-Code
Die Art hat 15 mögliche Startpositionen und derzeit besteht eine zu große Chance, dass er genau den gleichen Weg einschlägt, wenn er an derselben Startposition startet. Wenn er ein Idiot ist, der Wände liebt, wird er immer wieder an derselben Wand hängen bleiben. Wenn er es glücklicherweise geschafft hat, eine weit vor ihm liegende Mauer zu erreichen, wird er mit seinen falschen Annahmen beginnen, den DNA-Pool zu dominieren. Was wir brauchen, ist, dass sein Nachwuchs einen etwas anderen Weg einschlägt (für ihn ist es sowieso zu spät) und nicht an der Wand weit vorne hängen bleibt, sondern an einer Wand in der Nähe . Dies kann durch die Einführung eines Hashcodes erreicht werden .
Ein Hashcode sollte den Zweck haben, die aktuelle Position auf dem Board eindeutig zu identifizieren und zu kennzeichnen . Der Zweck ist nicht herauszufinden, wie die (x, y) Position ist, sondern die Fragen zu beantworten, die meine Vorfahren zuvor an diesem Ort gestellt haben.
Nehmen wir an, Sie hätten das komplette Board vor sich und würden ein JPG von jeder 5 x 5-Zelle möglich machen. Am Ende erhalten Sie (53-5) x (15-5) = 380 Bilder. Geben wir diesen Bildern Nummern von 1 bis 380. Unser Hashcode sollte als solche ID angesehen werden, mit dem Unterschied, dass er nicht von 1 bis 330 läuft, sondern fehlende IDS hat, z. B. 563, 3424, 9424, 21245 usw.
Die Primzahlen
17
und31
sind dort, um zu verhindern, dass die am Anfang der Schleife hinzugefügten Informationen verschwinden. Später erfahren Sie mehr darüber, wie Sie unseren Hashcode in den Rest des Programms integrieren können.Ersetzen wir den Subscoring-Mechanismus "Look What's Beyond" durch einen anderen Subscoring-Mechanismus. Wenn zwei oder drei Zellen die gleichen Hauptpunkte haben, besteht eine 50% ige Chance, dass die oberste Zelle ausgewählt wird, eine 50% ige Chance, dass die unterste Zelle ausgewählt wird und eine 0% ige Chance, dass die mittlere Zelle ausgewählt wird. Die Chance wird nicht durch den Zufallsgenerator bestimmt, sondern durch Bits aus dem Speicher , da auf diese Weise sichergestellt wird, dass in der gleichen Situation die gleiche Auswahl getroffen wird.
In einer idealen Welt (in der wir unendlich viel Speicher haben) würden wir einen eindeutigen Hashcode für unsere aktuelle Situation berechnen , z. B. 25881, und zum Speicherort 25881 gehen und dort lesen, ob wir die obere oder untere Zelle auswählen sollten (wenn vorhanden) ist eine gleiche Punktzahl). Auf diese Weise wären wir in genau der gleichen Situation (wenn wir z. B. zum zweiten Mal über das Brett fahren und an der gleichen Position beginnen) und treffen die gleichen Entscheidungen. Da wir keinen unendlichen Speicher haben, wenden wir ein Modulo der Größe des verfügbaren Speichers auf den Hashcode an . Der aktuelle Hashcode ist in dem Sinne gut, dass die Verteilung nach der Modulo-Operation homogen ist.
Wenn der Nachwuchs das gleiche Board mit leicht veränderter DNA reist, trifft er in den meisten Fällen (> 99%) genau die gleiche Entscheidung. Aber je weiter er kommt, desto größer wird die Chance, dass sein Weg sich von seinen Vorfahren unterscheidet. Die Chance, dass er an dieser Wand hängen bleibt, ist also gering. Während er mit seinem Vorfahren an der gleichen Wand hängen bleibt, ist er relativ groß, aber das ist nicht so schlimm, da er nicht viel Nachwuchs zeugt. Ohne den Hashcode-Ansatz ist die Wahrscheinlichkeit, an der nahen und der entfernten Wand hängen zu bleiben, nahezu gleich
Optimierung
Nach der Optimierung wurde festgestellt, dass die Trap-Identifikationstabelle nicht benötigt wird und 2 Bit pro Farbe ausreichen. Der Rest des Speichers 100-2x16 = 68 Bits wird zum Speichern des Hash-Codes verwendet. Es scheint, dass der Hash-Code-Mechanismus in der Lage ist, Fallen zu vermeiden.
Ich habe für 15 Parameter optimiert. Dieser Code enthielt den besten Satz optimierter Parameter (bis jetzt):
Dies ist mein erstes C ++ - Programm. Ich habe, wie die meisten von euch, Hintergrundwissen in der Gnomenanalyse. Ich möchte mich bei den Organisatoren bedanken, da es mir wirklich Spaß gemacht hat, daran zu arbeiten.
Wenn Sie Feedback haben, hinterlassen Sie bitte unten einen Kommentar. Entschuldigung für die langen Texte.
quelle
Pathfinder, C ++, vorläufiges Ergebnis 35.8504 (50 Runden)
Eine komplette Überholung! Ich habe meinen Algorithmus auf C ++ portiert und ein wenig optimiert, aber die Punktzahl ist immer noch nicht sehr hoch, wahrscheinlich, weil die Ratten ihre Köpfe immer wieder gegen Wände schlagen. Ich bin es leid zu versuchen, dies zu verbessern, also lasse ich es einfach für den Moment sein.
Erläuterung
Die allgemeine Idee ist, jede Farbe als eine Falle oder nicht zu klassifizieren, dann Richtungen zu Fallen und Gewichte zu Nicht-Fallen zuzuweisen und zu versuchen, dem Pfad mit minimalem Gewicht zum rechten Rand des Sichtgitters zu folgen.
In den ersten 80 Bits des Genoms wird jede Farbe mit 5 Bits klassifiziert
abcde
. Wennab = 01
, ist die Farbe eine Falle undcde
codiert ihre Richtung (acht Möglichkeiten). Wennab ≠ 01
, die Farbe ist nicht eine Falle, und sein Gewicht ista + b + 2*(c + d + e)
.Als nächstes initialisieren wir ein 3x7-Gitter, das das Sichtfeld der Ratte auf der rechten Seite darstellt und mit "unbekannten" Farben aufgefüllt ist. Die Bits 80-84 codieren das Gewicht der unbekannten Zellen ähnlich wie die Nicht-Trap-Farben, und die Bits 85-89 codieren ein gemeinsames Gewicht für die Traps. Wir füllen das Gitter mit den Gewichten, berechnen die kürzesten Pfade und fügen den Zellen direkt über und unter der Ratte ein zusätzliches Gewicht (in den Bits 90-95 codiert) hinzu, um ein Ausweichen zu verhindern. Die Bits 95-99 codieren ein Zielgewicht. Wenn das Mindestgewicht eines Pfades darunter liegt, steckt die Ratte wahrscheinlich irgendwo fest und bewegt sich nach dem Zufallsprinzip (aber nie rückwärts). Andernfalls folgt er dem Pfad mit dem Mindestgewicht. Mit einer geringen Wahrscheinlichkeit, die von dem das Ausweichen verhindernden Gewicht abhängt, wählt die Ratte stattdessen den Weg des zweiten bis minimalen Gewichts. Dies soll verhindern, dass Sie an Wänden hängen bleiben (aber es scheint momentan nicht sehr gut zu funktionieren).
quelle
LookAheadPlayer C ++ .90 89.904
Mein ursprünglicher Gedanke war, nach 4 Bits zu suchen, die der gesuchten Farbe entsprechen, und die folgenden wenigen Bits als Punktzahl zu verwenden. Dies stellte sich als schreckliche Idee heraus, wahrscheinlich aufgrund von Mutationen.
Ich dachte über Möglichkeiten zum Schutz vor Mutationen und Überkreuzungen nach und erinnerte mich an die Arbeit, die ich an der Entschlüsselung von QR-Codes geleistet habe. In QR-Codes werden die Daten in Blöcke aufgeteilt und gestreift, um zu vermeiden, dass Fehler zu viel von einem bestimmten Teil der Daten zerstören.
Daher schneide ich wie der ColorScorePlayer die DNA in 16 Stücke und verwende diese als gegebene Punktzahl. Die Punkte sind jedoch gestreift, so dass die einzelnen Bits jedes Punktes nicht benachbart sind. Ich summiere dann die Punktzahl der aktuell möglichen Züge und der nächsten möglichen Züge und wähle den besten Zug aus.
Hinweis: Dies wurde auf MinGW codiert / getestet. Es würde nicht mit Optimierungen oder mit Multithreading kompilieren. Ich habe weder eine aktuelle Linux-Installation noch Visual Studio zur Hand, um einen Compiler zu verwenden, auf dem diese funktionieren. Ich werde es morgen früh schnell testen, aber lass es mich wissen, wenn du auf irgendwelche Probleme stößt.
quelle
SlowAndSteady C ++ (9,7 Punkte)
Wir können uns nicht darauf verlassen, Teile des Genoms als Zahlen zu interpretieren, da ein einzelner Bit-Flip abhängig von seiner Position radikal unterschiedliche Auswirkungen haben kann. Deshalb benutze ich einfach 16 6-Bit-Segmente und bewerte sie nach der Anzahl von
1
s. Anfänglich111111
war es gut und000000
war es schlecht, und während es auf lange Sicht (sobald das Genom vollständig entwickelt ist) in der Anfangskonfiguration der DNA keine Rolle spielt, haben die meisten Segmente 2-4, also wechselte ich zum9 - (#1 - 3)^2
Scoring ermöglicht viel mehr Bewegungsfreiheit in den ersten Runden und eine schnellere Evolution.Im Moment schaue ich nur die 7 nächsten Nachbarn an, füge der Farbbewertung eine Richtungskorrektur hinzu und bewege mich nach dem Zufallsprinzip in eine der höchsten Richtungen.
Obwohl die Punktzahl selbst nicht sehr hoch ist, erreichen meine Tiere die Ziellinie und erreichen in 3/4 der Fälle eine Punktzahl von> 1.
Und eine Probe auf 100 Brettern
Geometrischer Mittelwert: 9.76557
quelle
WeightChooser | C # | Scores: 220.8262 in 1520 Spielen
Berechnet das Gewicht für den möglichen nächsten Zug (blau) basierend auf dem Durchschnittsgewicht der möglichen verfolgten Züge (gelb)
quelle
RATS IN ACTION (keine Antwort, sondern ein grafisches Tool für C ++ - Bots)
Seit Beginn dieser Herausforderung hatte ich Schwierigkeiten herauszufinden, was die Ratten wirklich auf der Strecke zu suchen hatten.
Am Ende habe ich den Controller gehackt und ein Side-Tool geschrieben, um eine grafische Darstellung einer Spur zu erhalten.
Schließlich habe ich noch ein bisschen gehackt und eine Visualisierung der möglichen Pfade der DNA einer bestimmten Ratte hinzugefügt.
Die Karte ist sehr unübersichtlich und gewöhnungsbedürftig, aber ich fand es sehr hilfreich zu verstehen, wie meine Bots funktionierten.
Hier ist ein Beispiel:
Sie müssen wahrscheinlich zoomen, um etwas zu sehen. Hier ist nur die erste Hälfte:
Schauen wir uns zunächst die Wege der Ratte an. Für jeden möglichen Startort gibt es einen Pfad (normalerweise 15, manchmal etwas weniger). Normalerweise verschmelzen sie und führen im Idealfall zu einem einzigen Siegesort.
Die Pfade werden durch große gerade Pfeile dargestellt. Die Farbe beschreibt das Ergebnis:
In diesem Beispiel haben wir 12 gewinnende Startpositionen, eine führt zu einer Endlosschleife und zwei zu einem grausamen Tod (wie es scheint wird in eine Falle teleportiert).
Die Pfaddiskontinuitäten sind auf Teleportationen zurückzuführen, die Sie mit den entsprechenden gekrümmten Pfeilen verfolgen können.
Nun zu den farbigen Symbolen. Sie repräsentieren die Bedeutung der 16 Farben (die grauen repräsentieren, was eine Ratte sieht).
leere Farben sind ... na ja ... leer.
Teleporter haben ausgehende Pfeile, die auf ihr Ziel zeigen.
Fallendetektoren haben auch Pfeile, die auf die Falle hinweisen, die als roter Kreis dargestellt ist.
In einem von 9 Fällen befindet sich die Falle in derselben Zelle wie ihr Detektor. In diesem Fall sehen Sie das kleine Oktogon über dem roten Kreis.
Dies ist in diesem Beispiel für die hellgelbe Falle der Fall.
Sie können auch die lila Fallenmelder sehen, die auf die angegebene Falle zeigen.
Beachten Sie, dass der rote Kreis einer Falle manchmal unter einer Wand versteckt ist. Beide sind tödlich, daher ist das Ergebnis bei der Teleportation dasselbe.
Beachten Sie auch, dass sich möglicherweise eine Falle auf einem Teleporter befindet. In diesem Fall hat der Teleporter Vorrang (dh die Ratte wird teleportiert, bevor sie in die Falle fällt, wodurch die Falle neutralisiert wird).
Schließlich stellen die grauen Symbole dar, was meine Ratten sehen (dh die Bedeutung ihrer Genomattribute für die Farben).
Grundsätzlich werden alle auf einem grauen Quadrat sitzenden Zellen von der Ratte als Wände betrachtet.
Große X stellen Zellen dar, die als Fallen betrachtet werden, wobei die entsprechenden Oktogone den Detektor angeben, der sie gemeldet hat.
In diesem Beispiel sind beide Wände als solche gekennzeichnet, ebenso wie die blassgelbe Falle (was auf eine tödliche Zelle hinweist, sodass es richtig ist, sie als Wand darzustellen).
Der Mauve-Trap-Detektor wurde als solcher identifiziert (er befindet sich auf einem grauen Oktogon), aber die Trap-Position ist falsch (Sie können sehen, dass einige rote Kreise keine Kreuze darunter haben).
Von 4 Teleportern gelten 2 als Wände (türkis und braun) und 2 als leere Zellen (rötlich und gelblich).
Einige leere Zellen werden als Fallendetektoren oder Wände betrachtet. Wenn man genau hinschaut, kann man sehen, dass diese "fehlerhaften Detektoren" tatsächlich den Zutritt zu Zellen verbieten, die die Ratte in Schwierigkeiten bringen würden, und obwohl sie nicht den tatsächlichen Farben entsprechen, haben sie einen bestimmten Zweck.
Der Code
Nun, es ist ein Durcheinander, aber es funktioniert ziemlich gut.
Vom Code des Spielers aus habe ich nur eine Schnittstelle hinzugefügt: eine Trace-Funktion, mit der die Bedeutung einer bestimmten DNA gemeldet wird. In meinem Fall habe ich 3 Typen verwendet (Wand-, Fallen- und Leermelder), aber Sie können grundsätzlich alles ausgeben, was mit Farbe zu tun hat (oder gar nichts, wenn Sie keine genombezogenen Grafiken wünschen).
Ich habe den Controller gehackt, um eine riesige Zeichenfolge zu generieren, in der die Beschreibung von Spur und Farben mit einem "Probelauf" der Ratten-DNA von allen möglichen Stellen aus verglichen wird.
Das bedeutet, dass die Ergebnisse nur dann wirklich aussagekräftig sind, wenn der Bot keine Zufallswerte verwendet. Andernfalls stellen die angezeigten Pfade nur ein mögliches Ergebnis dar.
Zuletzt werden alle diese Spuren in eine große Textdatei geschrieben, die später von einem PHP-Dienstprogramm gelesen wird, das die grafische Ausgabe erzeugt.
In der aktuellen Version mache ich jedes Mal einen Schnappschuss, wenn eine Ratte stirbt, nachdem sie eine neue maximale Fitness erreicht hat (die die fortschreitende Verfeinerung des Genoms ziemlich gut zeigt, ohne dass zu viele Schnappschüsse erforderlich sind), und einen letzten Schnappschuss am Ende des Spiels (das zeigt sich) die erfolgreichste DNA).
Bei Interesse kann ich den Code veröffentlichen.
Dies funktioniert natürlich nur für C ++ - Bots, und Sie müssen eine Trace-Funktion schreiben und möglicherweise den PHP-Code ändern, wenn Sie einige genomspezifische Daten anzeigen möchten (in meinem Fall die grauen Zahlen).
Auch ohne DNA-spezifische Informationen können Sie die von Ihrer DNA verfolgten Pfade auf einer bestimmten Karte mit sehr geringem Aufwand anzeigen.
Warum eine Zwischenausgabe?
Erstens hat C ++ keine anständige tragbare Grafikbibliothek, von der man sprechen könnte, insbesondere wenn MSVC verwendet wird. Selbst wenn Win32-Builds normalerweise verfügbar sind, entstehen sie oft aus einem nachträglichen Grund, und die Anzahl der benötigten externen Bibliotheken, Pakete und anderen unixartigen Feinheiten macht das Schreiben einer schnellen und einfachen grafischen Anwendung zu einem fürchterlichen Schmerz in einem Körperteil, der durch Anstand verhindert wird mich von der Benennung.
Ich dachte darüber nach, Qt zu verwenden (die einzige Umgebung, die die Entwicklung von portablen GUIs / Grafiken in C ++ zu einer einfachen und sogar angenehmen Aufgabe macht, IMHO - wahrscheinlich, weil sie ein Messaging-System à la Objective C hinzufügt , das C ++ schmerzlich fehlt und einen unglaublichen Job zur Begrenzung des Arbeitsspeichers leistet Management auf das Nötigste), aber das sah nach einem Overkill für die anstehende Aufgabe aus (und jeder, der den Code verwenden möchte, müsste das großartige SDK installieren - der Aufwand lohnt sich wohl kaum).
Selbst wenn man eine tragbare Bibliothek voraussetzt, muss man nicht über die erforderliche Geschwindigkeit sprechen (eine Sekunde oder so, um ein Bild zu erstellen, ist weitgehend ausreichend), und C ++ ist aufgrund seiner sprichwörtlichen Steifheit und inhärenten Unordnung sicherlich nicht das beste Werkzeug für diese Aufgabe.
Darüber hinaus bietet die Ausgabe von Zwischentexten viel Flexibilität. Sobald die Daten vorhanden sind, können Sie sie für andere Zwecke verwenden (zum Beispiel zum Analysieren der Leistung der Bots).
Warum PHP?
Ich finde die Sprache sehr einfach und anpassungsfähig, sehr praktisch für das Prototyping. Ich habe es zu meiner Lieblingssprache für Code-Herausforderungen gemacht, die keine extremen Leistungen erfordern.
Es ist eine schreckliche Sprache zum Golfen, aber Golf war sowieso nie meine Sache.
Ich nehme an, Python oder Ruby wären für den gleichen Zweck genauso angenehm, aber ich hatte nie die Gelegenheit, ernsthafte Arbeit mit ihnen zu leisten, und ich habe in letzter Zeit an Websites gearbeitet, also PHP.
Auch wenn Sie die Sprache nicht kennen, sollte es nicht allzu schwierig sein, den Code an Ihre Bedürfnisse anzupassen. Vergiss nur nicht die
$
s vor den Variablen, genau wie die guten alten Basic-Tage :).quelle
SkyWalker - Python - erzielt in 50 Spielen weniger als 231 Punkte
Also erst Code und dann ein paar Erklärungen. Ich hoffe, beim Kopieren ist nichts kaputt gegangen.
Einige Erklärung
Meiner Meinung nach besteht der Hauptunterschied darin, dass ich nicht jede Farbe codiere. Stattdessen versuche ich, die Anzahl der Farben zu speichern, die wichtig sind. Meiner Meinung nach sind diese Farben die Fallen, Wände und Teleporter. Die Probe muss nicht die Farbe einer guten Zelle kennen. Daher ist mein Genom folgendermaßen strukturiert.
Dadurch werden insgesamt 52 Bits verwendet. Ich benutze jedoch nur das erste Bit der 3 Teleporterentscheider (ich überprüfe, ob die Zahl 3 größer ist). Daher könnten die anderen 2 gelöscht werden, was mich bei 44 Bit belässt.
Bei jedem Zug überprüfe ich jedes Feld meiner Sicht, ob es eine der schlechten Farben ist (+ das Feld außerhalb des Bretts -1), und füge es einer Liste von Feldern hinzu, in die sich die Probe nicht bewegen möchte. Im Falle einer Überfüllung füge ich das Feld hinzu, das sich auf dem gespeicherten Versatz für diese Überfüllungsfarbe befindet.
Basierend auf der Liste dieser fehlerhaften Felder wird der nächste Zug berechnet. Die Reihenfolge der bevorzugten Felder ist:
Wenn zwei Felder einer Kategorie zutreffen, wird eines zufällig ausgewählt.
Ergebnisse
Gedanken
Ich habe keine Ahnung, ob ich mit den 50 Läufen Glück hatte oder ob meine Strategie wirklich etwas Weisheit enthält.
Meine Läufe scheinen sich nie zu verbessern und erzielen Super-Highscores, aber sie finden zumindest ein paar Mal das Ziel
Eine kleine Zufälligkeit ist gut, um nicht in einer Falle hängen zu bleiben, manche kurz vor dem Ende des Rennens
Ich denke, dass nicht spezielle Farben niemals schlecht sind. Instanzen von ihnen können jedoch schlecht sein, wenn sie sich auf dem Offset einer Falle befinden. Daher macht es keinen Sinn, eine Farbe als schlecht zu bezeichnen, wenn sie keine Falle, Wand oder schlechten Teleporter enthält.
Mauern sind die größten Feinde
Verbesserungen
Erstens ist ein C ++ - Port erforderlich, um mehr Tests durchzuführen und ein aussagekräftigeres Ergebnis zu erzielen, obwohl ich vermissen werde, dass die schwarzen Quadrate immer näher an das Ziel heranrücken.
Eines der Hauptprobleme besteht darin, dass sich schlechte Zellen (oder solche, die die Probe für schlecht hält) vor der Ratte leicht im Kreis auf und ab bewegen. Dies könnte gestoppt oder reduziert werden, indem in diesen Fällen 2 Züge nach vorne geschaut werden und verhindert wird, dass es sich auf ein Feld bewegt, auf dem es sich einfach wieder zurück bewegt.
Oft dauert es einige Zeit, bis eine Ratte mit guten Genen das Ziel erreicht und beginnt, diese Gene zu verbreiten. Vielleicht brauche ich eine Strategie, um die Vielfalt in diesen Fällen zu erhöhen.
Da Teleporter schwer zu kalkulieren sind, sollte ich vielleicht die Bevölkerung in diejenigen aufteilen, die riskant sind und immer gute Teleporter nehmen, und diejenigen, die besorgter sind und sie nur nehmen, wenn es keine andere Wahl gibt.
Ich sollte die zweite Hälfte meines Genoms irgendwie benutzen.
quelle
self.bit_chunk(16, 4)
undself.bit_chunk(20, 4)
haben beide den Wert0010
Sie effektiv nur dann gespeichert haben Informationen über eine der beiden Fallen.itervalues
zuvalues
.Python, NeighborsOfNeighbors, Score = 259.84395 über 100 Spiele
Dies ist eine Variation von ColorScorePlayer. Alle 6 Bits speichert einen Qualitätsfaktor für ein Quadrat. Wenn der Bot einen Zug macht, zählt er jedes der drei vorderen Felder - diagonal nach oben, vorwärts und diagonal nach unten. Die Punktzahl ist die Qualität des Quadrats plus die Hälfte der durchschnittlichen Qualität der nächsten 3 Quadrate. Dies gibt dem Bot einen gewissen Blick nach vorne, ohne die Qualität des ersten Quadrats zu beeinträchtigen. Der Algorithmus ähnelt LookAheadPlayer, den ich vor dem Schreiben dieser Lösung nicht gesehen habe.
quelle
else None
inelse 0
der vorherigen Zeile umgestellt , um Ihre Punktzahl zu berechnen. Hoffentlich bleibt Ihre Logik unverändert (ich habe hier auf SE keine Änderungen an Ihrem Code vorgenommen, abgesehen vom Hinzufügen des verlorenen Einzugs).ROUS (Nagetier ungewöhnlicher Größe), Java, Score = 0
Dadurch wird die Umgebung durchwühlt, um zu entscheiden, wohin sie gehen soll.
Da der Java-Controller nicht funktioniert, habe ich keine Punkte dafür. Dies wird nur sehr weit kommen, wenn es ein paar Teleporter findet, die ihm helfen.Dies kann dazu führen, dass der Controller von Zeit zu Zeit abstürzt. Dies ist wahrscheinlich auf die Tatsache zurückzuführen, dass es sich bei der natürlichen Umgebung um den Feuersumpf handelt.quelle
Grauer Lookahead (C ++, ~ 1,35)
Diesem geht es im Durchschnitt nicht sehr gut, aber in seltenen Fällen funktioniert es hervorragend. Leider werden wir im geometrischen Durchschnitt (1,35) und nicht im Maximalwert (20077) bewertet.
Dieser Algorithmus verwendet lediglich 4-Bit-Graucodes, um die Punktzahl jeder Farbe irgendwo zwischen -2 und 2 (mit einer Neigung in Richtung des Bereichs [-1..1]) abzubilden, und berechnet die Punktzahl der Kacheln und der nächsten Züge jeder Bewegung . Es wird auch ein 2-Bit-Gray-Code verwendet, um den Multiplikator für die Kachel selbst sowie den Vorspannungsfaktor für die Bewegung nach rechts zu bestimmen. (Gray-Codes sind aufgrund von Mutationen viel weniger anfällig für große Sprünge, obwohl sie für die Überkreuzung zwischen zwei Codepunkten eigentlich keinen Gefallen tun ...)
Es macht auch absolut nichts, zu versuchen, mit Fallen speziell umzugehen, und ich vermute, dass dies der Untergang sein könnte (obwohl ich dem Controller keine Instrumente hinzugefügt habe, um diese Theorie zu testen).
Für jeden möglichen Zug wird eine Punktzahl ermittelt, und unter allen Zügen mit der höchsten Punktzahl wird nach dem Zufallsprinzip ausgewählt.
Bei meinem letzten Lauf habe ich Punkte bekommen: 1 1 1 1 1 1 1 46 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20077 1 1 1 2 1 1 1 1 1
Ich wünschte, ich könnte mehr von den 20077s und weniger von den 1s bekommen. :)
quelle
C ++, TripleScore, Punktzahl: 100 ~ 400
Erstens variiert meine Punktzahl über mehrere Läufe stark (hauptsächlich aufgrund der Anzahl der Einsen).
Der Kern berechnet die Punktzahl aus 5 Richtungen: hoch, runter, vorwärts hoch, vorwärts und vorwärts runter. Zuerst wird die Punktzahl von Auf und Ab berechnet, dann werden die Ergebnisse mit dem Wert des Verbleibens an Ort und Stelle verglichen. Wenn es besser ist, an Ort und Stelle zu bleiben, als sich nach oben oder unten zu bewegen, werden diese Richtungen nicht gewählt (also muss es vorwärts gehen). Dies dient dazu, ein Springen (hoch, runter, hoch, runter, ...) zwischen 2 Punkten zu verhindern.
Jetzt werden die 3 anderen Richtungen gewertet: Vorwärts nach oben, geradeaus und vorwärts nach unten. Aus allen untersuchten Richtungen werden die mit der höchsten Punktzahl festgehalten und 1 davon wird zufällig ausgewählt.
Eine Richtung bewerten: TripleScore berechnet den Punktestand einer Bewegung anhand von 3 Unterpunkten:
Wie bei anderen Antworten hängt die Punktzahl stark von der Anzahl der zurückgegebenen 1-Punkte ab.
quelle
Ruby - ProbabilisticScorePlayer
Diese hochgradig nicht deterministische Ratte berechnet die Wahrscheinlichkeit, durch ihre Nachbarschaft auf ein Feld zu gelangen. Die ersten 16 Slots im Genom repräsentieren die 16 Farben. 1 in einem Slot bedeutet, dass die Farbe gut ist, 0 bedeutet schlecht. Die nächsten 16 gelten gleichermaßen für das Feld vor Ihrem Ziel und so weiter.
Der Hauptvorteil des probabilistischen Ansatzes besteht darin, dass es fast unmöglich ist, lange hinter einer Mauer zu stecken. Der Nachteil ist, dass Sie so gut wie nie eine perfekte Ratte bekommen.
quelle
c
einen Anfangswert anzugeben? Es scheint nicht definiert zu sein, wenn Sie es in der ersten verwendenif
.coords
ist keine Liste, die Sie&&
anstelle einerand
vergessenen Klammer verwenden, und selbst nachdem Sie all dies behoben haben, beschränken Sie die RNG-Werte nicht, sodass Sie eine leere Richtung erhalten. Ist dieser Pseudocode oder etwas, das mit einer Art Ruby-Dialekt ausgeführt werden soll?Java, RunningStar, Score = 1817.050970291959 über 1000 Spiele
Dieser Bot verwendet die Farbcodierung von Run-Bonus mit StarPlayer der Technik von .
Update: Java Controller behoben.
quelle
LeapForward, Python 2
Nicht besonders bahnbrechend, aber es ist mein einziger Versuch, der gut funktioniert hat.
Grundsätzlich codiert es vier Farben (jeweils 4 Bits), um dies im Genom zu vermeiden. Es wird dann zu einer Farbe weitergeleitet, die nicht in dieser Liste enthalten ist. Wenn alle Farben schlecht sind, springt es immer noch ins Unbekannte.
quelle
Java - IAmARobotPlayer - Punktzahl 3.7
Ich habe gerade diese Roboterratte zum Vergleich mit einem anderen (bisher nicht sehr interessanten) Programm erstellt. Es schneidet insgesamt nicht gut ab, aber wenn es irgendwo abschneidet, werden viele Ratten auftauchen. Die Idee ist, dass nur die drei Zellen davor betrachtet werden, jede Zelle ist gut oder schlecht. Dies ergibt eine Binärzahl. Dann wird es diese Nummer in seinem Genom nachschlagen, die drei aufeinanderfolgenden Bits nehmen, sie auch zu einer Nummer konvertieren und die Aktion ausführen, die unter dieser Nummer gespeichert ist. Es verhält sich also immer gleich, wenn es auf die gleiche Situation stößt.
Ergebnis:
quelle
Vorsichtige Exemplare - C ++ - erzielt ungefähr 2030 über 200 Läufe
Dabei wird der Farbanteil (16 x 4 Bit) der von Blind Faith codierten DNA verwendet, der Rest (36 Bit) der DNA bleibt jedoch vollständig ungenutzt.
Die Kodierung für eine Farbe ist entweder:
Wobei X nicht verwendete Bits angibt. Vorausgesetzt, dass nur 2 von 16 Farben Überfüllungen sind, die alle 4 ihrer Bits verwenden (und nur wenn die Überfüllung versetzt ist, was 8-von-9-mal der Fall ist), gibt es normalerweise 64 nicht verwendete Bits - Die Theorie besagt, dass Mutationen, die sich auf eines dieser nicht verwendeten Bits auswirken, das Genom nicht zerstören. Die Stabilität ist besser als bei anderen ausgefallenen Lösungen, die diese verbleibenden Bits verwenden können.
Die Proben verwenden dies dann, um eine sichere Route in einem 7x7-Raster zu planen, das auf sich selbst zentriert ist (die 5x5-Linien ermöglichen eine Sicht plus 1 Quadrat auf jeder Seite, um versetzte Fallen zu ermöglichen).
Ich habe anfänglich damit begonnen, einige Überprüfungen durchzuführen, um sicherzustellen, dass die Tatsache, dass die Farbe, auf der die Probe momentan steht, nicht tödlich ist, mit dem Genom übereinstimmt, und fehlerhafte Farben als Quadrate der UNSURE-Sicherheit (und ihrer benachbarten Quadrate) gekennzeichnet - dies trug jedoch erheblich dazu bei Komplikation für wenig bis gar keinen Gewinn im Vergleich zum Markieren dieser Quadrate als SICHER und Töten einiger zusätzlicher Exemplare. Ich werde darauf zurückkommen, wenn ich Zeit habe.
Sample Scores:
Maximale Punktzahl während des Tests: 8.150.817 gespeicherte Proben.
quelle