WCA Scramble Algorithm

[Fishcake]

I tried searching for it in Google and in this forum before posting this thread, but no luck.
My question is, what is the algorithm that is used for generating scrambles in WCA competitions/Cube Explorer?
Is it just some random sequence of maneuvers, or some other sort of complex algorithm to avoid easy scrambles or something?
I need to know this because I'm going to make a Rubik's cube scrambler and timer for my PSP
to improve my programming skills and so that I can practice cubing anywhere (damn, I have no life ).

And hopefully, I'm posting in the correct category.

 

[qqwref]

For the 3x3, it chooses a random position and then finds a fast way to create that position using the advanced Kociemba algorithm. (This is really hard to program, so I suggest just using 25 random moves.)

 

[Johannes91]

Kociemba algorithm. (This is really hard to program, so I suggest just using 25 random moves.)

I don't think it's hard at all, especially if efficiency isn't too important and solutions a few moves longer than 20 are good enough.

 

[spdqbr]

For the 3x3, it chooses a random position and then finds a fast way to create that position using the advanced Kociemba algorithm. (This is really hard to program, so I suggest just using 25 random moves.)

If it's important to you to have an "even" pool of scrambles to choose from, an analysis I ran some time ago suggested that 40 moves (HTM) is about as low as you can go for #of random scrambles to get this. 25 moves only generates a truly random position with about 20% confidence.

 

[Lucas Garron]

If it's important to you to have an "even" pool of scrambles to choose from, an analysis I ran some time ago suggested that 40 moves (HTM) is about as low as you can go for #of random scrambles to get this. 25 moves only generates a truly random position with about 20% confidence.

So 1/5 of the time it'll be truly random?

(Really, what do you mean?)

 

[d4m4s74]

If it's important to you to have an "even" pool of scrambles to choose from, an analysis I ran some time ago suggested that 40 moves (HTM) is about as low as you can go for #of random scrambles to get this. 25 moves only generates a truly random position with about 20% confidence.

So 1/5 of the time it'll be truly random?

(Really, what do you mean?)

I think he means certain positions will come up more often then others if you scramble useing 25 moves

 

[brunson]

This has been discussed before. Any sequence of random moves will tend towards a set of scrambles a certain distance away from solved (0htm) while tending away from a "maximal" scramble (20htm-23htm). Adding more random moves doesn't push you farther away from solved, in fact it would statistically increase the likelihood of ending up in the area of "pretty much scrambled".

Randomly choosing a cube state guarantees an identical probability of any state. The chance of generating a solved cube is exactly the same as generating a superflip or any other state.

 

[Cride5]

This has been discussed before. Any sequence of random moves will tend towards a set of scrambles a certain distance away from solved (0htm) while tending away from a "maximal" scramble (20htm-23htm). Adding more random moves doesn't push you farther away from solved, in fact it would statistically increase the likelihood of ending up in the area of "pretty much scrambled".

Randomly choosing a cube state guarantees an identical probability of any state. The chance of generating a solved cube is exactly the same as generating a superflip or any other state.

I've noticed this phenomenon with edge orientation cases in ZZ. Using a sequence of random moves to scramble usually results in a bias towards a lower number of bad (misoriented) edges. Although 4 and 8 bad edges should be equally probable, I seem to get more 4-edge than 8-edge cases (similarly for 2 and 10 edge cases).

Does anyone know which programs use a proper WCA-style scramble, rather than just a random sequence of moves?

 

[spdqbr]

If it's important to you to have an "even" pool of scrambles to choose from, an analysis I ran some time ago suggested that 40 moves (HTM) is about as low as you can go for #of random scrambles to get this. 25 moves only generates a truly random position with about 20% confidence.

So 1/5 of the time it'll be truly random?

(Really, what do you mean?)

An explanation of the analysis can be found here.

 

[fundash]

I need to know this because I'm going to make a Rubik's cube scrambler and timer for my PSP

Can You plese PM me that program (i've been searching FOREVER for a timer PSP)

It doesn't matter what firmware it's meant for, i have a pandora battery and so i have hybrid 1.50/5.xx M33 firmware (yes i know what homebrew is)

 

[JBCM627]

If it's important to you to have an "even" pool of scrambles to choose from, an analysis I ran some time ago suggested that 40 moves (HTM) is about as low as you can go for #of random scrambles to get this. 25 moves only generates a truly random position with about 20% confidence.

So 1/5 of the time it'll be truly random?

(Really, what do you mean?)

An explanation of the analysis can be found here.

That is an interesting analysis, and very ingenious way of testing the scrambles. I haven't read through all the replies yet, but I am assuming the experimental St Dev column has an error, since you only performed the test on 10^6 scrambles. Do you know what this error would be?

I'd also be curious to see this done for big cube scrambles using a different scramble algorithm: misalign each break on an axis, switch to another, and repeat. Normalizing these scrambles by the number of HTM moves performed, it would be nice to see how much more (or less) efficiently this method scrambles than the WCA scrambler for big cubes. It would also be nice to compare the WCA algorithm to one that randomly misaligns breaks (without backtracking) (note that the WCA scrambler doesn't actually do this - it has a bias in that it tends to perform turns on the same axis more often than the aforementioned alg would).

 

[Fishcake]

I need to know this because I'm going to make a Rubik's cube scrambler and timer for my PSP

Can You plese PM me that program (i've been searching FOREVER for a timer PSP)

It doesn't matter what firmware it's meant for, i have a pandora battery and so i have hybrid 1.50/5.xx M33 firmware (yes i know what homebrew is)

I'll be happy to share this program when it's done

 

[Sakarie]

Just to add something to the CCT discussion:
It doesn't make a new random state every time, since I've had the same scramble twice. Actually, _I_ haven't, but I have gotten a very good bld-scramble from this forum _and_ another forum, which are exactly the same! And both givers says that they have gotten it straight from CCT.

 

[TomZ]

It doesn't make a new random state every time, since I've had the same scramble twice.

The WCA scrambler can also come up with the same scramble twice, the previous picks do not affect the next ones.

 

[Stefan]

I've noticed this phenomenon with edge orientation cases in ZZ. Using a sequence of random moves to scramble usually results in a bias towards a lower number of bad (misoriented) edges. Although 4 and 8 bad edges should be equally probable, I seem to get more 4-edge than 8-edge cases (similarly for 2 and 10 edge cases).

You're right. From my 3x3 scramble analyzer:

scramble length: 25
  probability for  0 flipped edges: 0.00134544044252748545
  probability for  2 flipped edges: 0.03673557940805194881
  probability for  4 flipped edges: 0.25615535099536977496
  probability for  6 flipped edges: 0.44489037738355416974
  probability for  8 flipped edges: 0.23149165891662189241
  probability for 10 flipped edges: 0.02895679378114915976
  probability for 12 flipped edges: 0.00042479907272556887
  state 2047 is least probable with 0.00042479907272556887
  state    0 is most  probable with 0.00134544044252748545

 

[rokicki]

An explanation of the analysis can be found here.

That analysis could be done more precisely. For one thing, instead of 48x6 variables, there are *really* only 9 distinct variables. Next, it is pretty easy to generate a recurrence (a 9x9 matrix really) that lets you get exact probabilities to any scramble length (even trillions of moves). Finally, if you want to introduce the restrictions on the scramble reflecting no consecutive face turns and each slice pair must be in a particular order, this just multiplies the state space by 6 (to 54 variables, with a 54x54 matrix), which is hardly more difficult.

I've also done this analysis showing the probability of being in any of the different cosets of the Kociemba group, and here too it shows *significant* skewing, with 25 being an absolutely terrible scramble length and 40 being in some sense a minimum scramble length. If anyone is interested, I'd be happy to dig that data out of the archives. (This was an exact analysis of a situation with 138M unique state variables.)

Interestingly, in the quarter turn metric, things were not nearly so dire; in the quarter turn metric, the distribution was incredibly smooth after many fewer moves. Indeed, I think that the distribution was actually smoother for 25 QTM moves than for 25 HTM moves (except for the parity of course). I'll have to verify this of course but this is what I recall.

 

[JBCM627]

An explanation of the analysis can be found here.

That analysis could be done more precisely. For one thing, instead of 48x6 variables, there are *really* only 9 distinct variables. Next, it is pretty easy to generate a recurrence (a 9x9 matrix really) that lets you get exact probabilities to any scramble length (even trillions of moves).

What do you mean by this, as in, where does that number come from?

Interestingly, in the quarter turn metric, things were not nearly so dire; in the quarter turn metric, the distribution was incredibly smooth after many fewer moves. Indeed, I think that the distribution was actually smoother for 25 QTM moves than for 25 HTM moves (except for the parity of course). I'll have to verify this of course but this is what I recall.

Would this hold true for big cubes too? If so, the WCA scrambler could be redone a bit

 

[rokicki]

What do you mean by this, as in, where does that number come from?

Symmetry. Consider the corner facelet URF (the Up facelet of the
URF cubie). It can be of one of six colors, but by symmetry, the
chance of it being F is the same as R, the chance of it being B is
the same as L. So that's a total of four variables there.

Every corner facelet will have the same set of variables all with the
same values. So no more variables from the corners.

For the edgies, you get by the corresponding argument five more
variables.

Another way to say it is, there are 48x6 variables, but only 9 (or fewer)
distinct values at any given time.

Indeed, you can reduce the 9 down to 7 by the algebraic identity
that the sum of all the probabilities must be one.

Would this hold true for big cubes too? If so, the WCA scrambler could be redone a bit

It's hard to say, and maybe worth the analysis!

I've checked my numbers, and I'm preparing a longer report, but I can say
with pretty good confidence that 30 random QTM moves scrambles the cube better than 30 random FTM moves, by almost any metric (except of course in the QTM case you need to flip a coin on whether to add another move
or not to change the parity; doing the same to FTM doesn't significantly
improve the distribution.) So offhand, yes, I'd say your big cube scrambling
algorithms should use only quarter turns and never half turns.

It's kind of counterintuitive because a half turn is "further", it requires two
quarter turns, but the statistics are pretty convincing.

I think I'll be able to do an exhaustive analysis on a 2x2x2 to prove this for
certain.

 

[rokicki]

This will take some time to write up reasonably well, but here's a simple thought experiment.

Consider the group (U,F2,R2,D,B2,L2) and the obvious ten generators (half turn metric). The size of this group is about 20B; cosets of this group partition the cube space into about 2B distinct sets.

Now, consider a random sequence of length n of moves taken from the normal 18 generators in the half turn metric. Ten of those generators are in the group above, so the chance that *all* the generators lie within the group is (10/18)^n. This is a lower bound on the probability that after n moves, the resulting position is in the group above.

If we intend that the position be "random" that means the probability it lie in the group above needs to be roughly 1/2B (since there are 2B distinct sets all with the same size). So we need that (10/18)^n <= 1/2B. (Note that this is only a lower bound, because there are sequences that exit the group and then re-enter it). Solving this, we find that n >= 36.4. Restated, with fewer than 36 moves, the chances that the position to be solved lies within the above group is too high.

For the case of 25, the chances that the position lies within the group is about 1 in 2.4M, which is nearly a thousand times higher than it should be.

On the other hand, experimentally, random QTM moves do much better at leaving the group since only 4 of the 12 QTM moves remain in the group.

 

[Johannes91]

Consider the group (U,F2,R2,D,B2,L2) and the obvious ten generators (half turn metric). The size of this group is about 20B; cosets of this group partition the cube space into about 2B distinct sets.

Now, consider a random sequence of length n of moves taken from the normal 18 generators in the half turn metric. Ten of those generators are in the group above, so the chance that *all* the generators lie within the group is (10/18)^n.

I posted a similar calculation a couple of years ago in the yahoo group, and Chris pointed out that it's not exactly correct because the random moves aren't independent.

The chance is 10/18 only for the very first move. After that, it depends on previous moves; if they are F2 U, the probability is 7/15, if U D, 4/12, if U F2, 9/15, and if F2 B2, then it's 8/12. I made a finite state machine to get exact numbers for different scramble lengths: http://codepad.org/dR6uOWtG. For 25 moves, the chance is about 1 in 15.8M, so a bit better than what you got, but still much too big.

I used a C scrambler to test that the state machine works correctly, and the results are fairly close, but not quite: from 2^34 25-move scrambles, 1333 stayed in the group, which is about 1 in 12.9M. Could be because the built-in PRNG sucks or because the sample is too small. Or maybe I made a mistake.