Message #1646

From: David Smith <djs314djs314@yahoo.com>
Subject: Re: [MC4D] Hi everyone, I’m back!
Date: Tue, 03 May 2011 06:05:04 -0700

Hi Matt,

This is obviously very late, but I’m glad you joined the cubing group!  When I first
met you, I believe you hadn’t yet joined.  Again, thank you for your Magic120Cell
algorithms as well!

With regards to my mathematical observations and corrections, both you and
Brandon have said that you appreciate my results, and that it is insightful and
helpful to see my mistakes.  However, I don’t know how many more posts all of
you are going to want to hear from me - I have a lot of ground to cover!  So, I’m
working on a new collection of pages on the wiki, as Roice suggested I attempt.
There is now a Permutations section of the main page.  From there, one can
go to the Puzzle Index page or the Notation page.  The Puzzle Index page
has not yet been created, but it will contain a link to a unique page for every
puzzle in existence.  They will be sorted by the program(s) they appear in.
Each puzzle’s page will contain a picture, description, permutation equation
and number, and as complete of an explanation I can give without going too
far into the mathematical details.  Basically, the explanations will consist
of a list of each type of piece in the puzzle, accompanied by a count of the
number of such pieces in the puzzle, and how many permutations and
orientations they can achieve, also giving the restrictions for those counts
and the reasoning behind them (for example, the orientation of the last
corner piece is determined by the orientations of the others, thus we must
divide our result by 3).

I have completed the Notation page, which should be interesting reading
for some of you.  In it, I describe a way to name the pieces of any puzzle,
including MagicTile, and likely any future puzzle of any dimension, via a
single system.  I could have chosen to be more specific in some places
with my method (i.e. further distinguishing different types of pieces than
I currently do), but my focus was on to classify groups of pieces that have
the same permutation and orientation counts.  This method is generalized
from my n^4 formula and proof paper, available in the files section of the
yahoo group.  Some years ago there was a discussion of how to name
pieces of a cube of any dimension, so I humbly consider it a significant
acheivement that I have come up with a way to name any piece of any
possible puzzle with a single, precise method.

I very much enjoyed reading your explanation of determining the lower
bound of God’s algorithm of any puzzle!  You are right, Magic120Cell
most likely has a very large God’s number.  And the page I previously
pointed out showed that to make a puzzle random, you must scramble
it a number of moves which is many orders of magnitude larger than
God’s number, as you observed as well.  I just thought I went a bit too
far with claiming this number could be in the millions (although I honestly
don’t know.)

I hope that my Notation section will be interesting to take a look at for some
of you, though of course there is no need to do so.  It’s just another of my
odd contributions. :)  By the way, as most of you probably know, Roice has
shown how to count the number of k-colored pieces on an n-dimensional
cube, which has been very helpful to me.  After much research, and with
credit to many others (the authors of The Rubik Tesseract and An n-dimensional
Rubik Cube), I have done something similar with counting orientations of any
family (‘family’ is defined in the Notation page) of pieces.  Furthermore, my
result is very general, such that it applies to virtually any puzzle.  The conditions
for its application are very minimal.  Roice suggested I share it with the group,
so I might do that soon.

Thanks for writing and welcoming me back!  I look forward to further
contributing to this wonderful community.

All the best,
David

— On Tue, 5/3/11, Matthew Galla <mgalla@trinity.edu> wrote:

From: Matthew Galla <mgalla@trinity.edu>
Subject: Re: [MC4D] Hi everyone, I’m back!
To: 4D_Cubing@yahoogroups.com
Date: Tuesday, May 3, 2011, 4:56 AM

 





David,
 
I for one am actually enjoying your outbursts of mathematical talk, erroneous or not, and even when you do make mistakes or hasty conclusions, I feel like we can all learn from them.
 
Some time ago, I was doing research into God’s Algorithm/God’s Number for the Rubik’s Cube. I came across a discussion of the first lower bounds set on God’s Number before Michael Reed’s work. Although it is a very crude proof and seems to be guaranteed to not get the right answer (having applied this idea to several puzzles), the argument does give a concrete proof of the lower bounds of God’s Number for any puzzle and can be calculated in seconds.

 
My apologies if you are familiar with this work already, but in case you (or anyone else!) aren’t (/isn’t) allow me to run through it quickly:
 
The basic argument is as follows: Assume we are operating in the free group on the generators formed by the available moves of the Rubik’s Cube. What this essentially means is every possible sequence of moves is considered different even if they lead to the same position: for example UD is considered different from DU, even though they result in the same position. Clearly, the number of positions reachable in n moves is less than or equal to the number of states in the free group reachable in n moves (i.e. the number of unique sequences of moves of length less than or equal to n; actually, I think I will just drop the free group perspective here, it isn’t really necessary). However, counting the number of sequences you can make in n moves is much easier than counting the number of states reachable in n moves. For a Rubik’s cube, there are 18 choices for the first move. After that, there are only 15 choices because if you move the same face again, it
could have been reached in only one move (using FTM). So, the number of sequences you could form in say, 3 moves or less is:

 
1+18+18*15+18*15*15 = 4339.
 
Now if we try to calculate the number of sequences you could form in 16 moves or less, we get
 
1+18+18*15+18*15*15 +… = 1 + 18*sum as n goes from 0 to 15 of (15^n) = 1 + 18*((1-15^16)/(1-16)) [using the partial sum of a geometric series]
 
which is about 7.88x10^18. Now the main point here is:
 
number of positions reachable in 16 moves <= number of sequences of 16 moves or less < total number of states to a Rubik’s Cube.
 
So the above is a simple proof that the lower bound for the Rubik’s Cube is greater than 16. In fact you can make some more arguments that will allow you to push the limit above 17, but that isn’t really necessary for my point.

 
On to what I wanted to share:
What I did was apply this same idea to many, many other twisty puzzles to get a decent guess at God’s Number for different puzzles. (One funny result is that this analysis gives a lower bound of 42 for the megaminx). I discovered something VERY interesting when I applied this to the 120Cell, though the numbers are significantly huger!

 
The 120 Cell has 120 faces that can each be in one of 60 orientations. If the 120Cell program used the equivalent of FTM, there would be 120*59=7080 possibilities for the 1st move and 119*59=7021 possibilities for every move after that. However, the program uses the equivalent of QTM which means any 2/5 rotation around a pentagonal face of any cell cannot be achieved in 1 move. As there are 6 axes in one face about which this type of rotation can happen, and 2 directions per axis, there are 6*2=12 orientations of a cell that are not reachable in a single click. However, all other orientations are reachable in a single click. Thus, for this program there are 120*(59-12)=5640 possibilities for the 1st move and 119*(59-12)=5593 possibilities for every move after that.

 
To simplify things, let’s only consider the last term in our sum. When you consider the geometric growth of the number of sequences of length n and the fact that countless sequences will return you to solved in less than those n moves (once n>3), it is fairly easy to see that in all likelihood, the last term alone is sufficient to GROSSLY overestimate the number of positions reachable in n moves. So, the question becomes what is the smallest n such that the number of sequences of length n (just exactly, not less than or equal to) is greater than the number of positions of the 120Cell, which we all know is 2.3*10^8126 thanks to you! In other words, what is the smallest value of n such that

 
5640*5593^(n-1)>2.3*10^8126.
 
With some clever logarithmic manipulation, you can find this value on even a simple scientific calculator: n=2169. Although there is a small hole in this proof as I have presented it, I can say with 100% confidence that the 120Cell requires at least 2169 moves (and probably many more!) to even REACH every possible state, let alone reach them with a degree of equal likelihood. As far as I am aware, the stored scramble is only 1000 random moves, less than half of the number of the lower bounds for God’s Number for the 120Cell.

 
Not that I think it helps ANYONE, but this means that, strictly speaking, the Magic 120Cell has NEVER been FULLY scrambled…. ;)
 
I just wanted to reassure you that there is some truth in your concern over the insufficient number of scrambling moves for the 120Cell. I unfortunately discovered this near the very end of my solve, so as you can probably imagine, I wasn’t terribly thrilled at the result because, again strictly speaking, none of the 120Cell solves can really be considered legitimate… :(    (but again, I don’t see how a solver can benefit from the less than sufficient scramble)

 
Think nothing of correcting yourself multiple times! I for one enjoy following your work even in its mistakes. I am of the opinion that if the mistake is caught by the same person who made it, it was never a mistake at all, just an equation that hadn’t been proofread. Many writers and editors would call such a thing a typo! ;)

 
Enjoy,
Matt Galla
 

PS: My best guess for the actual God’s Number to the 120Cell is somewhere between 2450 and 2550, if anyone was curious. I by no means have any proof, just a guess based on extrapolation from puzzles with known God’s Numbers.


On Sat, Apr 30, 2011 at 9:58 PM, David Smith <djs314djs314@yahoo.com> wrote:


 

Hello all,

I’ve given the matter below some more careful and serious thought, and realize that I was a bit hasty to say that Magic120Cell would theoretically require ‘millions’ of twists to randomize it - that is probably far, far too high.  Also, I had made an implicit assumption without first checking the facts.  Having revisited MagicTile and MC4D 4.0, I see that you are giving the puzzle many more twists that I had remembered.  My apologies!  So, it seems my analysis below was more than a bit flawed.  At least I was trying to help, but next time I’ll give the matter more careful thought.  It’s actually a bit humorous to read, given that I was suggesting to consider we rewrite all of the scrambling code. :)


I’m certain Melinda, Don, Roice, and Jay are far more qualified than I am to evaluate the number of twists needed to randomize a particular puzzle, simply through experience.  I don’t think I am capable of providing an adequate ‘Goldilocks’ function; sorry for that.  The mathematics is far too heavy, and I wouldn’t even know where to begin, given that I cannot base my answer on the optimal or near-optimal number of moves it takes to solve a particular puzzle.  I’m betting that the current scrambling methods being used are more than adequate.


I apologize, but hopefully this was a good laugh for some of you. :)

All the best,
David

— On Sat, 4/30/11, David Smith <djs314djs314@yahoo.com> wrote:

From: David Smith <djs314djs314@yahoo.com>

Subject: Re: [MC4D] Hi everyone, I’m back!
To: 4D_Cubing@yahoogroups.com
Date: Saturday, April 30, 2011, 8:22 AM

 

Thank you so much Melinda!  You are very gracious. :)

I haven’t browsed most of the messages I’ve missed (obviously there are a lot!), but after my reintroduction, I was immediately astounded by all of the new programs!  7-dimensional Rubik’s Cubes? Magic Hyperbolic Tile?  5-dimensional Pac-man?  4-dimensional Tetris?!  Incredible!  I think Andrey deserves an award for being one of the talented programmers in the world, in the ‘Creative Genius’ category!  And Roice provided the inspiration, being the first person to ever program a 5D Cube and Tile-based puzzles! (I’m sure he could do even more, but he is very busy!)  And you and Don provided the inspiration for Roice, and this group. :)


I feel so bad I missed out sharing the good times.  But, it seems there are still plenty to be had!  The only computer program I have written recently simulates Ulam’s Game, a mathematical thought experiment.  I believe it is the only one of its kind.  But it was trivial to create; nothing even remotely close to what all of you have accomplished.  I’m constantly inspired by your intelligence!  And I forgot to mention that one day I do intend to work out solving these puzzles for myself.


I’ve done some research into the Goldilocks function problem, and I have some bad news, and some worse news. :(  The implications could be unfortunate, and you may wish I had never looked into it.  It’s up to all of you as to how you would like to proceed.  I’m fine with keeping things as they are, and that what I am about to say may be considered questionable and irrelevant to our current scrambling methods.


First, the bad news: This Goldilocks function is almost certainly beyond my capabilities.  I’m betting a mathematician would have much trouble.  The problem is that the number of moves it takes to produce a ‘sufficiently random’ position (which is already a subjective term; it can be made more precise mathematically, in a way that is somewhat above my head), varies from puzzle to puzzle.  I doubt there is a general solution.  Also, I doubt that it is practical to answer this question for any particular puzzle by purely mathematical methods, given the extreme difficulty.  Computer tests need to be performed, i.e. scrambles need to be done repeatedly and analyzed with statistics.


Here is the worse news: Such statistical analyses have already been performed for the 3^3 Cube and Megaminx.  You can see the report on this page:

http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/41005


It is true that the results are not the work of a mathematician, and the analyses could have been simplified and improved upon, but I’ve studied the paper and there appear to be no errors.  I believe that the results are accurate enough for our purposes.


I originally conjectured that 20 moves would suffice to scramble the Rubik’s Cube, since every position can be solved in at most 20 moves.  This turns out to be a very naive and flawed assumption.  According to the report, it takes around 45 moves to scramble a Rubik’s Cube so that it is sufficiently random.


Now, he also studied the megaminx.  This is where things begin to get depressing.  According to the page, it takes around 250 moves for the megaminx to begin to become randomly mixed.  We can see the number of moves rapidly increasing with the complexity of the puzzle.  The megaminx is simpler than even the standard 3^4 cube.  So, I’m very roughly estimating that for a puzzle such as Magic120Cell, which is hugely complex, the number of moves required to generate a sufficiently random position could be in the hundred thousands, millions, or even higher!


So, I feel that for the more complex puzzles, and perhaps even for the simpler ones, we have not performed anywhere near the necessary number of scrambling moves required.  The solution to the question you asked me, i.e. how many moves it takes to generate sufficiently random positions on various puzzles, may be much, much higher than any of us previously thought, even for the puzzles we have all been enjoying for years now.  I only see two solutions to this problem, and the second is my recommendation.


First, we could reexamine the entire way we have been generating random positions.  We could find a way to do so that does not involve twisting a random puzzle a certain number of times from the solved state, but rather generating a random permutation and orientation of all of the pieces.  We then check (this is where my formulas would actually come in handy!) if each particular type of piece (they would be the ‘families’ in my NxNxNxN Cube permutation paper) satisfies the mathematical criteria for producing a solvable cube.  If not, then we twist one of the pieces or swap two of them or both, depending on the situation.


This method, however, has several obvious and significant drawbacks:

  1. We would need to reprogram all of the scrambling mechanisms for every program (depending on who would accept to do so), which would be an arduous, lengthy and painstaking task.


  1. The algorithm for doing so would be enormously complicated.

  2. We would need to find the mathematical restrictions on the pieces of every type of puzzle available.  This would involve a huge mathematical effort on my part, making us all very busy for months.  Also, the ‘create a puzzle’ feature in MC4D 4.0 might have to be discarded.


Now, here is the second option: we do nothing.  Or, to put it in more optimistic terms, we reevaluate what ‘sufficiently random’ means to us, not what it means technically.  We have all been enjoying all of your collective creations for many years now.  We never realized the possibility that the scrambles are *technically* not close to random.  From our point of view, it appears as if it is random.  And maybe that’s good enough for us.  I’m betting that no one will have a problem with accepting that our puzzles, especially the more complex ones, may not be technically even close to random as we once thought, but that this knowledge in no way affects our enjoyment of solving the puzzle, or the difficulty we perceive.  Indeed, we could probably never recognize the difference between ‘technically sufficiently random’ and ‘practically sufficiently random’ if we were presented with both.  So, I would suggest simply using the maximum number of
scrambles you feel you can reasonably employ, taking into consideration the sizes of the log files, for each puzzle.  Maybe the puzzles with two pieces per edge could be less than the maximum.  Of course, this maximum should vary for the complexity of each puzzle.  It will be the best we can do, and it should certainly be sufficient.


So, hopefully we can consider the Goldilocks function to not be of too much importance.  You have already said yourself that it was of very low priority, so perhaps this lengthy dialogue was unnecessary.  But I thought I would go into as much detail as possible, for the benefit of everyone.


Thanks again for welcoming me back!  It’s good to be back. :)  I now belong to many yahoo groups, but this was the first, and all of you were really my first true friends, honestly.  It’s a shame I made such a poor decision in leaving, and I regret it, but at least I’ve summoned the courage to come back and repair my mistake.


Anyway, I hope my Goldilocks discussion was helpful, and I’m confident we don’t need to modify the algorithms, as you most likely are as well.  Have a great weekend, everyone!  I’ll be keeping in touch. :)


All the best,
David

— On Sat, 4/30/11, Melinda Green <melinda@superliminal.com> wrote:


From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Hi everyone, I’m back!

To: 4D_Cubing@yahoogroups.com
Date: Saturday, April 30, 2011, 1:17 AM


 

Hello David, and welcome home! :-)

I was sad when you left, but mostly I was worried that you felt badly
about somehow letting anybody down. So far as I know, you did nothing
wrong nor let anybody down when you left. I don’t need any explanations.

Since you ask, the only thing that I could have made use of was the
Goldilocks function we discussed but I never depended on you for that
and it is of such low priority as to not matter. Please don’t even think

about it unless you want to do that for your own satisfaction. Everyone
can come and go from this group as they please, and contribute what they
like and change their mind at any time. As long as people are nice to

each other and keep the discussions even vaguely on-topic, I’m perfectly
happy. Of course I’m thrilled that you are back because you have been
such a helpful resource in the past! Roice is perfectly correct. You are

among friends.

Have fun catching up! :-D
-Melinda

On 4/29/2011 3:47 PM, djs314djs314 wrote:
> Hello my friends,
>
> First of all, I very deeply apologize for my inexplicable behavior when I suddenly and mysteriously left this group of very close friends over half a year ago. I have had some very serious issues going on in my life. In November I was hospitalized for a couple of weeks. To be a bit further ambiguous (sorry!), my departure was related to a symptom of my multiple illnesses. Of course, I can’t blame a foolish, consciousness decision entirely on a symptom, and don’t intend to. If any of you really want to know the whole story, I’ll share it, but with some hesitation! :) Melinda, you probably deserve an explanation, so I will send one to you privately at your request. Again, I apologize for my behavior, but am very much looking forward to being an active member again, if you will have me.

>
> A very meaningful conversation with my good friend Roice inspired me to rejoin this group. I have wanted to for a while, but was honestly afraid of how everyone would respond. Roice helped me realize that I am among friends, and don’t need to worry about such things.

>
> Well, I’m honestly thrilled to be back! :D I have so much to catch up on! I’ve only briefly scanned some of the recent messages, but I see that Magic120Cell and Klein’s Quartic have some new solvers! And of course, there have been contests (blindfold solving?!) and new programs. I’ll have to check out all that!

>
> Hopefully my reintroduction will inspire me to help out and contribute wherever I can. I would like to get back into the combinatorics of the puzzles. Specifically, I’ve been promising myself for quite a while to find the order of the ‘n^d super-superhypercube group’ (at least that is what I call it! :) ). A super-supercube is like a Rubik’s Cube of any size in which every cubie is either on the surface or on the inside of the cube; the cube is solid. Any layer can be twisted. Also, each cubie has a unique identity and orientation (imagine that each face of each cubie has a unique integer associated to it). Obviously I don’t need to expalin how this extends to higher dimensions. My goal is to find a formula for the number of visually ditinguishable permutations of a cube of arbitrary size,>= 2, and arbitrary dimension,>= 3, that can be produced by a sequence of legal moves from the solved position

>
> Also, there are so many other areas I could investigate. If Andrey would like, I can supply an explicit 7-dimensional formula for counting cube permutations, but that probably isn’t necessary. (My general formula handles all dimensions, and who needs such a formula anyway? ;) ) There is also Klein’s Quartic (if you guys haven’t figured it out already), general MagicTile puzzles, general MagicCube4D 2.0 puzzles, etc. I know such efforts are not terribly important to the group, but they do provide me some satisfaction and I would be happy to provide any new formulas I find.

>
> My page of research has moved again, by the way, it is now here:
>
> http://seti.weebly.com/channel.html
>

> Amongst the materials are formulas for n^4, n^5, n^6, and n^d permutations, my Magic120Cell paper, my paper deriving the n^4 formula, and a coloring result for Magic120Cell.
>
> I would also like to wish a warm welcome to any members who may have joined since my unfortunate departure. I wish you the best, and look forward to meeting you!

>
> And Melinda, I had previously promised to help you with some research for MagicCube4D 2.0. If you still require my assistance, I am ready to help as soon as possible.
>
> Thank you everyone so much for your understanding and patience. :) It’s time for me to browse the messages and download some programs! I’ll be writing again soon, and have a great day!

>
> All the best,
> David