Message #1645

From: Matthew Galla <mgalla@trinity.edu>
Subject: Re: [MC4D] Hi everyone, I’m back!
Date: Tue, 03 May 2011 03:56:43 -0500

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.
>
> 2. The algorithm for doing so would be enormously complicated.
>
> 3. 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
>
>
>