Speedcube.de Forum

Hallo Speedcuber,

Im Rahmen meiner Bachelorarbeit in Informatik arbeite ich zur Zeit an einem FMC-Solver. Ziel ist es, möglichst gute Lösungen zu finden, die auch von Menschen gefunden werden können. Nachdem der Solver seit einigen Tagen in der Lage ist, Lösungen auszugeben und die ersten Tests durchaus erfreuliche Ergebnisse geliefert habee, ist es nun an der Zeit, die gefundenen Lösungen auf ihre Plausibilität hin zu testen, d.h. ob ein Mensch diese Lösungen auch tatsächlich hätte finden können.

Meine Idee dazu ist folgende: Jeden Freitagabend, sobald es neue Scrambles für die FMC-Challenge gibt, werde ich die vom Solver gefundenen Lösungen für die Scrambles der Vorwoche hier als "FMC-Bot" posten. Meine bitte an Euch ist, dass Ihr einen kurzen Blick auf die Lösungen werft und schreibt, was Ihr von den Lösungen haltet. Hätte man die Lösung innerhalb des Limits finden können? Wärt Ihr stutzig geworden, wenn jemand diese Lösung im Rahmen eines Wettbewerbs gepostet oder gar bei einer Competition abgegeben hätte?

Gerne könnt Ihr mir auch Scrambles (auch mit Lösungsansätzen) schicken, die ich mit dem Solver testen soll.

Ich bin mir relativ sicher, dass diejenigen, die ich bisher noch nicht in die Entwicklung des Solvers eingeweiht hatte, ein paar der folgenden Fragen haben.

Warum?
 
Weil ich ein Thema für eine Bachelorarbeit gebraucht habe, FMC sehr mag und es mich bei FMC oft gestört hat, wenn bei einem Scramble Zeitlimit oder fehlende Geduld dazu geführt haben, dass ich nicht alle Möglichkeiten des Scrambles testen konnte. Und nicht zuletzt war und bin ich neugierig, wie weit man FMC algorithmisieren kann und was für Lösungen so erreicht werden können.

Wie funktioniert der Solver?

Der Solver ist in PHP programmiert und läuft auf einem Server mit 4GB RAM. In einer MySQL-Datenbank sind alle 8.3 millionen Permutationen bis zu 6 Zügen Länge in HTM gespeichert (Zugfolge und deren Ergebnis auf einem gelösten Würfel). Aus einem eingegebenen Scramble wird ermittelt, wie der Würfel aussieht. Dann wird für jeden der 8 möglichen 2x2x2-Blöcke ermittelt, wie die dafür benötigten 3 Edges und 1 Corner bewegt werden müssen, damit der Block gelöst wird. Aus der Pruning Table werden dann alle Zugfolgen gelesen, die diesen Block lösen.

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.

Die maximale Suchtiefe pro Schritt liegt bei 6 Moves. Aktuell kann der Solver nur L3C- und L5C-Skeletons lösen. Bei L5C-Skeletons werden für die erste Insertions nur die Kommutatoren berücksichtigt, die am meisten Moves canceln; eben genau so, wie auch ein Mensch nach Insertions suchen würde.

Was hat das für Auswirkungen auf FMC?

Man könnte den Solver benutzen, um bei Forencomps bei FMC zu betrügen. Diese wettbewerbe laufen allerdings jetzt schon im Vertrauen darauf, dass niemand die Lösung eines anderen abschreibt und als selbst gefunden ausgibt. Zur Zeit hat außer mir auch keiner direkten Zugang zum Solver.

Bei WCA-Comps sind elektronische Hilfsmittel eh verboten.

Wie gut ist der Solver?

Der Mean of 100 auf den scrambles, die Linus mir geschickt hat, lag nur für den normalen Scramble bei 23.85 Moves. Wenn man das jeweils beste ergebnis von normalem und inversem Scramble nimmt, lag der Mean bei 23.11 Moves. Die Laufzeit lag bei knapp über 3 Minuten pro Scramble. Ich hoffe allerdings, dass ich die Laufzeit noch auf unter 2 Minuten reduzieren kann.

Bei den Scrambles der FMC-Challenge gab es bereits 2 Fälle, in denen der Solver Lösungen gefunden hat, die mit denen aus dem Forum identisch waren.

Auf Reddit gibt es schon einige Lösungen zu Scrambles.

Welche Erweiterungen sind geplant?

Im Rahmen der Bachelorarbeit wird sich außer an der durchschnittlichen laufzeit vermutlich nicht mehr viel ändern. Danach möchte ich aber die restlichen Skeletons, die 2 Corner-Insertions brauchen, NISS, Pseudoblöcke und pre-Moves implementieren.

Die Vorgehensweise deines Algorithmus ist der eines Menschen ja recht ähnlich, nur das man als Mensch natürlich meisten nicht so Optimal ist, da man z.B. kein Table mit allen Möglichkeiten im Kopf hat und auch häuifig nicht unbeding alle Möglichkeiten für den nächsten Schritt duchpropieren kann.
Einen Nutzen um beim FMC zu betrügen hat das Programm meines Erachtens nach eher nicht. Auf einer Comp ist es natürlich klar nutzlos, und hier im Forum ebenfalls, weil man nichts gewinnen kann und eher sich selber betrügt, da der FMC-Thread ja in erster Linie zum üben und vergleichen ist. Ich finde aber zum trainieren könnte es durchaus interessant sein, man kann dann eventuell auch sehen, wo man falsche Ansätze hatte, oder gute Ansätze und falsch weiter gemacht hat, etc.

Falls du deinen Code und die DB herausgeben magst, kann ich gerne mal schauen, ob/wo ich Potential für Geschwindigkeitsverbesserungen sehe. (Auf die Empfehlung, kein PHP zu verwenden, würde ich verzichten :-))

Gute Idee für eine Bachelorarbeit.

Nachdem ich mit Fritz schon einige Zeit drüber diskutiert und schon einige Solutions gesehen habe kann ich jetzt auch mal meinen ersten Eindruck schildern.
Grundsätzlich finde ich die Idee ziemlich cool, weil sich dadurch einfach die Möglichkeit ergibt auch "optimale" FMC-Solutions zu finden, zumindest soweit das für Menschen möglich ist.
Was mich daran allerdings am meisten stört ist, dass sehr häufig auch 12 Moves für den 2x2x3 (oder 6 Moves für 2x2x2, 18 Moves für F2L-1) in Kauf genommen werden und sich dann am Ende alles in ziemlich wenig Zügen löst. Das Problem das ich damit habe ist: Ich würde vermutlich die wenigsten der Solutions die so entstehen überhaupt in Erwägung ziehen, weil es mir schon zu viele Moves sind. Dadurch werden in meinen Augen zumindest diese Solutions eher unglaubhaft.
Viele von den Solutions lassen sich natürlich gut argumentieren mit "ich hatte halt Glück beim Finish". Ist natürlich in Ordnung weil das sonst beim FMC ja auch immer wieder so läuft, aber wir haben halt in einer Stunde (oder generell auch ohne Limit) lange nicht die Möglichkeit, die große Anzahl an Anfängen und sonstigem zu testen.

Was mich am meisten stört (und worüber sich auch schon Leute auf Reddit aufgeregt haben ) sind immer wieder so Dinge wie L5C in 21, die dann zu einer 23 führen

Und hier noch ein kleiner Fun-Fact: Bisher hat der Bot alle Scrambles (bis auf einen), die ich mitbekommen habe, "Sub-human" gelöst, also hat der Bot weniger oder gleich viele Züge gebraucht wie die Solutions von Jan, Marcel, Basti, mir, ...
Der eine Scramble ist der WR Scramble von Marcel

(24.02.2016, 15:25)Linus F schrieb: [ -> ]Was mich daran allerdings am meisten stört ist, dass sehr häufig auch 12 Moves für den 2x2x3 (oder 6 Moves für 2x2x2, 18 Moves für F2L-1) in Kauf genommen werden und sich dann am Ende alles in ziemlich wenig Zügen löst. Das Problem das ich damit habe ist: Ich würde vermutlich die wenigsten der Solutions die so entstehen überhaupt in Erwägung ziehen, weil es mir schon zu viele Moves sind.

Gut, das ist die Heuristik, die ein Mensch benutzt, weil er nicht alles ausprobieren kann. Man könnte ja in das Programm einbauen (ggf. per Option-Flag), dass nur die kürzeste Solution in jedem Schritt verwendet werden soll

FMC-Challenge vom 12.02.2016:

1. Scramble: L2 F2 L2 U2 L2 B R2 B' R2 F2 D U R U' F L' D' R B' D' F  
.
2. Scramble: B2 R2 D' R2 D F2 L2 F2 U' F2 D' B' U' R D2 U' B' L2 U B2 F'   
.
3. Scramble: R2 D' B2 D L2 U' B2 F2 U2 B2 F' R2 B' R U' L D' R' B' U2  

(24.02.2016, 15:01)AKOM schrieb: [ -> ]Die Vorgehensweise deines Algorithmus ist der eines Menschen ja recht ähnlich, nur das man als Mensch natürlich meisten nicht so Optimal ist, da man z.B. kein Table mit allen Möglichkeiten im Kopf hat und auch häuifig nicht unbeding alle Möglichkeiten für den nächsten Schritt duchpropieren kann.

Genau das ist ja Sinn, Zweck und Ziel des Ganzen. Grad bei Scrambles, die am Anfang besonders viele oder besonders wenige Möglichkeiten bieten, kann man so interessante Ansätze finden.

(24.02.2016, 15:01)AKOM schrieb: [ -> ]Falls du deinen Code und die DB herausgeben magst, kann ich gerne mal schauen, ob/wo ich Potential für Geschwindigkeitsverbesserungen sehe. (Auf die Empfehlung, kein PHP zu verwenden, würde ich verzichten :-))

Aktuell gehen 50-70% der Laufzeit für die Insertions drauf, da ich diesen Lösungsschritt noch nicht vernünftig implementiert habe. Mit ein paar kleinen Änderungen sollten durchschnittliche Zeiten von unter 2 Minuten kein Problem sein.

Im Rhamen der Bachelorarbeit wird sich an anderen Stellen wohl nicht mehr viel grundlegendes ändern aber für spätere Änderungen, z.B. NISS und andere Skeletons als L3C und L5C wäre es sicher interessant und vernünftig, über Wege nachzudenken, um die Laufzeit weiter zu verringern.

(24.02.2016, 15:25)Linus F schrieb: [ -> ]Was mich am meisten stört (und worüber sich auch schon Leute auf Reddit aufgeregt haben ) sind immer wieder so Dinge wie L5C in 21, die dann zu einer 23 führen

Noch schlimmer: L3C in 22 und am Ende ne 21 :/

Mit der Erkennung andere Skeletons als L3C und L5C sollte die Hääufigkeit solcher Solutions stark abnehmen. Von den 100 Scrambles, die Linus mir geschickt hat, waren Lösungen, bei denen wirklich unwahrscheinlich viele Moves gecancelt worden, in vermutlich 20-30 Fällen dabei.

(24.02.2016, 15:36)AKOM schrieb: [ -> ]Gut, das ist die Heuristik, die ein Mensch benutzt, weil er nicht alles ausprobieren kann. Man könnte ja in das Programm einbauen (ggf. per Option-Flag), dass nur die kürzeste Solution in jedem Schritt verwendet werden soll

Das könnte man machen. Allerdings kann es durchaus Sinnvoll sein, in einen Schritt zusätzliche Moves einzubauen, um damit z.B. Edges zu orientieren oder ein Pair zu lösen. Ein Beispiel dafür ist die 22 auf invers vom 2. Scramble letzter Woche. Vielleicht wäre es sinnvoller, eine Obergrenze für Cancellations vorzugeben.

Ich finde die Idee gut und was mich als Intermediate FMCler natürlich reizt:
Die Solutions des Bots sind für uns ein gutes Beispiel und können das Training von FMC unterstützen, weil der Bot mal Blöcke baut, die man selbst so nicht kannte oder ähnliches

Also, ich habe die Postings auch schon immer mal wieder bei reddit gesehen und fand die Lösungen größtenteils, aus oben genannten Gründen, eher obskur.
Wenn es 5 tendenziell eher offensichtliche Möglichkeiten einen 2x2x3 Block mit 8 Moves zu bauen gibt, ist es unwahrscheinlich, dass man sich für den 12 Move 2x2x3 entscheidet, daraus L3C in 20 macht und dann auch noch 6 Moves Cancellation hat. Klar, kommt vor, aber wenn das drei Mal in einer 22er Mean vorkommt, hätte ich definitiv meine Zweifel.

(24.02.2016, 14:40)Fritz schrieb: [ -> ]Bei WCA-Comps sind elektronische Hilfsmittel eh verboten.

Was ein Statement.... das hat etwas von "Ich verkaufe Dopingmittel, aber ich fühl mich gut dabei, denn Doping ist ja eh im Sport verboten".  

Natürlich kann man niemandem einen Vorwurf machen, der Spaß daran hat, entsprechende Tools zu implementieren. Allerdings sollte sich jeder bewusst sein, welche Verantwortung er damit hat.
Langfristig wird das dazu führen, dass die Bedingungen in Competitions deutlich strenger und für Teilnehmer unangenehmer werden. Speedcubing wird immer größer und professioneller und damit steigt zum einen der Reiz zu cheaten, zum anderen aber auch aus Perspektive der Verantwortlichen der Zwang, dies möglichst zu verhindern.
Aktuell haben wenige Delegates auf der Welt etwas dagegen, wenn die Teilnehmer ihr Smartphone während Fewest Moves in der Hosentasche behalten. Manchmal ist es auch kein Problem, während des Attempts auf die Toilette zu gehen. Die Rechenzeit, die du für bei dein Lösungen angibst, liegt sicherlich unter der Zeit, zu der ein Toilettengang auffällig werden würde... 
Und ja, Incidents, bei denen Teilnehmer Smartphones während FMC benutzen wollten, gab es schon. Das ist allerdings immer recht einfältig gewesen, indem jemand z.B. einen optimalen PLL auf einer Website nachgeschaut hat. Wenn man jedoch genau in dieser Zeit eine rekordtaugliche Lösung produzieren kann, hat das ganze schon eine andere Qualität.

(24.02.2016, 17:08)Laura schrieb: [ -> ]Aktuell haben wenige Delegates auf der Welt etwas dagegen, wenn die Teilnehmer ihr Smartphone während Fewest Moves in der Hosentasche behalten. Manchmal ist es auch kein Problem, während des Attempts auf die Toilette zu gehen. Die Rechenzeit, die du für bei dein Lösungen angibst, liegt sicherlich unter der Zeit, zu der ein Toilettengang auffällig werden würde... 
Und ja, Incidents, bei denen Teilnehmer Smartphones während FMC benutzen wollten, gab es schon. Das ist allerdings immer recht einfältig gewesen, indem jemand z.B. einen optimalen PLL auf einer Website nachgeschaut hat. Wenn man jedoch genau in dieser Zeit eine rekordtaugliche Lösung produzieren kann, hat das ganze schon eine andere Qualität.

Stimmt, das hatte ich gar nicht bedacht.

(24.02.2016, 16:56)AlexICG schrieb: [ -> ]Ich finde die Idee gut und was mich als Intermediate FMCler natürlich reizt:
Die Solutions des Bots sind für uns ein gutes Beispiel und können das Training von FMC unterstützen, weil der Bot mal Blöcke baut, die man selbst so nicht kannte oder ähnliches

Den Eindruck habe ich auch. Grad beim Schritt von 2x2x3 zu F2L-1 waren immer mal wieder ein paar spannende Sachen dabei. Interessant ist es auch, Ansätze für 2x2x2 oder 2x2x3 an den Scramble zu hängen, um zu sehen, was mit diesem Ansatz möglich ist.

(24.02.2016, 17:08)Laura schrieb: [ -> ]Wenn es 5 tendenziell eher offensichtliche Möglichkeiten einen 2x2x3 Block mit 8 Moves zu bauen gibt, ist es unwahrscheinlich, dass man sich für den 12 Move 2x2x3 entscheidet, daraus L3C in 20 macht und dann auch noch 6 Moves Cancellation hat. Klar, kommt vor, aber wenn das drei Mal in einer 22er Mean vorkommt, hätte ich definitiv meine Zweifel.

Wenn es einen offensichtlichen 2x2x3 in 8 Zügen gibt, der bei 6 bad Edges landet, würde ich erst mal suchen, wie ich möglichst viele Edges mit ein paar extra Zügen richtig orientieren kann. Ich denke nicht, dass man pauschal sagen kann, dass alle Ansätze, die nicht jeweils die minimal mögliche Zahl an Zügen für einen Schritt brauchen, automatisch unwahrscheinlich oder unplausibel sind. Ein möglicher Ansatz wäre, die Zahl der bad Edges zu vergleichen, wobei auch das keine absolute Sicherheit bringt (siehe F D L D statt F D2 bei der 22 beim 2. Scramble).

(24.02.2016, 17:08)Laura schrieb: [ -> ]

(24.02.2016, 14:40)Fritz schrieb: [ -> ]Bei WCA-Comps sind elektronische Hilfsmittel eh verboten.

Was ein Statement.... das hat etwas von "Ich verkaufe Dopingmittel, aber ich fühl mich gut dabei, denn Doping ist ja eh im Sport verboten".  

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.

(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?

(24.02.2016, 17:08)Laura schrieb: [ -> ]Aktuell haben wenige Delegates auf der Welt etwas dagegen, wenn die Teilnehmer ihr Smartphone während Fewest Moves in der Hosentasche behalten. Manchmal ist es auch kein Problem, während des Attempts auf die Toilette zu gehen. Die Rechenzeit, die du für bei dein Lösungen angibst, liegt sicherlich unter der Zeit, zu der ein Toilettengang auffällig werden würde... 

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

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