Megaminx Scrambler

[hawkmp4]

I read Dan Hayes' post on the speedsolving yahoo group (http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/41005) a while ago, and now I have the programming ability to implement some of the ideas.
So, I threw together a quick scrambler that generates 125 move scrambles (not counting cube turns). It allows 1/5 and 2/5 turns in both directions. It rejects sequences like D Y D or Y D Y and duplicate turns, of course. Cube turns are randomly interspersed and as I said, are not counted in the move count.
Now, the quality of the scrambles is phenomenal. No problems whatsoever. The problem lies in...well...
Here's a sample output...
D+ R-- D-- Y++ R+ Y+ R++ D- R++ Y+ R++ D++ Y+ R- Y-- R++ D+ Y++ R- D-- R-- D++ R-- D+ Y- R- D- R- Y++ D- R+ Y-- D- R++ D+ Y++ R-- D-- R++ Y+ R-- D-- R++ Y-- D- R+ Y-- D- R- D+ Y+ R++ Y- R- D-- Y++ R+ D-- Y- R++ D+ Y++ R-- Y-- D+ R++ D+ R- D+ Y+ R+ D-- R+ D-- R+ Y++ D++ R- Y++ D++ R++ D-- R+ D++ R-- Y++ R- D-- Y+ R+ Y-- R-- Y+ D++ R-- D++ R+ D++ R++ D- Y- R+ Y- D-- R-- D++ Y- R- D++ Y- R++ Y+ D-- R+ Y- R-- D- R++ Y++ R++ D-- Y++ R- D- Y+ R+ D++ Y++ R-- Y-- D+ R+ Y+ R-- D- Y+ R+ D++ R++ Y+ D+ R++ D++ R+ D++ Y- R-- Y- D-- R++ Y++ R++ Y-- D- R- Y- D+ R++ Y++ D+ R- Y++ R- Y+ D++ R- D+ Y-- R- Y++ R- Y-- R++ Y+ R- Y-- D-- R--
Frankly, it takes forever. It takes me longer to scramble than solve.
Does anyone have any ideas for improving this, without compromising the scramble quality?

 

[Kickflip1993]

as far as i know, normal scrambles are only 60 turns and have a U or U' as every 10th turn

 

[Jake Gouldon]

We need to find a way to get better megaminx scrambles, and I think the non-Pochman system did that. There are many more possible cube states using it.

As to your scrambler, perhaps a lower move-count? I would say 100 is plenty.

 

[hawkmp4]

Neither of you have seemed to read the link I supplied.

 

[qqwref]

The statistics in the link you posted are pretty weird. I'm not really sure to make of something that says we need >50 moves to get an adequate 3x3 scramble... it's just so far away from what we've observed as a community that I would definitely have to do the analysis myself to be sure.

Anyway, if you want high-quality megaminx scrambles without doing a huge number of moves, I think the best solution is to go back to 3x3-style scrambles... give each face a name and just randomly do 60 or 70 moves, like the 3x3 scrambler. It's just not practical to have to read and do 120 or so moves for something that's going to take only a minute for a fast competitor to solve.

 

[Lucas Garron]

It rejects sequences like D Y D or Y D Y and duplicate turns, of course.

Why?

Now, the quality of the scrambles is phenomenal. No problems whatsoever.

How does the phenomenality compare to current official scrambles?
...if we use the same scramble lengths? (Count rotations, because those take time to do.)

 

[hawkmp4]

It rejects sequences like D Y D or Y D Y and duplicate turns, of course.

Why?

Now, the quality of the scrambles is phenomenal. No problems whatsoever.

How does the phenomenality compare to current official scrambles?
...if we use the same scramble lengths? (Count rotations, because those take time to do.)

D Y D can be rewritten as some combination of a single D move and a single Y move. So I didn't think it was necessary. For example, D++ Y+ D- is more effectively written as D+ Y+, which the scrambler is perfectly capable of generating.

I haven't done enough scrambles to really see empirically the difference, I'll be honest. But I've had rather poor results with the Pochmann scrambles. Way more intact CE pairs than I think there should be with 70 turns, which Dan's statistics seem to support. I haven't seen anything like that with the scrambler I wrote. Yet, at least. I could be wrong.

qq- Rather than rejecting the statistics because the result seems weird, can you explain what's wrong with them? Dan Hayes lays out pretty clearly the tests he did. Apart from arithmetic error, I don't see anything that could be a problem. It's not what we'd expect, no. That doesn't mean it should be discounted without examination. If you do see something though, please let me know. I'm curious.

In regards to the old style of scrambling- unfortunately I think that is the best way to go. Slow, but effective.

 

[qqwref]

qq- Rather than rejecting the statistics because the result seems weird, can you explain what's wrong with them? Dan Hayes lays out pretty clearly the tests he did. Apart from arithmetic error, I don't see anything that could be a problem. It's not what we'd expect, no. That doesn't mean it should be discounted without examination. If you do see something though, please let me know. I'm curious.

Sure, he says what tests he did, but I doubt the results. No calculations/code are shown so I don't even know if he calculated anything correctly; arithmetic error is a huge fact. For instance he lists expected SDs of 360 and 279 without any explanation. Don't accuse me of rejecting things "without examination"... did you even notice the post was in 2008? There is no backing evidence or data, or macros we can run ourselves, just a bunch of numbers someone posted. I'm not rejecting the results automatically, but if his analysis gives numbers that are much different from what we expect, I personally think it is more likely that he did something numerically wrong than that we need 50 moves to get good 3x3 scrambles. It could be either way, but we would have to see the code to decide.

 

[hawkmp4]

qq- Rather than rejecting the statistics because the result seems weird, can you explain what's wrong with them? Dan Hayes lays out pretty clearly the tests he did. Apart from arithmetic error, I don't see anything that could be a problem. It's not what we'd expect, no. That doesn't mean it should be discounted without examination. If you do see something though, please let me know. I'm curious.

Sure, he says what tests he did, but I doubt the results. No calculations/code are shown so I don't even know if he calculated anything correctly; arithmetic error is a huge fact. For instance he lists expected SDs of 360 and 279 without any explanation. Don't accuse me of rejecting things "without examination"... did you even notice the post was in 2008? There is no backing evidence or data, or macros we can run ourselves, just a bunch of numbers someone posted. I'm not rejecting the results automatically, but if his analysis gives numbers that are much different from what we expect, I personally think it is more likely that he did something numerically wrong than that we need 50 moves to get good 3x3 scrambles. It could be either way, but we would have to see the code to decide.

I'm sorry- I didn't mean that to be offensive in any way. I have the utmost respect for you. I just meant that you provided no more justification for your dismissal than he did for the numbers. I've sent Dan an email for the programs. I guess we can't do much more until we can go over them, can we?

Also, I wasn't around during the change, why was the previous method abandoned? Ease of use for non-Megaminxers, for lack of a better word?

 

[qqwref]

Also, I wasn't around during the change, why was the previous method abandoned? Ease of use for non-Megaminxers, for lack of a better word?

Pretty much. As soon as Stefan introduced the new scrambler everyone loved it - it IS far easier to do (a lot of people commented that they pretty much never made a mistake with it, whereas the original scrambler was easy to make errors with) and the scrambles it produces look scrambled enough (ha). As far as I can tell nobody seems to mind that it only generates 10^21 out of the 10^68 possible positions.

I would like to see some kind of analysis of, on average after X random moves, how close edges and corners are to being paired up. What I mean is, you take every adjacent corner and edge from the solved state, and see how many moves it would take to pair them up again from the scramble. A value for this that is significantly lower than the random scramble average would signify that however many moves is not enough. I think this is a better metric than many others (since it's obviously related to how easy the scrambles are to actually solve) but I've never seen it computed.

 

[hawkmp4]

That does bother me quite a lot. That's a significant amount of states we just can't generate with this scrambler. It IS a lot easier, but it makes me squirm. That's why I've been working on a better scrambler, if only for my own use.
That would be a very interesting analysis- but well over my head. I'd have no idea how to approach that.

 

[qqwref]

OK, I did a basic analysis looking at the # of stickers of the center color on each face for 3x3. I used Jaap's old scrambler and did 100k scrambles each (so 600k faces) and used a version of the chi-square test to check if the distributions of the number of same-color stickers were the same for X turn scrambles as for 1000 turn scrambles.

My results somewhat correlated with the results you linked to, which I found a bit surprising. The test said that the 40, 50, and 100 turn scrambles were probably not from different distributions as the 1000-turn scrambles, but the 30-turn scramble failed the test (p = 0.00993 that they were from the same distribution) and the 25-turn scramble failed it really hard (p ~= 10^-15). So as far as this variable is concerned 25 turns is really not enough, and we might even need a bit more than 30 to get something that doesn't look not random.

 

[spdqbr]

There has been some analysis like this done here. I am trying to dig up the code I used to generate those numbers, I should still have it somewhere.

 

[Stefan]

Now, the quality of the scrambles is phenomenal.

"Phenomenal"? Are you doing mathematics or marketing? Numbers, please.

why was the previous method abandoned? Ease of use for non-Megaminxers, for lack of a better word?

Change that to "for non-Megaminx-official-scramblers". Cause I consider myself a decent Megaminxer and I had trouble doing the 60 moves in five minutes. With the new method I can do the 70 moves in 50 seconds easily (and others do it much faster). In other words, I could do 420 moves with the new method in the same time the old method takes me.

And I believe Daniel did make some mistake:

Megaminx:
WCA Scrambler
Turns | Std Dev | Expected Std Dev | Confidence
10 |108483.94| 279 | 0.3%
50 | 21986.84| 279 | 0.9%
70 | 12559.95| 279 | 1.7% *official scramble length
100 | 5546.20| 279 | 5.0%
150 | 1451.23| 279 | 19.2%
200 | 469.90| 279 | 59.4%
210 | 398.26| 279 | 70.1%
220 | 351.96| 279 | 79.3%
230 | 312.99| 279 | 89.2%
240 | 307.22| 279 | 90.9%
250 | 294.32| 279 | 94.8%
260 | 285.37| 279 | 97.8%
270 | 280.47| 279 | 99.5%
300 | 278.30| 279 | 99.7%
400 | 275.66| 279 | 98.7%
500 | 269.56| 279 | 96.6%
1000 | 264.62| 279 | 94.8%

Note how starting at 300 moves the measured standard deviation drops further and further below the expected standard deviation, and the confidence shrinks accordingly. I'm no statistician, either, but that seems rather odd to me. I think it should just get closer and closer to 279 from above. Daniel, if you can still run the program to get those numbers, can you look how it develops with even more moves (2000, 3000, etc)?

 

[hawkmp4]

Now, the quality of the scrambles is phenomenal.

"Phenomenal"? Are you doing mathematics or marketing? Numbers, please.

why was the previous method abandoned? Ease of use for non-Megaminxers, for lack of a better word?

Change that to "for non-Megaminx-official-scramblers". Cause I consider myself a decent Megaminxer and I had trouble doing the 60 moves in five minutes. With the new method I can do the 70 moves in 50 seconds easily (and others do it much faster). In other words, I could do 420 moves with the new method in the same time the old method takes me.

And I believe Daniel did make some mistake:

Megaminx:
WCA Scrambler
Turns | Std Dev | Expected Std Dev | Confidence
10 |108483.94| 279 | 0.3%
50 | 21986.84| 279 | 0.9%
70 | 12559.95| 279 | 1.7% *official scramble length
100 | 5546.20| 279 | 5.0%
150 | 1451.23| 279 | 19.2%
200 | 469.90| 279 | 59.4%
210 | 398.26| 279 | 70.1%
220 | 351.96| 279 | 79.3%
230 | 312.99| 279 | 89.2%
240 | 307.22| 279 | 90.9%
250 | 294.32| 279 | 94.8%
260 | 285.37| 279 | 97.8%
270 | 280.47| 279 | 99.5%
300 | 278.30| 279 | 99.7%
400 | 275.66| 279 | 98.7%
500 | 269.56| 279 | 96.6%
1000 | 264.62| 279 | 94.8%

Note how starting at 300 moves the measured standard deviation drops further and further below the expected standard deviation, and the confidence shrinks accordingly. I'm no statistician, either, but that seems rather odd to me. I think it should just get closer and closer to 279 from above. Daniel, if you can still run the program to get those numbers, can you look how it develops with even more moves (2000, 3000, etc)?

Fair enough, I'll cut the rhetoric.

Okay. I wasn't sure. I've never used the old scrambler so it really was an honest question. The question that lurks in my mind though is whether those 420 moves are really as effective as they could be.

That also bothered me- which is why I wanted to see if the results were reproduced. I have confidence in Daniel's work, absolutely, but that is an odd phenomena that no one ever came up with an explanation for.

 

[Stefan]

Fair enough, I'll cut the rhetoric.

Well, if you have a reason to call it phenomenal, then please, by all means, call it that. Just let us know the reason as well.

We need to find a way to get better megaminx scrambles, and I think the non-Pochman system did that. There are many more possible cube states using it.

So the low number of possible outcomes is your complaint? How is that bad? You think 10^21 scrambles isn't enough for all of us for a long time?

 

[qqwref]

So the low number of possible outcomes is your complaint? How is that bad? You think 10^21 scrambles isn't enough for all of us for a long time?

If nothing else, it's an indication that there is almost certainly some kind of bias. The set of positions that the scrambler can generate is a minuscule subset of the set of possible positions, and since the scrambler positions were not chosen as random samples from the larger set (but simply by looking at every position that can be reached in 70 pochmann-scrambler moves) it is very likely that the positions that the scrambler can reach are significantly different (on average) than the positions that you would get from just randomly choosing one minx position. There's no way to know if the positions the scrambler generates are easier/harder/closer to solved/less blocky/whatever compared to the positions a uniform random distribution would generate, but the fact that the number of positions the scrambler generates is so small means that there is almost certainly a significant difference. We just don't know what the difference is.

I think in the cube community there is a bit of a problem with people assuming scramblers 'work' (i.e. provide a distribution of solves that closely resembles the one we would get by randomly picking a cube state) when they aren't proven to. For some scramblers, such as optimal random state scramblers, it is trivial to prove this is true; for others, I think we tend to just assume that if positions look scrambled they are, without really doing an analysis. For example the Square-1 scrambler programmed by Jaap, which is currently in use for WCA scrambles, seems to provide parity only ~40% of the time in practice when the puzzle is solved with optimal cubeshape. Your megaminx scrambler might provide positions that look scrambled, but this is not enough to show the scramble is as hard on average as it should be - try doing 40 random moves on a 7x7. Personally I think the fact that the megaminx scrambler generates such a small fraction of the positions is evidence against its having a distribution similar to a theoretical optimal random scrambler, and I think we really cannot be sure whether it provides positions that are truly as difficult as random positions or whether it just provides positions that appear scrambled but might not be.

 

[Mike Hughey]

One thing that I couldn't help noticing was that the week we started using Stefan's scrambles for megaminx on the weekly competitions, my times suddenly seemed to get a lot better. Of course, there are lots of possible explanations for this: I simply got better that week; not having to apply the old scrambles meant I was less fatigued so I was better at actually solving; psychologically I felt they were better so I went faster; just coincidence due to insufficient data points; etc. But it is something I noticed, FWVLIW (for what very little it's worth).

 

[hawkmp4]

One thing that I couldn't help noticing was that the week we started using Stefan's scrambles for megaminx on the weekly competitions, my times suddenly seemed to get a lot better. Of course, there are lots of possible explanations for this: I simply got better that week; not having to apply the old scrambles meant I was less fatigued so I was better at actually solving; psychologically I felt they were better so I went faster; just coincidence due to insufficient data points; etc. But it is something I noticed, FWVLIW (for what very little it's worth).

That's how I've felt using my scrambler. It's not as easy to find the right C/E pair, and my 'cross' edges aren't nearly always in the bottom half of the minx. It just feels to be more random. I'd never known the numbers of states possible by the Pochmann scrambler, but as qqwref said, I doubt that they're a representative sample of all the scrambles.

 

[Stefan]

That's how I've felt using my scrambler. It's not as easy to find the right C/E pair, and my 'cross' edges aren't nearly always in the bottom half of the minx.

Again: Numbers, please.

This did sound interesting so I did a small test with one WCA scramble:
R++ D++ R++ D++ R++ D++ R-- D-- R-- D++ U
R-- D-- R-- D-- R++ D-- R-- D++ R++ D++ U
R-- D-- R++ D++ R++ D-- R++ D++ R++ D-- U'
R-- D-- R-- D++ R++ D-- R-- D-- R++ D-- U'
R++ D++ R++ D-- R-- D-- R++ D-- R++ D++ U
R++ D-- R-- D-- R-- D-- R++ D++ R-- D-- U'
R-- D++ R-- D-- R-- D++ R-- D++ R-- D++ U

I counted where the edges of each face ended up. On/adjacent to their goal layer (10 positions), in the middle zig-zag (10 positions), or on/adjacent to the layer opposite their goal layer (10 positions). I did it for all sides cause I don't know how you hold your minx before scrambling, and to get more data. The results:

white: 1/2/2
brown: 3/2/0
blue: 1/2/2
purple: 2/1/2
green: 0/3/2
turquoise: 2/2/1
yellow: 2/3/0
red: 1/2/2
orange: 0/1/4
green2: 0/2/3
pink: 0/4/1
blue2: 0/2/3

Sum: 12/26/22

Assuming you meant bottom=whereTheCrossIs, here I experienced the exact opposite of what you describe. But please, share your numbers with us that you had but forgot to post along with your claim.

Of course on average the result should be 20/20/20 since all three areas are the same size, so my above result deviates quite a bit. If someone's able to test this on a larger scale with a program, I'd be very interested in the results.