GOD'S ALGORITHM
:: Cuber's Talk :: Speedcubing
Page 1 of 2 • Share •
Page 1 of 2 • 1, 2
GOD'S ALGORITHM
TwoPhaseAlgorithm 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 TwoPhaseAlgorithm. 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 TwoPhaseAlgorithm 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 TwoPhaseAlgorithm 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 OnLine 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 *1020
18
1
4.16166*1019
13.5
2
5.61824*1018
13.3333
3
7.49098*1017
13.3454
4
9.99699*1016
13.2961
5
1.32921*1014
13.2516
6
1.76141*1013
13.2315
7
2.3306*1012
13.2173
8
3.08042*1011
13.2072
9
4.06836*1010
13.1986
10
5.36965*109
~13.12 (estimated)
11
7.08242×108
~13.12 (estimated)
12
~9.3*107
~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 twophasealgorithm 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 twophasealgorithm 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 TwoPhaseAlgorithm. 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 TwoPhaseAlgorithm 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 TwoPhaseAlgorithm 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 OnLine 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 *1020
18
1
4.16166*1019
13.5
2
5.61824*1018
13.3333
3
7.49098*1017
13.3454
4
9.99699*1016
13.2961
5
1.32921*1014
13.2516
6
1.76141*1013
13.2315
7
2.3306*1012
13.2173
8
3.08042*1011
13.2072
9
4.06836*1010
13.1986
10
5.36965*109
~13.12 (estimated)
11
7.08242×108
~13.12 (estimated)
12
~9.3*107
~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 twophasealgorithm 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 twophasealgorithm which includes the analysis of suboptimal solutions of phase 1.
BaruhbaL 2x2x2

Number of posts : 168
Age : 33
Registration date : 20070624
Re: GOD'S ALGORITHM
hahaha, I can't understand this! But whoever discovers God's Algorithm, it would be me! hehe! kidding.
_________________
A picture or image, generally, is not one sided but a multiplex of vertical horizons compiled into one. So basically, if viewed critically, an image has multiple particulars; it is then for you to find out what roles these particulars act in compliance to make the picture work.
...and this is not just about photography.
MetaboringJohnCañares 3x3x3

Number of posts : 722
Age : 32
Location : Cebu City
Registration date : 20070624
Re: GOD'S ALGORITHM
can you translate this in english
van21691 4x4x4

Number of posts : 1092
Age : 26
Location : Anaheim, CA, USA
Registration date : 20070629
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
jettyboy1 2x2x2

Number of posts : 421
Age : 25
Location : Greenhills, San Juan
Registration date : 20070709
Re: GOD'S ALGORITHM
cant understand the numbers.... to technical... hehehe
but interesting topic....
but interesting topic....
_________________
cubekid 2x2x2

Number of posts : 237
Age : 38
Location : Antipolo City
Registration date : 20071016
Re: GOD'S ALGORITHM
aarrrghh.. my brain hurts.. hehe.
_________________
Just like cubing, if you let God do the work, first it seems impossible, then it's difficult, then it's done.
cmdsaved 3x3x3

Number of posts : 716
Age : 29
Location : Pasay city!
Registration date : 20071017
Re: GOD'S ALGORITHM
Grabe! dumudugo ang ilong ko!
_________________
hell yeah! i'm really bald! one day, i just woke up and decided to shave my head. and it beats the sh*t out of me.
pajodaep 3x3x3

Number of posts : 781
Age : 32
Registration date : 20070716
Re: GOD'S ALGORITHM
meron ka bang sample code ng two phase algorithm..
geocine 2x2x2

Number of posts : 390
Age : 28
Location : J. Ruiz, San Juan City
Registration date : 20071019
Re: GOD'S ALGORITHM
naku sorry iba iba na natype ko kasi naman hirp intindihin nun...
pancho86 3x3x3

Number of posts : 577
Age : 31
Location : Santa Cruz, Laguna / España, Manila
Registration date : 20070928
Re: GOD'S ALGORITHM
aheheheh naintindihan ko ung ....ano nga ba un ahhehe
SlowestCuber 2x2x2

Number of posts : 354
Age : 27
Location : Dasmariñas Cavite
Registration date : 20071023
Re: GOD'S ALGORITHM
npakhusay.
ang galing...
nya...
hehehe...
d q maintindihan...
ang galing...
nya...
hehehe...
d q maintindihan...
_________________
prepare your rubix
and
gotta fix it
hyfly 2x2x2

Number of posts : 476
Age : 31
Location : malabon
Registration date : 20071020
Re: GOD'S ALGORITHM
cool.......
_________________
______________________________________________________
Once a cuber, is always a cuber......
YM: brian_trustworthyscout@yahoo.com
MSN: brian_trustworthyscout@hotmail.com
Gmail: brian.trustworthyscout@gmail.com
Official Champion Speedcuber of Chiang Kai Shek College.
XD PEACE!
Brian Nicole Uy 2x2x2

Number of posts : 198
Age : 24
Location : Manila, Manila Philippines
Registration date : 20070814
Re: GOD'S ALGORITHM
nag sesearch langako aksident lng ang pagkakakita ko ahaha
SlowestCuber 2x2x2

Number of posts : 354
Age : 27
Location : Dasmariñas Cavite
Registration date : 20071023
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 : 33
Registration date : 20070827
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.
Jome 2x2x2

Number of posts : 398
Age : 29
Location : Malate, Manila
Registration date : 20071125
Re: GOD'S ALGORITHM
ahehhe gwa nga tau sariling method
T_T ahehhe
T_T ahehhe
SlowestCuber 2x2x2

Number of posts : 354
Age : 27
Location : Dasmariñas Cavite
Registration date : 20071023
Re: GOD'S ALGORITHM
ilan algs kaya toh?? hehe
BaruhbaL 2x2x2

Number of posts : 168
Age : 33
Registration date : 20070624
Re: GOD'S ALGORITHM
interesting sir!!
kaso baka 'pag sinimulan kong pagaralan baka mawalan na ko ng interest mabuhay....
ahehe'
juklang....
salamat sa idea...
balang araw maiintindihan ko din yan..
kaso baka 'pag sinimulan kong pagaralan 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 : 26
Location : Sta. Mesa, Mla
Registration date : 20080206
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 : 26
Registration date : 20080128
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 : 30
Registration date : 20070629
Re: GOD'S ALGORITHM
epistaxis..whew...
phatj 2x2x2

Number of posts : 291
Age : 29
Location : V&G consolacion, cebu
Registration date : 20080312
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..
Purple Frost 2x2x2

Number of posts : 16
Age : 29
Location : BF Parañaque
Registration date : 20080314
Re: GOD'S ALGORITHM
cool..",) i also understand the 1st paragraphs..",) & others r supernatural.. wahaha!",)
joseph24 2x2x2

Number of posts : 270
Age : 28
Location : marikina city
Registration date : 20071215
Re: GOD'S ALGORITHM
try search rubot II on youtube... you can see that it uses GA....
jestoni143 2x2x2

Number of posts : 132
Age : 30
Registration date : 20070629
Re: GOD'S ALGORITHM
^ yes, I just found out that it uses the same program i just mentioned kanina.. cool!! XD
Purple Frost 2x2x2

Number of posts : 16
Age : 29
Location : BF Parañaque
Registration date : 20080314
Page 1 of 2 • 1, 2
:: Cuber's Talk :: Speedcubing
Page 1 of 2
Permissions in this forum:
You cannot reply to topics in this forum