Du bist nicht angemeldet.

Werbeanzeige

Schrompf

Alter Hase

Beiträge: 1 403

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

91

03.03.2013, 19:54

Mich hat jetzt wie befürchtet der Ehrgeiz gepackt und ich widme mich nochmal dem Contest. Meine Errungenschaften der letzten zehn Minuten, ungeachtet der Gefahr, damit Konkurrenten auf neue Ideen zu bringen:

- std::vector durch eigene Klasse ersetzt, deren primäre Verbesserung ist, dass sie in push_back() nicht auf Vergrößerung prüft: 5% Verbesserung
- std::vector<bool> durch eigene Klasse ersetzt - 30% Verbesserung
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

Schrompf

Alter Hase

Beiträge: 1 403

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

92

04.03.2013, 00:51

Ok, ich geb auf. Hab mich leider in der Erprobung einer Tabelle verrannt und erst zwei Minuten nach Mitternacht gemerkt, dass ich besser erstmal die letzte funktionierende Version einreichen sollte. Ich hoffe, das ist noch ok. Danach hab ich mich wieder den Tabellen-Experimenten gewidmet. Und nach Korrektur einiger Dummheiten in der Tabellenerzeugung stellt sich nun heraus: das Programm ist damit deutlich langsamer als vorher.

Ich nutze hier eine Tabelle unsigned char[8192], in der ich die Rück-Reichweite nach links (untere 4Bit) und nach rechts (obere 4Bit) abgelegt habe. Ich wüsste nicht, wie ich diese Tabelle kleiner bekommen sollte. Nun läuft das Programm wieder korrekt, aber ist 30% langsamer als mein bestes Ergebnis vorher. Und das, obwohl die Tabelle stressfrei in den First Level Cache passen sollte und die untersten 128 Einträge statistisch am meisten auftreten sollten. Tja.

Jetzt ist es eh vorbei. Ich hätte gern noch ausprobiert, ob es was bringt, wenn man von der Zielposition aus rückwärts der Breitensuche entgegenkommt. Aber das wäre mindestens nochmal ne Stunde Arbeit, die ich mir nun wohl ersparen werde.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 297

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

93

05.03.2013, 12:36

Hi,

ich habe nun einige Test-Levels erzeugt, mit denen ich eure Einsendungen im Laufe der Woche auswerten werde.
Ich habe mir gedacht, dass jeder von euch, der etwas eingesendet hat (oder auch nicht) ein paar Levels beitragen darf.
Die Levels sollen aber "leer" sein, d.h. keine Spielfiguren und Zielfelder, da ich diese zufällig bestimmen werde.

Also wer Lust hat, darf mir Levels schicken!

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 297

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

94

08.03.2013, 16:52

OK, ich mache jetzt die Auswertung!
Gerade werden ca. 15000 zufällige Levels, basierend auf meinen manuell entworfenen Level-Templates, erzeugt.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 297

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

95

08.03.2013, 21:33

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:
  1. 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

  2. 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

  3. Stef: 438.926 Sekunden (GCC) vs. 426.633 Sekunden (MSVC)
    Vorwärtssuche, Lookup-Tabelle für Spielfigurbewegungen, Zustände in 24 Bits, Byte-Array

  4. 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. :grumble:
    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.
»David Scherfgen« hat folgende Datei angehängt:
  • Auswertung.zip (264,03 kB - 98 mal heruntergeladen - zuletzt: 15.01.2021, 13:11)

domin

1x Contest-Sieger

  • Private Nachricht senden

96

08.03.2013, 22:01

Erstmal Herzlichen Glückwunsch an Helmut!! :)
Echt toll gelöst !!

Ich bin leider nicht ganz fertig geworden... Da ich noch nicht so viel Erfahrung mit solch extrem optimierten Algorithmen habe, fing ich zuerst an die Sache ohne Brute Force zu lösen. Kurz vor dem Abgabetermin habe ich dann aber erkannt, dass es viel zu aufwändig ist das Ganze mit (künstlicher) Intellegenz zu lösen. So blieb mir aber dann leider zu wenig Zeit für die BruteForce Variante und ich hatte nichts zum Abgeben. :(

Aber beim nächsten Contest bin auf jeden Fall wieder am Start.
Meine Projekte:
LightBulb, TurtleRun

Helmut

5x Contest-Sieger

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

97

08.03.2013, 23:19

Hach David, jetzt hast du mich doch noch geschlagen :) Ich hab's ja schon fast geahnt. Und dann auch noch so deutlich. Wir hätten doch noch die Zeiten austauschen sollen, dann hätte ich mich nochmal rangesetzt :)
Naja, immerhin finde ich sind meine Makros hübscher :) Bei meinen musste ich nämlich nicht für jede Richtung den Code kopieren :) Die Idee die Richtung in der Queue zu speichern ist aber echt nicht übel. Da hätt' ich eigentlich auch drauf kommen müssen :)

Bei Schrompfs Code muss man übrigens nur diese Zeilen rausnehmen, dann ist der Code korrekt:

C-/C++-Quelltext

1
2
    if( anzZuege > 50 )
      break;
Ich vermute mal das hat er beim Debuggen benutzt und dann vergessen...

Meine Lieblingszeile kommt aber aus meinem eigenen Beitrag:

C-/C++-Quelltext

1
delete[] std::min(curStates, nextStates);

Ich mein, wie oft macht man schon sowas? :)
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

98

09.03.2013, 02:55

Und den nächsten Contest dann mal bitte nicht in meiner Prüfungszeit, dann mach ich auch mal wieder mit ;)
"Theory is when you know something, but it doesn’t work. Practice is when something works, but you don’t know why. Programmers combine theory and practice: Nothing works and they don’t know why." - Anon

stef

Treue Seele

Beiträge: 241

Wohnort: Kassel

Beruf: Softwareentwickler

  • Private Nachricht senden

99

09.03.2013, 09:08

Gratulation an Helmut !

Freue mich über einen (weit abgeschlagenen) zweiten Platz, aber bei mir galt eh nur der Olympische Gedanke :) .

An dieser Stelle auch mal ein herzliches Dankeschön an David für die investierte Zeit und Arbeit.
Schade das nur so wenig eingesendet haben.
"In C++ it's harder to shoot yourself in the foot, but when you do, you blow off your whole leg." — Bjarne Stroustrup.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 297

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

100

09.03.2013, 09:13

Ich habe jetzt den Fehler bei Schrompf korrigiert, danke an Helmut. Oben stehen die erreichten Zeiten, die etwas besser sind als die von Stef ;)

Helmut:
Ja, dein Code ist kürzer und eleganter.
Die delete-Zeile war mir auch schon aufgefallen, die ist echt lustig! :)

Werbeanzeige