Themabewertung:
  • 0 Bewertung(en) - 0 im Durchschnitt
  • 1
  • 2
  • 3
  • 4
  • 5
FMC-Bot
#1
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.
R' U' B U' L' B L B' U B' R' U R2
Zitieren


Nachrichten in diesem Thema
FMC-Bot - von Fritz - 24.02.2016, 14:40
RE: FMC-Bot - von AKOM - 24.02.2016, 15:01
RE: FMC-Bot - von Linus F - 24.02.2016, 15:25
RE: FMC-Bot - von AKOM - 24.02.2016, 15:36
RE: FMC-Bot - von FMC-Bot - 24.02.2016, 15:42
RE: FMC-Bot - von Fritz - 24.02.2016, 16:05
RE: FMC-Bot - von AlexICG - 24.02.2016, 16:56
RE: FMC-Bot - von Laura - 24.02.2016, 17:08
RE: FMC-Bot - von AKOM - 24.02.2016, 17:39
RE: FMC-Bot - von Fritz - 24.02.2016, 18:41
RE: FMC-Bot - von Laura - 24.02.2016, 19:39
RE: FMC-Bot - von FMC-Bot - 24.02.2016, 19:24
RE: FMC-Bot - von AKOM - 24.02.2016, 19:35
RE: FMC-Bot - von Linus F - 24.02.2016, 19:39
RE: FMC-Bot - von AKOM - 24.02.2016, 19:59
RE: FMC-Bot - von Fritz - 24.02.2016, 19:45
RE: FMC-Bot - von AKOM - 24.02.2016, 19:54
RE: FMC-Bot - von Fritz - 24.02.2016, 19:56
RE: FMC-Bot - von AKOM - 24.02.2016, 22:33
RE: FMC-Bot - von Fritz - 24.02.2016, 23:54
RE: FMC-Bot - von AKOM - 25.02.2016, 00:24
RE: FMC-Bot - von Fritz - 25.02.2016, 00:49
RE: FMC-Bot - von AKOM - 25.02.2016, 00:56
RE: FMC-Bot - von FMC-Bot - 26.02.2016, 13:12

Gehe zu:


Benutzer, die gerade dieses Thema anschauen: 1 Gast/Gäste