Message #1647

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Hi everyone, I’m back!
Date: Tue, 03 May 2011 15:26:02 -0700

Hello David,

Thank you for your kind words.

I know that you worry a lot about your place here and like others before
me, I want to assure you that there is no reason to doubt that. Really,
as long as you are nice to everybody and remain even vaguely on-topic,
you have nothing to worry about. Regarding lengthy or frequent messages,
everybody on the list is quite able to delete messages that they are not
interested in. If someone is not interested in combinatorics, they can
even filter out all messages from you, and they shouldn’t have the
slightest guilt about doing that. Of course you will want to avoid that
as much as that is within your control. For that, I suggest waiting 24
hours after composing a long message, and rereading it before you hit
"send". That way you may realize some potential problems before posting.

I also agree with Roice that the best place to share detailed
calculations is in the wiki, so I’m glad that you are having fun with
that. You can then announce new sections as you feel they are complete,
and of course you can fix any mistakes later without even announcing
them. People can watch pages of interest to them, and otherwise just
look-up particular pages as needed and see the latest data.

It is fascinating to remember all of the amazing puzzles and interesting
discussions that have transpired since you left. Certainly this has been
one of our richest periods especially due to Andrey and Roice’s
contributions. There have been many times in the past when I thought
that maybe everything worthy of discussing in this realm had already
been discussed, but then something new and interesting always crops up.
That has happened so often that I no longer think the stream of
interesting puzzles and topics will ever end. The group may go quiet for
several months, but then something completely unexpected crops up and we
all get to watch it being explored even if we don’t participate in the
discussion.

I have some thoughts to share regarding the Goldilocks function. The
first is that I had a small epiphany the other day while thinking about
the insights you gave. I now feel that I have a good feeling for why the
number of scrambling twists needed to fully scramble some puzzles can be
so amazingly high. Imagine the path of a single piece during the
scrambling process. If the puzzle is to be fully scrambled, then that
piece needs to be equally likely to end up in any possible position. For
a puzzle with a lot of faces (cells), a given piece must be able to
easily wander to the extreme opposite side of the puzzle. Scrambling
using random twists will cause that piece to move around with something
like Brownian motion which makes it unlikely for any piece to move very
far in just a few random twists that affect it. The result is something
like carefully placing a single drop of ink into a glass of water and
watching it spread. Eventually it will be fully dispersed, but the time
required for that to happen is highly dependent upon the amount of water
in the glass. In our case this means that it will be far more difficult
to fully scramble a face-turning 120 Cell compared to one where the
slices cut through the center. I find it interesting that the puzzles
that are more difficult to scramble seem to be the easiest to solve, and
vise versa. I now feel that I understand why.

My other thought about the Goldilocks formula is regarding the practical
applications to my problem. Even though a given puzzle may never be
practically scrambled this way, that doesn’t let you off the hook. We
still need to at least choose a heuristic function, and some are better
than others. Here is the code that I currently use:

     int totalTwistsNeededToFullyScramble =<br>
                 puzzleManager.puzzleDescription.nFaces() // needed <br> twists is proportional to nFaces<br>
                 &#42; <br> (int)puzzleManager.puzzleDescription.getEdgeLength() // and to number of <br> slices<br>
                 &#42; 2; // and to a fudge factor that brings the 3&#94;4 <br> close to the original 40 twists.

It is simple, which is a good thing, but I am sure that it is far too
simple. The good news is that I don’t need to know how many twists will
guarantee a well-scrambled puzzle. I only need a function that is "good
enough". For a function to be good enough, it needs to produce results
that appear to be fully scrambled, *and* that doesn’t require an
impractical number of scrambling twists that would make the log files
impractically huge. My question for you then boils down to this: How
would you improve the above function to be more reasonable for any
puzzle the user might generate? I’m not looking for an optimal answer. I
just want an expert like yourself to advise me on how to improve my
clearly inadequate implementation. Of course maybe I should be asking
an engineer rather than a mathematician! :-)

As I was writing the above, it occurred to me that a practical solution
might relax the requirement of not bloating the log files with
scrambling twists. (You do get to suggest modifications to the
requirements if you feel they are over-constrained.) If the number of
twists needed for a decent scrambling is too large to be practical,
maybe we can just leave them out of the log file and just include the
resulting puzzle state. The previous log file format supported this, and
the scrambling twists were optional. That would mean that the "cheat"
version of the solve button will not be possible for those puzzles,
which is a limitation I’m sure we could live with. It even has the nice
feature of making it far harder for a solver to cheat.

Also, I *really* like your idea of manufacturing legitimately scrambled
states directly. I feel that this could be the best solution if it can
be implemented for the general case. I respect that you feel this would
be extremely difficult to do, and possibly even impossible for the
"build-your-own" option, so we can just let this idea sit until maybe
someone will think of a reasonably safe and practical implementation.

So for now, if you or anyone else have any suggestions for improving my
function above, please share them. Just remember that this is not a very
high priority feature, but it does deserve to be improved and would make
me happy.

-Melinda

On 4/30/2011 5:22 AM, David Smith wrote:
>
>
> 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
>
>
>
>