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.

 

[Cubemir]

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

Scrambles are in FTM (moves U2, R2, F2 are included) and do not allowed to repeat the face in next move.
BTW, if we allow such a repetition (for example U U', R2 R sequences), the distribution becomes much worse. If i'm not mistaken, the peak of the histogram increases 100 times or something...

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/

To check my RNG, I implemented the algorithm as follows: first is scramble of N random moves and the position is recorded in statistics, then the same RNG choose random position, and this position is recorded in other statistics. Thus, I compare two statistics (red line and green line) for the same RNG.

 

[Chrisalead]

@Lucas : Well simply read the "Advantages" section of the wiki article to understand why it is a good RNG. You can also read the original article describing the algorithm if you really want to be convinced.

 

[Stefan]

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.

"almost" sounds like it isn't non-trivial, but I'd say it is (I actually can't explain/prove it).

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

Hey, I was going to suggest that

Analyzing *all* scrambles exactly once instead of some billions randomly would be complete, exact, and much faster.

 

[Cubemir]

Analyzing *all* scrambles exactly once instead of some billions randomly would be complete, exact, and much faster.

Thank you, I understand the idea.
The number of possible scrambles, that have length 11, is relatively small. 9*6^10=544195584. So we need't use Monte Carlo method. OK, I'll try to do complete calculation for number of moves <=15.

 

[Stefan]

Thank you, I understand the idea.
The number of possible scrambles, that have length 11, is relatively small. 9*6^10=544195584. So we need't use Monte Carlo method. OK, I'll try to do complete calculation for number of moves <=15.

No, I don't think you understood what we meant, otherwise you wouldn't limit yourself to just 15. You can easily do all 20-move scrambles as well. Or all 30-move scrambles. Or all 1000-move scrambles.

The idea is to use dynamic programming. Rough outline:

scrambles[Moves][Lastside][State] := the number of scrambles of <Moves> moves with the last move being on <Lastside> and resulting in state <State>

int64 scrambles[21][4][3674160]
scrambles[0][0(=noside)][0(=solvedstate)] = 1
for moves = 0 to 19
    for lastside = 0 to 3
        for state = 0 to 3674159
            for side = 1 to 3
                if side != lastside
                    for quarters = 1 to 3
                        resultState = makeMove( state, side, quarters )
                        scrambles[moves+1][side][resultState] += scrambles[moves][lastside][state]
use the results in scrambles[20][1-3][0-3674159]

Note that with 30 moves, int64 should suffice, only farther than that you'll eventually need to use a different data type. And for large move numbers like 1000, you shouldn't use scrambles[1001][4][3674160] but scrambles[2][4][3674160] and index with the moves modulo 2 (since you only need the current and next).

 

[Lucas Garron]

@Lucas : Well simply read the "Advantages" section of the wiki article to understand why it is a good RNG. You can also read the original article describing the algorithm if you really want to be convinced.

Indeed. Just wondering if that's what you were reasoning from.
(Also, Mark 2 uses Mersenne Twister right now, but I really need to switch to a crypto library.)

"almost" sounds like it isn't non-trivial, but I'd say it is (I actually can't explain/prove it).

Ergodicity. For sane puzzles, if you can find a steady distribution, it's also an average limiting distribution. Parity and uneven distributions get a bit confusing, though.

For this example, each state (more generally, any coset) spreads out to its neighbors. Hmm, I need to think of a completely correct intuitive explanation here.

Thank you, I understand the idea.
The number of possible scrambles, that have length 11, is relatively small. 9*6^10=544195584. So we need't use Monte Carlo method. OK, I'll try to do complete calculation for number of moves <=15.

Hmm, it wasn't clear from your first post that you were using Monte Carlo; the choice of numbers related to the number of 2x2x2 states made it look otherwise. In any case, would you mind doing the calculations for 11, *allowing* repeating moves?

 

[Stefan]

The most common position for any length of scramble - solved state.

Can't be the most common for lengths 1 to 5, and apparently also isn't for lengths 6 and 7. Looks like it's indeed the most common after that, though (all based on preliminary results of my own program).

Ergodicity. For sane puzzles, if you can find a steady distribution, it's also an average limiting distribution.

I think we have different definitions of "trivial"

 

[Stefan]

I analyzed the 1.176*10^78 scrambles of length up to 100, here are my results:

all scrambles    = number of scrambles with that many moves
max scrambles    = highest number of scrambles of any reached state
min scrambles    = lowest number of scrambles of any reached state
max/min          = max/min
solved scrambles = number of scrambles reaching the solved state
avg dist         = average distance to solved

moves           all scrambles            max scrambles            min scrambles      max/min         solved scrambles   avg dist
   1                        9                        1                        0     infinity                        0  1.0000000
   2                       54                        1                        0     infinity                        0  2.0000000
   3                      324                        2                        0     infinity                        0  3.0000000
   4                     1944                        4                        0     infinity                        0  3.9814815
   5                    11664                        6                        0     infinity                        0  4.9074074
   6                    69984                       16                        0     infinity                        6  5.7870370
   7                   419904                       46                        0     infinity                       12  6.6005373
   8                  2519424                      150                        0     infinity                      150  7.3250362
   9                 15116544                      336                        0     infinity                      336  7.9021046
  10                 90699264                     1314                        0     infinity                     1314  8.2195190
  11                544195584                     4428                       16   276.750000                     4428  8.4041579
  12               3265173504                    17358                      296    58.641892                    17358  8.5252573
  13              19591041024                    62616                     2894    21.636489                    62616  8.6040903
  14             117546246144                   243786                    21464    11.357902                   243786  8.6557525
  15             705277476864                  1026324                   148149     6.927647                  1026324  8.6896424
  16            4231664861184                  4302486                   967745     4.445888                  4302486  8.7119467
  17           25389989167104                 19724544                  6143263     3.210760                 19724544  8.7266508
  18          152339935002624                 90383874                 38253224     2.362778                 90383874  8.7363700
  19          914039610015744                442174332                234986932     1.881698                442174332  8.7428064
  20         5484237660094464               2248043022               1434333200     1.567309               2248043022  8.7470761
  21        32905425960566784              11936720136               8709768820     1.370498              11936720136  8.7499122
  22       197432555763400700              65504864730              52714583696     1.242633              65504864730  8.7517985
  23  1.1845953345804042e+018             369133041972             318186475796     1.160115             369133041972  8.7530544
  24  7.1075720074824253e+018            2119744309782            1917013644168     1.105753            2119744309782  8.7538914
  25  4.2645432044894552e+019           12344375487120           11534926256692     1.070174           12344375487120  8.7544498
  26  2.5587259226936735e+020           72578394895506           69345799368072     1.046616           72578394895506  8.7548227
  27  1.5352355536162028e+021          429565384905372          416636228087624     1.031032          429565384905372  8.7550718
  28  9.2114133216972253e+021         2553868498841742         2502128736097608     1.020678         2553868498841742  8.7552384
  29  5.5268479930183365e+022        15229552646035560        15022257722481100     1.013799        15229552646035560  8.7553498
  30  3.3161087958109997e+023        91003303291040400        90172405265844416     1.009215        91003303291040400  8.7554244
  31     1.9896652774866e+024       544526676235263870       541193300290851070     1.006159       544526676235263870  8.7554744
  32  1.1937991664919606e+025  3.2611875044042552e+018  3.2478084802267003e+018     1.004119  3.2611875044042552e+018  8.7555079
  33  7.1627949989517586e+025  1.9543227752676286e+019  1.9489495664272626e+019     1.002757  1.9543227752676286e+019  8.7555304
  34  4.2976769993710569e+026  1.1716363960369073e+020  1.1694774625737467e+020     1.001846  1.1716363960369073e+020  8.7555454
  35  2.5786061996226341e+027  7.0259818482472701e+020  7.0173030280526954e+020     1.001237  7.0259818482472701e+020  8.7555555
  36  1.5471637197735797e+028  4.2140502207357402e+021  4.2105599657841158e+021     1.000829  4.2140502207357402e+021  8.7555623
  37  9.2829823186414849e+028  2.5278125602778307e+022  2.5264083358311445e+022     1.000556  2.5278125602778307e+022  8.7555669
  38  5.5697893911848899e+029  1.5164395318471736e+023  1.5158743688897876e+023     1.000373  1.5164395318471736e+023  8.7555699
  39  3.3418736347109341e+030  9.0976407903529057e+023  9.0953653273169539e+023     1.000250  9.0976407903529057e+023  8.7555720
  40    2.00512418082656e+031  5.4581839352921419e+024  5.4572674809950812e+024     1.000168  5.4581839352921419e+024  8.7555734
  41  1.2030745084959361e+032  3.2747492783900283e+025  3.2743800510260895e+025     1.000113  3.2747492783900283e+025  8.7555743
  42    7.21844705097562e+032  1.9647847550337479e+026  1.9646359524862475e+026     1.000076  1.9647847550337479e+026  8.7555749
  43  4.3310682305853691e+033  1.1788447650130839e+027   1.178784778065528e+027     1.000051  1.1788447650130839e+027  8.7555754
  44  2.5986409383512227e+034  7.0729635377187698e+027  7.0727216426482805e+027     1.000034  7.0729635377187698e+027  8.7555757
  45  1.5591845630107334e+035  4.2437358035879309e+028  4.2436382332464103e+028     1.000023  4.2437358035879309e+028  8.7555758
  46  9.3551073780643999e+035  2.5462244280707174e+029  2.5461850617510279e+029     1.000015  2.5462244280707174e+029  8.7555760
  47  5.6130644268386396e+036  1.5277277818212204e+030  1.5277118947081142e+030     1.000010  1.5277277818212204e+030  8.7555761
  48  3.3678386561031835e+037  9.1663389660865052e+030  9.1662748340507851e+030     1.000007  9.1663389660865052e+030  8.7555761
  49  2.0207031936619109e+038  5.4997921954047171e+031  5.4997663006155051e+031     1.000005  5.4997921954047171e+031  8.7555762
  50  1.2124219161971464e+039  3.2998708040566532e+032  3.2998603459167537e+032     1.000003  3.2998708040566532e+032  8.7555762
  51  7.2745314971828749e+039   1.979920660664424e+033  1.9799164359331233e+033     1.000002   1.979920660664424e+033  8.7555762
  52  4.3647188983097269e+040  1.1879516608121967e+034  1.1879499537700352e+034     1.000001  1.1879516608121967e+034  8.7555762
  53  2.6188313389858354e+041  7.1277069938910302e+034  7.1277000948592003e+034     1.000001  7.1277069938910302e+034  8.7555762
  54  1.5712988033915006e+042  4.2766229960364099e+035  4.2766202071608249e+035     1.000001  4.2766229960364099e+035  8.7555762
  55  9.4277928203490098e+042  2.5659733125593013e+036  2.5659721849314769e+036     1.000000  2.5659733125593013e+036  8.7555762
  56  5.6566756922094049e+043  1.5395837914602518e+037  1.5395833354267414e+037     1.000000  1.5395837914602518e+037  8.7555762
  57  3.3940054153256433e+044  9.2375019559644961e+037    9.23750011021766e+037     1.000000  9.2375019559644961e+037  8.7555762
  58  2.0364032491953862e+045  5.5425008529425855e+038  5.5425001045016896e+038     1.000000  5.5425008529425855e+038  8.7555762
  59  1.2218419495172312e+046  3.3255003820560222e+039  3.3255000784951648e+039     1.000000  3.3255003820560222e+039  8.7555762
  60  7.3310516971033881e+046  1.9953001767482485e+040   1.995300053598008e+040     1.000000  1.9953001767482485e+040  8.7555762
  61  4.3986310182620335e+047  1.1971800848062624e+041  1.1971800348345223e+041     1.000000  1.1971800848062624e+041  8.7555762
  62  2.6391786109572201e+048  7.1830804228404908e+041   7.183080220019926e+041     1.000000  7.1830804228404908e+041  8.7555762
  63  1.5835071665743319e+049   4.309848218881844e+042  4.3098481365445629e+042     1.000000   4.309848218881844e+042  8.7555762
  64  9.5010429994459941e+049  2.5859089172253521e+043  2.5859088837922341e+043     1.000000  2.5859089172253521e+043  8.7555762
  65   5.700625799667594e+050   1.551545344621629e+044  1.5515453310431239e+044     1.000000   1.551545344621629e+044  8.7555762
  66  3.4203754798005576e+051  9.3092720445782736e+044  9.3092719894187157e+044     1.000000  9.3092720445782736e+044  8.7555762
  67  2.0522252878803337e+052  5.5855632173638794e+045  5.5855631949517889e+045     1.000000  5.5855632173638794e+045  8.7555762
  68  1.2313351727282009e+053  3.3513379266146226e+046  3.3513379175063527e+046     1.000000  3.3513379266146226e+046  8.7555762
  69  7.3880110363692023e+053  2.0108027544264999e+047  2.0108027507241237e+047     1.000000  2.0108027544264999e+047  8.7555762
  70  4.4328066218215212e+054  1.2064816520304266e+048  1.2064816505251522e+048     1.000000  1.2064816520304266e+048  8.7555762
  71  2.6596839730929134e+055  7.2388899096453997e+048  7.2388899035241426e+048     1.000000  7.2388899096453997e+048  8.7555762
  72  1.5958103838557479e+056  4.3433339447578548e+049  4.3433339422681105e+049     1.000000  4.3433339447578548e+049  8.7555762
  73  9.5748623031344854e+056  2.6060003664369807e+050  2.6060003654241019e+050     1.000000  2.6060003664369807e+050  8.7555762
  74  5.7449173818806927e+057  1.5636002196926343e+051  1.5636002192804909e+051     1.000000  1.5636002196926343e+051  8.7555762
  75  3.4469504291284156e+058  9.3816013174674592e+051  9.3816013157900957e+051     1.000000  9.3816013174674592e+051  8.7555762
  76  2.0681702574770492e+059  5.6289607902009681e+052  5.6289607895181681e+052     1.000000  5.6289607902009681e+052  8.7555762
  77  1.2409021544862291e+060  3.3773764740070614e+053    3.37737647372906e+053     1.000000  3.3773764740070614e+053  8.7555762
  78  7.4454129269173785e+060  2.0264258843581226e+054   2.026425884244912e+054     1.000000  2.0264258843581226e+054  8.7555762
  79  4.4672477561504265e+061  1.2158555305961373e+055  1.2158555305500254e+055     1.000000  1.2158555305961373e+055  8.7555762
  80  2.6803486536902551e+062  7.2951331835006822e+055  7.2951331833128279e+055     1.000000  7.2951331835006822e+055  8.7555762
  81  1.6082091922141537e+063  4.3770799100694607e+056  4.3770799099929152e+056     1.000000  4.3770799100694607e+056  8.7555762
  82  9.6492551532849249e+063  2.6262479460290946e+057   2.626247945997898e+057     1.000000  2.6262479460290946e+057  8.7555762
  83   5.789553091970954e+064  1.5757487676123404e+058  1.5757487675996237e+058     1.000000  1.5757487676123404e+058  8.7555762
  84  3.4737318551825727e+065  9.4544926056532344e+058  9.4544926056013862e+058     1.000000  9.4544926056532344e+058  8.7555762
  85  2.0842391131095386e+066  5.6726955633834757e+059  5.6726955633623328e+059     1.000000  5.6726955633834757e+059  8.7555762
  86  1.2505434678657231e+067  3.4036173380266418e+060  3.4036173380180177e+060     1.000000  3.4036173380266418e+060  8.7555762
  87  7.5032608071944195e+067  2.0421704028145837e+061  2.0421704028110655e+061     1.000000  2.0421704028145837e+061  8.7555762
  88  4.5019564843165719e+068  1.2253022416881798e+062  1.2253022416867441e+062     1.000000  1.2253022416881798e+062  8.7555762
  89   2.701173890589925e+069  7.3518134501267552e+062  7.3518134501208964e+062     1.000000  7.3518134501267552e+062  8.7555762
  90  1.6207043343539818e+070  4.4110880700751075e+063  4.4110880700727165e+063     1.000000  4.4110880700751075e+063  8.7555762
  91  9.7242260061238626e+070  2.6466528420446798e+064   2.646652842043703e+064     1.000000  2.6466528420446798e+064  8.7555762
  92  5.8345356036743028e+071  1.5879917052266508e+065  1.5879917052262521e+065     1.000000  1.5879917052266508e+065  8.7555762
  93    3.50072136220469e+072  9.5279502313592671e+065  9.5279502313576377e+065     1.000000  9.5279502313592671e+065  8.7555762
  94  2.1004328173228154e+073  5.7167701388152984e+066  5.7167701388146331e+066     1.000000  5.7167701388152984e+066  8.7555762
  95  1.2602596903936484e+074  3.4300620832890731e+067  3.4300620832888013e+067     1.000000  3.4300620832890731e+067  8.7555762
  96  7.5615581423616581e+074  2.0580372499734005e+068  2.0580372499732894e+068     1.000000  2.0580372499734005e+068  8.7555762
  97  4.5369348854170676e+075  1.2348223499840225e+069  1.2348223499839773e+069     1.000000  1.2348223499840225e+069  8.7555762
  98  2.7221609312502438e+076  7.4089340999040647e+069  7.4089340999038793e+069     1.000000  7.4089340999040647e+069  8.7555762
  99  1.6332965587501428e+077  4.4453604599424094e+070  4.4453604599423328e+070     1.000000  4.4453604599424094e+070  8.7555762
 100   9.799779352501371e+077  2.6672162759654335e+071  2.6672162759654026e+071     1.000000  2.6672162759654335e+071  8.7555762

It's amazing I can get away with this kind of poor programming (using sticker strings in the first part) even on my four years old laptop. The program needs about 800MB of RAM and ran about 4.5 minutes.

Spoiler: My program

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

const int Length = 100;   // maximum scramble length
const int Sides = 3;      // usually 3, but use 2 for quicker testing

const int MaxStates  = 7*6*5*4*3*2 * 3*3*3*3*3*3;
map<string,int> states;
string stateStrings   [MaxStates];
int    distances      [MaxStates];
double scrambles[2][4][MaxStates];
int    prevState[3][3][MaxStates];
int moveEffects[3][3][4] = { { { 0, 3, 6, 9 }, { 1, 4, 7, 10 }, { 2, 5, 8, 11 } },
                             { { 0, 14, 18, 5 }, { 1, 12, 19, 3 }, { 2, 13, 20, 4 } },
                             { { 0, 10, 15, 13 }, { 1, 11, 16, 14 }, { 2, 9, 17, 12 } } };

int main ( int argc, char *argv[] ) {

  //--- Breadth-first search to enumerate all states, their distances and their transitions
  states[ stateStrings[0] = "UFRURBUBLULFDRFDFLDBR" ] = 0;
  for ( int state=0; state<states.size(); state++ ) {
    for ( int side=0; side<Sides; side++ ) {

      //--- Consider the next states reachable from this one
      string nextStateString = stateStrings[state];
      for ( int angle=0; angle<3; angle++ ) {

        //--- Turn that side
        for ( int i=0; i<3; i++ ) for ( int j=0; j<3; j++ )
            swap( nextStateString[moveEffects[side][i][j]], nextStateString[moveEffects[side][i][j+1]] );

        //--- If new state discovered, collect its stuff
        if ( ! states.count( nextStateString ) ) {
          int nextState = states.size();
          states[ nextStateString ] = nextState;
          stateStrings[ nextState ] = nextStateString;
          distances[ nextState ] = distances[ state ] + 1;
          if ( states.size() % 10000 == 0 ) cout << nextStateString << "  " << states.size() << endl;
        }

        //--- Remember the transition
        prevState[side][angle][states[nextStateString]] = state;
      }
    }
  }
  cout << states.size() << " states" << endl;

  //--- Show the distance distribution, can be checked against http://www.jaapsch.net/puzzles/cube2.htm#numpos
  int distFreq[99] = {};
  for ( int state=0; state<states.size(); state++ )
    distFreq[ distances[state] ]++;
  for ( int dist=0; dist<99; dist++ )
    if ( distFreq[dist] )
      printf( "%7d times distance %2d\n", distFreq[dist], dist );

  //--- Now to the scrambles... with 0 moves, the solved state can be reached one way
  scrambles[0][3][0] = 1;

  //--- Compute all scramble numbers, one move at a time
  printf( "moves%24s %24s %24s %12s %24s %10s\n", "all scrambles", "max scrambles", "min scrambles", "max/min", "solved scrambles", "avg dist" );
  for ( int move=1; move<=Length; move++ ) {

    //--- Compute scramble numbers from previous round
    for ( int side=0; side<Sides; side++ ) {
      for( int state=0; state<states.size(); state++ ) {
        scrambles[move%2][side][state] = 0;
        for( int prevSide=0; prevSide<4; prevSide++ ) if( side!=prevSide && !(move>1 && prevSide==3) )
          for( int angle=0; angle<3; angle++ )
            scrambles[move%2][side][state] += scrambles[(move-1)%2][prevSide][prevState[side][angle][state]];
      }
    }

    //--- Analyze
    double allScrambles = 0, maxScrambles = 0, minScrambles = 1.0/0, solvedScrambles, totalDistance = 0;
    for( int state=0; state<states.size(); state++ ) {
      double scrambs = 0;
      for( int side=0; side<Sides; side++ )
        scrambs += scrambles[move%2][side][state];
      allScrambles += scrambs;
      maxScrambles = max( maxScrambles, scrambs );
      minScrambles = min( minScrambles, scrambs );
      if ( state == 0 ) solvedScrambles = scrambs;
      totalDistance += scrambs * distances[state];
    }
    printf( "%4d %24.18lg %24.18lg %24.18lg %12.6lf %24.18lg %10.7lf\n",
            move, allScrambles, maxScrambles, minScrambles, maxScrambles/minScrambles, solvedScrambles, totalDistance/allScrambles );
  }
}

Spoiler: The sticker numbering, in case someone's interested

Edit:

Spoiler: A more compact presentation, with the three interesting columns together on the right

 all scrambles   max scrambles   min scrambles  moves    max/min   avg dist
             9               1               0    1     infinity  1.0000000
            54               1               0    2     infinity  2.0000000
           324               2               0    3     infinity  3.0000000
          1944               4               0    4     infinity  3.9814815
         11664               6               0    5     infinity  4.9074074
         69984              16               0    6     infinity  5.7870370
        419904              46               0    7     infinity  6.6005373
       2519424             150               0    8     infinity  7.3250362
      15116544             336               0    9     infinity  7.9021046
      90699264            1314               0   10     infinity  8.2195190
5.4419558e+008            4428              16   11  276.7500000  8.4041579
3.2651735e+009           17358             296   12   58.6418919  8.5252573
1.9591041e+010           62616            2894   13   21.6364893  8.6040903
1.1754625e+011          243786           21464   14   11.3579016  8.6557525
7.0527748e+011         1026324          148149   15    6.9276472  8.6896424
4.2316649e+012         4302486          967745   16    4.4458881  8.7119467
2.5389989e+013        19724544         6143263   17    3.2107601  8.7266508
1.5233994e+014        90383874        38253224   18    2.3627779  8.7363700
9.1403961e+014  4.4217433e+008  2.3498693e+008   19    1.8816975  8.7428064
5.4842377e+015   2.248043e+009  1.4343332e+009   20    1.5673088  8.7470761
3.2905426e+016   1.193672e+010  8.7097688e+009   21    1.3704979  8.7499122
1.9743256e+017  6.5504865e+010  5.2714584e+010   22    1.2426327  8.7517985
1.1845953e+018  3.6913304e+011  3.1818648e+011   23    1.1601154  8.7530544
 7.107572e+018  2.1197443e+012  1.9170136e+012   24    1.1057534  8.7538914
4.2645432e+019  1.2344375e+013  1.1534926e+013   25    1.0701738  8.7544498
2.5587259e+020  7.2578395e+013  6.9345799e+013   26    1.0466156  8.7548227
1.5352356e+021  4.2956538e+014  4.1663623e+014   27    1.0310322  8.7550718
9.2114133e+021  2.5538685e+015  2.5021287e+015   28    1.0206783  8.7552384
 5.526848e+022  1.5229553e+016  1.5022258e+016   29    1.0137992  8.7553498
3.3161088e+023  9.1003303e+016  9.0172405e+016   30    1.0092145  8.7554244
1.9896653e+024  5.4452668e+017   5.411933e+017   31    1.0061593  8.7554744
1.1937992e+025  3.2611875e+018  3.2478085e+018   32    1.0041194  8.7555079
 7.162795e+025  1.9543228e+019  1.9489496e+019   33    1.0027570  8.7555304
 4.297677e+026  1.1716364e+020  1.1694775e+020   34    1.0018461  8.7555454
2.5786062e+027  7.0259818e+020   7.017303e+020   35    1.0012368  8.7555555
1.5471637e+028  4.2140502e+021    4.21056e+021   36    1.0008289  8.7555623
9.2829823e+028  2.5278126e+022  2.5264083e+022   37    1.0005558  8.7555669
5.5697894e+029  1.5164395e+023  1.5158744e+023   38    1.0003728  8.7555699
3.3418736e+030  9.0976408e+023  9.0953653e+023   39    1.0002502  8.7555720
2.0051242e+031  5.4581839e+024  5.4572675e+024   40    1.0001679  8.7555734
1.2030745e+032  3.2747493e+025  3.2743801e+025   41    1.0001128  8.7555743
7.2184471e+032  1.9647848e+026   1.964636e+026   42    1.0000757  8.7555749
4.3310682e+033  1.1788448e+027  1.1787848e+027   43    1.0000509  8.7555754
2.5986409e+034  7.0729635e+027  7.0727216e+027   44    1.0000342  8.7555757
1.5591846e+035  4.2437358e+028  4.2436382e+028   45    1.0000230  8.7555758
9.3551074e+035  2.5462244e+029  2.5461851e+029   46    1.0000155  8.7555760
5.6130644e+036  1.5277278e+030  1.5277119e+030   47    1.0000104  8.7555761
3.3678387e+037   9.166339e+030  9.1662748e+030   48    1.0000070  8.7555761
2.0207032e+038  5.4997922e+031  5.4997663e+031   49    1.0000047  8.7555762
1.2124219e+039  3.2998708e+032  3.2998603e+032   50    1.0000032  8.7555762
7.2745315e+039  1.9799207e+033  1.9799164e+033   51    1.0000021  8.7555762
4.3647189e+040  1.1879517e+034    1.18795e+034   52    1.0000014  8.7555762
2.6188313e+041   7.127707e+034  7.1277001e+034   53    1.0000010  8.7555762
1.5712988e+042   4.276623e+035  4.2766202e+035   54    1.0000007  8.7555762
9.4277928e+042  2.5659733e+036  2.5659722e+036   55    1.0000004  8.7555762
5.6566757e+043  1.5395838e+037  1.5395833e+037   56    1.0000003  8.7555762
3.3940054e+044   9.237502e+037  9.2375001e+037   57    1.0000002  8.7555762
2.0364032e+045  5.5425009e+038  5.5425001e+038   58    1.0000001  8.7555762
1.2218419e+046  3.3255004e+039  3.3255001e+039   59    1.0000001  8.7555762
7.3310517e+046  1.9953002e+040  1.9953001e+040   60    1.0000001  8.7555762

 

[Cubemir]

Using dynamic algorithm, suggested by Stefan, I recalculated the histograms for 1-19 moves. Now they are complete and absolutely exact.

11 moves:

14 moves:

19 moves:

1 move:

5 moves:

7 moves:

8 moves:

9 moves:

 

[Cubemir]

Hmm, it wasn't clear from your first post that you were using Monte Carlo; the choice of numbers related to the number of 2x2x2 states made it look otherwise. In any case, would you mind doing the calculations for 11, *allowing* repeating moves?

What happens, if we allow repeating sides: