Inaccuracy of scrambling using a random sequence of moves

[Cubemir]

Hello!

Recently I got interested in such a question: if we scramble a puzzle using random sequence of moves, do we really get an "absolutely random" position? How many moves should we perform, before we scramble puzzle really well?

Obviously, the ideal scramble should give the discrete uniform distribution for all puzzle positions.
So, if we know, for example, that God's Number for a puzzle is N, what distribution do we get after N random moves, after N+5 moves, etc?

I did a little experiment for 2x2x2 puzzle, and the results surprised me a bit.

God's number in FTM for 2x2 cube is 11. If we use 11moves-scramble, we would get solved cube 30 times more likely, than any average position. The distribution is very different from the uniform one.





Another type of sorting positions:






Ok.. So what if we use 14 moves scramble? Even here the mistake is quite significant for more than 1/3 of positions.





20-moves scrambles. Inaccuracy begins to decrease, but it is still present:




For calculations I used random number generator of my home laptop. The program is quite simple: it scrambled the cube tens of billions of times and collected statistics.

[Dacuba]

Someone clever answered to a similar question that in fact a random sequence of moves increases the chance of some states while decreasing others. So it's not accurate and it is better to use a random state generator and an inverse solution for the scramble.

[Zarxrax]

What happens if you use a random number of moves? For instance, between 10-14 moves.

[Owen]

How long did it take for the computer to collect that data?

[Dacuba]

Does it actually make any difference if you use a speedsolving method? I could imagine the difference could be huge for FMC, but not really for a random CFOP user

[Cubemir]

What happens if you use a random number of moves? For instance, between 10-14 moves.

I think we will get some kind of average histogram for histograms for 10-14 moves. Because in all cases the same positions have more probability to appear, with slight differences. The most common position for any length of scramble - solved state. Further there are positions that can be solved in one or two moves and so on.

How long did it take for the computer to collect that data?

For 3 histograms it took about 12 hours.

[Lucas Garron]

Awesome; this will be a useful link for showing people that using random moves is not good enough at all.

How did you simulate this? Did you allow repeated moves on the same axis? (Makes it much easier, but doesn't match existing scramblers)

[CarlBrannen]

Intuitively, I guess the deviation from randomness is due to the relatively high probability that consecutive (or near consecutive) random moves will cancel each other out. So there's a higher probability that a given cubie is left unaltered by a sequence of random moves than by a random position.

Besides choosing a random final state, you could also see what effect increasing the random number sequence would have.

I'm assuming that the random series includes double turns (i.e. LL) as just one move. Otherwise one problem would be that a sequence of 11 random moves would always be an odd permutation on the corners and edges.

[Chrisalead]

One big problem with monte carlo simulations is that the random number generator algorithm to use must be really good. So if you just used the standard one, then all your result may be biased. You should try with the Mersenne Twister Pseudo-Random Number Generator.
http://en.wikipedia.org/wiki/Mersenne_Twister
and for the c++ source code : http://www.bedaux.net/mtrand/

[Lucas Garron]

I'm assuming that the random series includes double turns (i.e. LL) as just one move. Otherwise one problem would be that a sequence of 11 random moves would always be an odd permutation on the corners and edges.

I presume so, else 11 moves would not be enough.

But yes, if you use quarter turns, you *do* need to randomize parity. Note that the eventual distribution would be the same for QTM and HTM (all 3,674,160 the same). This could be considered intuitive, but it's *almost* non-trivial.

One big problem with monte carlo simulations is that the random number generator algorithm to use must be really good. So if you just used the standard one, then all your result may be biased. You should try with the Mersenne Twister Pseudo-Random Number Generator.

What are your reasons for suggesting that Mersenne Twister? It's alright if your answer is "I heard it's good", because that's the same reason I would use.

In any case, I hope he didn't need a random number generator. See Stefan's analyzer.