Dokumentation

 

EvoHamster Dighty

 

von Torsten Sommerfeld und Simon Steinmeyer

 

 

 

Einleitung:

 

EvoHamster Dighty ist das Produkt zweier parallel unabhängig entwickelter Hamster, deren Strategien und Algorithmen sich grundlegend unterschieden haben. Während der eine Hamster hauptsächlich auf ziemlich schnelle und gute statische Algorithmen basierte, versuchte der andere Hamster auf Basis genetischer Algorithmen seinen Weg durch das Labyrinth zu bahnen.

Beide Ansätze hatten ihre Vor- und Nachteile; somit Stand fest, dass der finale Hamster aus beiden Hamstern profitieren soll.

Eine Gemeinsamkeit besaßen jedoch beide Hamster von Anfang an: Sie haben ihre Aufgabe in zwei Phasen unterteilt: Die Erkundungsphase, in der das Labyrinth hauptsächlich erforscht wird. Ist die Phase abgeschlossen erfolgt die Einsammelphase, in der die Körner zum Heimatfeld gebracht werden. Auch der finale Hamster hat somit diese zwei Phasen bekommen.

 

Bevor wir nun zur Beschreibung der 2 Phasen kommen, fehlt uns der strukturelle Aufbau der Daten und er Ausführungslogik.

 

Struktur des Hamsters:

 

Ganz grob findet das Leben des Hamsters in der Hauptklasse Dighty statt, diese jedoch ist jedoch recht faul und delegiert fast alle Aufgaben weiter. Die Hauptaufgabe besteht darin, die Datenstruktur des Hamsters aufzubauen, und die einzelnen Phasen zu starten.

Eine kleine aber wichtige Finesse ist  integriert worden: die TimeOutSaver- Klasse. Sie dient dazu, die für uns sehr unschöne 3-Minuten-Regel, vom Sinn her auszuhebeln: Um Endlosschleifen zu erkennen, in die sich ein Hamster verfangen kann, muss er alle drei Minuten ein Lebenszeichen von sich geben, ansonsten wird er getötet. Unser Hamster braucht jedoch zum Ende der Phase zwei bei mittleren und großen Labyrinthen jede Menge Zeit zum optimieren, bei sehr großen Labyrinthen kann er auch mal locker die Maximalzeit von zwei Stunden in Beschlag nehmen.

Deshalb ist eine Funktion integriert  worden, die Dighty alle drei Minuten noch bewegt und außerdem auf das 2-Stundenlimit achtet. Das kostet alle 6 Minuten jedoch 2 Punkte, aber es lohnt sich fast immer, wenn der zuständige Algorithmus das meint.

 

Wenn man nun einen genaueren Blick in die Hamsterstruktur wirft, stellt man fest, das für fast jede Basisaufgabe, wie laufen, sammeln, sehen usw., eine extra Klasse angelegt wurde.

Die wichtigsten werde ich jetzt einmal kurz beschreiben, beginnend mit der einfachsten.

1.      CHamsterGetCornInfo: der Aufruf der Run-Methode dieser Klasse bringt das Wissen der Kornanzahl des Feldes, auf dem sich der Hamster befindet, auf den neusten Stand.

2.      CHamsterGetFeldInfo: diese Klasse übernimmt den Auftrag, Information des vor ihm befindlichen Feldes zu bestimmen und mit möglichst viel Gehalt zu speichern

3.      CHamsterLockTo: ebenfalls eine sehr tief angesiedelte Funktionsverkapslung. Es wird in die gewünschte Richtung geschaut, um dann CFeldGetFeldInfo aufzurufen

4.      CHamsterLockAround: hier treffen wir nun das erste mal auf eine komplexere Funktion. Der Hamster blickt um sich, um alle Felder, die er noch nicht kennt, in sein Gedächtnis abzuspeichern. Hierzu verwendet er CHamsterLockTo.

5.      CHamsterDoAStep: ohne diese Methode könnte sich der Hamster keinen Schritt bewegen. Gleichzeitig wird hier die Schnittstelle für die TimeoutSaver-Klasse gestellt.

6.      CHamsterMoveTo: eine der wichtigsten – sämtliche Bewegungen von Punkt a zu Punkt B laufen hier werden hier bewerkstelligt.

7.      CPathFinder_A: Beantworte mir die folgende Frage: wie komme ich am günstigsten von Punkt A nach Punkt B, und wie anstrengend ist das? Um Antwort dieser Frage kümmert sich diese Klasse. Sie ist sehr eng mit der Datenstruktur des Hamsters verbunden und gehört damit eigentlich fast nicht mehr in diese Aufzählung. Sicherlich interessiert es nun einige, wie das anstellt: ganz einfach ausgedrückt, er nutzt einen Algorithmus der als A* bekannt ist.

 

Die Daten des Hamsters:

 

Was wäre der Hamster ohne ein Gedächtnis? Da das Labyrinth auf Sechsecke aufbaut, kann man es nicht einfach linear auf ein zweidimensionales Array abbilden. Was tun? Wir haben eine einfache Lösung in Form einer linearen Abbildung gewählt. Dazu sollte man wissen, wie sich ein Feld für den Hamster darstellt. Für jeden Punkt des Labyrinths gibt es eine Instanz der Klasse CFeld. Diese speichert die (bekannte) Anzahl von dort liegenden Körner, die Beschaffenheit der Wände, die Höhe, ein Flag, welches besagt, ob das Feld schon erkundschaftet wurde, das später wichtig für Phase 1 ist, und einen Puffer für Entfernungen, dieser ist unerlässlich für Phase 2.

So nun wissen wir, wie ein Feld aussieht, wie entsteht nun der Zusammenhang? Hier kommt es - die nächst größere Stufe wird von der Klasse CLabyrinth_ly0 getragen. Diese beinhaltet ein zweidimensionales Array von 62 mal 62 aus CFeld’ern. Da es nun unpraktisch ist, immer direkt darauf zuzugreifen, wie gesagt, dieses Arrays eignet sich von Natur aus eigentlich nur für Vierecke, wird nun eine Zugriffsebene dazwischengeschaltet, die jedem Feld im Labyrinth eineindeutig ein Feld im Array zuordnet. In den meisten Fällen greift der Hamster also nicht direkt, sondern über eine Hilfsfunktion indirekt auf seine Daten zu. Zusammengefasst definiert die Klasse CLabyrinth_ly0 das gesamte Labyrinth, und stellt Funktionen bereit, die den Zugriff ermöglichen. Weiterhin sind die meisten Konstanten und einige weitere Hilfsfunktionen hier verankert, die das Leben mit dieser Klasse noch ein wenig vereinfachen.

Das komplette Wissen wird aber in einer noch höheren Ebene abgelegt, die CDightyData – Klasse. Hier werden alle Daten, die dem Hamster allgemein betreffen abgelegt – seine Position, seine Blickrichtung, und sogar 2! Labyrinthe. Diese Daten werden an jedem ausführenden Algorithmus übergeben, in Form von Parameter, oder indirekt über den Konstruktor. Wer also wissen möchte, was der Hamster weis, muss hier her schauen.

 

 

Nun aber genug der Vorrede – ab zum eigentlichen Arbeiten des Hamsters:

 

 

Erforschen des Labyrinthes:

 

Man stelle sich vor, man wacht eines Tages aus einem Alptraum auf, und man realisiert plötzlich, dass man seine Umgebung überhaupt nicht kennt. Man auf sich alleine gestellt ist, man aber einen ganz kräftigen Hunger verspürt. Genau so ergeht es unserem Hamster, und er macht sich auch sogleich daran, seine Umgebung zu erforschen. Das zu sucht er nach die am nächsten befindlichen unbekannten Felder. Findet er keine, so ist er schon am Ziel seines Schaffens, er kennt alles, was erkennen muss. Was aber nun, wenn nicht ?- ganz einfach, er sucht sich das Feld aus, das ihm am besten gefällt. Das können wir nun aber nicht dem Zufall überlassen, wo kommen wir da auch hin, sondern definieren ein paar ganz einfache Regeln:

1.      Nimm das jeweils höhere Feld, der Hintergedanke ist der, das man von oben nach unten besser auskundschaften kann als andersherum

2.      Nimm das Feld, welches weiter von Bau entfernt liegt. Diese Regel hat sich durch praktische Erfahrung bestens bewährt

3.      übergehe Felder, die einfach zu weit weg vom Bau sind – wir wollen ja unterwegs nicht „verhungern“

4.      ignoriere Felder, die einigermaßen von außen bekannt sind, und keine Körner enthalten

Um den Hamster noch besser zu gestallten, und das ist möglich, hat man genau hier einen gute Ansatzmöglichkeit.

So, nun weis er welches Feld er nun inspizieren möchte. Sollte er nun einfach hinspazieren? Na wenn ich schon so frage, kommt natürlich noch etwas. Er guckt, ob er auf seinem Weg nicht noch herrenlose Körner findet, die er auf ein günstigeres, d. h. heimatfeldnäheres Feld, dass auf seinen Weg liegt, wieder hinwerfen kann. Dighty kann dabei sogar Umwege beim Erkunden einplanen, um somit möglichst nie leer laufen zu müssen. Denn wie beim Auto gilt auch beim Hamster, dass Leerlauf eigentlich nur Ressourcenverschwendung ist.

 

Einsammeln der Körner:

 

Die Einsammelphase ist von beiden Urhamstern geprägt: Es existieren statische Algorithmen, die schon ein sehr gutes Ergebnis liefern, aber es sind auch genetische Algorithmen implementiert, die das Ergebnis noch verbessern können.

 

Das statische Einsammeln wird folgendermaßen realisiert: Es wird eine sortierte Kornliste erstellt, in der alle Kornpositionen des Labyrinthes gespeichert sind. Die Sortierung erfolgt durch spiralförmige Durchsuchung des Labyrinthes nach Kornfeldern, ausgehend vom Heimatfeld.

Nun wird eine neue Einsammelliste erstellt, in der nach der Reihenfolge alle Einträge aus der Kornliste hinzugefügt werden, d. h. erst Eintrag eins, dann Eintrag zwei, etc. Jeder Eintrag repräsentiert ein Gen. Beim Einfügen der Gene wird geschaut, an welcher Position das Korn am meisten Punkte liefert, wenn der Hamster diese Liste virtuell ablaufen würde. Aus der fertigen Liste, die dem Genom des Individuums entspricht, wird dann zum Test jedes Gen entfernt; verbessert sich das Ergebnis bleibt es auch aus dem Genom draußen. Nun haben wir unser erstes Individuum.

 

Die ursprünglich spiralförmig erstellte Kornliste wird nun auf den Kopf gestellt und daraus wie beschrieben ein weiteres Individuum gewonnen.

 

Das Einsammeln der Körner ist in insgesamt drei Phasen unterteilt.

 

Phase 1:

Die erste Phase wird nur bei erweiterten Labyrinthen aktiviert: Sie schmeißt überall Körner von Klippen, wo es sich lohnt. Dabei versucht der Algorithmus noch Körner zu möglichst großen Paketen zusammenzufassen bevor er sie den Berg runterschmeißt. Er arbeitet rekursiv, d. h. er kann bereits runtergeschmissene Körner noch weitere Etagen tiefer befördern, wenn er meint, dass es sich lohnt.

 

Phase 2:

Diese Phase erstellt wie beschrieben mehrere statische Individuen und wählt das beste aus. Dieses darf anfangen einzusammeln, wird aber gestoppt, sobald es das Heimatfeld erreicht und seine Körner dort fallengelassen hat. Als nächstes sammelt der EvoHamster Dighty die Körner ein, die auf einem Haufen von mindestens 20 Körnern liegen, so dass nach dieser Phase jeder Haufen weniger als 20 Körner hat. Wenn man nun die Kornliste erstellt, finden sich meistens weniger Einträge; es fehlen alle Felder, die ursprünglich ein ganzzahliges vielfaches von 20 Körnern hatten. Es ist zu erwarten, dass dieser das theoretische Maximum durch diese Aktion nur um ganz wenig Punkte gesenkt haben kann. Dafür hat die nächste Phase weniger Kornfelder zu optimieren.

 

Phase 3:

Die Startpopulation wird mit zufällig generierten Individuen gefüllt, d. h. dass die Reihenfolge der Kornfelder im Genom zufällig ist. Es werden nun erneut die statischen Individuen erstellt und der Population hinzugefügt.

Als nächstes erfolgt die Selektion nach Rang und Zufall, wobei die Elite aber geschützt wird. Die nun freigewordenen Plätze in der Population werden aufgefüllt: Zu 75 % durch Kreuzung und zu 25 % durch Klone & Muation. Es sind verschiedene Kreuzungs- und Mutationsalgorithmen implementiert, die Aufrufwahrscheinlichkeiten sind: 25 % ERX, 25 % PMX, 25 % OX und 20 % Klonen & Mutation durch Genpositionstausch, 5 % Klonen & Mutation durch zufälliges Entfernen eines Gens.

 

Nachdem es sehr viele Generationen keine Verbesserungen mehr gegeben hat, wird die Evolution angehalten und der beste Hamster darf einsammeln.

Bei der Evolution beobachtet man, dass es erst einige Generationen dauert, bevor optimiert wird, weil erst die Gesamtpopulationsstärke auf dem Niveau der statischen Individuen angepasst werden muss.

Diese Phase ist mit der zeitaufwendigste Teil des Hamsters, so dass es bei mittleren oder größeren Labyrinthen häufiger die TimeOutSaver-Klasse zuschlagen muss.