Megaminx Scrambler

[spdqbr]

You're correct hawk, I did find that variable length scrambles were bad. I'm curious what would happen if I re-ran the test with the minimum length being the lowest length which was deemed "good enough" It seems reasonable that if 45 moves gets us generally scrambled (on a 3x3) and we use variable length scrambles in the range 45-55 moves that should also be sufficient. The main result I was concerned with back then was could you decrease the required number of moves to randomize a cube by allowing variable length scrambles. (i.e. 45 was enough, but would selecting from a range between 30 and 40 get you there, the answer to which seems to be "no").

But yes, this feels like a cludge more than anything, I agree.

As for the Mersenne Twister, it seems relatively simple to implement. You can find an implementation in javascript here which I have yet to try. I did seamlessly incorporate this implementation in Java into my scramble generator with almost no work. Perhaps I should run the cube scramble analysis using this and other PRNGS and see what we see.

It looks like it's been implemented in just about every reasonable language.

Is this overkill? Probably. But I would like to pose the question: If it is exceedingly easy to implement in the scramblers and it gives us access to a larger portion of the puzzles' scramble-spaces, why not use it?

 

[blade740]

I agree with that: a better PRNG can only be a good thing.

 

[Stefan]

I haven't thought of a more clever solution using a single PRNG at this point, but if I were coding this, I would suggest perhaps using two instances of a prng, one for the scrambles and one to determine scramble length.

Or... if you're going to use another PRNG instance anyway, you could just use both directly for the scrambles. For example always use 35 bits from the first instance and 36 from the second.

Stefan, I'm quite curious to hear your solution, as I'm sure there should be a more elegant way to do it and I'd wager you've found it.

Well, the other reason I asked for your idea was that mine wasn't particularly exciting. I summarize it as "reuse and reinterpret". For example reuse the same PRNG output from the first scramble to produce a second scramble by using the old WCA scrambler. Or rotate the data, e.g., instead of using bits 1-70 use bits 2-70 followed by bit 1, then 3-70 followed by 1-2, etc. Or flip every second bit. Or xor with a chaotic bitmask.

Another idea is to really ask for a number of bits (Java's PRNG does support this) and have that number relatively prime to the number of bits in the cycle. So with a cycle of 2^48 values of 32 bits each, you could get 32*2^48 different scrambles rather than "only" 2^48.

But in my opninion this is all just overkill, provides no practical advantage and only makes things more complicated and error-prone.

 

[hawkmp4]

You're correct hawk, I did find that variable length scrambles were bad. I'm curious what would happen if I re-ran the test with the minimum length being the lowest length which was deemed "good enough" It seems reasonable that if 45 moves gets us generally scrambled (on a 3x3) and we use variable length scrambles in the range 45-55 moves that should also be sufficient. The main result I was concerned with back then was could you decrease the required number of moves to randomize a cube by allowing variable length scrambles. (i.e. 45 was enough, but would selecting from a range between 30 and 40 get you there, the answer to which seems to be "no").

But yes, this feels like a cludge more than anything, I agree.

As for the Mersenne Twister, it seems relatively simple to implement. You can find an implementation in javascript here which I have yet to try. I did seamlessly incorporate this implementation in Java into my scramble generator with almost no work. Perhaps I should run the cube scramble analysis using this and other PRNGS and see what we see.

It looks like it's been implemented in just about every reasonable language.

Is this overkill? Probably. But I would like to pose the question: If it is exceedingly easy to implement in the scramblers and it gives us access to a larger portion of the puzzles' scramble-spaces, why not use it?

I agree with everything you've said here. I'll take your word that it's easy to implement. Given that, if it's simple to do, and like you said gives us more states of the puzzle, I see no reason not to improve our scrambling programs.

 

[spdqbr]

3 weeks later...

A series of circumstances involving:
a) A room full of trampolines
b) An artificial mountain
c) A realization that CCT has done most of the hard work for me

Have all converged in such a way that I could finally finish coding the cube stats program. (The first two left me too battered and bruised to do anything else, while the third made me stop staring at my megaminx with a sense of dread.)

The code I used is all jarred up and attached to the post (accessible through winzip, 7zip, or any other zip program you like). If you just want to run the same test I did, drop to a command line and type
java -jar CubeStats.zip

I have also included all of the source code which anyone is free to use and free to modify (and obligated to tell me of mistakes ). Stefan, feel free to add this to your code repository if you like. I have not thoroughly tested most of the scramble tracking algs. They were ripped out of CCT and slightly modified. (Thanks CCT!)

I have tried to make everything extensible enough to accommodate any other puzzles or scramble generators people would like to throw at it, but I'm sure there's plenty I missed.

The biggest problem I see currently is that with even numbered cubes or generally puzzles without centres, the scrambles look artificially better than they are. This is because for puzzles with centres we can be sure to orient the puzzle before checking the scramble. I thought of defining orientation by a single corner, but I'm not sure how effective this would be. I'm also too lazy to do it right now.

I have also added the option to use the Mersenne Twister for generating scrambles, though I haven't done much testing with it so far. A cursory examination leads me to believe that the MT alg is actually worse for quickly producing random scrambles, but that's without any in depth analysis.

Last but not least, here is the output I got from executing the standard CubeStats.zip as is:

3x3x3 - 100000 trials 
20		443.1620148755661
25		211.50820611587486
30		147.651557995157
35		110.43133676349672
40		116.5568456069386
45		125.9131939241523
50		125.83197690233523
55		115.44001564684383

4x4x4 - 100000 trials 
40		119.66390614877406
45		119.06296470866742
50		128.85403943323186
55		124.14081765759262
60		123.39170573210444
65		117.62148576277836
70		121.84658921918096
75		115.44957868000778

WCA Megaminx Scrambler - 100000 trials 
70		720.509295011079
80		511.63070040095505
90		370.6176689892984
100		270.74721971613343
110		197.88530030760757
120		152.74470563906405
130		125.54038855738122
140		107.02766036586652
150		96.1607554902514
160		92.65781383996249
170		90.6069948685559
180		90.85247570597147

Megaminx Non-WCA - 100000 trials 
70		567.6484820433203
80		371.2118931711233
90		251.11136711335263
100		176.45536596516814
110		129.568316248223
120		106.91459055425659
130		99.10904699705459
140		90.8678258737009
150		85.95969286692603
160		86.15861223825169
170		89.65422729883069
180		87.531548963407

Megaminx Old Style - 100000 trials 
70		134.21530108955525
80		106.06835615725058
90		87.26749114317384
100		88.48152263108986
110		89.10289513129383
120		87.06746563398393
130		89.68395593831148
140		88.02043479965928
150		86.79848940122729

 

[jfly]

a) A room full of trampolines

Boy, am I glad I subscribed to this thread. Sky High was totally awesome. It was great to see you last weekend!

c) A realization that CCT has done most of the hard work for me

 

[spdqbr]

Yup, it was a blast. I totally screwed up one of my fingers though, hopefully it'll stop hurting in time for Utah... You know, where the cool people are going

 

[xyzzy]

Dan Hayes' post on the speedsolving yahoo group (http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/41005)

Reproducing here for posterity, since Yahoo Groups is die. (Source: Internet Archive.)

I am NOT a statastician, but I do have a strong math background.  If
you notice any errors in my reasoning or methodology, please tell me.

After busting out the stats book and talking to some of the smart folk
at the xkcd message boards, I developed a rudimentary test for
comparing the effectiveness of scramblers. I have since conducted a
few experiments to compare the WCA megaminx scrambler and a scrambler
which behaves a little differently. (Also tested a standard 3x3x3
scrambler). I will explain the methodology first, so if you just want
the results, skip to the end.

The test I conducted was the simplest I could imagine, I applied
scrambles to the puzzle and kept track of how often each color landed
in each position.  The assumption:  Given a scramble algorithm
generator that generates an n move scrambling algorithms, if we take a
large number of solved puzzles and apply those algorithms, each
position should end up with each color a roughly equal number of times.

That is if an n move scramble from a generator truly approximates
random, all colors should have equal probability of showing up in all
locations.  Essentially this is a test for how flat the distribution
of colors over locations is.

Methodology:  Apply many scrambles to a cube and track how often each
color shows up in each position.  The standard deviation of this list
should tell us approximately how well the scrambles approximate true
random.
So a list would look like this for 10 scrambles on a cube:
Position | R O G B Y W
0        | 3 2 1 2 2 0
1        | 4 1 4 0 0 1
....
47       | 1 1 2 1 3 2

Ignore the position column and take the standard deviation of the
rest.  Centers are ignored as well since they are always the same
after scrambling.  On the megaminx, after a scramble was applied, the
puzzle was reoriented so that the same center color was on top and the
same was on the front face every time, this prevents puzzle rotations
skewing the results.

The expected standard deviations which are used as a baseline were NOT
calculated directly, as I could not figure out how.  Instead, they
were taken from an average of very long scramble algorithms which were
presumed to be random based on the data at hand.  This bugs me, so if
you can figure out how to directly calculate the expected stdDev,
please let me know.

On to the results:
Each of these cases is conducted with 1 million (10^6) trials.  Turns
is the number of non-puzzle rotating turns (except in the WCA megaminx
scrambler case, where puzzle rotations are counted).  StdDev is the
observed standard deviation.  Expected std dev is the standard
deviation which a truly random scramble generator should give. 
Confidence is the % confidence that this scrambler / length
combination approximates true random in the long term (essentially the
ratio of expected stdDev to observed.)  The standard practice I
believe is to take 95% confidence as the threshold for rejecting the
null hypotheses that sigma = s.  Thus if the confidence is less than
95%, by convention we can assume the scramble is not truly random.  In
practice, I would be willing to go as low as 93% or so.  The custom
3x3x3 and megaminx scramblers are the same as from the excel sheet
generator I posted a few days ago.

3x3x3 Cube, generic scrambler (avoids redundant turns, etc):
Turns | Std Dev | Expected Std Dev | Confidence
  1   |264953.60|     360          |  0.1%
  10  | 26320.07|     360          |  1.4%
  20  |  4274.47|     360          |  8.4%
  30  |   794.28|     360          | 45.3%
  35  |   514.75|     360          | 69.9%
  40  |   387.39|     360          | 92.9%
  45  |   347.40|     360          | 96.5%
  50  |   341.04|     360          | 94.7%
  75  |   350.58|     360          | 97.4%
 100  |   372.78|     360          | 96.6%
 500  |   347.09|     360          | 96.4%
1000  |   355.14|     360          | 98.7%

When a range for the length was used, the results were pretty
miserable.  I have been converted to an advocate for fixed length
scrambles.  when allowed to range from 30-40 moves, the CI was only 73.1%!

Based on these results my scrambles for practice will always be at
least 40 moves, and I'd rather use 45.


On to the megaminx.  It should be noted that the entirety of the
testing I did was in Java, and as such I had to modify the code from
the wca scrambler to java code.  I'm not 100% familiar with
javascript, but I do think that my conversion is accurate.  All code
used in this project is available on request.

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%

This is the heart of why I'm posting.  Based on this analysis the
official wca scrambler does not appear to be random until you reach
250 turns or more.  And the official scramble length of 70 turns gives
a feeble 1.7% confidence of randomness.

Now lets examine a different scramble generator the big difference is
that puzzle rotations are randomly interspersed and do not count
against the move count.  So a 10 move scramble may in fact be 15 moves
long.  As such, for a scramble of length n, there will be at least
n/10 more non-puzzle rotating moves than in an n move wca scramble. 
So an 80 move scramble here should only be compared to 88 or more move
wca scrambles.  Also 1/5 twists are allowed as opposed to just 2/5:

Turns | Std Dev | Expected Std Dev | Confidence
  10  | 91955.36|     279          | 0.3%
  50  |  5529.65|     279          | 5.0%
  70  |  1572.39|     279          | 17.8%
 100  |   380.54|     279          | 73.4%
 110  |   315.88|     279          | 88.4%
 115  |   287.75|     279          | 97.0%
 120  |   291.12|     279          | 95.9%
 125  |   279.61|     279          | 99.8%
 150  |   273.86|     279          | 98.1%
 200  |   282.68|     279          | 98.8%
 500  |   279.16|     279          |100.0%
1000  |   286.71|     279          | 97.4%

Clearly this converges toward random much more quickly, in fact around
twice as quickly.  I would put 115 moves as the bare minimum and will
probably henceforth use 125 moves myself.  I suspect the difference
comes from having so many extra puzzle rotations, not from having 1/5
and 2/5 turns included, though I have not yet tested this.

There you have it.  I will probably be posting this to the wca boards
sometime soon, as the megaminx situation concerns me a bit.

I will consider in the future analyzing the wca scramble lengths /
generators for the 4x4x4 and 5x5x5 cubes as well, but writing the
scramble tracking code is mind numbingly tedious and my wife is
complaining about me spending too much time on this ;) .  As I
mentioned, if you are better at stats than I am (not hard to do) and
there is any error in my assumptions or methodology, please LET ME
KNOW!  All source code used is available upon request.

I'm going to bed now, cheers.
-Daniel