Megaminx Scrambler

[AvGalen]

I am probably one of very few people that has actually used the old notation for scrambles. It basically meant that 1 person that knew how that notation worked scrambled all megaminxes during a competition because nobody else could. It also took me minutes to perform and only about half of the time I got it right.

With the new method everyone can help scrambling megaminx resulting in more competitors during tournaments, less burden on 1 scrambler and most importantly competitors actually have to solve the same scramble because it is so easy to perform it correct. (I pop megaminxes more often than I make scrambling mistakes). With the increased interest has come increased solving speed and I think we are getting to the point where we could change the format of megaminx to be average of 5 (with a possible cut-off time to prevent beginners to take to much time) much like 5x5x5.

For me the most important things about any scramble is that it is
1) "random enough"
2) the same for all competitors

Getting a perfectly random stated generated scramble with an optimal generated scramble-string would be ideal for every puzzle, but it isn't going to happen for megaminx. The current method Just Works (tm).

The thing I am most interested in are the exclusive double turns. They seem to reduce randomness of scrambles (possible number of positions) without a good need for that. The only sources I could find about this choice are the following two quotes and they are both not very scientific (doesn't make them less true though). The first only mentions a belief without any further explanation, the second takes the extreme of only 10 moves in the example (with only one double turn). I have tested the following:
1) Perform the scramble as stated, alternating y and y' rotations at the end of each line
2) Perform the scramble as stated, alternating y and y' rotations at the end of each line but also alternating between single and double turns (a++b++c++d++e++f++g++h++ becomes a++b++c+d+e++f++g+h+)
The first had one pair build after the entire scramble, the second didn't have any pairs build at all. Both looked like they had no solved corners or edges at all. Both had 3 faces where 1 cross-edge was attached, but not solved (like FRB D would do to the D-face on a cube

I realise that this isn't a good scientific analysis, but for me it is Good Enough (another tm). I would like to know in more detail why Stephan thinks exclusive double turns are a good idea. Changing the scrambler to include quarterturns would greatly increase the amount of possible results (from 2^70 to 4^70 or 10^42 if my math is not mistaken not taking rotations into account) and didn't significantly increase the difficulty/accurarcy/time of scrambling.

The two quotes I mentioned earlier:

Notice that "++" means two-fifth turns clockwise (in the direction of the arrow) and "--" means two-fifth turns counterclockwise (against the direction of the arrow). It's intentional that there are only two-fifth turns and no one-fifth turns, I believe this improves the scramble quality.

Now an improvement...

I thought I use many more "two fifth" turns than "one fifth" turns when I scramble for practice, and I just checked it and it turns out I do 2/5 turns *exclusively*. And they look better, too. Try just the first line of the above scramble:
R- D- R++ D+ R+ D- R- D- R+ D-

It leaves a large part of the megaminx untouched. Now undo that and instead do:
R-- D-- R++ D++ R++ D-- R-- D-- R++ D--

That's the same but all 1/5 turns turned into 2/5 turns. It has effects all around the megaminx. I then tried this scramble:

R++ D++ R-- D++ R++ D-- R++ D-- R-- D++
R++ D++ R++ D-- R++ D++ R-- D-- R-- D--
R++ D-- R++ D++ R++ D++ R-- D-- R-- D++
R-- D++ R++ D++ R++ D++ R-- D-- R++ D--
R-- D-- R-- D-- R++ D-- R-- D++ R-- D--
R-- D++ R++ D-- R++ D++ R-- D++ R++ D++
R++ D++ R++ D-- R++ D++ R-- D++ R-- D++
R++ D-- R-- D-- R++ D-- R-- D-- R-- D--
R++ D++ R++ D++ R-- D++ R++ D-- R++ D--
R-- D-- R++ D++ R++ D-- R++ D++ R++ D++

After the first sixty moves, there was not a single unbroken pair left.

 

[Stefan]

Arnaud, if I remember correctly that first quote of mine was a result of the second, particularly the ending part of that one where I was delighted that sixty 2/5 turns had broken up all pairs. I think with mixed 1/5 and 2/5 I usually had more pairs or even unscrambled areas left at this point, presumably because 1/5 turns didn't "get me around" much. But it wasn't a thorough analysis and I don't have statistics to support it.

I just adapted my center-analysis to compare only2/5, only1/5 and mixed. Interestingly, only2/5 and only1/5 perform exactly the same in this respect. And mixed performs much better, which is why I show the results of not 70 but only 15 moves scrambling, that's shortly before mixed flatlines (when rounding the results like I do).

only2/5:

          DLB   DLF   DRB   URF   ULF   B     F     U     URB   DRF   ULB   D       min   max    stdDev sum
     pink 10.236 10.812 9.302 6.506 6.006 9.668 7.181 4.749 5.933 10.599 6.250 12.759   4.749-12.759  2.419  100.0
    blue2 10.812 10.236 9.302 5.933 6.006 10.599 6.250 4.749 6.506 9.668 7.181 12.759   4.749-12.759  2.419  100.0
   orange 9.302 9.302 3.784 6.006 14.160 5.713 11.359 12.366 6.006 5.713 11.359 4.932   3.784-14.160  3.256  100.0
   purple 6.506 5.933 6.006 10.236 9.302 7.181 9.668 12.759 10.812 6.250 10.599 4.749   4.749-12.759  2.419  100.0
turquoise 6.006 6.006 14.160 9.302 3.784 11.359 5.713 4.932 9.302 11.359 5.713 12.366   3.784-14.160  3.256  100.0
   green2 9.668 10.599 5.713 7.181 11.359 6.470 10.052 8.682 6.250 7.974 8.545 7.507   5.713-11.359  1.732  100.0
    green 7.181 6.250 11.359 9.668 5.713 10.052 6.470 7.507 10.599 8.545 7.974 8.682   5.713-11.359  1.732  100.0
    white 4.749 4.749 12.366 12.759 4.932 8.682 7.507 9.302 12.759 8.682 7.507 6.006   4.749-12.759  2.896  100.0
     blue 5.933 6.506 6.006 10.812 9.302 6.250 10.599 12.759 10.236 7.181 9.668 4.749   4.749-12.759  2.419  100.0
      red 10.599 9.668 5.713 6.250 11.359 7.974 8.545 8.682 7.181 6.470 10.052 7.507   5.713-11.359  1.732  100.0
    brown 6.250 7.181 11.359 10.599 5.713 8.545 7.974 7.507 9.668 10.052 6.470 8.682   5.713-11.359  1.732  100.0
   yellow 12.759 12.759 4.932 4.749 12.366 7.507 8.682 6.006 4.749 7.507 8.682 9.302   4.749-12.759  2.896  100.0

only1/5:

          DLB   DLF   DRB   URF   ULF   B     F     U     URB   DRF   ULB   D       min   max    stdDev sum
     pink 6.470 7.974 5.713 10.052 11.359 10.599 6.250 7.507 8.545 9.668 7.181 8.682   5.713-11.359  1.732  100.0
    blue2 7.974 6.470 5.713 8.545 11.359 9.668 7.181 7.507 10.052 10.599 6.250 8.682   5.713-11.359  1.732  100.0
   orange 5.713 5.713 3.784 11.359 14.160 9.302 6.006 4.932 11.359 9.302 6.006 12.366   3.784-14.160  3.256  100.0
   purple 10.052 8.545 11.359 6.470 5.713 6.250 10.599 8.682 7.974 7.181 9.668 7.507   5.713-11.359  1.732  100.0
turquoise 11.359 11.359 14.160 5.713 3.784 6.006 9.302 12.366 5.713 6.006 9.302 4.932   3.784-14.160  3.256  100.0
   green2 10.599 9.668 9.302 6.250 6.006 10.236 6.506 12.759 7.181 10.812 5.933 4.749   4.749-12.759  2.419  100.0
    green 6.250 7.181 6.006 10.599 9.302 6.506 10.236 4.749 9.668 5.933 10.812 12.759   4.749-12.759  2.419  100.0
    white 7.507 7.507 4.932 8.682 12.366 12.759 4.749 9.302 8.682 12.759 4.749 6.006   4.749-12.759  2.896  100.0
     blue 8.545 10.052 11.359 7.974 5.713 7.181 9.668 8.682 6.470 6.250 10.599 7.507   5.713-11.359  1.732  100.0
      red 9.668 10.599 9.302 7.181 6.006 10.812 5.933 12.759 6.250 10.236 6.506 4.749   4.749-12.759  2.419  100.0
    brown 7.181 6.250 6.006 9.668 9.302 5.933 10.812 4.749 10.599 6.506 10.236 12.759   4.749-12.759  2.419  100.0
   yellow 8.682 8.682 12.366 7.507 4.932 4.749 12.759 6.006 7.507 4.749 12.759 9.302   4.749-12.759  2.896  100.0

mixed:

          DLB   DLF   DRB   URF   ULF   B     F     U     URB   DRF   ULB   D       min   max    stdDev sum
     pink 8.334 8.334 8.332 8.333 8.334 8.333 8.334 8.334 8.333 8.333 8.334 8.334   8.332-8.334  0.001  100.0
    blue2 8.334 8.334 8.332 8.333 8.334 8.333 8.334 8.334 8.333 8.333 8.334 8.334   8.332-8.334  0.001  100.0
   orange 8.332 8.332 8.338 8.334 8.333 8.332 8.334 8.332 8.334 8.332 8.334 8.332   8.332-8.338  0.002  100.0
   purple 8.333 8.333 8.334 8.334 8.332 8.334 8.333 8.334 8.334 8.334 8.333 8.334   8.332-8.334  0.001  100.0
turquoise 8.334 8.334 8.333 8.332 8.338 8.334 8.332 8.332 8.332 8.334 8.332 8.332   8.332-8.338  0.002  100.0
   green2 8.333 8.333 8.332 8.334 8.334 8.334 8.333 8.334 8.334 8.334 8.333 8.334   8.332-8.334  0.001  100.0
    green 8.334 8.334 8.334 8.333 8.332 8.333 8.334 8.334 8.333 8.333 8.334 8.334   8.332-8.334  0.001  100.0
    white 8.334 8.334 8.332 8.334 8.332 8.334 8.334 8.332 8.334 8.334 8.334 8.334   8.332-8.334  0.001  100.0
     blue 8.333 8.333 8.334 8.334 8.332 8.334 8.333 8.334 8.334 8.334 8.333 8.334   8.332-8.334  0.001  100.0
      red 8.333 8.333 8.332 8.334 8.334 8.334 8.333 8.334 8.334 8.334 8.333 8.334   8.332-8.334  0.001  100.0
    brown 8.334 8.334 8.334 8.333 8.332 8.333 8.334 8.334 8.333 8.333 8.334 8.334   8.332-8.334  0.001  100.0
   yellow 8.334 8.334 8.332 8.334 8.332 8.334 8.334 8.334 8.334 8.334 8.334 8.332   8.332-8.334  0.001  100.0

The program:

Spoiler

#-----------------------------------------------------------------------------
# This program analyses the WCA megaminx scrambler. See also:
# http://www.stefan-pochmann.info/spocc/other_stuff/tools/scramble_megaminx/
#
# So far it only computes the probability of where each center ends up. The
# results are shown on the above-mentioned page.
#
# Implementation:
#   1) Configure the scramble length and specify the puzzle (pieces+moves).
#   2) Compute the probability of center C ending up at position P after
#      M moves as $probability{C}{P}{M}. This is done using dynamic programming.
#   3) Evaluate the results.
#
# Note that this is *not* an analysis of a limited number of scrambles, for
# example a million scrambles. This is an analysis of *all* 2^70 possible
# scrambles.
#-----------------------------------------------------------------------------

use strict;

#--- Configure the scramble length
my $scrambleLength = 15;

#--- Specify where the centers start
my %origin = (
  white     => 'U',
  green     => 'F',
  turquoise => 'ULF',
  brown     => 'ULB',
  blue      => 'URB',
  purple    => 'URF',
  yellow    => 'D',
  green2    => 'B',
  pink      => 'DLB',
  blue2     => 'DLF',
  red       => 'DRF',
  orange    => 'DRB'
);

#--- Specify the effects of the moves on the centers (list the cycles)
my %effects = (
  'D++' => 'F ULB URF ULF URB + B DLF DRB DLB DRF',
  'R++' => 'U DLB F ULB DLF + URF B DRF URB D',
  'D+' => 'F ULF ULB URB URF + B DLB DLF DRF DRB',
  'R+' => 'U ULB DLB DLF F + URF URB B D DRF',
);
@effects{'R-','R--','D-','D--'} = map { join ' ', reverse split } @effects{'R+','R++','D+','D++'};

#--- Initialize the center-position probabilities before scrambling
my %probability;
for my $center ( keys %origin ) {
  $probability{$center}{$origin{$center}}{0} = 1;
}

#--- Spread the love (the probabilities through moves)
for my $numberOfMoves ( 1..$scrambleLength ) {
  for my $center ( keys %origin ) {
    for my $positionBeforeMove ( values %origin ) {
#      my @moves = $numberOfMoves%2 ? ( 'R++', 'R--' ) : ( 'D++', 'D--' );
#      my @moves = $numberOfMoves%2 ? ( 'R+', 'R-' ) : ( 'D+', 'D-' );
      my @moves = $numberOfMoves%2 ? ( 'R+', 'R++', 'R--', 'R-' ) : ( 'D+', 'D++', 'D--', 'D-' );
      for my $move ( @moves ) {
        my $positionAfterMove = applyMove( $move, $positionBeforeMove );
        $probability{$center}{$positionAfterMove}{$numberOfMoves} +=
          $probability{$center}{$positionBeforeMove}{$numberOfMoves-1} / @moves;
      }
    }
  }
}

#--- Evaluate the center-position probabilities after scrambling
print "          ";
printf "%-6s", $_ foreach values %origin;
print "  min   max    stdDev sum\n";
for my $center ( keys %origin ) {
  printf "%9s ", $center;
  my ( $min, $max, $stdDev, $sum ) = ( 100, 0, 0, 0 );
  for my $position ( values %origin ) {
    my $p = 100 * $probability{$center}{$position}{$scrambleLength};
    printf "%.3f ", $p;
    $min = $p if $p < $min;
    $max = $p if $p > $max;
    $stdDev += ( $p - 100/12 ) ** 2; 
    $sum += $p;
  }
  printf "  %.3f-%.3f  %.3f  %.1f\n", $min, $max, sqrt( $stdDev / 12 ), $sum;
}



#--- Helper for applying a move
sub applyMove {
  my ( $move, $position ) = @_;
  my $effects = join ' + ', map { "$_ $_" } split / \+ /, $effects{$move};
  return $effects =~ /\b$position\b (\w+)/  ?  $1 : $position;
};

#--- Helper for debugging
sub show {
  use Data::Dumper;
  print Dumper( @_ );
};

Granted, this doesn't necessarily tell much about the scrambling results, but it's something I could do quickly so I just did.

 

[Stefan]

You can and apparently do think of the centers solely as a frame, a reference defining where all other pieces have to move to. But that's just one perspective.

You say "just one perspective" as if there are other meaningful ones from the context of speedsolving. There aren't. Nobody fast holds an edge/corner fixed and moves the centers and the rest of the pieces around it.

Actually I think most of them do that. Every time using the WCA scrambler. Which is what we're talking about here.

I just realized I had forgotten a main reason for implementing the center-analysis first: I pretty much need to do it anyway. Cause the scrambler does move them around. I could consider the centers fixed but then I'd need to keep track of which sides I can move next and that just seems to be a complicated and unnatural way to hide the center movements. Also, other scramblers might move centers as well and I want to build an analyzer where you can easily just describe any scrambling method and then the analyzer does the statistics. So that we can easily compare different scrambling methods statistically. I want it to be capable of covering the WCA scrambler so I need to be general and cover the center movements and treating all pieces (including centers) the same way looks like a good and natural way to implement that.

 

[AvGalen]

So based on your feeling and some handscrambling your conclusion is that only 2/5 is best because it moves pieces around more

But the first computer result indicates that 1/5 and 2/5 mixed is basically perfect (I would actually say too perfect. If I would get results like that I would think either "bug in code" or "there must be a logical explanation for this"). I might have some time tomorrow to look at the code but it depends on the number of questions my students will have for me as they have a big deadline coming up

 

[Stefan]

If I would get results like that I would think either "bug in code" or "there must be a logical explanation for this"

Well, I see two reasons:

1) Each value is spread to four different values rather than to just two. With every single move. So this alone spreads the probabilities much faster.
2) I haven't understood why only1/5 and only2/5 behave exactly the same (same values just on different places) but I imagine each has a pattern and the mixed scrambling has the advantage of being able to switch between the two patterns.

It's like driving twice as fast and being able to use shortcuts.

I did indeed have a bug in my program, btw, I specified the first cycle of D++ and D+ in the wrong direction. After fixing it I got the same results, though. Next I'll implement analyzing groups of pieces so I can find out where they move relative to each other, and the first test will be two centers. This should result in 60 outcomes and I'll test again with the false D++ specification, it should fail then.

 

[Pedro]

I've read the whole thread, and I'm not a mathematician (spelling?) but I'm interested in the discussion. (probably because I solve the megaminx)

From what I understood, we can generate "only" 2^70 (or 10^21) positions with the current scramble. So if we use 80 moves, we can get ~10^24 positions. Is it still that bad? I wouldn't mind doing an extra line of scrambling. Or maybe 2 or 3. (10^30 possible positions)


Arnaud, I think alternating between 1/5 and 2/5 turns would lead to many mistakes. The way it is now is pretty cool, because I can do it almost on auto-pilot, just reading - or + and turning accordingly.

If I had 2 megaminxes, I could try doing the same scramble twice and seeing if they match, and how long it takes. Anyone can do it?

EDIT
Forgot to say that I check sometimes the scramble on cct, and is correct.
Also, just did a scramble in 36.15. Of course it's with my own minx, which I know pretty well and can move fast and nice.
Solved in 1:38.22.

Then I did a scramble with 100 moves...in 46.78. Guess I messed up a little bit on the first one. Solved in 1:52.09 (yeah, I suck).
Solve didn't feel harder (mom talking to me makes it harder). Will do another one.

Scramble: 47.96
Solve: 1:39.31

 

[hawkmp4]

I've read the whole thread, and I'm not a mathematician (spelling?) but I'm interested in the discussion. (probably because I solve the megaminx)

From what I understood, we can generate "only" 2^70 (or 10^21) positions with the current scramble. So if we use 80 moves, we can get ~10^24 positions. Is it still that bad? I wouldn't mind doing an extra line of scrambling. Or maybe 2 or 3. (10^30 possible positions)


Arnaud, I think alternating between 1/5 and 2/5 turns would lead to many mistakes. The way it is now is pretty cool, because I can do it almost on auto-pilot, just reading - or + and turning accordingly.

If I had 2 megaminxes, I could try doing the same scramble twice and seeing if they match, and how long it takes. Anyone can do it?

EDIT
Forgot to say that I check sometimes the scramble on cct, and is correct.
Also, just did a scramble in 36.15. Of course it's with my own minx, which I know pretty well and can move fast and nice.
Solved in 1:38.22.

Then I did a scramble with 100 moves...in 46.78. Guess I messed up a little bit on the first one. Solved in 1:52.09 (yeah, I suck).
Solve didn't feel harder (mom talking to me makes it harder). Will do another one.

Scramble: 47.96
Solve: 1:39.31

2^70/10^68 = 1.180591621*10^−47
2^100/10^68 = 1.2676506*10^−38
Adding 3 more lines of scrambling still results in a tiny fraction of one percent of all the possible states. An insignificant gain really.
In fact...
We'd need to do ~230 twists to get all the possible states of the megaminx. Or, 23 lines of scrambling. And that's a lower bound- that assumes that every possible sequence generates a different state.
This is all assuming we could actually generate that many sequences. Currently we're limited by the PRNG of whatever language we're using for the scrambler program. Java, for example, only provides 48 random bits. In other words, it can provide only 2^48 different scrambles at most. So, the scrambling method is not what's holding us back. It's our random number generation.

 

[spdqbr]

*snip*
This is all assuming we could actually generate that many sequences. Currently we're limited by the PRNG of whatever language we're using for the scrambler program. Java, for example, only provides 48 random bits. In other words, it can provide only 2^48 different scrambles at most. So, the scrambling method is not what's holding us back. It's our random number generation.

This is not actually the case. If we were relying on the RNG to generate one of the possible states of the megaminx, and then finding an algorithm to generate that state, this would be true.

Since we are not generating random states, but a random sequence (ok, pseudo random) of moves we are not limited in this fashion. If we assume that all states achievable on the megaminx are achievable by use of R++, R--, D++, D--, Y and Y' then all states would be achievable with a scrambler that generates a sufficiently long sequence of moves.

Example, consider a 3x3 cube. We have 6 sides and 3 possible ways of turning each side. You could generate all possible states of a 3x3 using 2 dice if you roll them enough times (1st die chooses the side, second die chooses the direction of the turn 1-2 clockwise, 3-4 half turn, 5-6 anti-clockwise). So even though this pair of dice only has 36 possible outcomes (7 bits), and really only 18 because of the binning of the second die (6 bits), it is possible to generate all possible states of the cube if you roll them enough times.

 

[hawkmp4]

I'm very sleepy at the moment and largely incoherent, but I'll have a go at this and clarify in the morning if needed.
My understanding though, is that a RNG is not like a large pool of dice, but a large pool of results of previously rolled dice. We can use however many dice rolls results we want, and if we go over the total number of dice roll results in memory it 'wraps' around to the beginning of the sequence of dice roll results.
Is that correct?
If so, that would still mean that we could only generate a limited amount of unique sequences of dice roll results, since we have a limited number of dice roll results and must start 'reusing' the sequence at the beginning.

 

[AvGalen]

That is correct hawkmp4. RNG's start with a seed/randomise call that generates a random number in the case of Java that could apparently generate 2^48 random FIRST numbers. All numbers after that seem random, but are actually fixed based on the first number. You can test this by calling a random fucntion without seeding/randomising it first. There is enough information in this thread to learn more and otherwise you can surely google about it.

I don't care if our scrambler will never genereate all possible states because there are never going to be enough competitions to use all of them anyway. The important thing for me is if the scrambles are random enough (a 4x4x4 scramble with always OLL parity or a 3x3x3 scramble that never scrambles the white-green edge would obviously be bad) and if they are easy enough to perform quickly so competitors are very likely to get the same scramble

I disagree with Pedro that adding 1/5th turns would be a lot slower or more problematic to perform. Obviously I would prefer simpler scrambles but if the quality can be improved adding 1/5th turns would be worth it

Stefan, can you recommend a good, downloadable, free debugger for that code?

 

[spdqbr]

I hadn't thought of it from that angle.

However, even if we are only capable of generating 2^48 first numbers, we can pick any of those 2^48 first numbers to be our first twist. Further we can twist for as long or as short as we wish. You're not guaranteed to hit every state, but surely you could hit more than 2^48 states this way...

I agree it's not necessarily important have every state as a possible outcome, but a representative distribution would be nice.

I'm almost done recoding the scramble analyzer, just the tedious coding of the megaminx scramble tracking is left.. blech.

 

[Stefan]

a 4x4x4 scramble with always OLL parity [...] would obviously be bad

Indeed. I vote for one with always *no* OLL parity.

Stefan, can you recommend a good, downloadable, free debugger for that code?

I just debug using print statements. If you need Perl (it's written in that) and are using Windows, I recommend ActivePerl.

Further we can twist for as long or as short as we wish. You're not guaranteed to hit every state, but surely you could hit more than 2^48 states this way...

1. Not without an independent second source of randomness.
2. How are you going to determine for how long or short you twist?

I have tested the following:
1) Perform the scramble as stated, alternating y and y' rotations at the end of each line

If we assume that all states achievable on the megaminx are achievable by use of R++, R--, D++, D--, Y and Y'

Where's the Y/Y' still coming from? The WCA uses U/U'.

 

[Stefan]

I did indeed have a bug in my program, btw, I specified the first cycle of D++ and D+ in the wrong direction. After fixing it I got the same results, though. Next I'll implement analyzing groups of pieces so I can find out where they move relative to each other, and the first test will be two centers. This should result in 60 outcomes and I'll test again with the false D++ specification, it should fail then.

Bonus points if you see why it didn't fail so far and why I expect it to fail that planned test.

 

[Stefan]

Further we can twist for as long or as short as we wish. You're not guaranteed to hit every state, but surely you could hit more than 2^48 states this way...

1. Not without an independent second source of randomness.

Ok I somewhat take that back, I can see now how to do it. Would like to see how *you* would do it, though.

 

[hawkmp4]

If we allowed the scramble length to vary we could get more states. Say, generating scrambles with either 70 or 80 moves would double the number of unique scrambles we could get over a strictly 70 move scramble, if we're limited by a 48 bit PRNG.
EDIT: I take that back. We'd need to use one random bit to decide how long the scramble would be, cancelling any gain.

 

[spdqbr]

Further we can twist for as long or as short as we wish. You're not guaranteed to hit every state, but surely you could hit more than 2^48 states this way...

1. Not without an independent second source of randomness.

Ok I somewhat take that back, I can see now how to do it. Would like to see how *you* would do it, though.

While that seems a little high-handed, I'll I've it a go after work when I don't have to type on my phone...

 

[Stefan]

Ok I somewhat take that back, I can see now how to do it. Would like to see how *you* would do it, though.

While that seems a little high-handed

Just wanna see what you had in mind or come up with without being influenced by reading what I have in mind. (If you meant the marking of "you", that was not for "I don't think *you* can do it" but to clearly distinguish it from "one" which I thought it can be interpreted as in English. In other words, I just wanted to address you specifically).

I did that analysis of center pairs now. As expected, the result was 60 outcomes (also as expected, the wrong D+/D++ definition resulted in 132 outcomes). The results of 70 moves scrambling:

only2/5:
number of outcomes:  60
minimum probability: 1.66131
maximum probability: 1.67202
standard deviation:  0.00248
sum (sanity check):  100.00000

only1/5:
number of outcomes:  60
minimum probability: 1.66131
maximum probability: 1.67202
standard deviation:  0.00248
sum (sanity check):  100.00000

mixed:
number of outcomes:  60
minimum probability: 1.66667
maximum probability: 1.66667
standard deviation:  0.00000
sum (sanity check):  100.00000

I also just created a sourceforge project for this. I made it general, to cover both scramblers and scramble analyzers, and for all our puzzles. My program is in the subversion repository already. If someone wants to join (for example Daniel, so we don't lose your work again), let me know.

Project: http://sourceforge.net/projects/cubescrambles/
SVN trunk: http://cubescrambles.svn.sourceforge.net/viewvc/cubescrambles/trunk/
My current program: http://cubescrambles.svn.sourceforg...k/megaminx/analyzer.pl?revision=3&view=markup

Next are edges and corners...

 

[spdqbr]

Ah, the ambiguities of text on a page, gotta love it. Sorry for the mix up. I'll let you know what I come up with.

 

[spdqbr]

Ok, now that the house guest is gone I can do a little calculating.

The first thing that comes to mind when trying to get more scrambles out of a prng by varying length is to vary the length on a set schedule. Example:
Assume our PRNG has a period of 2^48-1 bits. We can define a wca compliant megaminx scramble in only 77 bits:
00101001111 -> R++ R++ D-- R++ D-- R++ R++ D-- D-- D-- U' and so on in this fashion.

The most obvious schedule, however impractical, is to increase the length of the scrambles by 11 bits every 2^48+1 moves (though changing length at any interval length which is not commensurate with the period of the PRNG would do). This can be done for quite a long time before all possible scrambles of all possible lengths have been exhausted. In fact, for every possible scramble length there are 2^48 new scrambles you can get from the prng. The scrambles get very long though, and it doesn't solve the real-world problem, because we're never going to make it through all of the first 2^48 scrambles to get to the extended ones.

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. This would be extremely easy in many languages available.

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.

Alternatively, we could just use the Mersenne Twister which should provide us with sufficient scrambles for as long as we need them.

 

[hawkmp4]

Using the variable length scrambles seems to be just a workaround to me, and besides, are there any other puzzles that don't have optimal scrambles that have variable length scrambles?
Also Dan, you saw for yourself with your analysis in the yahoo group topic that varying the scramble length lowered the confidence quite a bit. Is that something we should be taking into account, too?
How hard would implementing this Mersenne Twister algorithm into our scrambles for competition use? Also, can it be used easily in the myriad of online scramblers? I really don't know, I just think those are important questions. For example, if it wouldn't be hard to implement into cube explorer I think it would be a good idea too, but it may be a deterrent if it couldn't be used in javascript.
Just my thoughts. Off to bed now.