Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Fri Apr 18, 2014 3:44 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 20 posts ] 
Author Message
 Post subject: If God's Number for the Cube is 20...
PostPosted: Thu Sep 23, 2010 10:33 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
...is it possible to at least estimate the number for a Megaminx?

Has any work on minimal-move solving on the Megaminx ever been done?


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Thu Sep 23, 2010 11:09 pm 
Offline
User avatar

Joined: Tue Mar 10, 2009 7:06 pm
Location: Nowhere in particular.
I don't even know how to begin figuring out least number of moves cases, but I can tell you an exact number for megaminx sounds pretty much out of the question (nowadays, at least... maybe in 20 years we'll have the computer power to do so. Did you see the amount of power it took to find the 3x3 God's Number? And even that was only possible because of Google.)

_________________
~Kapusta

PB: At home (In Competition)
2x2 1.xx (2.88)
3x3 11.xx (15.81)
4x4 1:18.26 (1:24.63)
5x5 (3:00.02)
6x6 4:26.05 (6:34.68)
7x7 6:38.74 (9:48.81)
OH (35.63)

Current Goals:
7x7 sub 6:30
4x4 sub 1:10


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 1:31 am 
Offline

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
I can give a VERY primitive analysis:

There are 1.01x10^68 possible positions on a 12 color megaminx (wikipedia explains it correctly). There are 48 available moves to make on a megaminx (12 faces, 4 available rotations). So we can directly see there are 48 positions that can be solved in 1 move. Note that there are really only 44 moves available for every consecutive move after the first because spinning the same face as last time was already accounted for.

So we can get a rough estimate of how many positions you can get to from solved in n moves.

This estimate is 48*44^(n-1). For n<42, we get less than 1.01x10^68. So we can conclude that God's Number for the megaminx is AT LEAST 42.

There are SEVERAL problems with this analysis. To list a few,

1) Several of the sequences we counted are interchangeable (for ex: UD and DU) so should only count as one position but have been counted multiple times in our analysis

2) We also have not counted the positions that can be reached in LESS than n moves. Notice there are 49 postions that can be solved in 1 or less moves, because the solved position counts as one of these. However this error isn't as big of a problem as it may seem. There are numerous redundant n-sequences that can lead to positions that could have been solved in much fewer than n-moves (ex: (UD)*40 U D is a 42 move sequence that leads to a position that can be solved in just 2 moves 2 different ways, U'D' and D'U' so the above analysis counts that specific position at least twice [though in reality many more times])

3)There are sequences that look like they would scramble the megaminx but end up affecting nothing. Travelling down these sequences will place you back to a postion that could have been solved in fewer moves. This is really already included in point 2, but I added this in separate because it isn't 100% clear that these "silent" sequences should exist for any number of moves less than God' number for a given puzzle. (I did for example discover on a Skewb Ultimate there are MANY 10-move sequences that overall don't affect anything on the puzzle, while God's Number for a Skewb Ultimate is 14. This is truly remarkable when you realize that no two moves on the Skewb Ultimate are commutative :wink: there is, however, NO sequence shorter than 10 moves on the Skewb Ultimate with this same property)

So we can conclude that our estimate of 48*44^(n-1) is, in general, a gross overestimate of the number of moves that can be solved in n moves or less. (there is some fudging especially dealing with point 2 above, maybe someone else can give a better analysis if they find too much fault with mine, but I did this in about 3 minutes, and comparing this with a rubiks cube and using intuition... it works...)

Conclusion: God's Number for a 12-Color megaminx is at least 42 (though most likely in the 45-55 range)

There's a start 8-)
Peace,
Matt Galla


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 1:54 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Hi Matt, thanks for the counting argument, you explained it well. Jaap described the same technique here.
Allagem wrote:
there is, however, NO sequence shorter than 10 moves on the Skewb Ultimate with this same property
I'm really curious how you proved that. Did you do so computationally or is there some really neat proof?

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 9:54 am 
Offline
User avatar

Joined: Mon Feb 06, 2006 12:52 am
Quote:
I don't even know how to begin figuring out least number of moves cases, but I can tell you an exact number for megaminx sounds pretty much out of the question (nowadays, at least... maybe in 20 years we'll have the computer power to do so. Did you see the amount of power it took to find the 3x3 God's Number? And even that was only possible because of Google.)
I don't even know how to begin figuring out least number of moves cases, but I can tell you an exact number for megaminx sounds pretty much out of the question (nowadays, at least... maybe in 20 years we'll have the computer power to do so. Did you see the amount of power it took to find the 3x3 God's Number? And even that was only possible because of Google.)


I can't say anything of worth to the question of this topic. But concerning your statement, Kapusta, I can say that I don't think it must take 20 years. As for the 3x3x3 cube I have just a couple of months ago read that it would definetly take another couple of decades to figure out that number. Now it's all of a sudden done. Although the 1000s of terabyte harddisk PCs that were thought to be needed for memorizing all the scenarios aren't there. Why is that? Because the program that examined the cube was much improved and full of new ideas (aparantly).
All I can say is as far as my experience with questions like these is going and from all things that I have heard throughout my life, it never is about hardware. Hardware in general seems to be quite ahead of software in general. Write an ingenious programm and all of a sudden you can figure out things you thought could not be estimated. The cube proved it.

However I also have to say there's an additional problem to the megaminx that might prove your guess to be right afterall (in about possibly 20 years). That is it's publicity. You and a lot of other people here in the forum might be interested. But the god's number of the old 3x3x3 cube, the everlasting interest of all mathematics since the cube hit the stores years ago will not be shared by the megaminx too. So you will have to start working on your own basically.

_________________
Life is simple.
eat. sleep. train. repeat.


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 11:08 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
alaskajoe wrote:
I can't say anything of worth to the question of this topic. But concerning your statement, Kapusta, I can say that I don't think it must take 20 years. As for the 3x3x3 cube I have just a couple of months ago read that it would definetly take another couple of decades to figure out that number. Now it's all of a sudden done. Although the 1000s of terabyte harddisk PCs that were thought to be needed for memorizing all the scenarios aren't there. Why is that? Because the program that examined the cube was much improved and full of new ideas (aparantly).
All I can say is as far as my experience with questions like these is going and from all things that I have heard throughout my life, it never is about hardware. Hardware in general seems to be quite ahead of software in general. Write an ingenious programm and all of a sudden you can figure out things you thought could not be estimated. The cube proved it.

However I also have to say there's an additional problem to the megaminx that might prove your guess to be right afterall (in about possibly 20 years). That is it's publicity. You and a lot of other people here in the forum might be interested. But the god's number of the old 3x3x3 cube, the everlasting interest of all mathematics since the cube hit the stores years ago will not be shared by the megaminx too. So you will have to start working on your own basically.
I hate to be a pessimist but the Megaminx is definitely out of reach of computing power and Moore's Law won't help. The recent work on the Rubik's cube wasn't an amazing algorithmic breakthrough. They did creative symmetry canceling to reduced the search space and then they observed that the don't have to optimize all solves but just beat 20 moves. In short, they reduced the amount of work they had to do by a constant factor but the O() order of their work was the same.

Now, lets assume that the total computing power available to an individual or group doubles every two years. This might mean you have one processor that gets twice as fast or it might mean you double the number of processors you have. Either way, the number of years from now before we can expect for Moore's law to help us catch up is:

2 years * log2(O(Megaminx)/O(Rubik's Cube))

O(Megaminx) is 1.01 * 10 ^ 68
O(Rubik's Cube) is 4.32 * 10 ^ 18

Which means the problem is about 161 orders of magnitude (base 2) harder. That means that we need Moore's law to hold for another 321 years before the Megaminx becomes as "easy" as the Rubik's cube is today.

Sadly, there is a limit to the amount a transistor can be shrunk and we're going to reach it in less than 20 years. Also, even though we can scale computing density exponentially, power has been scaling sub-exponentially.

If you had 1.01 * 10 ^ 68 electrons it would weigh 46 million times the mass of the sun. Unless we have a computer the size of our solar system and feed it stars for its energy source we're never going to examine all the routines on the Megaminx.

There is a great paper by Seth Lloyd on arXiv called Ultimate physical limits to computation that gets to the heart of computation by looking at physical principles and limits. The paper's approach covers both classical and quantum computing.

EDIT: the real mathy folks on this forum will be annoyed that I abused big-O notation. Sorry, it seemed like the right tool for the job.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 11:23 am 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
IDK about that. For fairly cheap, you can rent distributed computer services from amazon. Go a less legal route and find a bot net to do the computing. Set up something like folding@home, but call it twisting@home.

There's plenty of ways to get a great start on this!

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 11:34 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
theVDude wrote:
IDK about that. For fairly cheap, you can rent distributed computer services from amazon. Go a less legal route and find a bot net to do the computing. Set up something like folding@home, but call it twisting@home.

There's plenty of ways to get a great start on this!
Lets pretend for a moment that there are 1000 billion (1 trillion) computers on Earth (cell phones + computer + etc) and that EACH computer is so fast that it can prove god's number for the Rubik's cube in 1 femto second. That is, each one can prove it a quadrillion times in 1 second.

Then, having all of those computers working together it would only take 7.4 * 10 ^ 13 years, or about 74 trillion years.

1.01e68 / 4.3e19 is a HUGE number. It will never happen. It's physically impossible. We don't have the energy (or time) necessary to do it.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 11:44 am 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
How was the lower bound for the original cube proved?


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 12:08 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Jared wrote:
How was the lower bound for the original cube proved?

The counting argument had the lower bound at 18 moves until this post: http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__superflip_requires_20_face_turns.html.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 12:12 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Jared wrote:
...is it possible to at least estimate the number for a Megaminx?

Has any work on minimal-move solving on the Megaminx ever been done?

G(Megaminx) = log(total combinations) / log(new combinations per move)

=log(10^68) / log (42*) = ~42 moves

*NB. the branching factor (new combinations per move) is ~42 rather than 48 because you must subtract 4 moves for redundant rotation of the same layer in the next move, and half that again (another 2 moves) for redundant rotation of the opposite layer in alternation (as I explained here for the Rubik's Cube).

This gives the same result as Allagem above (42), but by a very different calculation. :D

And of course, we all knew the answer anyway, from Hitchiker's Guide to the Galaxy! :lol:

...but having said that I would add another 3 moves to catch any last tricky combinations at the end, just to be on the safe side. :wink:

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 1:58 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Kelvin Stott wrote:
G(Megaminx) = log(total combinations) / log(new combinations per move)

=log(10^68) / log (42*) = ~42 moves

*NB. the branching factor (new combinations per move) is ~42 rather than 48 because you must subtract 4 moves for redundant rotation of the same layer in the next move, and half that again (another 2 moves) for redundant rotation of the opposite layer in alternation (as I explained here for the Rubik's Cube).

This gives the same result as Allagem above (42), but by a very different calculation. :D
Kevin, I don't see why this is actually a different calculation? I just seems like an algebraic reordering of Matt's counting argument.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 2:10 pm 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
bmenrigh wrote:
theVDude wrote:
IDK about that. For fairly cheap, you can rent distributed computer services from amazon. Go a less legal route and find a bot net to do the computing. Set up something like folding@home, but call it twisting@home.

There's plenty of ways to get a great start on this!
Lets pretend for a moment that there are 1000 billion (1 trillion) computers on Earth (cell phones + computer + etc) and that EACH computer is so fast that it can prove god's number for the Rubik's cube in 1 femto second. That is, each one can prove it a quadrillion times in 1 second.

Then, having all of those computers working together it would only take 7.4 * 10 ^ 13 years, or about 74 trillion years.

1.01e68 / 4.3e19 is a HUGE number. It will never happen. It's physically impossible. We don't have the energy (or time) necessary to do it.

What about starting? You don't have to go over EVERY POSSIBLE POSITION of the megaminx to start to get a lower boundary. I'd say go with ones that are similar to the "harder" ones on the rubik's cube, and include the superflip. Look for minimum moves for those and then start to see what else you can do.

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 2:18 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
bmenrigh wrote:
Kevin, I don't see why this is actually a different calculation? I just seems like an algebraic reordering of Matt's counting argument.

Oops, now that I have read through and understand his logic properly I see you are correct and we're using the same approach!

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 4:07 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
theVDude wrote:
What about starting? You don't have to go over EVERY POSSIBLE POSITION of the megaminx to start to get a lower boundary. I'd say go with ones that are similar to the "harder" ones on the rubik's cube, and include the superflip. Look for minimum moves for those and then start to see what else you can do.
You're right that you only need to prove a single position requires at least N moves to set the lower bound to N.

Unfortunately proving a particular position requires at least N moves is hard. In the case of the superflip, Michael Reid first proved that any solution to the superflip must be of a certain set of forms. He then had to exhaust the cube entire space that took on those forms. That could probably be done for the Megaminx too. But even an amazing result like "any solution to position X on the Megaminx must start with these 10 moves" still leaves about 32 moves left. Even reducing the problem by a factor of 44^10 still leaves an insurmountable problem.

In general, finding a solution to a position is easy -- we do it when we solve the puzzles. Shortening the sequence a bit is pretty easy too. But proving that the sequence is as short as possible usually requires brute force. If you have a solution that is 42 moves long, you have to show that there is NO sequence of length 41 that can solve the puzzle. Even with symmetry canceling and other tricks there doesn't seem to be any algorithm known that is better than brute force.

The only way progress could be made is if somebody could relate a position on the Megaminx to some mathematical problem and then analyze it that way. That only worked a little bit for the Rubik's cube though and the Megaminx seems less easily relatable to math than the Rubik's cube.

Matt/Kevin's counting argument is probably the best that will ever be done.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 7:38 pm 
Offline
User avatar

Joined: Fri Jul 09, 2010 9:05 am
Location: Wisconsin
Just curious; will computing ever be applied towards big cubes in the near future (e.g.: the 4x4, the 5x5, the 6x6, etc.)? How much computing power would it require?

lol the v cube 6 has over a googol combinations (1.57 * 10116). :lol:

_________________
www.youtube.com/jerry533482


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 7:56 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
I'd say any cubes larger than 3x3 aren't feasible based on bmenrigh's points. The Megaminx is somewhere between the 4x4 and 5x5 in terms of combinations.

It's kind of depressing that we'll never find out... but that means fewest-move competitions on the Megaminx, both human and computer, will always be possible. Not that there's enough interest for that... :P


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Fri Sep 24, 2010 8:43 pm 
Offline
User avatar

Joined: Fri Jul 09, 2010 9:05 am
Location: Wisconsin
Has any work been done on the 4x4?

_________________
www.youtube.com/jerry533482


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Sat Sep 25, 2010 12:29 am 
Offline

Joined: Fri Jul 17, 2009 5:32 pm
Location: Tokyo
bmenrigh wrote:
If you had 1.01 * 10 ^ 68 electrons it would weigh 46 million times the mass of the sun. Unless we have a computer the size of our solar system and feed it stars for its energy source we're never going to examine all the routines on the Megaminx.
You mean you haven't seen Men In Black III? You didn't know that's exactly the computation our galaxy was created for?

The part that confuses me is, after Doug Adams got the answer, why do we still exist?

_________________
May the force not be with you.


Top
 Profile  
 
 Post subject: Re: If God's Number for the Cube is 20...
PostPosted: Tue Sep 28, 2010 9:22 am 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
ndiamond wrote:
bmenrigh wrote:
If you had 1.01 * 10 ^ 68 electrons it would weigh 46 million times the mass of the sun. Unless we have a computer the size of our solar system and feed it stars for its energy source we're never going to examine all the routines on the Megaminx.
You mean you haven't seen Men In Black III? You didn't know that's exactly the computation our galaxy was created for?

The part that confuses me is, after Doug Adams got the answer, why do we still exist?

Because the answer isn't interesting in itself, it's the question.

http://www.gtri.gatech.edu/casestudy/Te ... ity-System
Would something like this help solve the case where center orientation matters?

Quote:
“GPUs are much better at large-scale mathematical operations than CPUs because of this parallel layout. “.

This is generally wrong. This is true only for mathematical operations which can be splitted into a large number of small independant computations, which is not at all the most common situation.

Password cracking is not exactly the typical “large scale mathematical operation”. The most typical ones are operations on large matrices, for which GPU computing is often not suitable.
from another website.

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 20 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Boris and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group