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.