fischertechnik community forum

Ich baue seit ca. einem Jahr an einem Roboter der in der Lage ist alle derzeit üblichen Zauberwürfel zu lösen (2*2*2, 3*3*3, 4*4*4, 5*5*5)

Der Roboter ist mit einer Webcam ausgestattet und soll selbstständig erkennen um welchen Würfel es sich handelt, alle 6 Seiten zu scannen und der schnellsten Weg berechnen, ihn zu lösen.

Um alle möglichen Züge ausführen zu können, ist der Roboter mit folgenden Werkzeugen ausgestattet:

• Linker Schuieber um den Würfel zu kippen
• Rechter Schieber um die oberen Ebenen zu halten
• Drehkranz um entweder den ganzen Würfel oder nur die untersten Ebenen zu drehen
• Boden im Drehkranz ist höhenverstellbar um entweder eine oder 2 Ebenen zu drehen.

Wir wollen folgende Weltrekorde aufstellen:

• Schnellste Lösung eines Rubik's Revenge (4*4*4) durch einen Roboter
• Schnellste Lösung eines Professor's Cube (5*5*5) durch einen Roboter

und folgenden Rekord verbessern:

• Schnellste Lösung eines Rubik's Cube (3*3*3) durch einen Roboter, aktuell bei 1min 04 sek

Für den 2*2*2 und 3*3*3 Würfel wird die schnellste Lösung per Brute-Force ermittelt, bei den größeren Würfeln wird jede Schicht durch vordefinierte Züge gelöst, danach wird jede Schicht einzeln mit Brute-Force optimiert.

Hier ein paar Bilder:

Hallo,

für 3x3x3 liegt der Rekord unter 64 Sekunden. http://www.youtube.com/watch?v=eaRcWB3jwMo

Gruß
Heiko

Ich habe zwar gerade gesehen, das der Roboter, der den Rekord hält verbessert wurde: http://en.wikipedia.org/wiki/RuBot_II, aber die vom Cube-Stormer haben sich wohl nicht bei Guinness gemeldet und somit auch keinen neuen Weltrekord aufgestellt.

3*3*3 Würfel wird die schnellste Lösung per Brute-Force ermittelt

Das kann ich kaum glauben. Hast du das Programm dazu selbst geschrieben? Ein Brute-Force-Programm für den 3*3*3 Würfel, das in so kurzer Zeit lösen kann würde ich gerne sehen. Oder zählst du die Rechenzeit nicht mit bei der Angabe von 1:04?

Jede Position des 3*3*3 ist in maximal 20 Zügen lösbar. Bei jedem Zug gibt es 18 Möglichkeiten (jede Seite 1/4cw, 1/4ccw und eine halbe Drehung). Insgesamt muss der Algorithmus also im schlimmsten Fall 18^20 = 127482362200000000000000 Züge durchrechnen. Ich lasse mich natürlich gerne überzeugen, dass das möglich ist, kann es aber bis jetzt nicht richtig glauben.

Achso, falls ihr wirklich einen neuen Weltrekord schafft: Respekt. Ich habe ungefähr eine Vorstellung davon, wie schwer es ist einen schnellen Cube-Solver zu bauen.

Viele Grüße,
Jan

Es stimmt nicht ganz, das man soviele Möglichkeiten berechnen muss: Nur 0,000000001% alle möglichen Kombinationsmöglichkeiten brauchen 20 Züge und nur 3,3% aller Kombinationen brauchen 19 Züge, siehe hier ein Diagramm für die optimale Lösung von 1000000 zufälligen Würfeln:


Nein, der Algorithmus ist nicht von mir, sondern von Herbert Kociemba. Das Programm von ihm (Cube Explorer) kann entweder die optimale Lösung (in fast immer unter einer Minute) ausrechnen, oder mit dem sogenannten "Two-Phase-Algorithm" in Sekundenbruchteilen eine Lösung finden, die meist nur 1-3 Züge mehr braucht als die optimale Lösung.

Beim 3-er Würfel nehmen dir den Two-Phase-Algoritmus und beim 4er und 5er Würfel, wo zuerst die 6* 4 oder 9 Mittelsteine und 12 * 2 oder 3 Kanten sortiert werden (um einen 3*3*3 Würfel zu haben) den optimalen Algorithmus, der kann ja die ganze Zeit rechnen in der die Steine sortiert werden.

Für den 2er Würfel werden wir wahrscheinlich eine 47 764 080 Byte große Datei erzeugen, in der alle 3.674.160 Möglichkeiten samt Lösungen gespeichert sind. (7 Bytes für den Ausgangszustand weil 21 Flächen (3 sind konstant) und 6 Farben (je 3 können in einem Byte gespeichert werden) ergeben 7 Byte , 6 Bytes für die Lösung weil 18 Zugmöglichkeiten*maximal 11 Züge=6Bytes). Diese Tabelle wird dann nach dem eingescannten Würfel durchsucht.

peter.poetzi hat geschrieben:haben sich wohl nicht bei Guinness gemeldet

Na prost. Zum Glueck ist Guiness nicht die allein wahrheitsstiftende Instanz. Ich halte mich lieber aus den juristischen Haarspaltereien heraus, und achte auf den Maschinenbau, den ich tatsaechlich sehen kann. Und da ist der Cubestormer schon arg schwer zu schlagen.

Zumindest wird es schwierig, diese ~10 Sekunden zu knacken. Und genau das muesste man tun, wenn man mit gutem Gewissen ankuendigen will, den weltschnellsten Roboter zu bauen.

Gruss
Heiko

Für den 3*3*3 Cube Solver werden wir in naher Zukunft wahrscheinlich eh einen eigenen Roboter bauen, der so wie der Cube Stormer funktioniert (den kennen wir schon länger). Also einfach 4 Drehkränzemit wegklappbaren Greifern, die mit 1:8 Power Motoren 1:1 über eine Kette angetrieben werden. (so wie dzt. beim linken Schieber)

Aber derzeit geht es uns eh einmal nur um den Rekord für den 4er und 5er Würfel

Hi,

gibts schon was neues?

Gruß
Heiko

Wir werden jetzt bei ft nachfragen, ob die uns unterstützen, schließlich machen wir ja werbung für Fischertechnik.

warum ft ?
fehlts an Teilen, oder an KnowHow?

Es fehlt uns an Teilen.