Would you like to react to this message? Create an account in a few clicks or log in to continue.

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

Page 1 of 2 1, 2  Next

Go down

GOD'S ALGORITHM Empty GOD'S ALGORITHM

Post by BaruhbaL Tue Jul 10, 2007 3:19 am

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.
BaruhbaL
BaruhbaL
2x2x2
2x2x2

Male
Number of posts : 168
Age : 39
Registration date : 2007-06-24

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by MetaboringJohnCañares Wed Jul 11, 2007 3:15 am

hahaha, I can't understand this! But whoever discovers God's Algorithm, it would be me! hehe! kidding.
MetaboringJohnCañares
MetaboringJohnCañares
3x3x3
3x3x3

Male
Number of posts : 722
Age : 38
Location : Cebu City
Registration date : 2007-06-24

http://www.flickr.com/photos/metaboringjohn/

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by van21691 Wed Jul 11, 2007 2:56 pm

can you translate this in english Smile
van21691
van21691
4x4x4
4x4x4

Male
Number of posts : 1092
Age : 33
Location : Anaheim, CA, USA
Registration date : 2007-06-29

http://www4.pcriot.com

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by jettyboy1 Sat Jul 21, 2007 12:46 pm

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 Razz
jettyboy1
jettyboy1
2x2x2
2x2x2

Male
Number of posts : 421
Age : 31
Location : Greenhills, San Juan
Registration date : 2007-07-09

https://www.youtube.com/profile?user=jettyboy1

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by cubekid Sat Oct 20, 2007 8:29 am

cant understand the numbers.... to technical... hehehe
but interesting topic....
cubekid
cubekid
2x2x2
2x2x2

Male
Number of posts : 237
Age : 44
Location : Antipolo City
Registration date : 2007-10-16

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by cmdsaved Sat Oct 20, 2007 7:57 pm

aarrrghh.. my brain hurts.. hehe. Smile
cmdsaved
cmdsaved
3x3x3
3x3x3

Male
Number of posts : 716
Age : 36
Location : Pasay city!
Registration date : 2007-10-17

http://lesmallari.multiply.com/

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by pajodaep Sun Oct 21, 2007 2:19 pm

Grabe! dumudugo ang ilong ko!
pajodaep
pajodaep
3x3x3
3x3x3

Male
Number of posts : 781
Age : 39
Registration date : 2007-07-16

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by geocine Wed Oct 31, 2007 1:52 pm

meron ka bang sample code ng two phase algorithm..
geocine
geocine
2x2x2
2x2x2

Male
Number of posts : 390
Age : 34
Location : J. Ruiz, San Juan City
Registration date : 2007-10-19

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by pancho86 Wed Oct 31, 2007 4:07 pm

naku sorry iba iba na natype ko kasi naman hirp intindihin nun...
pancho86
pancho86
3x3x3
3x3x3

Male
Number of posts : 577
Age : 37
Location : Santa Cruz, Laguna / España, Manila
Registration date : 2007-09-28

http://profiles.friendster.com/12449592

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by SlowestCuber Fri Nov 23, 2007 4:44 pm

aheheheh naintindihan ko ung ....ano nga ba un ahhehe

SlowestCuber
2x2x2
2x2x2

Male
Number of posts : 354
Age : 33
Location : Dasmariñas Cavite
Registration date : 2007-10-23

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by hyfly Sat Nov 24, 2007 6:43 pm

npakhusay.



ang galing...



nya...



hehehe...


d q maintindihan...
hyfly
hyfly
2x2x2
2x2x2

Male
Number of posts : 476
Age : 37
Location : malabon
Registration date : 2007-10-20

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by Brian Nicole Uy Mon Nov 26, 2007 9:42 pm

cool.......

Brian Nicole Uy
2x2x2
2x2x2

Male
Number of posts : 198
Age : 31
Location : Manila, Manila Philippines
Registration date : 2007-08-14

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by SlowestCuber Mon Nov 26, 2007 9:52 pm

nag sesearch langako aksident lng ang pagkakakita ko ahaha

SlowestCuber
2x2x2
2x2x2

Male
Number of posts : 354
Age : 33
Location : Dasmariñas Cavite
Registration date : 2007-10-23

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by greatauror28 Mon Nov 26, 2007 10:58 pm

you did well researching all of this...anyway, i prefer CFOP for that matter.....Smile
greatauror28
greatauror28
3x3x3
3x3x3

Number of posts : 530
Age : 39
Registration date : 2007-08-27

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by Jome Mon Nov 26, 2007 11:06 pm

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.
Jome
Jome
2x2x2
2x2x2

Male
Number of posts : 398
Age : 36
Location : Malate, Manila
Registration date : 2007-11-25

http://scarredpetal.livejournal.com

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by SlowestCuber Tue Nov 27, 2007 9:48 pm

ahehhe gwa nga tau sariling method
T_T ahehhe

SlowestCuber
2x2x2
2x2x2

Male
Number of posts : 354
Age : 33
Location : Dasmariñas Cavite
Registration date : 2007-10-23

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by BaruhbaL Fri Mar 14, 2008 9:04 pm

ilan algs kaya toh?? hehe
BaruhbaL
BaruhbaL
2x2x2
2x2x2

Male
Number of posts : 168
Age : 39
Registration date : 2007-06-24

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by jhong Fri Mar 14, 2008 10:55 pm

interesting sir!!
kaso baka 'pag sinimulan kong pag-aralan study baka mawalan na ko ng interest mabuhay.... scratch
ahehe' Laughing
juklang.... Very Happy
salamat sa idea... Very Happy
balang araw maiintindihan ko din yan.. study
jhong
jhong
2x2x2
2x2x2

Male
Number of posts : 59
Age : 33
Location : Sta. Mesa, Mla
Registration date : 2008-02-06

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by lorcan Sat Mar 15, 2008 3:17 pm

wtf ano yan statistics waaaahhh d ko maintindihan hehe ang gling ni

kuya

can u explain it in an easy way waaaaaaahhh
lorcan
lorcan
2x2x2
2x2x2

Male
Number of posts : 279
Age : 32
Registration date : 2008-01-28

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by jestoni143 Mon Mar 17, 2008 10:21 am

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
jestoni143
2x2x2
2x2x2

Male
Number of posts : 132
Age : 37
Registration date : 2007-06-29

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by phatj Mon Mar 17, 2008 6:06 pm

epistaxis..whew...
phatj
phatj
2x2x2
2x2x2

Male
Number of posts : 291
Age : 35
Location : V&G consolacion, cebu
Registration date : 2008-03-12

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by Purple Frost Tue Mar 18, 2008 1:53 pm

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..
Purple Frost
Purple Frost
2x2x2
2x2x2

Male
Number of posts : 16
Age : 35
Location : BF Parañaque
Registration date : 2008-03-14

http://callanta88.blogspot.com

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by joseph24 Tue Mar 18, 2008 2:19 pm

cool..",) i also understand the 1st paragraphs..",) & others r supernatural.. wahaha!",)
joseph24
joseph24
2x2x2
2x2x2

Male
Number of posts : 270
Age : 34
Location : marikina city
Registration date : 2007-12-15

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by jestoni143 Tue Mar 18, 2008 3:24 pm

try search rubot II on youtube... you can see that it uses GA....
jestoni143
jestoni143
2x2x2
2x2x2

Male
Number of posts : 132
Age : 37
Registration date : 2007-06-29

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by Purple Frost Tue Mar 18, 2008 4:04 pm

^ yes, I just found out that it uses the same program i just mentioned kanina.. cool!! XD
Purple Frost
Purple Frost
2x2x2
2x2x2

Male
Number of posts : 16
Age : 35
Location : BF Parañaque
Registration date : 2008-03-14

http://callanta88.blogspot.com

Back to top Go down

GOD'S ALGORITHM Empty Re: GOD'S ALGORITHM

Post by Sponsored content


Sponsored content


Back to top Go down

Page 1 of 2 1, 2  Next

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum