Message #1650
From: David Smith <djs314djs314@yahoo.com>
Subject: Re: [MC4D] Hi everyone, I’m back!
Date: Tue, 03 May 2011 17:53:30 -0700
Hi Melinda,
Thanks for your reassurance that I belong here! I know I can be a bit of a downer
on myself sometimes, and will try to stay more positive in the future. :) The
less time people have to spend reassuring me, that’s less time wasted! And
thanks for the good advice regarding sending long or mathematically detailed
messages, as well. And I agree that the wiki is a great idea. I’m hoping that
some of you find my efforts enjoyable and/or useful.
Yes, it appears I must have missed out on a whole lot of great times. Shame on
me! At least I’m back, and I’m definitely going to make the best of it, and
contribute as much as I can.
Speaking of contributing, permutations are good and all, but I’d really like to
help in a more significant way. And so I’m delighted to hear that you have some
ideas for how I can contribute with the Goldilocks function! (I like your Brownian
motion explanation, by the way. It is even more clear when one considers that
for any particular piece, the vast majority of random face turns won’t even move
it, much less get it equally likely to be in any position! And by symmetry, we
can say the puzzle is fully scrambled when a single piece is equally likely to
be anywhere after random face turns.) I certainly didn’t feel off the hook before,
it was more of a let-down! Now I’m very glad you have clarified that I will be
able to help with this. :)
Before, I didn’t actually realize that the very low number of twists, compared to
the number needed to randomize the puzzle, had a noticeable impact on the puzzle
solving, but now I’m hearing that it does. And wouldn’t it be wonderful to have
a truly scrambled puzzle? I’m truly happy that you love the idea of generating
completely scrambled puzzles. I’ve been thinking about it, and I believe we can
make it work, possibly even for the create your own puzzle option! In my earlier
post, I was mostly concerned with you as the programmers, having to modify your
code too much. But if you willing to do so for such a huge benefit, I can try
and make it work. It would be a great contribution! When finding my formulas,
the hard part nowadays is in counting the number of pieces of every family. The
easy part is actually finding the restrictions, and I may be able to do so for any
puzzle given the Schlafli symbol. As I mentioned in my previous post about the
corner algorithm, I have a systematic method for determining permutation and
orientation restrictions of any puzzle very quickly and easily. I’ll write up the
complete algorithm is pseudocode, once I finish, and then we’ll see if you think
it’s worth implementing.
There might be a difficulty in implementing such a scrambling method for
pieces called wings (see the wiki for an explanation; it’s a bit lengthy), however.
You might need to modify your code so you know which pieces are wings and
which are normals as you generate them. But in any case, I’m confident at this
point that I can come up with an algorithm.
Thanks a lot for writing, and I look forward to assisting you!
All the best,
David
— On Tue, 5/3/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: Tuesday, May 3, 2011, 6:26 PM
Hello David,
Thank you for your kind words.
I know that you worry a lot about your place here and like others<br>
before me, I want to assure you that there is no reason to doubt<br>
that. Really, as long as you are nice to everybody and remain even<br>
vaguely on-topic, you have nothing to worry about. Regarding lengthy<br>
or frequent messages, everybody on the list is quite able to delete<br>
messages that they are not interested in. If someone is not<br>
interested in combinatorics, they can even filter out all messages<br>
from you, and they shouldn't have the slightest guilt about doing<br>
that. Of course you will want to avoid that as much as that is<br>
within your control. For that, I suggest waiting 24 hours after<br>
composing a long message, and rereading it before you hit "send".<br>
That way you may realize some potential problems before posting.
I also agree with Roice that the best place to share detailed<br>
calculations is in the wiki, so I'm glad that you are having fun<br>
with that. You can then announce new sections as you feel they are<br>
complete, and of course you can fix any mistakes later without even<br>
announcing them. People can watch pages of interest to them, and<br>
otherwise just look-up particular pages as needed and see the latest<br>
data.
It is fascinating to remember all of the amazing puzzles and<br>
interesting discussions that have transpired since you left.<br>
Certainly this has been one of our richest periods especially due to<br>
Andrey and Roice's contributions. There have been many times in the<br>
past when I thought that maybe everything worthy of discussing in<br>
this realm had already been discussed, but then something new and<br>
interesting always crops up. That has happened so often that I no<br>
longer think the stream of interesting puzzles and topics will ever<br>
end. The group may go quiet for several months, but then something<br>
completely unexpected crops up and we all get to watch it being<br>
explored even if we don't participate in the discussion.
I have some thoughts to share regarding the Goldilocks function. The<br>
first is that I had a small epiphany the other day while thinking<br>
about the insights you gave. I now feel that I have a good feeling<br>
for why the number of scrambling twists needed to fully scramble<br>
some puzzles can be so amazingly high. Imagine the path of a single<br>
piece during the scrambling process. If the puzzle is to be fully<br>
scrambled, then that piece needs to be equally likely to end up in<br>
any possible position. For a puzzle with a lot of faces (cells), a<br>
given piece must be able to easily wander to the extreme opposite<br>
side of the puzzle. Scrambling using random twists will cause that<br>
piece to move around with something like Brownian motion which makes<br>
it unlikely for any piece to move very far in just a few random<br>
twists that affect it. The result is something like carefully<br>
placing a single drop of ink into a glass of water and watching it<br>
spread. Eventually it will be fully dispersed, but the time required<br>
for that to happen is highly dependent upon the amount of water in<br>
the glass. In our case this means that it will be far more difficult<br>
to fully scramble a face-turning 120 Cell compared to one where the<br>
slices cut through the center. I find it interesting that the<br>
puzzles that are more difficult to scramble seem to be the easiest<br>
to solve, and vise versa. I now feel that I understand why.
My other thought about the Goldilocks formula is regarding the<br>
practical applications to my problem. Even though a given puzzle may<br>
never be practically scrambled this way, that doesn't let you off<br>
the hook. We still need to at least choose a heuristic function, and<br>
some are better than others. Here is the code that I currently use:
int totalTwistsNeededToFullyScramble =
puzzleManager.puzzleDescription.nFaces() //<br>
needed twists is proportional to nFaces
*<br>
(int)puzzleManager.puzzleDescription.getEdgeLength() // and to<br>
number of slices
* 2; // and to a fudge factor that brings the<br>
3^4 close to the original 40 twists.
It is simple, which is a good thing, but I am sure that it is far<br>
too simple. The good news is that I don't need to know how many<br>
twists will guarantee a well-scrambled puzzle. I only need a<br>
function that is "good enough". For a function to be good enough, it<br>
needs to produce results that appear to be fully scrambled, *and*<br>
that doesn't require an impractical number of scrambling twists that<br>
would make the log files impractically huge. My question for you<br>
then boils down to this: How would you improve the above function to<br>
be more reasonable for any puzzle the user might generate? I'm not<br>
looking for an optimal answer. I just want an expert like yourself<br>
to advise me on how to improve my clearly inadequate <br>
implementation. Of course maybe I should be asking an engineer<br>
rather than a mathematician! :-)
As I was writing the above, it occurred to me that a practical<br>
solution might relax the requirement of not bloating the log files<br>
with scrambling twists. (You do get to suggest modifications to the<br>
requirements if you feel they are over-constrained.) If the number<br>
of twists needed for a decent scrambling is too large to be<br>
practical, maybe we can just leave them out of the log file and just<br>
include the resulting puzzle state. The previous log file format<br>
supported this, and the scrambling twists were optional. That would<br>
mean that the "cheat" version of the solve button will not be<br>
possible for those puzzles, which is a limitation I'm sure we could<br>
live with. It even has the nice feature of making it far harder for<br>
a solver to cheat.
Also, I *really* like your idea of manufacturing legitimately<br>
scrambled states directly. I feel that this could be the best<br>
solution if it can be implemented for the general case. I respect<br>
that you feel this would be extremely difficult to do, and possibly<br>
even impossible for the "build-your-own" option, so we can just let<br>
this idea sit until maybe someone will think of a reasonably safe<br>
and practical implementation.
So for now, if you or anyone else have any suggestions for improving<br>
my function above, please share them. Just remember that this is not<br>
a very high priority feature, but it does deserve to be improved and<br>
would make me happy.
-Melinda
On 4/30/2011 5:22 AM, David Smith wrote:<br>
<br>
<br>
<br>
<br>
<br>
<br>
Thank you so much<br>
Melinda! You are very gracious. :)
I haven't browsed most of the messages I've missed<br>
(obviously there are a lot!), but after my reintroduction,<br>
I was immediately astounded by all of the new programs! <br>
7-dimensional Rubik's Cubes? Magic Hyperbolic Tile? <br>
5-dimensional Pac-man? 4-dimensional Tetris?! <br>
Incredible! I think Andrey deserves an award for being<br>
one of the talented programmers in the world, in the<br>
'Creative Genius' category! And Roice provided the<br>
inspiration, being the first person to ever program a 5D<br>
Cube and Tile-based puzzles! (I'm sure he could do even<br>
more, but he is very busy!) And you and Don provided the<br>
inspiration for Roice, and this group. :)
I feel so bad I missed out sharing the good times. But,<br>
it seems there are still plenty to be had! The only<br>
computer program I have written recently simulates Ulam's<br>
Game, a mathematical thought experiment. I believe it is<br>
the only one of its kind. But it was trivial to create;<br>
nothing even remotely close to what all of you have<br>
accomplished. I'm constantly inspired by your<br>
intelligence! And I forgot to mention that one day I do<br>
intend to work out solving these puzzles for myself.
I've done some research into the Goldilocks function<br>
problem, and I have some bad news, and some worse news.<br>
:( The implications could be unfortunate, and you may<br>
wish I had never looked into it. It's up to all of you as<br>
to how you would like to proceed. I'm fine with keeping<br>
things as they are, and that what I am about to say may be<br>
considered questionable and irrelevant to our current<br>
scrambling methods.
First, the bad news: This Goldilocks function is almost<br>
certainly beyond my capabilities. I'm betting a<br>
mathematician would have much trouble. The problem is<br>
that the number of moves it takes to produce a<br>
'sufficiently random' position (which is already a<br>
subjective term; it can be made more precise<br>
mathematically, in a way that is somewhat above my head),<br>
varies from puzzle to puzzle. I doubt there is a general<br>
solution. Also, I doubt that it is practical to answer<br>
this question for any particular puzzle by purely<br>
mathematical methods, given the extreme difficulty. <br>
Computer tests need to be performed, i.e. scrambles need<br>
to be done repeatedly and analyzed with statistics.
Here is the worse news: Such statistical analyses have<br>
already been performed for the 3^3 Cube and Megaminx. You<br>
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<br>
mathematician, and the analyses could have been simplified<br>
and improved upon, but I've studied the paper and there<br>
appear to be no errors. I believe that the results are<br>
accurate enough for our purposes.
I originally conjectured that 20 moves would suffice to<br>
scramble the Rubik's Cube, since every position can be<br>
solved in at most 20 moves. This turns out to be a very<br>
naive and flawed assumption. According to the report, it<br>
takes around 45 moves to scramble a Rubik's Cube so that<br>
it is sufficiently random.
Now, he also studied the megaminx. This is where things<br>
begin to get depressing. According to the page, it takes<br>
around 250 moves for the megaminx to begin to become<br>
randomly mixed. We can see the number of moves rapidly<br>
increasing with the complexity of the puzzle. The<br>
megaminx is simpler than even the standard 3^4 cube. So,<br>
I'm very roughly estimating that for a puzzle such as<br>
Magic120Cell, which is hugely complex, the number of moves<br>
required to generate a sufficiently random position could<br>
be in the hundred thousands, millions, or even higher!
So, I feel that for the more complex puzzles, and perhaps<br>
even for the simpler ones, we have not performed anywhere<br>
near the necessary number of scrambling moves required. <br>
The solution to the question you asked me, i.e. how many<br>
moves it takes to generate sufficiently random positions<br>
on various puzzles, may be much, much higher than any of<br>
us previously thought, even for the puzzles we have all<br>
been enjoying for years now. I only see two solutions to<br>
this problem, and the second is my recommendation.
First, we could reexamine the entire way we have been<br>
generating random positions. We could find a way to do so<br>
that does not involve twisting a random puzzle a certain<br>
number of times from the solved state, but rather<br>
generating a random permutation and orientation of all of<br>
the pieces. We then check (this is where my formulas<br>
would actually come in handy!) if each particular type of<br>
piece (they would be the 'families' in my NxNxNxN Cube<br>
permutation paper) satisfies the mathematical criteria for<br>
producing a solvable cube. If not, then we twist one of<br>
the pieces or swap two of them or both, depending on the<br>
situation.
This method, however, has several obvious and significant<br>
drawbacks:
1. We would need to reprogram all of the scrambling<br>
mechanisms for every program (depending on who would<br>
accept to do so), which would be an arduous, lengthy and<br>
painstaking task.
2. The algorithm for doing so would be enormously<br>
complicated.
3. We would need to find the mathematical restrictions on<br>
the pieces of every type of puzzle available. This would<br>
involve a huge mathematical effort on my part, making us<br>
all very busy for months. Also, the 'create a puzzle'<br>
feature in MC4D 4.0 might have to be discarded.
Now, here is the second option: we do nothing. Or, to put<br>
it in more optimistic terms, we reevaluate what<br>
'sufficiently random' means to us, not what it means<br>
technically. We have all been enjoying all of your<br>
collective creations for many years now. We never<br>
realized the possibility that the scrambles are<br>
*technically* not close to random. From our point of<br>
view, it appears as if it is random. And maybe that's<br>
good enough for us. I'm betting that no one will have a<br>
problem with accepting that our puzzles, especially the<br>
more complex ones, may not be technically even close to<br>
random as we once thought, but that this knowledge in no<br>
way affects our enjoyment of solving the puzzle, or the<br>
difficulty we perceive. Indeed, we could probably never<br>
recognize the difference between 'technically sufficiently<br>
random' and 'practically sufficiently random' if we were<br>
presented with both. So, I would suggest simply using the<br>
maximum number of scrambles you feel you can reasonably<br>
employ, taking into consideration the sizes of the log<br>
files, for each puzzle. Maybe the puzzles with two pieces<br>
per edge could be less than the maximum. Of course, this<br>
maximum should vary for the complexity of each puzzle. It<br>
will be the best we can do, and it should certainly be<br>
sufficient.
So, hopefully we can consider the Goldilocks function to<br>
not be of too much importance. You have already said<br>
yourself that it was of very low priority, so perhaps this<br>
lengthy dialogue was unnecessary. But I thought I would<br>
go into as much detail as possible, for the benefit of<br>
everyone.
Thanks again for welcoming me back! It's good to be back.<br>
:) I now belong to many yahoo groups, but this was the<br>
first, and all of you were really my first true friends,<br>
honestly. It's a shame I made such a poor decision in<br>
leaving, and I regret it, but at least I've summoned the<br>
courage to come back and repair my mistake.
Anyway, I hope my Goldilocks discussion was helpful, and<br>
I'm confident we don't need to modify the algorithms, as<br>
you most likely are as well. Have a great weekend,<br>
everyone! I'll be keeping in touch. :)
All the best,
David
--- On Sat, 4/30/11, Melinda Green <melinda@superliminal.com><br>
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
<br>
<br>
<br>
Hello David, and welcome home! :-)
I was sad when you left, but mostly I was worried<br>
that you felt badly
about somehow letting anybody down. So far as I<br>
know, you did nothing
wrong nor let anybody down when you left. I don't<br>
need any explanations.
Since you ask, the only thing that I could have<br>
made use of was the
Goldilocks function we discussed but I never<br>
depended on you for that
and it is of such low priority as to not matter.<br>
Please don't even think
about it unless you want to do that for your own<br>
satisfaction. Everyone
can come and go from this group as they please,<br>
and contribute what they
like and change their mind at any time. As long as<br>
people are nice to
each other and keep the discussions even vaguely<br>
on-topic, I'm perfectly
happy. Of course I'm thrilled that you are back<br>
because you have been
such a helpful resource in the past! Roice is<br>
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<br>
inexplicable behavior when I suddenly and<br>
mysteriously left this group of very close friends<br>
over half a year ago. I have had some very serious<br>
issues going on in my life. In November I was<br>
hospitalized for a couple of weeks. To be a bit<br>
further ambiguous (sorry!), my departure was<br>
related to a symptom of my multiple illnesses. Of<br>
course, I can't blame a foolish, consciousness<br>
decision entirely on a symptom, and don't intend<br>
to. If any of you really want to know the whole<br>
story, I'll share it, but with some hesitation! :)<br>
Melinda, you probably deserve an explanation, so I<br>
will send one to you privately at your request.<br>
Again, I apologize for my behavior, but am very<br>
much looking forward to being an active member<br>
again, if you will have me.
>
> A very meaningful conversation with my good<br>
friend Roice inspired me to rejoin this group. I<br>
have wanted to for a while, but was honestly<br>
afraid of how everyone would respond. Roice helped<br>
me realize that I am among friends, and don't need<br>
to worry about such things.
>
> Well, I'm honestly thrilled to be back! :D I<br>
have so much to catch up on! I've only briefly<br>
scanned some of the recent messages, but I see<br>
that Magic120Cell and Klein's Quartic have some<br>
new solvers! And of course, there have been<br>
contests (blindfold solving?!) and new programs.<br>
I'll have to check out all that!
>
> Hopefully my reintroduction will inspire me<br>
to help out and contribute wherever I can. I would<br>
like to get back into the combinatorics of the<br>
puzzles. Specifically, I've been promising myself<br>
for quite a while to find the order of the 'n^d<br>
super-superhypercube group' (at least that is what<br>
I call it! :) ). A super-supercube is like a<br>
Rubik's Cube of any size in which every cubie is<br>
either on the surface or on the inside of the<br>
cube; the cube is solid. Any layer can be twisted.<br>
Also, each cubie has a unique identity and<br>
orientation (imagine that each face of each cubie<br>
has a unique integer associated to it). Obviously<br>
I don't need to expalin how this extends to higher<br>
dimensions. My goal is to find a formula for the<br>
number of visually ditinguishable permutations of<br>
a cube of arbitrary size,>= 2, and arbitrary<br>
dimension,>= 3, that can be produced by a<br>
sequence of legal moves from the solved position
>
> Also, there are so many other areas I could<br>
investigate. If Andrey would like, I can supply an<br>
explicit 7-dimensional formula for counting cube<br>
permutations, but that probably isn't necessary.<br>
(My general formula handles all dimensions, and<br>
who needs such a formula anyway? ;) ) There is<br>
also Klein's Quartic (if you guys haven't figured<br>
it out already), general MagicTile puzzles,<br>
general MagicCube4D 2.0 puzzles, etc. I know such<br>
efforts are not terribly important to the group,<br>
but they do provide me some satisfaction and I<br>
would be happy to provide any new formulas I find.
>
> My page of research has moved again, by the<br>
way, it is now here:
>
> http://seti.weebly.com/channel.html
>
> Amongst the materials are formulas for n^4,<br>
n^5, n^6, and n^d permutations, my Magic120Cell<br>
paper, my paper deriving the n^4 formula, and a<br>
coloring result for Magic120Cell.
>
> I would also like to wish a warm welcome to<br>
any members who may have joined since my<br>
unfortunate departure. I wish you the best, and<br>
look forward to meeting you!
>
> And Melinda, I had previously promised to<br>
help you with some research for MagicCube4D 2.0.<br>
If you still require my assistance, I am ready to<br>
help as soon as possible.
>
> Thank you everyone so much for your<br>
understanding and patience. :) It's time for me to<br>
browse the messages and download some programs!<br>
I'll be writing again soon, and have a great day!
>
> All the best,
> David