+- Speedcube.de Forum (https://forum.speedcube.de)
+-- Forum: Speedcubing (https://forum.speedcube.de/forumdisplay.php?fid=7)
+--- Forum: Diskussion zu Methoden, Theorie und Techniken (https://forum.speedcube.de/forumdisplay.php?fid=26)
+--- Thema: God's Number (/showthread.php?tid=4949)
RE: God's Number - Yeti - 02.12.2009
Ok, diese Aussage macht sicherlich Sinn. Daß es wirklich so ist, war mir bislang allerdings nicht bekannt.
Ich war halt in deinem Satz über das "darum" gestolpert, das ich so interpretiert habe, daß du aus durchschnittlich 18 unmittelbar auf fast immer 18 folgerst.
Kann man den Beweis für optimale Lösung meist in 18 Zügen irgendwo nachlesen, oder wurde das rein empirisch mit brutaler Rechenpower ermittelt, indem ein Computer die optimalen Lösungen für eine Stichprobe von Samples ermittelt hat? Bei 4,3*10^20 unterschiedlichen Stellungen war das dann allerdings sicher eine relativ kleine Stichprobe.
RE: God's Number - TobiasD - 02.12.2009
Gods Number... Fuer den 3x3.. Was ist denn mit dem 2x2?
RE: God's Number - Yeti - 02.12.2009
(02.12.2009, 17:12)TobiasD schrieb: Gods Number... Fuer den 3x3.. Was ist denn mit dem 2x2?
Hier wird behauptet, daß diese 11 ist, allerdings ohne Quellenangabe. Aber bei einem Lösungsraum von 3674160 Stellungen ist es wohl trivial, das einfach durchrechnen zu lassen. Insofern glaube ich die 11 jetzt einfach mal.
RE: God's Number - schimpler - 02.12.2009
11 für den 2x2 kommt mir etwas viel vor. Ich mein ca.18 für den 3er...
RE: God's Number - sol1x - 02.12.2009
11 für den 2x2 kommt dir viel vor???? Überleg mal genauer ;-)
im übrigen gibt es ein System, das im Durchschnitt 12,75 Züge braucht ;-)
Ich bin sehr gespannt, ob irgendjemand mal einen Weg findet zu beweisen wieviel Züge man max. braucht.
Mit dem PC ausrechnen ist ja mal viel zu billig ;-) das wäre ab 3x3 aber sowieso nichtmehr möglich.
RE: God's Number - Sébastien - 02.12.2009
(02.12.2009, 18:02)schimpler schrieb: Ich mein ca.18 für den 3er...
Ne, is nich!
RE: God's Number - Hubi - 02.12.2009
(02.12.2009, 17:06)Yeti schrieb: Kann man den Beweis für optimale Lösung meist in 18 Zügen irgendwo nachlesen, oder wurde das rein empirisch mit brutaler Rechenpower ermittelt, indem ein Computer die optimalen Lösungen für eine Stichprobe von Samples ermittelt hat? Bei 4,3*10^20 unterschiedlichen Stellungen war das dann allerdings sicher eine relativ kleine Stichprobe.Das mit den durchschnittlich 18? im Jahr 1997 glaub ich kaum, dass es empirisch gemacht wurde... aber ich hab keine Ahnung, wo...
der 22er Beweis wurde mit gewaltiger Rechenleistung durchgeführt...
RE: God's Number - sol1x - 02.12.2009
(02.12.2009, 17:06)Yeti schrieb: Ok, diese Aussage macht sicherlich Sinn. Daß es wirklich so ist, war mir bislang allerdings nicht bekannt.
Ich war halt in deinem Satz über das "darum" gestolpert, das ich so interpretiert habe, daß du aus durchschnittlich 18 unmittelbar auf fast immer 18 folgerst.
Kann man den Beweis für optimale Lösung meist in 18 Zügen irgendwo nachlesen, oder wurde das rein empirisch mit brutaler Rechenpower ermittelt, indem ein Computer die optimalen Lösungen für eine Stichprobe von Samples ermittelt hat? Bei 4,3*10^20 unterschiedlichen Stellungen war das dann allerdings sicher eine relativ kleine Stichprobe.
http://www.speedcubers.de/forum/showthread.php?tid=1611&page=1
lies da mal nach ... vll. weißt du dann wie groß die Zahl ist - die du nanntest.
Außerdem hast du dich bei der 10er Potenz etwas vertan - aber egal.
Und natürlich muss man nicht alle Stellungen durchrechnen ;-)
RE: God's Number - Markus Pirzer - 02.12.2009
(02.12.2009, 17:06)Yeti schrieb: Ok, diese Aussage macht sicherlich Sinn. Daß es wirklich so ist, war mir bislang allerdings nicht bekannt.
Ich war halt in deinem Satz über das "darum" gestolpert, das ich so interpretiert habe, daß du aus durchschnittlich 18 unmittelbar auf fast immer 18 folgerst.
Kann man den Beweis für optimale Lösung meist in 18 Zügen irgendwo nachlesen, oder wurde das rein empirisch mit brutaler Rechenpower ermittelt, indem ein Computer die optimalen Lösungen für eine Stichprobe von Samples ermittelt hat? Bei 4,3*10^20 unterschiedlichen Stellungen war das dann allerdings sicher eine relativ kleine Stichprobe.
Herbert Kociemba hat das mal mit einer Stichprobe von 100000 Stellungen ausgerechnet, und kam dabei zu dem Ergebnis, dass 67% dieser Stellungen in 18 Zügen lösbar waren (http://www.kociemba.org/performance.htm). Aber du hast natürlich vollkommen recht, im Vergleich zu 4,3 Trillionen Stellungen ist das wirklich eine extrem kleine Stichprobe.
(02.12.2009, 17:18)Yeti schrieb:(02.12.2009, 17:12)TobiasD schrieb: Gods Number... Fuer den 3x3.. Was ist denn mit dem 2x2?
Hier wird behauptet, daß diese 11 ist, allerdings ohne Quellenangabe. Aber bei einem Lösungsraum von 3674160 Stellungen ist es wohl trivial, das einfach durchrechnen zu lassen. Insofern glaube ich die 11 jetzt einfach mal.
Auf wikipedia steht genau dasselbe (http://en.wikipedia.org/wiki/Pocket_Cube#Permutations), sogar mit einer Auflistung wieviele Stellungen sich in wievielen Zügen lösen lassen. Durchschnittlich läßt sich der 2er Würfel in 9 Zügen lösen (etwas mehr als 50% aller Stellungen). Es wird auch erwähnt dass sich das mit einem Brute-Force-Algorithmus berechnen läßt, bei den wenigen Möglichkeiten ist das mit einem schnellen Rechner ja kein Problem.
RE: God's Number - Yeti - 03.12.2009
(02.12.2009, 21:02)sol1x schrieb: http://www.speedcubers.de/forum/showthread.php?tid=1611&page=1
lies da mal nach ... vll. weißt du dann wie groß die Zahl ist - die du nanntest.
Außerdem hast du dich bei der 10er Potenz etwas vertan - aber egal.
Und natürlich muss man nicht alle Stellungen durchrechnen ;-)
Mir fehlt zwar eine intuitive Vorstellung, wie groß 10^19 ist, aber mir ist durchaus bewußt, daß das verdammt viel ist. Sicherlich zu viel, um jeden dieser Fälle mit unserer heutigen Hardware durchspielen zu lassen.
Da kommt es dann auf den Faktor 10, um den ich mich da vertan habe, auch schon nicht mehr an.
(02.12.2009, 21:30)Markus Pirzer schrieb: Herbert Kociemba hat das mal mit einer Stichprobe von 100000 Stellungen ausgerechnet, und kam dabei zu dem Ergebnis, dass 67% dieser Stellungen in 18 Zügen lösbar waren (http://www.kociemba.org/performance.htm). Aber du hast natürlich vollkommen recht, im Vergleich zu 4,3 Trillionen Stellungen ist das wirklich eine extrem kleine Stichprobe.
Jetzt kommt es halt darauf an, wie repräsentativ diese Stichprobe war. Und basierend auf dem heutigen Wissen stelle ich es mir sehr schwierig vor, Regeln für eine repräsentative Stichprobe aufzustellen. Natürlich kann man per Zufallsgenerator erzeugte Scrambles nehmen. Aber ich denke, das Risiko dafür, nicht repräsentativ zu sein ist relativ hoch.