GOD'S ALGORITHM
+34
omarismyname
popoy
shirosaki
luigiyotoko
dotdotdot
luk
rafael1991
o0sample0o
sirian23
isaganiesteron
pricz
tungkel_08
stralbem
jolo_mat2008
joseph24
Purple Frost
phatj
jestoni143
lorcan
jhong
Jome
greatauror28
Brian Nicole Uy
hyfly
SlowestCuber
pancho86
geocine
pajodaep
cmdsaved
cubekid
jettyboy1
van21691
MetaboringJohnCañares
BaruhbaL
38 posters
:: Cuber's Talk :: Speedcubing
Page 1 of 2
Page 1 of 2 • 1, 2
GOD'S ALGORITHM
Two-Phase-Algorithm and God's Algorithm
The algorithm which gives an optimal solution in the sense that there is no shorter solution is called God's algorithm. There are cube positions (for example the superflip which flips all 12 edges), which are known to have a shortest maneuver length of 20 moves to be solved. It is still an open problem if there are cube positions which require 21 moves or more with God's Algorithm.
I generated 1 million random cubes on a 3 GHz Pentium 4 PC, trying to find a cube which was not solvable within 20 moves with the Two-Phase-Algorithm. This cube then would be a test candidate for a position which would need at least 21 moves to be solved with God's Algorithm.
But the Two-Phase-Algorithm solved all generated random positions within 20 moves. More precisely, it solved about 30000 random cubes per hour and the final distribution of the maneuver length was:
13: 4, 14: 18, 15: 81, 16: 609, 17: 3893, 18: 23411, 19: 141366, 20: 830618.
This shows, that the probability to find a random cube position which cannot be solved within 20 moves with the Two-Phase-Algorithm in a reasonable time must be very low or zero.
It also shows: If there are any cube positions which need at least 21 moves to be solved, these positons are very rare and there is almost no chance to find such positions by random.
I also used the optimal solver module of Cube Explorer to solve 1000 random positions optimally. I found the following distribution for the optimal maneuver length:
The average optimal solving length is ~17.7 .
The average solving time for a random cube was less than two minutes on a 3 GHz Pentium 4 PC and a special version of Cube Explorer, which needs 3 GB of Ram. In this sense Cube Explorer's implementation of God's Algorithm does a decent job, though there theoretically could exist some situations, which would need days, months, years... to be solved.
The theoretical distribution for the maneuver length of God's Algorithm for Rubiks Cube is only known for maneuver lengths less then 11.
Because there are 1, 18, 243, 3240, 43239, 574908, 7618438, 100803036,1332343288, 17596479795, 232248063316, 3063288809012 positions which have a shortes maneuver length of n moves for n = 0 to 11 (see sequence A080601 in the On-Line Encyclopedia of Integer Sequences) and there are 43252003274489856000 different cube positions, we get for the probability P to solve a random cube optimally in n moves:
Maneuver Length n
Probability P
Branching Factor B
0
2.31203 *10-20
18
1
4.16166*10-19
13.5
2
5.61824*10-18
13.3333
3
7.49098*10-17
13.3454
4
9.99699*10-16
13.2961
5
1.32921*10-14
13.2516
6
1.76141*10-13
13.2315
7
2.3306*10-12
13.2173
8
3.08042*10-11
13.2072
9
4.06836*10-10
13.1986
10
5.36965*10-9
~13.12 (estimated)
11
7.08242×10-8
~13.12 (estimated)
12
~9.3*10-7
~13.12 (estimated)
13
~0.000012
~13.12 (estimated)
14
~0.00016
~13.12 (estimated)
15
~0.0022
~13.12 (estimated)
16
~0.029
~13.12 (estimated)
17
simulation result: ~0.26
~2.65
18
simulation result: ~0.69
~0.04
19
simulation result: ~0.03
?
20
P > 0
?
21 ..... 29
unknown, but presumably 0
?
30 or more
0
0
That the maneuver lenght of God's Algorithm has an upper bound of 29 moves is a consequence of the fact, that the two-phase-algorithm has an upper bound of 29 moves. Phase 1 needs at most 12 moves and phase 2 needs at most 18 moves. Michael Reid showed in 1995, that the 18 moves case for phase 2 always can be avoided.
In my opinion the most promising way to reduce the upper bound of God's Algorithm will be a more detailed analysis of the two-phase-algorithm which includes the analysis of suboptimal solutions of phase 1.
The algorithm which gives an optimal solution in the sense that there is no shorter solution is called God's algorithm. There are cube positions (for example the superflip which flips all 12 edges), which are known to have a shortest maneuver length of 20 moves to be solved. It is still an open problem if there are cube positions which require 21 moves or more with God's Algorithm.
I generated 1 million random cubes on a 3 GHz Pentium 4 PC, trying to find a cube which was not solvable within 20 moves with the Two-Phase-Algorithm. This cube then would be a test candidate for a position which would need at least 21 moves to be solved with God's Algorithm.
But the Two-Phase-Algorithm solved all generated random positions within 20 moves. More precisely, it solved about 30000 random cubes per hour and the final distribution of the maneuver length was:
13: 4, 14: 18, 15: 81, 16: 609, 17: 3893, 18: 23411, 19: 141366, 20: 830618.
This shows, that the probability to find a random cube position which cannot be solved within 20 moves with the Two-Phase-Algorithm in a reasonable time must be very low or zero.
It also shows: If there are any cube positions which need at least 21 moves to be solved, these positons are very rare and there is almost no chance to find such positions by random.
I also used the optimal solver module of Cube Explorer to solve 1000 random positions optimally. I found the following distribution for the optimal maneuver length:
The average optimal solving length is ~17.7 .
The average solving time for a random cube was less than two minutes on a 3 GHz Pentium 4 PC and a special version of Cube Explorer, which needs 3 GB of Ram. In this sense Cube Explorer's implementation of God's Algorithm does a decent job, though there theoretically could exist some situations, which would need days, months, years... to be solved.
The theoretical distribution for the maneuver length of God's Algorithm for Rubiks Cube is only known for maneuver lengths less then 11.
Because there are 1, 18, 243, 3240, 43239, 574908, 7618438, 100803036,1332343288, 17596479795, 232248063316, 3063288809012 positions which have a shortes maneuver length of n moves for n = 0 to 11 (see sequence A080601 in the On-Line Encyclopedia of Integer Sequences) and there are 43252003274489856000 different cube positions, we get for the probability P to solve a random cube optimally in n moves:
Maneuver Length n
Probability P
Branching Factor B
0
2.31203 *10-20
18
1
4.16166*10-19
13.5
2
5.61824*10-18
13.3333
3
7.49098*10-17
13.3454
4
9.99699*10-16
13.2961
5
1.32921*10-14
13.2516
6
1.76141*10-13
13.2315
7
2.3306*10-12
13.2173
8
3.08042*10-11
13.2072
9
4.06836*10-10
13.1986
10
5.36965*10-9
~13.12 (estimated)
11
7.08242×10-8
~13.12 (estimated)
12
~9.3*10-7
~13.12 (estimated)
13
~0.000012
~13.12 (estimated)
14
~0.00016
~13.12 (estimated)
15
~0.0022
~13.12 (estimated)
16
~0.029
~13.12 (estimated)
17
simulation result: ~0.26
~2.65
18
simulation result: ~0.69
~0.04
19
simulation result: ~0.03
?
20
P > 0
?
21 ..... 29
unknown, but presumably 0
?
30 or more
0
0
That the maneuver lenght of God's Algorithm has an upper bound of 29 moves is a consequence of the fact, that the two-phase-algorithm has an upper bound of 29 moves. Phase 1 needs at most 12 moves and phase 2 needs at most 18 moves. Michael Reid showed in 1995, that the 18 moves case for phase 2 always can be avoided.
In my opinion the most promising way to reduce the upper bound of God's Algorithm will be a more detailed analysis of the two-phase-algorithm which includes the analysis of suboptimal solutions of phase 1.
BaruhbaL- 2x2x2
-
Number of posts : 168
Age : 39
Registration date : 2007-06-24
Re: GOD'S ALGORITHM
hahaha, I can't understand this! But whoever discovers God's Algorithm, it would be me! hehe! kidding.
Re: GOD'S ALGORITHM
ok. i get the first few paragraphs but the rest is kind of boggling (and i'm in math honors...T_T)
sounds interesting. if you had more labels ehehe and easy english
sounds interesting. if you had more labels ehehe and easy english
Re: GOD'S ALGORITHM
cant understand the numbers.... to technical... hehehe
but interesting topic....
but interesting topic....
cubekid- 2x2x2
-
Number of posts : 237
Age : 44
Location : Antipolo City
Registration date : 2007-10-16
Re: GOD'S ALGORITHM
Grabe! dumudugo ang ilong ko!
pajodaep- 3x3x3
-
Number of posts : 781
Age : 39
Registration date : 2007-07-16
Re: GOD'S ALGORITHM
meron ka bang sample code ng two phase algorithm..
geocine- 2x2x2
-
Number of posts : 390
Age : 34
Location : J. Ruiz, San Juan City
Registration date : 2007-10-19
Re: GOD'S ALGORITHM
aheheheh naintindihan ko ung ....ano nga ba un ahhehe
SlowestCuber- 2x2x2
-
Number of posts : 354
Age : 33
Location : Dasmariñas Cavite
Registration date : 2007-10-23
Re: GOD'S ALGORITHM
npakhusay.
ang galing...
nya...
hehehe...
d q maintindihan...
ang galing...
nya...
hehehe...
d q maintindihan...
hyfly- 2x2x2
-
Number of posts : 476
Age : 38
Location : malabon
Registration date : 2007-10-20
Re: GOD'S ALGORITHM
cool.......
Brian Nicole Uy- 2x2x2
-
Number of posts : 198
Age : 31
Location : Manila, Manila Philippines
Registration date : 2007-08-14
Re: GOD'S ALGORITHM
nag sesearch langako aksident lng ang pagkakakita ko ahaha
SlowestCuber- 2x2x2
-
Number of posts : 354
Age : 33
Location : Dasmariñas Cavite
Registration date : 2007-10-23
Re: GOD'S ALGORITHM
you did well researching all of this...anyway, i prefer CFOP for that matter.....
greatauror28- 3x3x3
- Number of posts : 530
Age : 39
Registration date : 2007-08-27
Re: GOD'S ALGORITHM
God's Algorithm simply states that the cube can be solved in set number of moves, whatever the scramble. Parang sa cross, ang GA nun is 7 since it can always be solved in 7 moves or less.
There's a study about this a while back, diba? About the God's Algorithm of the Rubik's Cube. It was done by some university math professors in the US.
Ang pagkakaalam ko, 25 moves lang ang God's Algorithm. Tops. Pero di na ako sure. Ito yung sinusubukan palaging gawin sa Fewest Moves Competition. Hanapin yung GA so that sobrang baba ng moves na kailangan.
There's a study about this a while back, diba? About the God's Algorithm of the Rubik's Cube. It was done by some university math professors in the US.
Ang pagkakaalam ko, 25 moves lang ang God's Algorithm. Tops. Pero di na ako sure. Ito yung sinusubukan palaging gawin sa Fewest Moves Competition. Hanapin yung GA so that sobrang baba ng moves na kailangan.
Re: GOD'S ALGORITHM
ahehhe gwa nga tau sariling method
T_T ahehhe
T_T ahehhe
SlowestCuber- 2x2x2
-
Number of posts : 354
Age : 33
Location : Dasmariñas Cavite
Registration date : 2007-10-23
Re: GOD'S ALGORITHM
ilan algs kaya toh?? hehe
BaruhbaL- 2x2x2
-
Number of posts : 168
Age : 39
Registration date : 2007-06-24
Re: GOD'S ALGORITHM
interesting sir!!
kaso baka 'pag sinimulan kong pag-aralan baka mawalan na ko ng interest mabuhay....
ahehe'
juklang....
salamat sa idea...
balang araw maiintindihan ko din yan..
kaso baka 'pag sinimulan kong pag-aralan baka mawalan na ko ng interest mabuhay....
ahehe'
juklang....
salamat sa idea...
balang araw maiintindihan ko din yan..
jhong- 2x2x2
-
Number of posts : 59
Age : 33
Location : Sta. Mesa, Mla
Registration date : 2008-02-06
Re: GOD'S ALGORITHM
wtf ano yan statistics waaaahhh d ko maintindihan hehe ang gling ni
kuya
can u explain it in an easy way waaaaaaahhh
kuya
can u explain it in an easy way waaaaaaahhh
lorcan- 2x2x2
-
Number of posts : 279
Age : 32
Registration date : 2008-01-28
Re: GOD'S ALGORITHM
as far as i know, only rubot II uses the god's algorithm... at around 26 moves tops at ~20 sec considering its hydraulic arms. never heard of the 25 moves only....
jestoni143- 2x2x2
-
Number of posts : 132
Age : 37
Registration date : 2007-06-29
Re: GOD'S ALGORITHM
epistaxis..whew...
phatj- 2x2x2
-
Number of posts : 291
Age : 36
Location : V&G consolacion, cebu
Registration date : 2008-03-12
Re: GOD'S ALGORITHM
I downloaded this program that solves ANY given cube within 21 moves or less.. It uses GA as well, I guess..
I'll host it if anyone requests for it, though.. ^__^ Less than 1 MB lang naman ung file, pero mangangailangan ng more or less 60MB.. XD
PM me na lang kung gusto nyo..
I'll host it if anyone requests for it, though.. ^__^ Less than 1 MB lang naman ung file, pero mangangailangan ng more or less 60MB.. XD
PM me na lang kung gusto nyo..
Re: GOD'S ALGORITHM
cool..",) i also understand the 1st paragraphs..",) & others r supernatural.. wahaha!",)
joseph24- 2x2x2
-
Number of posts : 270
Age : 34
Location : marikina city
Registration date : 2007-12-15
Re: GOD'S ALGORITHM
try search rubot II on youtube... you can see that it uses GA....
jestoni143- 2x2x2
-
Number of posts : 132
Age : 37
Registration date : 2007-06-29
Re: GOD'S ALGORITHM
^ yes, I just found out that it uses the same program i just mentioned kanina.. cool!! XD
Page 1 of 2 • 1, 2
Similar topics
» Favorite Algorithm...............
» OH practice algorithm (video)
» Official blindfold algorithm list!
» cycle decomposition algorithm&corner orientation(3cycle)
» OH practice algorithm (video)
» Official blindfold algorithm list!
» cycle decomposition algorithm&corner orientation(3cycle)
:: Cuber's Talk :: Speedcubing
Page 1 of 2
Permissions in this forum:
You cannot reply to topics in this forum