Message #1627

From: David Smith <djs314djs314@yahoo.com>
Subject: Re: [MC4D] Hi everyone, I’m back!
Date: Sat, 30 Apr 2011 05:22:47 -0700

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:

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