GOD'S ALGORITHM

Page 1 of 2 1, 2  Next

View previous topic View next topic Go down

GOD'S ALGORITHM

Post by BaruhbaL on 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
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

Post by MetaboringJohnCañares on 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.

_________________
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
3x3x3

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

View user profile http://www.flickr.com/photos/metaboringjohn/

Back to top Go down

Re: GOD'S ALGORITHM

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

can you translate this in english Smile

van21691
4x4x4
4x4x4

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

View user profile http://www4.pcriot.com

Back to top Go down

Re: GOD'S ALGORITHM

Post by jettyboy1 on 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
2x2x2
2x2x2

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

View user profile http://www.youtube.com/profile?user=jettyboy1

Back to top Go down

Re: GOD'S ALGORITHM

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

cant understand the numbers.... to technical... hehehe
but interesting topic....

_________________

cubekid
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

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

aarrrghh.. my brain hurts.. hehe. Smile

_________________
Just like cubing, if you let God do the work, first it seems impossible, then it's difficult, then it's done.

cmdsaved
3x3x3
3x3x3

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

View user profile http://lesmallari.multiply.com/

Back to top Go down

Re: GOD'S ALGORITHM

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

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
3x3x3

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

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

meron ka bang sample code ng two phase algorithm..

geocine
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

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

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

pancho86
3x3x3
3x3x3

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

View user profile http://profiles.friendster.com/12449592

Back to top Go down

Re: GOD'S ALGORITHM

Post by SlowestCuber on 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 : 26
Location : Dasmariñas Cavite
Registration date : 2007-10-23

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

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

npakhusay.



ang galing...



nya...



hehehe...


d q maintindihan...

_________________
prepare your rubix

and

gotta fix it

hyfly
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

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

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

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

Post by SlowestCuber on 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 : 26
Location : Dasmariñas Cavite
Registration date : 2007-10-23

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

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

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

_________________

greatauror28
3x3x3
3x3x3

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

Post by Jome on 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
2x2x2
2x2x2

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

View user profile http://scarredpetal.livejournal.com

Back to top Go down

Re: GOD'S ALGORITHM

Post by SlowestCuber on 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 : 26
Location : Dasmariñas Cavite
Registration date : 2007-10-23

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

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

ilan algs kaya toh?? hehe

BaruhbaL
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

Post by jhong on 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
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

Post by lorcan on 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
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

Post by jestoni143 on 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
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

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

epistaxis..whew...

phatj
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

Post by Purple Frost on 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
2x2x2
2x2x2

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

View user profile http://callanta88.blogspot.com

Back to top Go down

Re: GOD'S ALGORITHM

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

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

joseph24
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

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

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

jestoni143
2x2x2
2x2x2

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

View user profile

Back to top Go down

Re: GOD'S ALGORITHM

Post by Purple Frost on 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
2x2x2
2x2x2

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

View user profile http://callanta88.blogspot.com

Back to top Go down

Re: GOD'S ALGORITHM

Post by Sponsored content Today at 2:00 am


Sponsored content


Back to top Go down

Page 1 of 2 1, 2  Next

View previous topic View next topic Back to top


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