Speedcube.de Forum

Unter den 100 Scrambles, die Linus mir geschickt hat, waren ein paar interessante dabei:

10. Scramble: U2 R2 D2 U2 R' B U' B' U' B2 U2 R' U2 B U B2


Die gefundene Lösung ist also genau das Inverse des Scrambles. Dieser Scramble ist vermutlich ein absoluter Einzelfall, aber die Frage bleibt trotzdem, was wäre, wenn ein solcher Scramble bei FMC Europe oder einer ähnlichen Competition vorkäme. 


17. Scramble: B' D2 R2 B2 D2 F R2 F D B' U2 F2 L2 D F' R' D' B2 D

Wie suchst du eigentlich die Insertions? Die kannst du ja nicht komplett über die Tabelle auslesen, da Insertions ja 8-12 Züge brauchen.

(24.02.2016, 19:35)AKOM schrieb: [ -> ]da Insertions ja 8-12 Züge brauchen.

Nein? Normale Corner-Kommutatoren haben immer 8 Moves.
Und nachdem er momentan nur nach L3C oder L5C sucht benötigt er ja nicht mehr als die.

(24.02.2016, 18:41)Fritz schrieb: [ -> ]Es werden überhaupt keine Lösungen "verkauft", da außer mir und dem Betreuer meiner Bachelorarbeit keiner Zugriff auf den Solver hat. Ich vermute, dass der Lehrstuhl später gerne eine Verison des Solvers auf seine Seite hätte, allerdings in einer Abwandlung, die mehr auf eine garantiert relativ geringe Laufzeit ausgelegt ist als auf besonders kurze Lösungen. Bevor irgendetwas in diese Richtung passiert, werde ich mich sowieso noch mal ein paar Leute wenden, um mögliche Auswirkungen zu besprechen.

"das hat etwas von" != "du machst das"
Und du hast konkret WCA Competitions erwähnt. Was nun genau mit deinem Solver passiert, ist ja erst einmal egal. Du sagst, was es aus deiner Sicht für Auswirkungen hätte, ich beantworte das mit meiner langfristigen Sicht der Dinge aus Perspektive der WCA.

Zitat:

(24.02.2016, 17:08)Laura schrieb: [ -> ]Langfristig wird das dazu führen, dass die Bedingungen in Competitions deutlich strenger und für Teilnehmer unangenehmer werden.

Inwiefern?

Siehe unten, insbesondere Smartphones am Körper verbieten bzw. von Delegates einsammeln lassen und Toilettengänge verbieten.

Zitat:

Zitat:E3) The competitor may use the following objects during the attempt. Penalty for using unauthorised objects: disqualification of the attempt (DNF).
   E3a) Paper and pens (both supplied by judge).
   E3b) Rubik's Cubes (at most 3, self-supplied), as described in Article 3.
   E3c) Coloured stickers (self-supplied).
   E3d) Stopwatch or watch (self-supplied) for keeping track of the elapsed time, if it is approved by the WCA Delegate.

Ich kann dort nichts finden, was einen Gang zur Toilette während eines Attempts erlauben würde.

Was genau ist die Logik hinter dieser Schlussfolgerung? Was nicht explizit erlaubt ist, ist verboten?
Da steht auch nicht drin, dass ich während FMC ein grünes T-Shirt tragen darf. Es ist trotzdem erlaubt.

Die einzige Interpretation, die hier noch sinnvoll wäre, wäre dass hier kein Klopapier (oder was auch immer man so dabei benutzt) als erlaubter Gegenstand aufgelistet ist. Aber naja...

Zitat:Meiner Meinung nach sollte ein teilnehmer seinen Attempt in diesem Fall vorzeitig beenden müssen. ich erinnere mich in dieser Hinsicht auch gut an eine Franconia Open, bei der Björn Markus Pirzer die Teilnahme an FMC verweigerte, weil dieser ein paar Minuten zu spät kam.

Und was ist der Zusammenhang hier?
Deine Meinung wie es sein sollte, ist nicht relevant. Ich schrieb, dass es *manchmal* kein Problem ist, zur Toilette zu gehen. Ebenso haben manche Delegates kein Problem damit, wenn Teilnehmer zu spät kommen, zumindest wenn bisher niemand seinen Attempt beendet hat. Die meisten dieser Situationen werden als "at the discretion of the WCA Delegate" gehandhabt.

Zitat:Einerseits ist es zur Zeit ja erlaubt, elektronische Geräte während eines Attempts am Körper zu tragen, so lange man diese nicht benutzt. Andererseitsist es auch jetzt schon notwendig, während FMC darauf zu achten, dass niemand sein Smartphone zum Cheaten benutzt (JARCS, Insertion Finder).

Korrekt. Allerdings ist die Erarbeitung von Solutions mit JARCS deutlich aufwändiger und führt nicht zu einer vollständigen FMC-typischen Lösung. Letzteres gilt für den Insertion Finder genauso. Dafür braucht man eben erst einmal ein Skeleton.

Ich habe alle 864 Corner-Kommutatoren mit Länge 8 in einer Tabelle. Bei allen gefundenen skeleotns, die tatsächlich überprüft werden, ermittle ich, wie die 3 oder 5 Corners getauscht werden müssen und berechne dann vor und nach jedem Moves des Skeletons, welches Ergebnis ein Kommutator liefern müsste. Falls einer oder mehrere dazu passen, wird überprüft, ob diese mindestens so viele Moves canceln, dass das bisher beste Zwischenergebnis erreicht wird.

Ein Beispiel:

Nach L5C gibt es folgende Ergebnisse: Ein Skip in 21 Moves, L3C in 16, 17, 18 und 24 Moves, L5C in 15 und 22 Moves.
Der Skip gibt 21 als Obergrenze vor, sodass alle anderen Skeletons mit mehr als 21 Moves nicht mehr berücksichtigt werden. Zuerst werden die L3C in aufsteigender Länge gelöst. Das L3C in 16 liefert eine Lösung mit 17 Zügen, wodurch danach nur nur L3C und L5C bis zur Länge 17 betrachter werden. Das L3C in 17 liefert nur eine 24 und wird deshalb gar nicht als Lösung geschrieben. Die L3C in 18 und 24 werden ignoriert. Danach wird nur noch das L5C in 15 geprüft. Es werden nur die Insertions verfolgt, die zu L3C in 17 oder weniger führen.

(24.02.2016, 19:45)Fritz schrieb: [ -> ]Ich habe alle 864 Corner-Kommutatoren mit Länge 8 in einer Tabelle. Bei allen gefundenen skeleotns, die tatsächlich überprüft werden, ermittle ich, wie die 3 oder 5 Corners getauscht werden müssen und berechne dann vor und nach jedem Moves des Skeletons, welches Ergebnis ein Kommutator liefern müsste. Falls einer oder mehrere dazu passen, wird überprüft, ob diese mindestens so viele Moves canceln, dass das bisher beste Zwischenergebnis erreicht wird.

Ein Beispiel:

Nach L5C gibt es folgende Ergebnisse: Ein Skip in 21 Moves, L3C in 16, 17, 18 und 24 Moves, L5C in 15 und 22 Moves.
Der Skip gibt 21 als Obergrenze vor, sodass alle anderen Skeletons mit mehr als 21 Moves nicht mehr berücksichtigt werden. Zuerst werden die L3C in aufsteigender Länge gelöst. Das L3C in 16 liefert eine Lösung mit 17 Zügen, wodurch danach nur nur L3C und L5C bis zur Länge 17 betrachter werden. Das L3C in 17 liefert nur eine 24 und wird deshalb gar nicht als Lösung geschrieben. Die L3C in 18 und 24 werden ignoriert. Danach wird nur noch das L5C in 15 geprüft. Es werden nur die Insertions verfolgt, die zu L3C in 17 oder weniger führen.

Ok, Danke.
Die Lösung für die 864 Corner-Kommutatoren hast du per Bruteforce ermittelt?

Die Liste mit den 864 Kommutatoren hab ich vom Insertion Finder, deren Ergebnisse dann schnell mit nem kleinen Skript ermittelt.

(24.02.2016, 19:39)Linus F schrieb: [ -> ]

(24.02.2016, 19:35)AKOM schrieb: [ -> ]da Insertions ja 8-12 Züge brauchen.

Nein? Normale Corner-Kommutatoren haben immer 8 Moves.
Und nachdem er momentan nur nach L3C oder L5C sucht benötigt er ja nicht mehr als die.

Ok, ich ging von den L3C-Algos für den LL aus, war totaler Unsinn.

Ich habe nochmal etwas über das Ganze nachgedacht und hätte interessehalber noch mal ein paar Fragen zu der Umsetzung:

Zitat:Aus der Pruning Table werden dann alle Zugfolgen gelesen, die diesen Block lösen.

Liest du die Zugfolgen tatsächlich direkt aus der DB aus oder werden die vorher in einen Baum/Hashtable o.Ä. geladen?
Wie findest du heraus, ob eine Zugfolge im Pruning-Table das Problem löst? Wendest du das Ergebnis der Zugfolge auf deinen Scramble an und prüftst dann, ob ein 222-Block entstanden ist? Oder durchsuchst du den 222-Block-Teil der Ergebnisse der Zugfolgen direkt nach dem Inversen des gescrambelten 222-Blocks (bzw. umgekehrt, du suchst nach dem Scramble und invertierst danach)? Oder ganz anders?

Zitat:Auf allen gefundenen nicht-redudanten (d.h. kein Präfix der gefundenen Zugfolge löst den Block bereits) Blöcken wird wie beim 2x2x2 gesucht, wie ein 2x2x3-Block gelöst werden kann. Analog wird auf 2x2x3 nach wegen zum F2L-1 und vor dort zu einem Skeleton, das alles bis auf höchstens 5 Corners gelöst hat, gesucht.

Für den 223-Block probierst du alle N 222-Blöcke durch, suchst du dann das F2L-1 auf N 223-Blöcken oder sind es danach mehr als N 223-Blöcke, weil jeweils noch verschiedene Lösungswege von 222 nach 223 betrachtet werden?

Die Zugfolgen werden jedes mal aus der DB gelesen. Grad zum Lösen der 2x2x2 erscheint mir das sinnvoll, da es dort immer nur genau 8 einzelne Abfragen sind und die Pruning Tables mit jeweils ca. 1 million Einträgen noch recht groß sind. Für den Schritt F2L-1 zu L5C ist allerdings geplant, die nur noch 316 möglichen Zugfolgen zu Beginn des Schritts in einem Array zu definieren.

Wenn ich einen bestimmten Schritt lösen will, gelten jedes mal ein paar Enschränkungen: Bei 2x2x2 sind nur genau 4 Pieces zu lösen. Ausgehend vom gegebenen Zustand des Cubes berechne ich, wie sich die Position dieser 4 Pieces ändern muss, damit sie gelöst werden. Darauf basiernd wird dann eine SQL-Abfrage erstellt, die genau die Zugfolgen liefert, die diese 4 Pieces lösen. Für spätere Schritte gilt dann noch die Einschränkung, dass bereits gelöste Pieces nicht mehr verändert werden. Deshalb gibt es für jeden Lösungsschritt eigene Pruning Tables, die nur die Zugfolgen enthalten, die die ab diesem Schritt bereits gelösten Pieces nicht mehr ändert. Um nicht für jeden einzelnen möglichen 2x2x2, 2x2x3 und F2L-1-Block extra Pruning Tables anlegen zu müssen, macht der Solver zwischen den Schritten ein paar Cube Rotations, so dass immer nur Blöcke an ein und der selben Position gelöst werden müssen.

Die einzelnen Lösungsschritte werden immer jeweils als Ganzes ausgeführt. Es werden erst alle 8 2x2x2-Blöcke gelöst. Dabei wird für jeden der 8 2x2x2 alle Zugfolgen gesucht, die ihn lösen. Für jede Zugfolge wird ermittelt, wie das ergebnis danach aussieht und welche Daten geschrieben werden sollen. Am Ende werden alle gefundenen 2x2x2 auf ein mal geschrieben.

Für 2x2x3 werden alle 2x2x2 gelesen und für jeden Einzelnen wird ermittelt, welche Zugfolgen aus dem 2x2x2 ein 2x2x3 machen. Für jede gefundene Zugfolge wird das Ergebnis am Cube ermittelt und die bisherige Lösung wird auf Cancellations geprüft. Für F2L-1 und L5C geht es ähnlich weiter.

Zur Zeit ist noch nichts mit inversen Scrambles oder NISS implementiert. Für die Lösungen auf inversen Scrambles habe ich den Scramble selbst invertiert und als neuen Scramble lösen lassen.

Zur letzten Frage: Es kann durchaus passieren, dass es sehr viele Möglichkeiten gibt, einen 2x2x2-Block zu einem 2x2x3 zu erweitern. Auf dem zuletzt getesteten Scramble gab es 108 2x2x2, darauf 3974 2x2x3, darauf 19516 F2L-1 und darauf 2258 L3C/L5C/Skips. Dem starken Anstieg von 2x2x3 zu F2L-1 könnte ich jetzt schon begegnen, indem ich vom Solver fordere, nur 2x2x3 zu finden, die höchsten s0, 2, 4 oder 6 bad Edges haben.