Zauberwürfel Roboter in ca 1 Sekunde

Stefan U. schrieb:
> Schaut mal, worüber Heise heute berichtet:
> http://www.heise.de/newsticker/meldung/Roboter-loe...
>
> Das ist doch der Hammer, oder?
>
> Hat mit µC nicht sehr viel zu tun, aber ich finde es trotzdem
> interessant.

Stimmt. Daß die Berechnung der Lösung schnell genug ist, darüber wundere 
ich mich nicht. Aber die Drehungen so sauber hinzukriegen, daß sich 
nichts verkantet und alles sauber läuft, das ist das eigentliche 
Meisterwerk.

Aber trotzdem frage ich mich immer wieder, wer den Blödsinn mit dem 
"Zauberwürfel" in die Welt gesetzt hat. Was hat das mit Zauberei zu tun?

Schade das er den Würfel dafür manipulieren musste (Löcher bohren).

Sonst klasse...

> Aber trotzdem frage ich mich immer wieder, wer den Blödsinn mit dem
> "Zauberwürfel" in die Welt gesetzt hat. Was hat das mit Zauberei zu
> tun?


Muggle werden das NIEMALS verstehen!

Technik wirkt oft wie Magie, bis man geschnallt hat, wie sie 
funktioniert.

Stefan U. schrieb:
> Schaut mal, worüber Heise heute berichtet:
> 
http://www.heise.de/newsticker/meldung/Roboter-loest-Rubik-s-Cube-und-braucht-nur-gut-eine-Sekunde-3083732.html
>
> Das ist doch der Hammer, oder?

Kalter Kaffee, schau dir mal einen montage robotor in ner chinafab an. 
Oder einen SMD-Bestücker: da fliegen x-Mal mehr Teile pro sekunde an die 
richtige Stelle als bei so nem lumpigen Spielzeugwürfel.

Nein wie unprofessionell, angesteuert von einem Arduino, igitt!  :-)

"Roboter" kann man auch sinnvoller einsetzen:

https://www.youtube.com/watch?v=dvaZQwW_T8M

Würde mich nicht wundern, wenn ein Mensch das genauso schnell könnte.

1. Man hat vorsichtshalber den Würfel Maschinengerecht gemacht.
   (Minuspunkte)
2. Man hat den Würfel - keine Ahnung wie lange das wirklich dauert -
   bereits eingespannt. (Sehr viele Minuspunkte, ungültiger Vorsprung)

Also solide Programmierung und saubere Konstruktion.

Michael K. schrieb:
> Wenn man mal bedenkt wie "lahm" der Arduino so ist (der µC kann ja bei
> weitem mehr)
Das verstehe ich nicht.

Michael K. schrieb:
> Wenn man mal bedenkt wie "lahm" der Arduino so ist (der µC kann ja bei
> weitem mehr) sieht man: Was besonderes ist das schnelle Lösen nicht.

Der Mikrocontroller löst aber den würfel nicht, sondern steuert nur die 
Motoren an. Lösen tut ein linux rechner der auch die Bildauswertung zur 
ermittlung der Anfangsposition übernimmt.
Wie lange das dauert steht nicht im text, da ist nur die Rede 
eigentlichen drehen das etwa eine sec dauert.
Wenn man bedenkt das in jedem fall 20 Züge zur Lösung genügen und 
darunter auch doppelzüge und Züge über unverbundene Ebenen fallen hat 
man eine Zugdauer (Vierteldrehung) von so 50 ms - die Motoren drehen 
sich also mit r rps - nicht sonderlich viel.

Über Links gedacht schrieb:
> Wenn man bedenkt das in jedem fall 20 Züge zur Lösung genügen und
> darunter auch doppelzüge und Züge über unverbundene Ebenen fallen hat
> man eine Zugdauer (Vierteldrehung) von so 50 ms - die Motoren drehen
> sich also mit r rps - nicht sonderlich viel.

nur würde man mehrere stunden brauchen um die schnellste Lösung zu 
finden.

Über Links gedacht schrieb:
> Wenn man bedenkt das in jedem fall 20 Züge zur Lösung genügen und
> darunter auch doppelzüge und Züge über unverbundene Ebenen fallen hat
> man eine Zugdauer (Vierteldrehung) von so 50 ms - die Motoren drehen
> sich also mit r rps - nicht sonderlich viel.

Der rechnet doch nicht bei jedem Zug. Der schaut sich einmal die 
Ausgangssituation an, berechnet die erforderlichen Bewegungsverläufe und 
dann gehts los mit maximal (mechanisch) möglicher Geschwindigkeit.

S. R. schrieb:
> Peter II schrieb:
>> nur würde man mehrere stunden brauchen um die schnellste Lösung zu
>> finden.
>
> Nein, der Algorithmus ist bekannt und relativ einfach. Sonst könnten
> Menschen den Würfel nicht blind lösen.

nein, sonst hätte man nicht Jahre gebraucht es zu beweisen.

Wenn man es nach "Handbuch" löst, dann ist das nicht die kürzeste weg.

?!? schrieb:
>> Wenn man bedenkt das in jedem fall 20 Züge zur Lösung genügen und
>> darunter auch doppelzüge und Züge über unverbundene Ebenen fallen hat
>> man eine Zugdauer (Vierteldrehung) von so 50 ms - die Motoren drehen
>> sich also mit r rps - nicht sonderlich viel.
>
> Der rechnet doch nicht bei jedem Zug. Der schaut sich einmal die
> Ausgangssituation an, berechnet die erforderlichen Bewegungsverläufe und
> dann gehts los mit maximal (mechanisch) möglicher Geschwindigkeit.

Nö, alles vor der bewegung zu berechnen ist dumm. Man spekuliert ein 
paar Züge und schaut ob die enstehende Situation näher am Ziel ist. 
Während man diese Züge ausführt spekuliert man parallel die nächste 
Sequenz und schaut wiederum bei welcher man dem Ziel näher gekommen 
wäre/wird.

Die Kunst ist wie beim Schach die Stellungsbewertung -> bin ich mit 
diesem Muster näher an der Ordnung oder entferne ich mich davon.

Über Links gedacht schrieb:
> Nö, alles vor der bewegung zu berechnen ist dumm. Man spekuliert ein
> paar Züge und schaut ob die enstehende Situation näher am Ziel ist.
> Während man diese Züge ausführt spekuliert man parallel die nächste
> Sequenz und schaut wiederum bei welcher man dem Ziel näher gekommen
> wäre/wird.

nein, das geht nicht. Die Bewertung ist fast nicht möglich.

Ich denke sie Lösen es nach dem typischen Anleitungen im Netz. Also erst 
die 1.Ebende dann die nächste usw. Am ende gibt es gewisse Zugfolgen um 
die Ecken oder Seiten zu tauschen.

Peter II schrieb:
> Über Links gedacht schrieb:
>> Nö, alles vor der bewegung zu berechnen ist dumm. Man spekuliert ein
>> paar Züge und schaut ob die enstehende Situation näher am Ziel ist.
>> Während man diese Züge ausführt spekuliert man parallel die nächste
>> Sequenz und schaut wiederum bei welcher man dem Ziel näher gekommen
>> wäre/wird.
>
> nein, das geht nicht. Die Bewertung ist fast nicht möglich.

Warum sollte sie unmöglich sein? Der Computer muss einfach nur schauen 
wie viel Cubies schon richtig liegen. nach dem vorletzten Zug sind zwei 
gegenüberliegenden Flächen und alle Ebenen korrekt, nach den 
vorvorletzten Zug ist mindestens eine 2x2x2 Ecke korrekt und so weiter.

das ganze ist nur eine variante des Pfannkuchenproblems:
https://de.wikipedia.org/wiki/Pfannkuchen-Sortierproblem

Über Links gedacht schrieb:
> Warum sollte sie unmöglich sein? Der Computer muss einfach nur schauen
> wie viel Cubies schon richtig liegen. nach dem vorletzten Zug sind zwei
> gegenüberliegenden Flächen und alle Ebenen korrekt, nach den
> vorvorletzten Zug ist mindestens eine 2x2x2 Ecke korrekt und so weiter.

genau das ist aber nicht der Fall. Die Anzahl der richtige Cubies sagt 
wenig über die Anzahl der verbleibenden schritte aus.

Da mit einen Zug sich sehr viel ändert, kann es schnell sein wenn mehre 
ecke nicht stimmen als wenn nur eine Ecke nicht stimmt.

Jan H. schrieb:
> In einem vollständig vorhersagbaren System (und ein solches ist der
> Würfel) ist dieses Vorgehen für einen Computer einfach nur dämlich.

Nööhh heutistische Optimierungsalgos sind clever, bspw:

https://de.wikipedia.org/wiki/Simulated_Annealing
https://de.wikipedia.org/wiki/Monte-Carlo-Algorithmus

Über Links gedacht schrieb:
> Nööhh heutistische Optimierungsalgos sind clever, bspw:

doch, es macht keinen sinn. Es wird vorher ein möglichst kurzer weg 
gesucht (für den kürzesten fehlt die Zeit) und dann wird gelöst.

Peter II schrieb:
> genau das ist aber nicht der Fall. Die Anzahl der richtige Cubies sagt
> wenig über die Anzahl der verbleibenden schritte aus.
>
> Da mit einen Zug sich sehr viel ändert, kann es schnell sein wenn mehre
> ecke nicht stimmen als wenn nur eine Ecke nicht stimmt.

Naja es ist eine Frage wie man richtig liegen definiert. Richtig in 
bezug auf seine nachbarn beispielsweise.

Denk einfach rückwärts, je mehr du einen Würfel verdrehst desto weniger 
"Päärchen aus richtigen" nachbarn gibt es.
Natürlich kann es zugfolgen geben bei denen es zwischendurch 
unordentlicher wird. deshalb permutiert man ja auch meherer Züge und 
bewertet alle entsandenen Möglichkeit bevor man sich für eine sequenz 
entscheidet. halt wie das Gambit beim Schach.

S. J. schrieb:
> Vielleicht kommt es ja auch drauf an, was man will. Was wenn die Suche
> nach der optimalen Lösung länger dauert als nach einer nicht-optimalen
> Lösung?
richtig, dazwischen muss man Abwegen.


> Könnte man
> in dieser Zeit nicht vielleicht schon ein paar sinnvolle Züge machen,
> die auf einer suboptimalen Lösung basieren?

genau das ist das Problem. Wenn dann die schnellste Lösung gefunden 
wurden ist, steht der Würfel dann nicht mehr so und man muss im 
Zweifelsfall zurückdrehen.

Über Links gedacht schrieb:
> Denk einfach rückwärts, je mehr du einen Würfel verdrehst desto weniger
> "Päärchen aus richtigen" nachbarn gibt es.

warum haben sich wohl jahrelang Leute und Computer damit beschäftig 
rauszufinden wie viele schritte man minimal braucht, wenn man es einfach 
bewerten könnte?

Die Bewertung ist - wie viele schritte braucht man zum Lösen. Dafür 
braucht man seeeehr viel Rechenleistung.

Jan H. schrieb:
> Ich sehe grade, ich hab deinen ersten Beitrag falsch verstanden. Ich
> dachte du willst am Würfel drehen und dabei dann kucken ob's besser oder
> schlechter wird. Was ziemlich langsam wird.
>
> Was du in der digitalen Welt machst, bis du anfängst den Würfel zu
> drehen, dabei dürften

Genau, züge vorausberechnen und stellung bewerten und dann drehen. Kann 
natürlich ein Computer wunderbar, während ein mensch sich eher mit 
bekannten zugfolgen von bekannter Verbesserung zu bekannten Verbesserung 
hangelt.

So machen es auch die Schachcomputer, Permutation der Ausgangsstellung 
durch durchspielen legaler Zugfolgen und bewertung der so erzielten 
stellungen.

Peter II schrieb:
> Die Bewertung ist - wie viele schritte braucht man zum Lösen. Dafür
> braucht man seeeehr viel Rechenleistung.

Nö, die Bertung ist nur um man weniger schritte von der neuen position 
braucht als von der Ausgangsposition, wieviel ist wurscht. wie im Wald, 
hauptsache es wird heller, wie heller ist wurscht.

S. J. schrieb:
> Hier kommt noch hinzu: Selbst wenn die optimale Lösung relativ schnell
> gefunden werden kann, steht in dieser Zeit der Würfel still. Könnte man
> in dieser Zeit nicht vielleicht schon ein paar sinnvolle Züge machen,
> die auf einer suboptimalen Lösung basieren?

Wieviele Züge wird der Linux-Rechner in einer Millisekunde berechnen 
können? Da fällt die "Stillstandszeit" des Würfels nicht ins Gewicht. Um 
einen einzigen Zug zu machen, brauchen die Schrittmotoren auf jeden Fall 
länger als die Lösung des gesamten Problems dauert.

@ Johann

So ist es. Um den Würfel zu lösen, brauch man nur einen einfacher 
Algorithmus zu programmieren. Ein 8035 ist hinreichend.

---

Hier noch ein Artikel zum Zauberwürfel:

http://www.spektrum.de/magazin/rubik-spiele-mit-einfachen-gruppen/995466

Frank G. schrieb:
> Mal fragen wie er es macht:Youtube-Video "Rubik's Cube World
> Record 5.25 sec Collin Burns Slow Motion"
> ;)

Der schaut ja während des Lösens den Würfel an! Hier geht es doch darum, 
ob man allein durch Betrachten der Ausgangsposition ALLE Züge 
vorausbestimmen kann. Hier ein Beispiel:
https://www.youtube.com/watch?v=0RfJbcydNJ0

S. J. schrieb:
> Dann erzähl mal wieviel Züge er in einer Millisekunde berechnen kann.
> Und wie kommst du jetzt gleich auf deine Schlußfolgerung? Aus deiner
> Frage??

Schau dir mal das verlinkte Video im obigen Beitrag an. So viel kann der 
Linuxrechner allemal. Es geht hier nicht um das sture Durchprobieren 
aller möglichen Züge, sondern um einen Algorithmus, der alle Züge im 
Voraus berechnet. Und wenn das ein Mensch durch einfaches Anschauen des 
Ausgangszustandes kann, dann kann das eine Software allemal.

?!? schrieb:
> Schau dir mal das verlinkte Video im obigen Beitrag an. So viel kann der
> Linuxrechner allemal. Es geht hier nicht um das sture Durchprobieren
> aller möglichen Züge, sondern um einen Algorithmus, der alle Züge im
> Voraus berechnet. Und wenn das ein Mensch durch einfaches Anschauen des
> Ausgangszustandes kann, dann kann das eine Software allemal.

ein Mensch kann das nicht!

Der Mensch und die meisten Computer lösen stück für stück den Würfel. 
Das ist nicht der optimale weg. Für den Optimalen weg braucht man ein 
Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC 
zu machen.

https://de.wikipedia.org/wiki/Zauberw%C3%BCrfel#Optimale_L.C3.B6sungen

https://de.wikipedia.org/wiki/Gottes_Algorithmus

Nachtrag:

http://www.zeit.de/wissen/2010-08/rubik-zauberwuerfel-mathematik
[...]
Für menschliche Spieler, die sich an Zugfolgen halten, die sie auswendig 
gelernt haben, mag das stimmen. Sie benötigen meist sogar mehr als 40 
Züge. Ein
[...]

Peter II schrieb:
> ein Mensch kann das nicht!

Na wenn du meinst...
Ich habs selber schon gesehen, aber wenn ein Mensch das nicht kann, dann 
hab ich eben phantasiert.

Peter II schrieb:
> ein Mensch kann das nicht!
>
> Der Mensch und die meisten Computer lösen stück für stück den Würfel.
> Das ist nicht der optimale weg. Für den Optimalen weg braucht man ein
> Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC
> zu machen.

Selbst in dem von dir verlinkten Wikipedia-Beitrag ist beschrieben, daß 
ein Mensch das DOCH kann. Der Rekord liegt bei 21 Sekunden.
https://de.wikipedia.org/wiki/Zauberw%C3%BCrfel#Blindfold_Cubing

Behauptest du immer noch, daß ein Mensch das nicht kann?

?!? schrieb:
> Ich habs selber schon gesehen, aber wenn ein Mensch das nicht kann, dann
> hab ich eben phantasiert.

was hast du gesehen? Das ein Mensch jeden Würfel in 20 Zügen lösen kann? 
Oder das ein Mensch den Würfen sehr schnell lösen kann?

?!? schrieb:
> Selbst in dem von dir verlinkten Wikipedia-Beitrag ist beschrieben, daß
> ein Mensch das DOCH kann. Der Rekord liegt bei 21 Sekunden.
> https://de.wikipedia.org/wiki/Zauberw%C3%BCrfel#Blindfold_Cubing
>
> Behauptest du immer noch, daß ein Mensch das nicht kann?

ich bin scheinbar zu blöd zu lesen - wo steht das?

J.-u. G. schrieb:
> Möglicherweise ist dann der Weg, der auf einem kleinen PC in ein paar
> Millisekunden ermittelt werden kann, optimaler als der "Optimale Weg"?

was willst du jetzt damit sagen?

Ja es macht sinn nicht den schnellsten weg zu suchen, dafür aber sehr 
schnell EINEN weg zu finden. Genau das wird ja vermutlich dort gemacht.

Peter II schrieb:
> ?!? schrieb:
>> Ich habs selber schon gesehen, aber wenn ein Mensch das nicht kann, dann
>> hab ich eben phantasiert.
>
> was hast du gesehen? Das ein Mensch jeden Würfel in 20 Zügen lösen kann?
> Oder das ein Mensch den Würfen sehr schnell lösen kann?

Daß ein Mensch einen von mir persönlich beliebig verdrehten Würfel in 
kurzer Zeit BLIND lösen kann, nachdem er sich den verdrehten 
Ausgangszustand angesehen hatte und dann die Augen verbunden bekam. Und 
das mehrmals, also nachvollziehbar. Auch das Verdrehen wurde nicht nur 
von mir gemacht, sondern von verschiedenen Personen. So wie es im Video 
zu sehen ist...

?!? schrieb:
> Daß ein Mensch einen von mir persönlich beliebig verdrehten Würfel in
> kurzer Zeit BLIND lösen kann, nachdem er sich den verdrehten
> Ausgangszustand angesehen hatte und dann die Augen verbunden bekam. Und
> das mehrmals, also nachvollziehbar. Auch das Verdrehen wurde nicht nur
> von mir gemacht, sondern von verschiedenen Personen. So wie es im Video
> zu sehen ist...

das bezweifelt auch niemand. Ich habe nur geschrieben, das ein Mensch 
nicht den optimalen weg zu Lösung findet und mehr Drehungen braucht als 
notwendig. Genauso wie ein Computer wenn er nicht viel zeit hat.

Peter II schrieb:
> ich bin scheinbar zu blöd zu lesen - wo steht das?

Einfach den Link anklicken und da bist du schon beim richtigen 
Abschnitt.
"Blindfold Cubing"

?!? schrieb:
> Peter II schrieb:
>> ich bin scheinbar zu blöd zu lesen - wo steht das?
>
> Einfach den Link anklicken und da bist du schon beim richtigen
> Abschnitt.
> "Blindfold Cubing"

und da steht nichts von optimaler Lösung.

Peter II schrieb:
> das bezweifelt auch niemand. Ich habe nur geschrieben, das ein Mensch
> nicht den optimalen weg zu Lösung findet und mehr Drehungen braucht als
> notwendig. Genauso wie ein Computer wenn er nicht viel zeit hat.

Ich habe nirgends was vom optimales Weg geschrieben, sondern daß ein 
Mensch das in kurzer Zeit blind lösen kann. Daraufhin hast du 
geschrieben: "Ein Mensch kann das nicht!"

Fazit: Wenn das schon ein Mensch nach einmaligem Anschauen der 
Ausgangsposition in 21s blind lösen kann, dann kann das doch eine 
Software auf einem heutigen Rechner allemal im Millisekunden-Bereich.

Peter II schrieb:
> und da steht nichts von optimaler Lösung.

Habe ich auch niemals behauptet, siehe meinen obigen Beitrag.

J.-u. G. schrieb:
> Die Diskrepanz besteht im unterschiedlichen Verständnis von "optimal"
> (z.B. geringste Anzahl von Zügen, schnellste Zeit, usw., usf.).

die "geringste Anzahl von Zügen" ist übliche Frage bei dem Würfel.

Man könnte auch jede Lösung speichern - leider reicht dafür nicht mal 
die Google und Amazon cloud aus.

?!? schrieb:
> Habe ich auch niemals behauptet, siehe meinen obigen Beitrag.

du hast geschrieben

> Wieviele Züge wird der Linux-Rechner in einer Millisekunde berechnen
> können? Da fällt die "Stillstandszeit" des Würfels nicht ins Gewicht. Um
> einen einzigen Zug zu machen, brauchen die Schrittmotoren auf jeden Fall
> länger als die Lösung des gesamten Problems dauert.

wenn er den Optimalen weg berechnet, dann braucht er länger als die 
Motoren.

Laß doch mal den "optimalen Weg" beiseite. Davon war doch niemals die 
Rede und ich habe auch nichts davon geschrieben.
Fakt ist doch, daß selbst ein Mensch nur 21s braucht...

Johann L. schrieb:
> @Über Links gedacht
>
> Was du da über Lösen des Cubes erzählst ist kompletter Unsinn.  Offenbar
> hast du vom Cube(n) absolut keine Ahnung.

Naja, mit ein bißchen guten Willen lassen sich schon Lösungsansätze für 
den Zauberwürfel auf basis heuristischer Suche finden:
http://www.aaai.org/Papers/AAAI/1997/AAAI97-109.pdf

Hier würde die Manhattan Distanz als Metrik benutzt um die Position zu 
bewerten.

Auch die IDA* Suche als weiter informierte Suche wird auf den 
Zauberwürfel angewandt:
http://kth.diva-portal.org/smash/get/diva2:816583/FULLTEXT01.pdf

Die engl. WP kennt noch etliche andere Computer-Lösungsverfahren:
https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

Mit der Aussage "kompletter Unsinn" wäre ich äußerst vorsichtig.

MfG,

Um 2010 hat wohl ein PC ("a good desktop PC") gut 3s für die optimale 
Lösung gebraucht. Für eine gute Lösung (<= 20 Züge) weniger als eine 
Millisekunde.
Daß das relativ schnell geht liegt einfach daran, daß nachgewiesen ist, 
daß sich jede beliebige Stellung in maximal 20 Zügen lösen läßt.

guest schrieb:
> Um 2010 hat wohl ein PC ("a good desktop PC") gut 3s für die optimale
> Lösung gebraucht. Für eine gute Lösung (<= 20 Züge) weniger als eine
> Millisekunde.
> Daß das relativ schnell geht liegt einfach daran, daß nachgewiesen ist,
> daß sich jede beliebige Stellung in maximal 20 Zügen lösen läßt.

Kannst Du bitte den Link hirfür schreiben? Ich such auch nach der Dauer 
für eine Lösung, werd aber aus den Kociemba nicht ganz schlau, was er 
für hardware verwendet hat. Jedenfalls nicht in 5 Minuten: 
http://kociemba.org/cube.htm

Fpga K. schrieb:
> Kannst Du bitte den Link hirfür schreiben?

Sorry:
http://www.cube20.org/

Mike B. schrieb:
> schlussendlich sollte man sagen:
> Problem gelöst, nächstes.
>
> Oder wer hält es für sinnvoll, weiter Maschinen zu entwicklen und zu
> bauen, die genau dieses Problem in 0,8 oder 0,7 oder gar 0,5 sec. lösen
> können?
>
> Vielleicht kann man diese vorhandene Maschine noch auf
> Energieverbrauch/Größe/Kosten optimieren. Aber jedwede Bemühung der
> zeitlichen Optimierung halte ich für reine Resourcenverschwendung.

oder größer Würfel

https://de.wikipedia.org/wiki/Professor%E2%80%99s_Cube

Mike B. schrieb:

> Vielleicht kann man diese vorhandene Maschine noch auf
> Energieverbrauch/Größe/Kosten optimieren. Aber jedwede Bemühung der
> zeitlichen Optimierung halte ich für reine Resourcenverschwendung.

Ja, eigentlich ist das Problem seit 2010 gelöst, seit nachgewiesen ist 
das die optimale Lösung max. 20 hat.

Ein sich selbst lösender Würfel wäre vielleicht noch spannend. 
Beispielsweise mit Motoren in den Zentralsteinen.

Dass das System nur aus dem Anfangszustand einmal die nötigen Züge 
berechnet, wird im Video gesagt, ebenso, welcher Algorithmus verwendet 
wird. Und dass die Berechnung nicht schon im Vorfeld stattfindet, wird 
durch das Abdecken einer der Kameras illustriert.

Übrigens glaube ich, dass der Würfel auch leichtgängiger gemacht wurde. 
Er verdreht sich einmal in der Hand bei geringster Kraft.

Cooles Teil, vor allem wegen der simplen, billigen Hardware.

Ein Wuerfel eines Wuerfel-Profis ist auch auf superleichtgaengig 
getrimmt. Die koennen mit minimal Kraft gedreht werden. Man erreicht das 
mit Ausleiern, zb am Akkuschrauber, und mit Sand.

butsu schrieb:
> Dass das System nur aus dem Anfangszustand einmal die nötigen Züge
> berechnet, wird im Video gesagt, ebenso, welcher Algorithmus verwendet
> wird.

Etwa 01:40, "Kociemba algorithm"

Damit ist wohl das gemeint:
http://kociemba.org/math/imptwophase.htm

produziert eine Lösung mit etwa 30 moves. Ob wirklich alle Züge vor dem 
Start des Motors berechnet werden, wird nicht gesagt. Im Video läuft die 
PC-Anzeige und Motoren gleichzeitig. Es kann gut sein, das nach Phase 1 
(12 moves) die Motoren anlaufen und parallel Phase 2 (18 moves) 
berechnet wird. Und die 30 Züge Variante von 1992 hat Kociemba 
inzwischen auch verbessern können.


> Und dass die Berechnung nicht schon im Vorfeld stattfindet, wird
> durch das Abdecken einer der Kameras illustriert.

Ja illustriert, bewiesen ist durch das Ab-/Auf-Decken einer von vier 
Kameras nichts. Gut möglich das Kamera 4 nur das Startsignal liefert. 
Bei den anderen Läufen startet die Maschienerei auf Knopfdruck.

Peter II schrieb:
> Für den Optimalen weg braucht man ein
> Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC
> zu machen.

Die Berechnung (Kociemba) selber ist wohl grösstenteils Table-Lookup, 
also keine Hexerei und wurde vor über 20 Jahren auf einen Homecomputer 
implementiert. Also nix mit SuperDuper Rechencluster.
http://kociemba.org/math/imptwophase.htm


MfG,

Angeblich kann man durch genügend langes Ansehen des Würfels eine Lösung 
finden, die maximal 24 Züge dauert und nur auf Rotationen von 5 Seiten 
beruhen. Bei allen 6 Seiten sind es maximal 21 Züge, die man 
deterministisch ermitteln kann.

Optimiert waren es sogar unter 20 aber nicht mehr deterministisch.

Ganz gute Arbeit trotzdem.

Fpga K. schrieb:
> Peter II schrieb:
>> Für den Optimalen weg braucht man ein
>> Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC
>> zu machen.
>
> Die Berechnung (Kociemba) selber ist wohl grösstenteils Table-Lookup,
> also keine Hexerei und wurde vor über 20 Jahren auf einen Homecomputer
> implementiert. Also nix mit SuperDuper Rechencluster.
> http://kociemba.org/math/imptwophase.htm

das ist aber nicht der weg mit den wenigsten (optimale) schritten.

Peter II schrieb:
> Fpga K. schrieb:
>> Peter II schrieb:
>>> Für den Optimalen weg braucht man ein
>>> Rechencluster und viel zeit - das ist nicht mit einen kleinen Linux PC
>>> zu machen.
>>
>> Die Berechnung (Kociemba) selber ist wohl grösstenteils Table-Lookup,
>> also keine Hexerei und wurde vor über 20 Jahren auf einen Homecomputer
>> implementiert. Also nix mit SuperDuper Rechencluster.
>> http://kociemba.org/math/imptwophase.htm
>
> das ist aber nicht der weg mit den wenigsten (optimale) schritten.

Den hat er dann später auf einem PC implementiert, der mehr Speicher 
hatte als das eine MB des Atari ST. Die Rechendauer blieb weiterhin im 
Sekundenbereich. Wobei die Tabellen fürs lookUp (sicher) vorher 
berechnet wurden.

Das steht alles unter den genannten Links,auch die Quelltexte, für die 
Berechnung der optimalen Lösung einer Konfiguration brauchts wirklich 
nicht mehr.

Für den Nachweis das der algo für jeden Verdreher nicht mehr als x Züge 
braucht, muss man aber alle (signifikanten) Verdrehmöglichkeiten 
austesten. Da addieren sich die Sekunden zu (ca. 90) Rechenjahren auf 
und da macht sich der google cluster nicht schlecht. Aber für einen 
einzelnen verdrehten Cube reicht der Linux-PC völlig.

MfG,

Tiefbohrer schrieb:
> Das steht alles unter den genannten Links

steht da wirklich das er immer die Optimale Lösung findet? Ich konnte 
davon auf der Übersicht Seite nichts find.

Kannst du mal bitte zeigen, wo steht das das Verfahren immer die kleinst 
mögliche Anzahl von Schritten ermittelt?

Fpga K. schrieb:
> Ob wirklich alle Züge vor dem Start des Motors berechnet werden, wird
> nicht gesagt. Im Video läuft die PC-Anzeige und Motoren gleichzeitig. Es
> kann gut sein, das nach Phase 1 (12 moves) die Motoren anlaufen und
> parallel Phase 2 (18 moves) berechnet wird.

Das kann natürlich sein und wäre je nach Rechenzeit auch sinnvoll, 
ändert aber nichts daran, dass zwischendurch nicht mehr evaluiert wird, 
ob der Lösung näher gekommen wurde, womöglich gar durch weitere 
Auswertung der Kameras, wie weiter oben spekuliert wurde.


>> Und dass die Berechnung nicht schon im Vorfeld stattfindet, wird durch
>> das Abdecken einer der Kameras illustriert.
>
> Ja illustriert, bewiesen ist durch das Ab-/Auf-Decken einer von vier
> Kameras nichts. Gut möglich das Kamera 4 nur das Startsignal liefert.
> Bei den anderen Läufen startet die Maschienerei auf Knopfdruck.

Ein Video beweist prinzipiell nichts. Die Jungs sagen explizit, dass es 
so ist. Muss man natürlich nicht glauben, dann kann man aber auch alles 
andere bezweifeln...Und der Lauf mit abgedeckter Kamera wird ebenfalls 
per Tastendruck gestartet.

Auf Lego Mindstorms NXT 2.0 wurde mal ein Algorithmus implementiert, der 
den Würfel in maximal ca 30 Zügen löst (die exakte Zahl weiss ich nicht 
mehr). Zur Berechnung brauchte das Script maximal eine Minute.

Wobei man bedenken muss, dass der Script-Interpreter super lahm ist. In 
einer einfachen Schleife addiert er eine Integer Konstante zu einer 
Variable mit ca 10.000 Wiederholkungen pro Sekunde.

Wenn man nun berücksichtigt, dass ein PC mit jeder gängigen 
Programmiersprache mindestens 10.000 mal schneller ist, erübrigt sich 
die ganze Diskussion, wie schnell der Algorithmus ist. Wir reden hier 
von einem kleinen Bruchteil einer Sekunde.

Die Berechnung ist absolut kein Hexenwerk. Wirklich nicht.

Stefan U. schrieb:
> Die Berechnung ist absolut kein Hexenwerk. Wirklich nicht.

wie schon mehrfach geschrieben - wenn man den schnellsten weg haben will 
ist es ein Hexenwerk. Um es einfach nur lösen braucht man gar nicht 
großartig rechnen.

Peter II schrieb:
> Tiefbohrer schrieb:
>> Das steht alles unter den genannten Links
>
> steht da wirklich das er immer die Optimale Lösung findet? Ich konnte
> davon auf der Übersicht Seite nichts find.

Da steht das in der verbesserten vVriante bei suboptimalen Lösungen 
nicht abgebrochen wird:

"As already mentioned above, the algorithm does not stop when a first 
solution is found but continues to search for shorter solutions by 
carrying out phase 2 from suboptimal solutions of phase 1."

http://kociemba.org/math/imptwophase.htm


Für Korf's algorithmus wird ausdrücklich gesagt, das er immer die 
optimale Lösung findet:
"Although this algorithm will always find optimal solutions, there is no 
worst case analysis."

https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube#Korf.27s_algorithm

Und er nutzt IDA* nutzt also die skizierte Vorgehensweise von Abschätzen 
des Abstands zur Lösung und verfolgt nur die Abfolgen die näher ans Ziel 
führen:

"Da nur die Länge des Weges vom Startknoten bis zum aktuell untersuchten 
Knoten exakt bekannt ist, wird die Weglänge vom aktuell untersuchten 
Knoten bis zum Zielknoten mittels einer Heuristik geschätzt."

https://de.wikipedia.org/wiki/IDA*

Also so wie ich es gestern beschrieb:

Über Links gedacht schrieb:
> Genau, züge vorausberechnen und stellung bewerten und dann drehen.
>
> So machen es auch die Schachcomputer, Permutation der Ausgangsstellung
> durch durchspielen legaler Zugfolgen und bewertung der so erzielten
> stellungen.

Der Trick dabei ist das Problem in die Graphentheorie zu überführen 
(über das Erstellen des Zustandsgraph) und dann den kürzesten Pfad zum 
Ursprungszustand zu finden. Dass ohne Brute-Force zu erreichen gibt es 
mehrere Ansätze. Folgend ein deutscher Artikel der mal in das Problem 
der "Kürzester Weg-Algos" einführt: 
http://www.gm.fh-koeln.de/~hk/lehre/ala/ws0506/Praktikum/Projekt/E_gelb/ALA-HeuristischeAlgorithmen-Jena-Liebelt.pdf

Johann L. schrieb:
> @Über Links gedacht
>
> Was du da über Lösen des Cubes erzählst ist kompletter Unsinn.  Offenbar
> hast du vom Cube(n) absolut keine Ahnung.

Ich betrachte diese Aussage als komplett wiederlegt.

Peter II schrieb:
> Stefan U. schrieb:
>> Die Berechnung ist absolut kein Hexenwerk. Wirklich nicht.
>
> wie schon mehrfach geschrieben - wenn man den schnellsten weg haben will
> ist es ein Hexenwerk.

Sorry, aber dein Beharren auf deine mehrfach wiederlegte Privatmeinung 
wirkt langsam kindisch.