PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Bewiesen: Egal welche Ausgangsstellung, Zauberwürfel in maximal 20 Zügen zu lösen.


Avalox
2010-08-11, 08:57:53
Tomas Rokicki konnte nun beweisen, dass mit maximal 20 Zügen der Zauberwürfel aus jeder beliebigen Stellung zu lösen ist.

http://www.n-tv.de/wissen/20-Zuege-reichen-zum-Loesen-article1239816.html

josefYY
2010-08-11, 09:23:06
Tomas Rokicki konnte nun beweisen, dass mit maximal 20 Zügen der Zauberwürfel aus jeder beliebigen Stellung zu lösen ist.

http://www.n-tv.de/wissen/20-Zuege-reichen-zum-Loesen-article1239816.html
20 ist überraschend wenig.
Erwartet hätte ich wohl eher das 10-fache.

drexsack
2010-08-11, 09:30:56
Beeindruckend, ich würde vermutlich ewig dafür brauchen.

Avalox
2010-08-11, 09:33:39
20 ist überraschend wenig.
Erwartet hätte ich wohl eher das 10-fache.

Ja, ist überraschend.

Bin mal gespannt wie lange es noch dauert, bis man beim Schachspiel beweisen kann, dass eine Seite optimal gespielt immer gewinnt, bzw. Schach optimal gespielt nicht zu gewinnen ist.


Interessant zum Ansatz oben ist ja auch die benötigte Rechenleistung.

"Am den entsprechenden Beweis erbringen zu können, benötigte Rokicki eine gewaltige Rechenleistung. Nach Angaben der Projektgruppe hätte ein moderner PC mit einem vierkernigen Intel Nehalem-Prozessor mit 2,8 Gigahertz rund 35 Jahre benötigt, um die notwendigen Berechnungen durchzuführen. "

tombman
2010-08-11, 09:45:24
Mein 4.2 Ghz Sechskerner würde nur 15.5 Jahre brauchen ;D

Und wenn man die Rechenleistung der 3 480er anzapfen könnte.... :naughty:

ed1k
2010-08-11, 09:48:04
Mein 4.2 Ghz Sechskerner würde nur 15.5 Jahre brauchen ;D

Und wenn man die Rechenleistung der 3 480er anzapfen könnte.... :naughty:

made my day xD n1 tombi

Baalzamon
2010-08-11, 09:50:35
[...]
Bin mal gespannt wie lange es noch dauert, bis man beim Schachspiel beweisen kann, dass eine Seite optimal gespielt immer gewinnt, bzw. Schach optimal gespielt nicht zu gewinnen ist.
[....]
Ich dachte es wäre schon längst klar das es für jedes Spiel mit zwei Spielern und ohne Zufall ein System gibt um entweder zu gewinnen oder (wenn der andere auch optimal spielt) ein Remis zu holen. :confused:

[...]
Und wenn man die Rechenleistung der 3 480er anzapfen könnte.... :naughty:
Was dir nichts hilft wenn die Berechnung nicht parallelisierbar ist. ;)

JaDz
2010-08-11, 09:54:42
Was dir nichts hilft wenn die Berechnung nicht parallelisierbar ist. ;)
Ist sie das in diesem Fall nicht?

Baalzamon
2010-08-11, 09:55:53
Ist sie das in diesem Fall nicht?
Ich weiss es nicht.

Avalox
2010-08-11, 10:11:32
Ich dachte es wäre schon längst klar das es für jedes Spiel mit zwei Spielern und ohne Zufall ein System gibt um entweder zu gewinnen oder (wenn der andere auch optimal spielt) ein Remis zu holen. :confused:



Ja. Nur weiss man nicht wozu Schach gehört. Zur Gruppe der Spiele, bei welche eine Seite immer im Vorteil ist, oder es optimal gespielt immer auf ein Remis hinausläuft

Wird dann auch den perfekt spielenden Schachcomputer geben. Ist bestimmt interessant dann gegen solch einen Computer zu spielen.
Der Mensch spielt und eine Zahl auf dem Bildschirm zeigt dann an, nach wie vielen Zügen der Mensch besiegt werden wird. Und bei jedem weiteren Fehler des Menschen, springt dann die Zahl in immer näher in Richtung 1.

Oid
2010-08-11, 11:29:07
Wie haben die das gemacht? Den Algorithmus auf jede mögliche Stellung angewendet?

_DrillSarge]I[
2010-08-11, 11:31:19
gilt das für alle (:freak:) oder nur für die 3x3 dinger? oder 4x4?

tombman
2010-08-11, 13:28:11
Was dir nichts hilft wenn die Berechnung nicht parallelisierbar ist. ;)
Ja klar, die haben bei google nur einen Rechner mit EINER Cpu angezapft, denn sie hatten gerade kein Geld für eine 100€ Cpu :ulol:

Die haben Google gerade wegen der unpackbaren Rechenleistung angezapft -> hochparallelisierter code...

Insofern: vielleicht nur 5 Jahre auf meinem Sys? ;D

Avalox
2010-08-11, 13:30:03
I[;8199902']gilt das für alle (:freak:) oder nur für die 3x3 dinger? oder 4x4?

4x4x4?
Habe ich noch nie gesehen. Wie soll den dort die Achse in der Mitte überhaupt halten?

_DrillSarge]I[
2010-08-11, 13:32:51
4x4x4?
Habe ich noch nie gesehen. Wie soll den dort die Achse in der Mitte überhaupt halten?
sowas:
http://www.zauberwuerfel.de/wuerfel/rubiks-cube-4x4x4/

Sephiroth
2010-08-11, 13:34:13
Wie haben die das gemacht? Den Algorithmus auf jede mögliche Stellung angewendet?
Im wesentlich haben sie das so gemacht, nur haben sie die Anzahl der nötigen Ausgangspositionen noch reduzieren können.
How We Did It
How did we solve all 43,252,003,274,489,856,000 positions of the Cube?

* We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.
* We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.
* We did not find optimal solutions to each position, but instead only solutions of length 20 or less.
* We wrote a program that solved a single set in about 20 seconds.
* We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets.

http://www.cube20.org/

Rooter
2010-08-11, 19:00:43
Der Informatiker Rokicki befasst sich schon länger mit der Mathematik des Zauberwürfels. Im August 2008 konnte er bereits beweisen, dass sich die farbigen Felder aus jeder beliebigen Position mit maximal 25 Zügen wieder ordnen lassen. Kürzlich wurde der Algorithmus von ihm auf maximal 22 Züge verbessert.Und wieso ist das hier jetzt der "Gottes Algorithmus"? Wer sagt dass er nicht nächstes Jahr einen Weg findest jede Stellung in z.B. 18 Zügen zu lösen? Bisher hat er ja auch ständig seinen eigenen Wert unterboten.


Insofern: vielleicht nur 5 Jahre auf meinem Sys? ;DDann kannst'e für min. 5 Jahre aber nimmer g'scheit zocken! :tongue:

MfG
Rooter

Rolsch
2010-08-11, 19:11:54
Bei meinem Würfel geht das deutlich schneller!

PatkIllA
2010-08-11, 19:17:25
Und wieso ist das hier jetzt der "Gottes Algorithmus"? Wer sagt dass er nicht nächstes Jahr einen Weg findest jede Stellung in z.B. 18 Zügen zu lösen? Bisher hat er ja auch ständig seinen eigenen Wert unterboten.Weil es mindestens eine Stellung gibt für die bewiesen ist, dass man sie nicht in weniger Schritten lösen kann.

Viel wichtiger ist doch der Beweisversuch von P != NP

doublehead
2010-08-11, 19:41:25
Da ich nicht mit der Bahn fahre, werde ich das wohl nie schaffen.

Sephiroth
2010-08-11, 19:43:29
Und wieso ist das hier jetzt der "Gottes Algorithmus"? Wer sagt dass er nicht nächstes Jahr einen Weg findest jede Stellung in z.B. 18 Zügen zu lösen? Bisher hat er ja auch ständig seinen eigenen Wert unterboten.

MfG
Rooter
18 Züge galten anfangs als Minimum, wurde aber 1995 durch einen Beweis von Michael Reid auf 20 erhöht. (siehe webseite (http://www.cube20.org/)) Aber prinzipiell hast du natürlich recht: vielleicht kommt irgendwann einer daher und beweist,dass es doch mit weniger als 20 Zügen möglich ist.

tombman
2010-08-11, 20:00:31
Dann kannst'e für min. 5 Jahre aber nimmer g'scheit zocken! :tongue:

I CAN :cool:

Guckstu:
http://www.forum-3dcenter.org/vbulletin/showpost.php?p=8200990&postcount=2643

Oid
2010-08-11, 20:07:23
18 Züge galten anfangs als Minimum, wurde aber 1995 durch einen Beweis von Michael Reid auf 20 erhöht. (siehe webseite (http://www.cube20.org/)) Aber prinzipiell hast du natürlich recht: vielleicht kommt irgendwann einer daher und beweist,dass es doch mit weniger als 20 Zügen möglich ist.

Wenn eine Höchstanzahl von 20 Zügen mathematisch korrekt bewiesen wurde, dann wird auch in 1Mio Jahren keiner beweisen, dass eigentlich doch weniger Züge nötig sind.

ux-3
2010-08-11, 20:12:09
Anekdote von ca 1980 oder 81. Ein Typ in meiner Klasse hatte damit geprahlt, den Würfel immer in ein paar Minuten zu lösen. Ich hatte gerade in Chemie gelernt, was optische Isomere sind. Also hab ich die Ecksteine etwas manipuliert. :redface:

Er hat ihn nicht gelöst bekommen... (Ja, das war unfair....)