Auswertung des Contests
Leider gab es nur drei Einsendungen, trotz der relativ einfachen Aufgabenstellung.
Aber dennoch hat mir der Contest viel Spaß gemacht und mich stark in den Bann gezogen, vor allem, weil ich mir mal wieder ein "Battle" mit Helmut liefern durfte!
Wie man das Problem löst
Im Prinzip führen alle Lösungen eine
Breitensuche durch, d.h. eine vereinfachte Version des Algorithmus von Dijkstra, bei dem alle Kantengewichte = 1 sind. Kurz erklärt funktioniert das wie folgt: man hat eine Warteschlange, die zu Beginn nur den Startzustand enthält. Nun nimmt man immer den vordersten Zustand aus der Warteschlange und schaut sich an, welche Zustände daraus mit einem einzigen Zug zu erreichen sind. Man geht also alle Spielfiguren und Bewegungsrichtungen durch. Die dabei entstehenden Zustände legt man wieder hinten in die Warteschlange, wenn sie nicht bereits schon einmal gefunden wurden. Hat man irgendwann den Zielzustand erreicht, so kann man aufhören zu suchen, denn man hat einen kürzesten Weg dorthin gefunden. Bei dieser Art der Suche erreicht man zuerst alle Zustände, die nach 0 Zügen möglich sind (= Startzustand), dann alle nach 1 Zug, dann alle nach 2 Zügen, und so weiter.
Nun gibt es verschiedene Möglichkeiten, wie man diese Suche beschleunigen kann, und das war das Entscheidende bei diesem Contest:
- Bidirektionale Suche: Parallel zur Vorwärtssuche (vom Startzustand ausgehend) wird eine Suche vom Zielzustand ausgehend rückwärts durchgeführt. Sobald die beiden Suchen sich treffen, kann man aufhören und hat die Lösung gefunden. Bei der Rückwärtssuche gelten natürlich etwas andere Regeln als bei der Vorwärtssuche, und der Suchbaum ist stärker verzweigt. Darum empfiehlt es sich, nicht abwechselnd jeweils eine Iteration vor- und rückwärts zu suchen, sondern immer diejenige Richtung weiter zu bearbeiten, die momentan weniger Knoten in der Warteschlange hat.
Die bidirektionale Suche bringt wohl den größten Geschwindigkeitsvorteil, da sie effektiv die Suchtiefe halbiert. Da die Laufzeit exponenziell mit der Suchtiefe steigt, lohnt sich das enorm.
- Effiziente Erzeugung von Nachfolgezuständen: Eine der Grundoperationen der Suche ist das Bewegen von Spielfiguren in eine der vier Himmelsrichtungen bis zur nächsten Wand oder zur nächsten Spielfigur. Anstatt jedes Mal Schritt für Schritt in eine Richtung zu gehen und zu testen, ob das jeweilige Feld frei ist, lohnt sich eine kleine 14x14-Lookup-Tabelle. In dieser Tabelle speichern wir für jedes Feld, wo eine Spielfigur stehen bleibt, wenn sie von dort aus in eine bestimmte Richtung rutscht. Natürlich kann man hier nur die Mauern berücksichtigen, da die Spielfiguren dynamisch sind. Also schaut man zuerst in der Tabelle nach und prüft anschließend noch auf mögliche Zusammenstöße mit den anderen Figuren.
- Effiziente Speicherung der Zustände: Die Warteschlange (oder im Falle bidirektionaler Suche: zwei Warteschlangen) enthält Zustände. Ein Zustand ist definiert durch die Position der Spielfiguren. Die Koordinaten der Spielfiguren reichen auf beiden Achsen von 1 bis 14 (0 und 15 können nicht vorkommen, da alle Levels außen eine Wand aufweisen). Also kann man auch generell 1 von den x- und y-Koordinaten abziehen, wodurch diese nur noch zwischen 0 und 13 liegen können, was unter Umständen später weniger Speicher benötigt. Es reichen also 4 Bits für eine x- oder y-Koordinate und somit 24 Bits für einen ganzen Zustand, und das passt in einen int. Die restlichen 8 Bits kann man auch noch nutzen. Die Frage, ob der Zielzustand erreicht ist, ist dann auch trivial durch das Vergleichen zweier ints zu beantworten.
Arbeitet man hingegen mit ganzen Bytes statt nur mit 4 Bits, so wächst die Größe eines Zustands schon auf mindestens 6 Bytes an, praktisch aber 8 Bytes (wegen Padding).
- Sinnvolle Nutzung der verbleibenden 8 Bits im Zustand: In den letzten 8 Bits jedes Zustands kann man sich merken, durch welchen Zug man dorthin gelangt ist (d.h. Index der Spielfigur, die bewegt wurde, und die Bewegungsrichtung - eigentlich nur die Achse, also x oder y). Dafür reichen auch 3 Bits aus. Wenn man den Zustand dann aus der Warteschlange holt und weiß, dass man ihn durch eine Bewegung der roten Spielfigur auf der x-Achse erreicht hat, dann kann man sich eine erneute Bewegung der roten Spielfigur auf dieser Achse ersparen, da die Zustände garantiert schon bekannt sind. Insbesondere bei der Rückwärtssuche lohnt sich dieser einfache Trick.
- Effiziente Beantwortung der Frage "Habe ich diesen Zustand schon einmal gesehen?": Bevor man einen neuen Zustand in die Warteschlange steckt, sollte man sich vergewissern, dass man ihn nicht bereits gesehen hat. Hier bietet es sich an, ein std::bitset oder etwas Ähnliches zu benutzen. Pro Zustand benötigt man ja nur 1 Bit, nämlich für "Ja, schon gesehen" oder "Nein, noch nicht gesehen". Auch hier ist es extrem vorteilhaft, wenn man die Zustände möglichst kompakt als Integer repräsentiert, denn dann kann man diese direkt als Indizes für das Bit-Set/Bit-Array benutzen.
Hier lohnt es sich, eine eigene Bit-Set-Implementierung anzufertigen. Dem std::bitset fehlt nämlich eine "test and set"-Methode, die ein Bit auf 1 setzt und dessen vorherigen Wert zurückliefert. Genau das braucht man nämlich jedes Mal, wenn man einen neuen Zustand erzeugt hat: erst muss man prüfen (test), ob er nicht schon gesehen wurde, und wenn nicht, dann hat man ihn jetzt neu gefunden und muss sich dies merken (set).
Bei bidirektionaler Suche benötigt man zwei solcher Bit-Sets, nämlich für jede Suchrichtung eins. Bei der Vorwärtssuche muss man bei jedem neuen Zustand testen, ob dieser bereits von der Rückwärtssuche gefunden wurde, und umgekehrt natürlich auch. Das bedeutet, dass kurz hintereinander auf das Bit Nr. N im Vorwärts-Bit-Set und das Bit Nr. N im Rückwärts-Bit-Set zugegriffen wird. Wenn man beide Bit-Sets im Speicher "verzahnt" anlegt, d.h. abwechselnd Vorwärts- und Rückwärts-Bits, dann wird beim zweiten Zugriff der entsprechende Speicherbereich bereits im Cache liegen und deutlich schneller erfolgen.
- Effiziente Implementierung der Warteschlange: std::queue ist zwar einfach zu benutzen, aber hier absolut nicht zu gebrauchen. Der Grund dafür ist, dass der Speicher der Warteschlange dynamisch angelegt wird und bei Bedarf wächst. Speicherreservierungen sind tendenziell langsam, außerdem muss bei der Vergrößerung der Warteschlange der ganze bereits vorhandene Inhalt in den neuen, größeren Speicherbereich kopiert werden.
Es ist empfehlenswert, die Warteschlange in einem Speicherbereich konstanter Größe abzulegen. Dieser muss natürlich so dimensioniert sein, dass er nie zu klein ist. Eine einfache Abschätzung für die benötigte Größe ist die Anzahl theoretisch möglicher Zustände des Spielfelds. Dazu zähle man einfach die freien Felder, auf denen sich Spielfiguren aufhalten können, und nenne sie N. Mit ein wenig einfacher Kombinatorik ergibt sich dann eine Anzahl von N * (N - 1) * (N - 2) Zuständen.
Auswertung der Einsendungen
Zur Auswertung habe ich 15 Level-Vorlagen erzeugt. Diese enthalten aber nur die Mauern, also keine Spielfiguren oder Zielfelder. Anschließend habe ich aus jeder Vorlage ca. 1000 Levels erzeugt, indem ich die Spielfiguren und Zielfelder zufällig auf die freien Felder verteilt habe. Natürlich muss auch sichergestellt sein, dass das Level lösbar ist und auch mit höchstens 255 Zügen.
Die daraus entstandenen ca. 15000 Levels bilden den "Parcours", den jede eingesendete Lösung abarbeiten muss. Die dafür benötigte Zeit wird gemessen. Um die Auswirkung von Geschwindigkeitsschwankungen zu minimieren, wurden von jeweils 10 Durchläufen der schnellste gewertet. Natürlich habe ich alle Hintergrundprogramme beendet, den Energieplan auf "Höchstleistung" gestellt, dem Prozess Echtzeitpriorität gegeben und den PC währenddessen nicht benutzt.
Das Ganze wurde nun einmal mit dem GCC und einmal mit Visual C++ 2012 getestet. Das jeweils bessere Ergebnis zählt.
Ein paar Informationen über die erzeugten Levels: das Kürzeste ist mit 3 Zügen lösbar, das Längste mit 149. Im Durchschnitt benötigt man 30.51 Züge (Median = 28
). Mit jeweils 564 Levels waren die 24- und 25-Zug-Levels am häufigsten vertreten.
Es folgt das Ranking:
- David Scherfgen (jedoch außer Konkurrenz
): 29.6233 Sekunden (GCC) vs. 35.3933 Sekunden (MSVC)
Bidirektionale Suche, Lookup-Tabelle für Spielfigurbewegungen, Zustände in 24 Bits, +8 Bits für das Merken des letzten Zugs, verzahnte Bit-Arrays, konstant große Warteschlangen
- Helmut: 64.0664 Sekunden (GCC) vs. 60.479 Sekunden (MSVC)
Bidirektionale Suche, Lookup-Tabelle für Spielfigurbewegungen, Zustände in 24 Bits, eigene Bit-Arrays, große aber vergrößerbare Warteschlangen
- Stef: 438.926 Sekunden (GCC) vs. 426.633 Sekunden (MSVC)
Vorwärtssuche, Lookup-Tabelle für Spielfigurbewegungen, Zustände in 24 Bits, Byte-Array
- Schrompf: Leider war deine Einsendung fehlerhaft. Der erste Fehler trat bei Level 66 auf, wo als Antwort 0 ("unlösbar") geliefert wurde statt 55. Ich habe auch deine zuerst eingereichte Version mit Intrinsics getestet, aber auch dort trat dieser Fehler auf. Zudem hast du Funktionen und Klassen außerhalb der Funktion definiert, was eigentlich nicht erlaubt war.
Nach Korrektur des "Fehlers" (danke an Helmut für den Hinweis): 341.514 Sekunden (GCC) vs. 320.499 Sekunden (MSVC)
Vorwärtssuche, Zustände in 24 Bits, +8 Bits für das Merken des letzten Zugs, große aber vergrößerbare Warteschlangen
And the Winner is ...
... Helmut once again!
Herzlichen Glückwunsch zum 5. Sieg! Wenn das so weiter geht, muss ich mir etwas Neues für die Rang-Grafik einfallen lassen. Für deinen Preis muss ich mir noch etwas ausdenken.
Dass meine Lösung schneller ist, liegt sicherlich hauptsächlich daran, dass ich erst sehr spät die Rückwärtssuche eingebaut habe und daher die Vorwärtssuche bis zum "Geht-nicht-mehr" optimiert habe.
Ich bedanke mich bei allen für die Teilnahme!
Download der Einsendungen und des Auswertungsprogramms
Alle Einsendungen sowie mein Programm zur Auswertung könnt ihr im Anhang dieses Postings herunterladen.
Szene »
Global Game Jam 2013 Leizpig - Videoreviews der Ergebnisse
(29.01.2013, 23:05)
18.04.2024, 07:11
Zum Seitenanfang
