n*n*n Cube Solver

Fussballroboter, Autofabrik...
Modellideas &- presentation - Soccerrobot, Carfactory...
Forumsregeln
Bitte beachte die Forumsregeln!
Antworten
Benutzeravatar
peter.poetzi
Beiträge: 87
Registriert: 06 Nov 2010, 10:00

n*n*n Cube Solver

Beitrag von peter.poetzi » 28 Nov 2010, 21:57

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:
Bild
Bild
Bild
Bild
Bild
Bild
Bild
Bild
Bild
Früherer Nick:hman13
int main(){return main();}

heiko
Beiträge: 256
Registriert: 28 Okt 2010, 17:10

Re: n*n*n Cube Solver

Beitrag von heiko » 29 Nov 2010, 00:29

Hallo,

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

Gruß
Heiko

Benutzeravatar
peter.poetzi
Beiträge: 87
Registriert: 06 Nov 2010, 10:00

Re: n*n*n Cube Solver

Beitrag von peter.poetzi » 29 Nov 2010, 08:33

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.
Früherer Nick:hman13
int main(){return main();}

kehrblech
Beiträge: 13
Registriert: 31 Okt 2010, 21:53

Re: n*n*n Cube Solver

Beitrag von kehrblech » 29 Nov 2010, 12:58

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

Benutzeravatar
peter.poetzi
Beiträge: 87
Registriert: 06 Nov 2010, 10:00

Re: n*n*n Cube Solver

Beitrag von peter.poetzi » 29 Nov 2010, 14:12

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:
Bild

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.
Zuletzt geändert von peter.poetzi am 29 Nov 2010, 20:05, insgesamt 1-mal geändert.
Früherer Nick:hman13
int main(){return main();}

heiko
Beiträge: 256
Registriert: 28 Okt 2010, 17:10

Re: n*n*n Cube Solver

Beitrag von heiko » 29 Nov 2010, 19:52

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

Benutzeravatar
peter.poetzi
Beiträge: 87
Registriert: 06 Nov 2010, 10:00

Re: n*n*n Cube Solver

Beitrag von peter.poetzi » 29 Nov 2010, 20:03

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
Früherer Nick:hman13
int main(){return main();}

heiko
Beiträge: 256
Registriert: 28 Okt 2010, 17:10

Re: n*n*n Cube Solver

Beitrag von heiko » 30 Dez 2010, 17:27

Hi,

gibts schon was neues?

Gruß
Heiko

Benutzeravatar
peter.poetzi
Beiträge: 87
Registriert: 06 Nov 2010, 10:00

Re: n*n*n Cube Solver

Beitrag von peter.poetzi » 30 Dez 2010, 17:30

Wir werden jetzt bei ft nachfragen, ob die uns unterstützen, schließlich machen wir ja werbung für Fischertechnik.
Früherer Nick:hman13
int main(){return main();}

Benutzeravatar
Pilami
Beiträge: 332
Registriert: 31 Okt 2010, 21:35
Wohnort: Mörshausen

Re: n*n*n Cube Solver

Beitrag von Pilami » 02 Jan 2011, 10:05

warum ft ? :shock:
fehlts an Teilen, oder an KnowHow?

Benutzeravatar
peter.poetzi
Beiträge: 87
Registriert: 06 Nov 2010, 10:00

Re: n*n*n Cube Solver

Beitrag von peter.poetzi » 02 Jan 2011, 10:19

Es fehlt uns an Teilen.
Früherer Nick:hman13
int main(){return main();}

Antworten