Slippery - Test fuer beste Loesungen

[TGGC]

Einige haben bestimmt schon von meinen neuen Mini-Spiel gehoert:
http://games-net.de/hosted/tggc/scores/ ... online.php

Ich suche nun fuer alle Level nach der besten Loesung um, damit ich diese fuer eine spaetere Version nochmal anpassen/ reparieren kann. Falls ihr also in irgendeinem Level findet, das die vorgegebenen Zuege nicht komplett ausgenutzt werden, selbst wenn ihr alle Mitspieler (graue Faesser) entfernt, dann zeigt doch mal eure Loesung hier. Ihr koenntet entweder Screenshots machen und Pfeile einzeichnen, oder ihr beschreibt einfach, z.b. "Block nach links, oben, rechts".

[Despotist]

Mal eine sehr blöde Frage aber würde es sich gerade dafür nicht anbieten eine Routine zu schreiben die alle möglichen Lösungen durchprobiert? Die Anzahl der Züge sowie die Anzahl der möglichen Aktionen ist relativ begrenzt und du könntest die Logik des Spiels direkt verwenden. Geht wahrscheinlich schneller als wenn einige Leute Screenshots bemalen und posten. Außerdem könntest du die Routine zum prüfen aller neuen Level nehmen um automatisch zu testen ob sie überhaupt machbar sind. Das wird gerade interessant wenn du vorhast mal einen Leveleditor zu veröffentlichen und sich jeder daran probieren kann. Falls ich was übersehe nichts für ungut.

[TGGC]

Der Problemraum kann nach wenigen Zuegen (etwa 10) so gross sein, das er nicht mehr komplett im Speicher abgebildet werden kann. Man kann also wirklich per Bruteforce einfachere Probleme loesen, aber nicht im Allgemeinen. Wenn du z.b. 3 vollbewegliche Steine plus den normalen Spieler hast, dann hast du bis zu 16 Zugmoeglichkeiten, das sind nach 7 Zuegen schon 16 ^ 7 Stellungen. Speichere ich nur 8 Byte (jeweils die x/y Positionen der Steine) fuer jede Stellung, sind das allein bereits 2GB.

[Alexander Kornrumpf]

Wer sagt denn dass du den kompletten Problemraum zur gleichen Zeit im Speicher halten musst?

[TGGC]

Niemand. Aber wenn du ihn speicherst und wieder laedst, dann bekommst du keine Loesung in annehmbarer Zeit.

[Despotist]

Das habe ich mich auch gefragt aber dachte ich hab was übersehen.

Ein weiterer Vorteil wäre dass du alle möglichen Lösungen kennst und so zb auch verschiedene Punkte/Boni udg je nach Schwierigkeit verteilen kannst. Du könntest auch anbieten den Level nochmal zu spielen um eine andere Lösung zu finden. Oder eben die von mir schon Vorgeschlagene Hilfeoption wenn jemand wirklich hängt.

Ob du die Zeit aufwendest musst du natürlich selbst wissen.

[Alexander Kornrumpf]

Ich denk gerade so an klassisch Depth First Search.

Wenn du die möglichen Züge in einem Zst. systematisierst (zugnr = steinnr*4 + richtungsnr) brauchst du ca. 1 byte pro Suchtiefe um dir zu merken welche Züge du in dieser Tiefe bereits gemacht hast. Du pflegst nur den aktuellen Zustand. Bei advance merkst du dir (startpos, endpos) bei retreat stellst du damit den Ausgangs zst wieder her. Da du bei slippery maximal ~20 mal advancen kannst bevor dir die züge ausgehen, brauchst du dafür ca. 100byte + den Callstack der auch entsprechend klein bleibt. Das plus Speicher für das Level und den aktuellen Zst. sollte locker unter 10K bleiben.

Ich sage nicht dass es schnell ist auf die Weise ca. 1M bis 1G Zustände zu durchsuchen. Aber Speicher wird dabei das kleinste Problem sein. Und da du die Zustände ja auch erstmal erzeugen müsstest um sie im Speicher zu haben (warum auch immer du das wolltest) ist diese Lösung sicher nicht wesentlich teurer als irgendeine Lösung die dir vorschwebte die davon ausging, dass die Zst im Speicher vorhanden sind.

[TGGC]

Du hast recht, so ginge es. An die Methode hatte ich gar nicht weiter gedacht, sondern gleich verworfen, die duerfte zu langsam sein, weil sie einige Nachteile hat. Erstmal brauchst du irgendeine Beschraenkung des Baumes, da du sonst unendlich absteigst, und ueber das was nach der Begrenzung passiert, hast du keine Aussage. Das waere aber hier nicht so schlimm, da ich ja Naehrungsloesungen kenne. Dann muss dein Algorithmus ganz dumm wirklich den komplette Baum durchgehen. Erstmal kann man nie wissen kann, ob man spaeter noch was findet, also irgendwo abbrechen geht nicht. Und man kann auch nicht wissen, ob die aktuelle Situation schon behandelt wurde, denn man kennt die anderen Stellungen nicht, also muessen auch Sinnlosikeiten ala "links rechts links rechts" abgesucht werden. Zudem sind ohnehin wesentlich mehr Situationen zu behandeln, wenn die Begrenzung nicht stimmt. Also z.b. 20 Zuege Limit, aber richtige Loesung ist 16. Bei 20 musst du 16^4=65000 (Beispiel von oben) mal mehr Stellungen untersuchen, als wenn 16 dein Limit ist.

Eigentlich wollt ich nur darauf hinaus, das einige ehh schon bei manchen Level angedeutet hatten, das sie Zuege uebrig hatte. Ich wollte das jetzt einfach nur sammeln. Aber der Quellcode ist offen, baut euch halt einen Loeser, bei einigen Leveln sollte der funktionieren.

[Helmut]

Hi TGGC,
Level 31 kann man mit 5 Zügen weniger lösen. Versuch doch mal selbst drauf zu kommen. Dann weißt du wie es ist, dein Spiel zu spielen ;)

Lösung:

Den oberen beweglichen Block nicht anfassen. So kommt man sehr schnell drauf ;)

Ciao
Helmut

[TGGC]

@Helmut:
Ich habe natuerlich alle meine Level gespielt (der Editor hat sogar eine Spielfunktion, die den Server und mehrer Mitspieler simulieren kann), manche Level habe ich danach dann nochmal angepasst oder die Zugzahl entsprechend angegeben. Darum kann ich eben auch nicht garantieren, das vieles nicht noch schneller geht.

[Alexander Kornrumpf]

Ich sage ja nicht dass es schnell ist, nur dass a) es den Speicher nicht braucht und b) jede Lösung die alles im Speicher braucht erst dasselbe tun müsste um den Speicher zu füllen und dann noch etwas anderes und somit noch langsamer wäre.

Aber:

Die meisten slippery Level die ich gesehen habe hatten Zuglimits die deutlich kleiner als 20 waren.

Du hast auch nicht immer den vollen Branching Faktor, da Steine ziemlich häufig am Rand landen, sodass sie sich in die Richtung nicht mehr bewegen können, einige Kisten sich von vornherein nur in eine Richtung bewegen können oder einfach weniger Kisten existieren.

Da man in jedem Zst. den Zug kennt, der in ihn hinein geführt hat, muss man die Kinder des Umkehrzugs natürlich nicht untersuchen. (Also fällt ein Großteil der von dir genannten Sinnlosigkeiten de Fakto doch weg). So werden aus deinen z.B. 16^7 Zügen dann ohne Aufwand schon mal 16*15^6.

Für die letzten beiden Züge kannst du eine earlystop Heuristik einbauen, nämlich dann wenn Der Spielstein noch x und y Versatz zum Ziel hat, dann gehen die Züge auf jeden Fall dafür drauf diesen Versatz zu kompensieren, und es macht keinen Sinn mehr Kisten zu bewegen. Es gibt dann nur noch zwei mögliche Zugfolgen: erst x, dann y oder erst y dann x.

Ja selbst Tabu-Search auf den obersten Leveln (wo es am meisten bringt) könnte hier schon etwas weiterhelfen. Wenn du Speicher (least recent cache) für 4096 bis 65536 Zustände nahe der Wurzel + Anzahl der Züge die in diesen Zst. geführt haben investierst und du kommst in gleichvielen oder mehr Zügen in einen solchen Zustand kannst du den gesamten Baum darunter wegwerfen. Somit filterst du effektiv die Permutationen der ersten 3-4 Züge. Schachprogramme machen das ja auch mit Eröffnungsdatenbanken.

Was vermutlich eher selten passieren wird, da die Level per Design so sind, aber auch eine gratis Optimierung ist, ist das Zuglimit herunterzusetzen, sobald eine Lösung in sovielen Zügen gefunden wurde, da man dann nur noch an kürzeren Lösungen interessiert ist.

Damit dürften viele der Level beherrschbar werden.

[TGGC]

Von mir aus, probier es. Ich glaub aber nicht, das es was bringt, hatte ja schon ueber das Feature im Leveleditor nachgedacht.

Wenn du nicht alle Zuege ausprobierst, musst du vorher testen, welche Zuege jetzt direkt gegen die Wand gehen und welche nicht. Links rechts fuehrt selten in den Zustand der davor herrschte, oft aber in den gleichen wie rechts. Und ohne Aufwand ist die Pruefung auch nicht, sie muss gemacht werden. Dabei faengt sie nur einen Bruchteil ab. Alles wo mehr als 2 Zuege oder austauschbare Zuege (erst Stein A ziehen, dann Stein B oder umgekehrt?) in den selben Zustand fuehren, kann niemals erkannt werden und der Baum dahinter wird mehrfach untersucht. Deine Heuristik gilt nur wenn keine Pfeile da sind. Und sie hat auch nichts damit zu tun, ob man Zustaende speichert oder nicht, sie macht das Loesen allgemein ein kleines bisschen leichter. Wirklich vereinfachen kannst du mit all dem Getrickse nichts, das Problem bleibt weiter exponentiell.

[Alexander Kornrumpf]

Links rechts fuehrt selten in den Zustand der davor herrschte, oft aber in den gleichen wie rechts.

Ja und rechts wird ja untersucht.

Wenn du nicht alle Zuege ausprobierst, musst du vorher testen, welche Zuege jetzt direkt gegen die Wand gehen und welche nicht. Und ohne Aufwand ist die Pruefung auch nicht, sie muss gemacht werden. Dabei faengt sie nur einen Bruchteil ab.

Entschuldige mal, aber es ist ja wohl billiger eine Prüfung durchzuführen, als den Gesamten Unterbaum zweimal zu durchsuchen. Je größer der Unterbaum desto mehr bringt es. Wenn du auf oberster Ebene einen Zug ausschließen kannst, sparst du dir in deinem Bsp. 1/16 aller Berechnungen. Das ist ein großer Bruchteil.

Alles wo mehr als 2 Zuege oder austauschbare Zuege (erst Stein A ziehen, dann Stein B oder umgekehrt?) in den selben Zustand fuehren, kann niemals erkannt werden und der Baum dahinter wird mehrfach untersucht.

Wie gesagt weit oben im Baum bringt es viel es abzufangen und ist leicht. Ich schrieb vorhin missverständlich "bei den höheren Leveln" und meinte damit weit oben im Baum und nicht weit hinten im Spiel.

Deine Heuristik gilt nur wenn keine Pfeile da sind.

Ok, hab ich nicht bedacht. Für den letzten Zug gilt dennoch dass er den Spielstein betreffen muss. Allgemein ist es überdies wahrscheinlich sinnvoll erst die züge durchzuprobieren die den Spielstein betreffen, sodass nicht eine unsinnige Kiste bewegt wird obwohl es reichen würde den Spieler zu bewegen. Das dürfte extrem viel bringen.

Und sie hat auch nichts damit zu tun, ob man Zustaende speichert oder nicht, sie macht das Loesen allgemein ein kleines bisschen leichter.

Habe ich etwas anderes behauptet?

Wirklich vereinfachen kannst du mit all dem Getrickse nichts, das Problem bleibt weiter exponentiell.

Asymptotisch korrekt, aber hier geht es darum ob mit heutiger consumer-grade Hardware die vorhandenen slippery Level vollständig lösbar sind. Und da könnte getrickse schon was helfen.

[RustySpoon]

Hashtabellen um den Baum zu einem Graphen zu degenerieren - und wenn man einmal dabei ist Hashtabellen zu integrieren: Bidirektionale Suche - tun ihr Übriges. Einfach mal schauen was da insbesondere speichermäßig geht, würde mich auch mal interessieren. :) Achja, iterative Tiefensuche ist auch fein, wenn du nicht sowieso vorhast, den kompletten Suchraum abzugrasen.

[TGGC]

Warum fuehre ich die Diskussion ueberhaupt? Hast du vor so einen Loeser zu bauen, nein, du breitest hier nur Theorien aus, die fuer mich uninteressant sind.

Ja und rechts wird ja untersucht.

Ja, und links rechts auch, sowie noch zig andere Permutationen, die alle zum gleichen Zustand fuehren, darum untersucht DFS viel mehr als noetig.

Das ist ein großer Bruchteil.

Und genau darauf bezog sich der kleine Bruchteil, den du mit deinen Sonderpruefungen abfangen willst.

Entschuldige mal, aber es ist ja wohl billiger eine Prüfung durchzuführen, als den Gesamten Unterbaum zweimal zu durchsuchen.

Ja "eine Prüfung durchzuführen" ist schneller "als den Gesamten Unterbaum zweimal zu durchsuchen." Du hast aber behauptet das waere "ohne Aufwand", die Pruefung ist aber ein Aufwand.

Je größer der Unterbaum desto mehr bringt es. Wenn du auf oberster Ebene einen Zug ausschließen kannst, sparst du dir in deinem Bsp. 1/16 aller Berechnungen.

Wenn deine ganzen Pruefungen die Berechnungen pro Schritt nur doppelt so lang machen, dann brauch dein Algorithmus danach also nur noch 2 * 15 /16 der Zeit?

Alles wo mehr als 2 Zuege oder austauschbare Zuege (erst Stein A ziehen, dann Stein B oder umgekehrt?) in den selben Zustand fuehren, kann niemals erkannt werden und der Baum dahinter wird mehrfach untersucht.

Wie gesagt weit oben im Baum bringt es viel es abzufangen und ist leicht. Ich schrieb vorhin missverständlich "bei den höheren Leveln" und meinte damit weit oben im Baum und nicht weit hinten im Spiel.

Allgemein ist es überdies wahrscheinlich sinnvoll erst die züge durchzuprobieren die den Spielstein betreffen, sodass nicht eine unsinnige Kiste bewegt wird obwohl es reichen würde den Spieler zu bewegen. Das dürfte extrem viel bringen.

Unsinn. Du musst ja trotzdem alle Zuege mit allen Kisten durchprobieren. Selbst wenn du komplett ohne Kiste eine Loesung finden wuerdest - wie beweist du, das dies die kuerzeste sein koennte?

Und sie hat auch nichts damit zu tun, ob man Zustaende speichert oder nicht, sie macht das Loesen allgemein ein kleines bisschen leichter.

Habe ich etwas anderes behauptet?

Warum schreibst du es dann unter ein grosses "Aber", das sich offensichtlich darauf bezieht, warum man Zuege nicht speichern muss?

Asymptotisch korrekt, aber hier geht es darum ob mit heutiger consumer-grade Hardware die vorhandenen slippery Level vollständig lösbar sind. Und da könnte getrickse schon was helfen.

Ja, es koennte aber auch schaden.

@RustySpoon: Man kann Slippery nicht rueckwaerts spielen ohne das es dann wesentlich aufwendiger wuerde.

[Alexander Kornrumpf]

Warum fuehre ich die Diskussion ueberhaupt? Hast du vor so einen Loeser zu bauen, nein, du breitest hier nur Theorien aus, die fuer mich uninteressant sind.

Keine Ahnung, woher soll ich wissen warum du die Diskussion führst?

Ja, und links rechts auch, sowie noch zig andere Permutationen, die alle zum gleichen Zustand fuehren, darum untersucht DFS viel mehr als noetig.

Dann kannst du genauso behaupten, dass dein Speichern von 16^7 Zuständen viel mehr Zustände speichert als nötig, da ja viele von denen auch mehrfach vorkommen würden.

Du hast aber behauptet das waere "ohne Aufwand", die Pruefung ist aber ein Aufwand. Wenn deine ganzen Pruefungen die Berechnungen pro Schritt nur doppelt so lang machen, dann brauch dein Algorithmus danach also nur noch 2 * 15 /16 der Zeit?

Oh ich ging davon aus dass die "ich liege an einer Wand Prüfung" ohnehin durchgeführt werden muss, wenn der Zug gemacht wird um zu prüfen ob es überhaupt ein gültiger Zug ist. Ich habe es gerade extra ausprobiert. Wenn der Stein links eine Wand hat und ich drücke Links, kostet das keinen Zug. Die andere Prüfung (kenne ich den Zst. schon) wollte ich, wie ich nun schon zum drittenmal schreibe nicht in jedem Schritt sondern nur in den oberen Ebenen des Baumes veranstalten, da wo das Verhältnis zwischen Aufwand und möglichem Nutzen am günstigsten ist.

Unsinn. Du musst ja trotzdem alle Zuege mit allen Kisten durchprobieren. Selbst wenn du komplett ohne Kiste eine Loesung finden wuerdest - wie beweist du, das dies die kuerzeste sein koennte?

Hab ich doch schon gesagt. Der Letzte Zug muss immer der Spieler sein. Da ich nicht weiß ob der folgende Zug der letzte ist, sollte ich immer zuerst probieren den Spieler zu ziehen. Wenn ich dann eine Lösung finde brauche ich in Zukunft nur nach nach Lösungen suchen die kürzer sind. Ich kann alle weiteen Teilbäume früher abschneiden. Und da liegt die mögliche Ersparnis. Beachte bitte auch dass die Änderung der Suchreihenfolge tatsächlich nicht mehr kostet. Die Prüfung ob es eine Lösung ist muss auch in jedem Schritt ohnehin gemacht werden.

Warum schreibst du es dann unter ein grosses "Aber", das sich offensichtlich darauf bezieht, warum man Zuege nicht speichern muss?

Eigentlich bezog sich das "aber" darauf, dass es komplex ist _aber_ in dem konkreten Fall eventuell trotzdem lösbar ist.

Ja, es koennte aber auch schaden.

Ja könnte. Wir wissen es nicht. Du behauptest einfach dass es nicht geht.

[TGGC]

Dann kannst du genauso behaupten, dass dein Speichern von 16^7 Zuständen viel mehr Zustände speichert als nötig, da ja viele von denen auch mehrfach vorkommen würden.

Darum ~10.

Oh ich ging davon aus dass die "ich liege an einer Wand Prüfung" ohnehin durchgeführt werden muss, wenn der Zug gemacht wird um zu prüfen ob es überhaupt ein gültiger Zug ist. Ich habe es gerade extra ausprobiert. Wenn der Stein links eine Wand hat und ich drücke Links, kostet das keinen Zug.

Muessen tut keiner, es ist ein normaler Zug, der einfach 0 Felder weit geht. Spiel kann aus Benutzerfreundlichkeit. Loeser brauch nicht.

Die andere Prüfung (kenne ich den Zst. schon) wollte ich, wie ich nun schon zum drittenmal schreibe nicht in jedem Schritt sondern nur in den oberen Ebenen des Baumes veranstalten, da wo das Verhältnis zwischen Aufwand und möglichem Nutzen am günstigsten ist.

Und die Pruefung "ist obere Ebene"?

Die Prüfung ob es eine Lösung ist muss auch in jedem Schritt ohnehin gemacht werden.

Nein, nur wenn der Spieler gezogen wurde.

Ja könnte. Wir wissen es nicht. Du behauptest einfach dass es nicht geht.

Machs halt, oder laber weiter...

[RustySpoon]

Vielleicht können wir die Diskussion hier mal wieder etwas entgiften, im Kern ist die nämlich durchaus interessant.

TGGC, kannst du vielleicht mal paar Screenshots der schwierigeren Levels (also bezüglich des korrespondierenden Suchraums) posten und angeben wieviele Spieler zur Lösung notwendig sind, damit man als Außenstehender einen Eindruck davon bekommt, über welchen Grad an Komplexität wir hier diskutieren. Ich bin nämlich leider auch nicht allzuweit mit spielen gekommen.

Du erwähntest, dass du eine Möglichkeit hast, die Welt und Aktionen zu simulieren. Könntest du in der Richtung ggf. irgendetwas veröffentlichen, so dass man deine Spiellogik/Kartenimporter etc. nicht zwangsläufig neu implementieren müsste, sollte man vorhaben tatsächlich einen Slippery-Solver zu bauen?

[TGGC]

Slippery ist doch quellenoffen, daher kann jeder so einen Loeser dazu bauen. Wuerde mich interessieren, wessen Bot am weitesten kommt.
Sieht dann z.b. so aus:

[Alexander Kornrumpf]

Die Multiplayerlevel verhindern wohl das ein (dummer) Bot das Spiel löst. Bzw. sie erfordern noch mal eine eigene Logik die ein wenig komplizierter sein wird, als das was bislang hier diskutiert wurde.

Und die Pruefung "ist obere Ebene"?

Auf welcher Ebene man ist muss auch ohnehin überprüft werden da dies die Abbruchbedingung ist. Ja man hätte dann einen branch mehr. Aber ich dachte darin sind moderne Compiler und Prozessoren so toll. Würde mich wundern wenn das ernsthaft ins Gewicht fallen würde.

Nein, nur wenn der Spieler gezogen wurde.

Und die Prüfung ob der Spieler gezogen wurde? Dein Argument!

[RustySpoon]

Slippery ist doch quellenoffen, daher kann jeder so einen Loeser dazu bauen. Wuerde mich interessieren, wessen Bot am weitesten kommt.

Ah danke, war mir irgendwie entgangen. Könntest du noch ein paar Levels freigeben, vielleicht bastel ich tatsächlich mal so einen Solver?

[TGGC]

Code zum Einladen der Level sollte auch dabei sein. Wenn du aber irgendwas Spezielles zum Testen brauchst, koennte ich dir sicher auch was basteln.