Megaminx Scrambler

[CharlieCooper]

Now, the quality of the scrambles is phenomenal.

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

Hilarious.

 

[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.

I said I felt that way because I didn't have any numbers to support it.
Might I add, though, that one scramble could hardly be called sound evidence, either.

 

[Stefan]

one scramble could hardly be called sound evidence, either.

Of course. Though I do have data for twelve sides and and the near area won against the far area only three times and lost eight times, and I think the sides are reasonably unrelated to count this as more than one result.

Btw, does anyone know how many outcomes our Cube Explorer scrambling for 3x3x3 can produce?

 

[hawkmp4]

Btw, does anyone know how many outcomes our Cube Explorer scrambling for 3x3x3 can produce?

I was under the impression that Cube Explorer picked a random state and solved it. So all of the legal states of the cube.

 

[Stefan]

I was under the impression that Cube Explorer picked a random state and solved it. So all of the legal states of the cube.

I doubt it. That would require a pretty darn good randomness generator.

 

[qqwref]

I don't want to get into an argument about how good the various pseudo-RNGs we use are. That argument is really not fun, and there is nothing we can do to affect it anyway. The best we can try to do as cubers is to create an algorithm which is as close to random as possible given an ideal RNG, because then if the statistics turn out wrong the error will at least not be on our end.

Given a perfect RNG, though, picking a random cube position is really easy. I'm not sure what you're trying to say Stefan :|

 

[Stefan]

Given a perfect RNG, though, picking a random cube position is really easy. I'm not sure what you're trying to say Stefan :|

Just curious, I don't remember having this answered in the previous discussions. I don't know what RNG Cube Explorer uses, but probably not a perfect one. And if it uses let's say a 32-bit one then the number of possible outcomes is small.

 

[Stefan]

Another thought: I don't know Javascript's PRNG and it might differ between implementations, but let's say it uses some 64-bit one so the current WCA megaminx scrambler can't even generate 2^70 but at most 2^64 different scrambles. This would limit all other scrambling methods the same way, including the previous WCA one and hawk's and the current WCA one cranked up to 1000 moves and even random state generators. So unless that issue is ruled out, blaiming a scrambler solely for small number of possible outcomes is flawed even as "indication" like qq explained.

 

[qqwref]

let's say it uses some 64-bit one so the current WCA megaminx scrambler can't even generate 2^70 but at most 2^64 different scrambles.

So what you're saying is, if it's deterministic and based only on one of its generated numbers, there would only be 2^64 possible 70-bit sequences and thus only 2^64 possible scrambles? That's true, and I don't know how many 'states' Javascript's random number generator has, but I hope it's larger than that. (Still, this problem is due to the programming language and not the scrambling algorithm itself - if the scrambling algorithm has a severe limitation on the number of scrambles it can generate, it's still in some sense faulty.)

This might be a bit of an overkill idea, but perhaps in the future we could generate official scrambles using data from random.org (which is literally random as opposed to pseudorandom). One section of the website will generate up to 10000 strings of length up to 20, so you could generate a bunch of those and then algorithmically transform them into scrambles. It's an interesting thought.

 

[Stefan]

I don't know how many 'states' Javascript's random number generator has, but I hope it's larger than that.

Well, if I understand correctly, *Java* even only uses 48 bits:
http://java.sun.com/javase/7/docs/api/java/util/Random.html

Still, this problem is due to the programming language and not the scrambling algorithm itself - if the scrambling algorithm has a severe limitation on the number of scrambles it can generate, it's still in some sense faulty.

Please judge this one:

Pick 10^50 states perfectly randomly and hardcode scrambles of optimal length for them into the program. When asked for a scramble, the program perfectly randomly picks one of these scrambles.

Wouldn't you agree that this would result in short and high quality scrambles and would thus be very very good rather than "faulty", despite the severe limitation on the number of scrambles it can generate?

 

[hawkmp4]

Honest question:
Though I see the issue if we were picking a random state of the Megaminx, with scrambles the way they are currently aren't we picking only from the available sides and how far to turn them? And doing this repeatedly? Many many less than 2^32 possibilities. So how is this applicable to the Megaminx scrambler?
Now I never thought of that applied to 3x3, and that's very...bothersome to say the least. That's a very small subset that we can generate.

 

[Stefan]

Honest question:
Though I see the issue if we were picking a random state of the Megaminx, with scrambles the way they are currently aren't we picking only from the available sides and how far to turn them? And doing this repeatedly? Many many less than 2^32 possibilities. So how is this applicable to the Megaminx scrambler?

Are you saying that 2^70 is less than 2^32?

I'm also confused about "picking only from the available sides" as that doesn't sound like the current WCA megaminx scrambler which I think you're talking about. That one doesn't pick sides and only picks direction, not how far to turn.

 

[hawkmp4]

I'm saying any of the available megaminx scramblers. The current one, for example, only picks from -- or ++. The old one (I'm not sure the exact mechanics) would pick from at most 12 sides * 4 ways to move each side = 48 possibilities. 2^32 is much greater than that. So how does the number of bits of the PRNG restrict the number of scrambles we can possibly output?

 

[qqwref]

If the PRNG only looks at the last thing it output to get the next number (and not all do), then the number of *sequences* of any length is the same as the number of bits it is calculating with. This is because every number output will give you the next number if you just know how to get it. So whether you are looking at one number or generating a bunch of numbers and taking them all mod 2 or 3, there are the same number of possible things that could happen.

 

[hawkmp4]

Okay. That makes sense. Thank you.
...now couldn't that be avoided just by reseeding the PRNG as needed?

 

[Stefan]

If the PRNG only looks at the last thing it output to get the next number (and not all do)

Indeed. The Java one for example uses its internal 48-bit state rather than the previous 32-bit output to determine the next. I admit though that this seems to be a requirement from portability and that Javascript may be much better thanks to only specifying to return a number between 0 and 1.

...now couldn't that be avoided just by reseeding the PRNG as needed?

How often, and with what?

 

[hawkmp4]

After it's 32 bit string has been used, and possibly with the system clock?

 

[Stefan]

After it's 32 bit string has been used, and possibly with the system clock?

Then you're abusing the PRNG as a simple hash function with bad input.

Oh and at least Mozilla's Javascript engine uses the same 48-bit PRNG as Java:
http://mxr.mozilla.org/mozilla/source/js/src/jsmath.c

So getting your WCA megaminx scrambles via Firefox means limiting yourself to 2^48 or fewer and it has nothing to do with the actual scrambling method.

 

[arckuss123]

cool

 

[hawkmp4]

Call it what you may, but doesn't that provide us with the end result we want?