# Inaccuracy of scrambling using a random sequence of moves



## Cubemir (Jun 4, 2012)

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 (Jun 4, 2012)

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 (Jun 4, 2012)

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


----------



## Owen (Jun 4, 2012)

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


----------



## Dacuba (Jun 4, 2012)

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 (Jun 5, 2012)

Zarxrax said:


> 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.



Owen said:


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



For 3 histograms it took about 12 hours.


----------



## Lucas Garron (Jun 6, 2012)

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 (Jun 6, 2012)

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 (Jun 6, 2012)

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 (Jun 6, 2012)

CarlBrannen said:


> 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.



Chrisalead said:


> 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 (Jun 6, 2012)

Lucas Garron said:


> 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...



Chrisalead said:


> 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 (Jun 6, 2012)

@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 (Jun 6, 2012)

Lucas Garron said:


> 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).



Lucas Garron said:


> 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 (Jun 6, 2012)

Stefan said:


> 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 (Jun 6, 2012)

Cubemir said:


> 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 (Jun 7, 2012)

Chrisalead said:


> @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.)



Stefan said:


> "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.



Cubemir said:


> 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 (Jun 7, 2012)

Cubemir said:


> 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).



Lucas Garron said:


> 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 (Jun 7, 2012)

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 (Jun 7, 2012)

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 (Jun 7, 2012)

Lucas Garron said:


> 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:


----------



## Stefan (Jun 7, 2012)

Cubemir said:


> Using dynamic algorithm



Excellent, thanks. I compared our numbers for 19 move scrambles. I had some trouble implementing things correctly, so I'm happy our numbers match exactly. But you have the much prettier presentation 

Btw, if we consider 2-gen (only R and U turns), then the solved position loses its dominant position as the most commonly reached state:


```
all scrambles   max scrambles   min scrambles  moves    max/min   avg dist      solved state wins by     winners
             6               1               0    1     infinity  1.0000000                        -1      6: 1 2 3 4 5 6
            18               1               0    2     infinity  2.0000000                        -1     18: 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
            54               2               0    3     infinity  3.0000000                        -2      1: 38
           162               2               0    4     infinity  3.9259259                        -2      4: 90 91 164 165
           486               2               0    5     infinity  4.8518519                        -2     44: 226 227 228 231 234 238 239 242 251 261 262 263 264 265 266 275 299 300 312 313 367 368 380 381 394 412 421 427 430 433 434 435 443 444 464 465 466 467 468 469 512 513 578 579
          1458               4               0    6     infinity  5.6296296                        -2      4: 226 435 798 902
          4374               7               0    7     infinity  6.2693187                        -3      4: 25 51 52 77
         13122              12               0    8     infinity  6.8449931                       -12      2: 226 435
         39366              26               0    9     infinity  7.2609358                       -14      8: 86 143 160 217 227 300 367 434
        118098              72               0   10     infinity  7.6234991                       -32      2: 226 435
        354294             132               0   11     infinity  7.9263267                       -16      1: 17520
       1062882             296               0   12     infinity  8.1870989                       -46      2: 2 5
       3188646             848               0   13     infinity  8.4021048                       136      1: 0
       9565938            2040              16   14  127.5000000  8.5892403                      -864      1: 17520
      28697814            4896             132   15   37.0909091  8.7463957                        72      1: 0
      86093442           12888             734   16   17.5585831  8.8850531                     -3464      1: 17520
2.5828033e+008           34024            2936   17   11.5885559  9.0032457                      -488      2: 3418 4781
7.7484098e+008           91568           10740   18    8.5258845  9.1076639                    -20486      1: 17520
2.3245229e+009          246324           38612   19    6.3794675  9.1966332                     -3552      2: 3418 4781
6.9735688e+009          672184          131548   20    5.1098002  9.2752829                   -131620      1: 17520
2.0920706e+010         1819956          436628   21    4.1682073  9.3424559                    -10512      2: 3418 4781
6.2762119e+010         5001300         1410204   22    3.5465082  9.4018607                   -809112      2: 226 435
1.8828636e+011        13839052         4513092   23    3.0664236  9.4526378                    -26344      2: 3418 4781
5.6485907e+011        38498984        14288912   24    2.6943258  9.4975439                  -5336182      1: 17520
1.6945772e+012   1.077877e+008        44815772   25    2.4051286  9.5359667                    -23968      2: 3418 4781
5.0837317e+012  3.0350195e+008  1.3956953e+008   26    2.1745574  9.5699296                 -36008700      1: 17520
1.5251195e+013  8.5849379e+008  4.3204395e+008   27    1.9870520  9.5989939                   -216100      2: 3418 4781
4.5753585e+013  2.4418439e+009  1.3312475e+009   28    1.8342524  9.6246775                -240398540      1: 17520
1.3726075e+014  6.9779749e+009  4.0860416e+009   29    1.7077591  9.6466565                   -251232      2: 3418 4781
4.1178226e+014  2.0035379e+010  1.2499246e+010   30    1.6029271  9.6660762               -1620394746      1: 17520
1.2353468e+015  5.7765907e+010  3.8126475e+010   31    1.5151127  9.6826969                  -2767444      2: 3418 4781
3.7060404e+015   1.672152e+011  1.1602831e+011   32    1.4411586  9.6973809              -10943316448      2: 226 435
1.1118121e+016  4.8583319e+011  3.5239478e+011   33    1.3786617  9.7099495                   5012548      1: 0
3.3354363e+016  1.4163405e+012  1.0684405e+012   34    1.3256148  9.7210529              -74143693964      2: 226 435
1.0006309e+017  4.1418932e+012  3.2347156e+012   35    1.2804505  9.7305574                  14022540      1: 0
3.0018927e+017  1.2146601e+013  9.7809148e+012   36    1.2418676  9.7389535             -503016901474      2: 226 435
9.0056781e+017  3.5712847e+013  2.9543213e+013   37    1.2088342  9.7461408                 124777836      1: 0
2.7017034e+018  1.0524385e+014  8.9152997e+013   38    1.1804858  9.7524898            -3416310993116      2: 226 435
8.1051103e+018  3.1079361e+014  2.6882523e+014   39    1.1561177  9.7579249                  58214548      1: 0
2.4315331e+019  9.1950913e+014  8.1004168e+014   40    1.1351380  9.7627260           -23215138079800      2: 226 435
7.2945993e+019  2.7249688e+015  2.4394318e+015   41    1.1170506  9.7668361                 790530148      1: 0
2.1883798e+020  8.0874023e+015  7.3425836e+015   42    1.1014382  9.7704668          -157842182953402      2: 226 435
6.5651393e+020  2.4034027e+016  2.2091133e+016   43    1.0879490  9.7735749                1949485016      1: 0
1.9695418e+021  7.1507014e+016   6.643879e+016   44    1.0762841  9.7763204         -1073515292493928      2: 226 435
5.9086254e+021  2.1296908e+017  1.9974793e+017   45    1.0661892  9.7786709                2472069984      1: 0
1.7725876e+022  6.3485944e+017  6.0036983e+017   46    1.0574473  9.7807471         -7302817494396672      1: 17520
5.3177629e+022  1.8940205e+018  1.8040475e+018   47    1.0498728  9.7825245                -588625920      2: 3418 4781
1.5953289e+023  5.6545226e+018  5.4198083e+018   48    1.0433067  9.7840946        -49686588151495680      1: 17520
4.7859866e+023  1.6891733e+019  1.6279425e+019   49    1.0376124  9.7854387              -58027974656      2: 3418 4781
 1.435796e+024  5.0487819e+019  4.8890457e+019   50    1.0326723  9.7866260       -338090512045998080      1: 17520
4.3073879e+024  1.5097466e+020  1.4680751e+020   51    1.0283851  9.7876425             -317175070720      2: 3418 4781
1.2922164e+025  4.5164888e+020  4.4077772e+020   52    1.0246636  9.7885404  -2.3006864723858555e+018      1: 17520
3.8766491e+025  1.3516204e+021  1.3232598e+021   53    1.0214323  9.7893090               68866539520      1: 0
1.1629947e+026  4.0461838e+021   3.972197e+021   54    1.0186262  9.7899880  -1.5656808313304646e+019      1: 17520
3.4889842e+026  1.2115915e+022  1.1922898e+022   55    1.0161888  9.7905693            -1659887419392      2: 3418 4781
1.0466953e+027  3.6288693e+022   3.578515e+022   56    1.0140713  9.7910828  -1.0655244600366596e+020      1: 17520
3.1400858e+027  1.0871203e+023  1.0739838e+023   57    1.0122316  9.7915223            -6799369437184      2: 3418 4781
9.4202574e+027  3.2573419e+023  3.2230713e+023   58    1.0106329  9.7919106   -7.251593601498942e+020      2: 226 435
2.8260772e+028  9.7615415e+023  9.6721356e+023   59    1.0092436  9.7922430             4338453839872      1: 0
8.4782317e+028  2.9257273e+024   2.902403e+024   60    1.0080362  9.7925367   -4.935262507442402e+021      1: 17520
```

The "winners numbers" (states reached by most scrambles) on the right are my internal ids, telling when I discovered these states during my breadth-first search from solved. You can see that states 1 to 6 are the most common after one turn, which makes sense as they are the six states one move away from solved. With two moves it's states 7 to 24, and then it gets more "chaotic", the winners are more scrambled positions. Interestingly, there are four alternating groups of winners:

0 is of course the solved state .
17520 is .
3418 and 4781 are  and , they rotate all corners in place in the same direction.
226 and 435 are  and , they _"swap and orient opposite corners"_.

Note that I eventually lose precision due to rounding errors, but I believe the numbers to be exact until about 40 moves, and those four groups pop up well before that already.


----------



## Stefan (Jun 7, 2012)

A comparison of your initial randomized graph and the exact recomputation:











The initial randomized one looks "smoother" in the middle, but it has noticeable strange steps in the beginning that shouldn't be there, from about 266000 down to 260000, another from about 258000 to 252000, and one from about 207000 to 200000. Could be an artifact of your random number generator.


----------



## Carson (Jun 8, 2012)

I have only a rudimentary understanding of statistics, and I am certainly not an expert on cube theory, but with that being said:

It appears to me that everyone is concerned with distribution of potential cube states resulting from a scramble. While I agree that a normal distribution should be the ultimate goal, the most aspect of a scramble, at least for me, is the difficulty of the solve. A far more "useful" statistic for me, would be a comparison of the distributions of the number of moves required to solve the cube across all possible cube states, and a set of scrambles produced by a "good" random move scrambler.

Am I way off the mark here?


----------



## Stefan (Jun 8, 2012)

Carson said:


> A far more "useful" statistic for me, would be a comparison of the distributions of the number of moves required to solve the cube across all possible cube states, and a set of scrambles produced by a "good" random move scrambler.



You mean a comparison between this and let's say a 25-random-moves scrambler?

Something a little like that is my "avg dist" column, you can see how that grows (towards the ideal 8.7555762 average) with growing number of moves.

Also, you can see in Cubemir's images and my tables how the most common and least common states get closer together, like at 25 moves they're about 7% apart. Since those are the extremes, no state then occurs more than 7% more or less often than it should, so the distribution will look fairly ideal.



Carson said:


> I agree that a normal distribution should be the ultimate goal



Like this? http://en.wikipedia.org/wiki/Normal_distribution
I'd say that's not the goal, at least not in Cubemir's images. There, the goal is that green perfectly flat horizontal line.


----------



## PandaCuber (Jun 8, 2012)

Can someone please explain all those graphs? Dumb it down a little bit? Or a conclusion...


----------



## Stefan (Jun 8, 2012)

PandaCuber said:


> Can someone please explain all those graphs? Dumb it down a little bit? Or a conclusion...



Like they say, they're histograms. All 3.7 million possible cube positions on the x-axis, and on the y-axis the number of scrambles that produced them. Sorted different ways and sometimes with a logarithmic scale to offer a better view.


----------



## Carson (Jun 8, 2012)

Stefan said:


> You mean a comparison between this and let's say a 25-random-moves scrambler?


Yes, that is exactly what I mean.



Stefan said:


> Something a little like that is my "avg dist" column, you can see how that grows (towards the ideal 8.7555762 average) with growing number of moves.


Yes, I must have missed that.



Stefan said:


> Like this? http://en.wikipedia.org/wiki/Normal_distribution
> I'd say that's not the goal, at least not in Cubemir's images. There, the goal is that green perfectly flat horizontal line.


I spoke before viewing the link you posted to Jaap's page above. I can see that, if graphed, this data would be severely skewed. What I should have said, is that any scrambler should produce similar results to this data. (Though it wouldn't be a bad idea to eliminate any scrambles that may be solved with a specific number of moves or fewer)

My thoughts:
Generate *3,674,160 random turn scrambles for each number of turns ranging from 4 - 25 (I hope that makes sense) and determine the number of moves required to solve each scramble**.*The number of scrambles is based off of the number of possible cube states, just to keep things equivalent.
The number of turns (4-25) is just what seems logical to me.
If random text in this post appears in bold, it is because the I used copy/paste and the new text editor in the forum and I are having a disagreement. 
​I'm not entirely sure my explanation makes sense. Also, I realize this could potentially be very system intensive, so if someone were willing to provide the code, I would be more than happy to run it.

edit: Hmm... the editor will not allow me to unbold the bold text, and I tried fixing the alignment but it reappears when hitting save.


----------



## Stefan (Jun 8, 2012)

Carson said:


> it wouldn't be a bad idea to eliminate any scrambles that may be solved with a specific number of moves or fewer



Though last time I saw, there still was heavy disagreement about this.



Carson said:


> Generate 3,674,160 random turn scrambles for each number of turns ranging from 4 - 25 (I hope that makes sense) and determine the number of moves required to solve each scramble



I'd prefer to analyze *all* scrambles of each length and scale the results to a total of 3,674,160.



Carson said:


> the editor will not allow me to ...



Have you tried the "Switch Editor to Source Mode" button (leftmost button for me)?


----------



## Stefan (Jun 8, 2012)

Stefan said:


> I'd prefer to analyze *all* scrambles of each length and scale the results to a total of 3,674,160.



Here are my results for that up to scramble length 60 (the outlined lines are the ideal distribution for comparison):

```
1    0.00  3674160.00        0.00        0.00        0.00        0.00        0.00        0.00        0.00        0.00       0.00     0.00
 2    0.00        0.00  3674160.00        0.00        0.00        0.00        0.00        0.00        0.00        0.00       0.00     0.00
 3    0.00        0.00        0.00  3674160.00        0.00        0.00        0.00        0.00        0.00        0.00       0.00     0.00
 4    0.00        0.00    11340.00    45360.00  3617460.00        0.00        0.00        0.00        0.00        0.00       0.00     0.00
 5    0.00     1890.00     7560.00    54810.00   200340.00  3409560.00        0.00        0.00        0.00        0.00       0.00     0.00
 6  315.00     1260.00    10080.00    39060.00   120645.00   375480.00  3127320.00        0.00        0.00        0.00       0.00     0.00
 7  105.00     1837.50     6510.00    22837.50    81480.00   231420.00   624750.00  2705220.00        0.00        0.00       0.00     0.00
 8  218.75     1032.50     4077.50    15137.50    50023.75   155890.00   402500.00   898030.00  2147250.00        0.00       0.00     0.00
 9   81.67      701.46     2502.50     9328.96    32774.58    99061.67   283237.50   658705.83  1226761.67  1361004.17       0.00     0.00
10   53.23      367.50     1603.68     5831.39    20461.15    68710.83   197333.89   516697.22  1111782.78  1454969.44  296348.89     0.00
------------------------------------------------------------------------------------------------------------------------------------------
      1           9          54         321        1847        9992       50136      227536      870072     1887748     623800     2644
------------------------------------------------------------------------------------------------------------------------------------------
11   29.90      230.21      934.95     3689.06    13745.76    46808.29   148373.59   415148.77  1032151.62  1608969.93  403053.19  1024.72
12   19.53      139.42      586.86     2394.57     9287.59    34082.33   113669.52   351467.25   978237.96  1705365.17  477385.36  1524.44
13   11.74       88.74      388.11     1619.60     6645.71    25458.67    91712.72   309003.88   942284.84  1769723.15  525337.43  1885.40
14    7.62       59.06      264.52     1162.49     4931.81    20029.89    77249.52   281288.82   918831.00  1809976.44  558234.55  2124.28
15    5.35       40.73      190.61      862.91     3846.35    16539.27    67892.70   263070.50   902787.49  1836631.41  580007.82  2284.87
16    3.74       29.94      142.25      672.25     3150.57    14271.54    61837.05   251055.50   891956.65  1854073.87  594566.98  2399.66
17    2.85       22.52      111.53      550.12     2698.21    12807.10    57859.01   243135.68   884708.93  1865506.32  604280.06  2477.66
18    2.18       17.88       91.53      470.82     2406.16    11847.09    55246.23   237895.48   879874.25  1873007.23  610769.75  2531.39
19    1.78       14.77       78.60      419.37     2215.30    11217.68    53522.10   234428.06   876629.25  1877971.67  615093.83  2567.59
20    1.51       12.79       70.13      385.81     2090.07    10803.35    52384.18   232123.50   874463.12  1881252.75  617980.39  2592.38
------------------------------------------------------------------------------------------------------------------------------------------
      1           9          54         321        1847        9992       50136      227536      870072     1887748     623800     2644
------------------------------------------------------------------------------------------------------------------------------------------
21    1.33       11.49       64.63      363.74     2007.81    10530.07    51630.26   230593.24   873012.81  1883428.05  619907.40  2609.17
22    1.22       10.64       61.02      349.27     1953.55    10349.33    51130.38   229575.20   872042.74  1884871.12  621195.01  2620.53
23    1.14       10.08       58.64      339.73     1917.72    10229.57    50798.45   228897.31   871393.17  1885830.30  622055.69  2628.19
24    1.10        9.72       57.08      333.43     1893.99    10150.15    50577.69   228445.46   870958.17  1886468.40  622631.45  2633.36
25    1.06        9.48       56.04      329.26     1878.27    10097.38    50430.76   228143.98   870666.63  1886893.54  623016.74  2636.85
26    1.04        9.32       55.36      326.50     1867.83    10062.28    50332.86   227942.71   870471.19  1887176.97  623274.76  2639.19
27    1.03        9.21       54.90      324.66     1860.89    10038.91    50267.56   227808.23   870340.09  1887366.13  623447.62  2640.77
28    1.02        9.14       54.60      323.44     1856.27    10023.34    50223.98   227718.31   870252.12  1887492.46  623563.49  2641.83
29    1.01        9.09       54.40      322.63     1853.19    10012.95    50194.87   227658.16   870193.07  1887576.89  623641.20  2642.54
30    1.01        9.06       54.27      322.09     1851.14    10006.01    50175.41   227617.89   870153.41  1887633.36  623693.33  2643.02
------------------------------------------------------------------------------------------------------------------------------------------
      1           9          54         321        1847        9992       50136      227536      870072     1887748     623800     2644
------------------------------------------------------------------------------------------------------------------------------------------
31    1.01        9.04       54.18      321.73     1849.77    10001.38    50162.40   227590.92   870126.76  1887671.16  623728.32  2643.34
32    1.00        9.03       54.12      321.49     1848.85     9998.28    50153.69   227572.85   870108.85  1887696.47  623751.81  2643.56
33    1.00        9.02       54.08      321.33     1848.24     9996.21    50147.86   227560.74   870096.80  1887713.42  623767.60  2643.70
34    1.00        9.01       54.05      321.22     1847.83     9994.82    50143.96   227552.61   870088.70  1887724.79  623778.20  2643.80
35    1.00        9.01       54.04      321.15     1847.56     9993.89    50141.34   227547.16   870083.25  1887732.41  623785.33  2643.87
36    1.00        9.01       54.02      321.10     1847.37     9993.27    50139.58   227543.50   870079.58  1887737.53  623790.13  2643.91
37    1.00        9.00       54.02      321.07     1847.25     9992.85    50138.41   227541.04   870077.11  1887740.96  623793.35  2643.94
38    1.00        9.00       54.01      321.04     1847.17     9992.57    50137.62   227539.39   870075.45  1887743.27  623795.52  2643.96
39    1.00        9.00       54.01      321.03     1847.11     9992.38    50137.09   227538.28   870074.32  1887744.82  623796.98  2643.97
40    1.00        9.00       54.00      321.02     1847.08     9992.26    50136.73   227537.53   870073.57  1887745.86  623797.97  2643.98
------------------------------------------------------------------------------------------------------------------------------------------
      1           9          54         321        1847        9992       50136      227536      870072     1887748     623800     2644
------------------------------------------------------------------------------------------------------------------------------------------
41    1.00        9.00       54.00      321.01     1847.05     9992.17    50136.49   227537.03   870073.06  1887746.56  623798.63  2643.99
42    1.00        9.00       54.00      321.01     1847.03     9992.12    50136.33   227536.70   870072.71  1887747.03  623799.08  2643.99
43    1.00        9.00       54.00      321.01     1847.02     9992.08    50136.22   227536.47   870072.48  1887747.35  623799.38  2643.99
44    1.00        9.00       54.00      321.00     1847.02     9992.05    50136.15   227536.32   870072.33  1887747.56  623799.58  2644.00
45    1.00        9.00       54.00      321.00     1847.01     9992.04    50136.10   227536.21   870072.22  1887747.70  623799.72  2644.00
46    1.00        9.00       54.00      321.00     1847.01     9992.02    50136.07   227536.14   870072.15  1887747.80  623799.81  2644.00
47    1.00        9.00       54.00      321.00     1847.00     9992.02    50136.05   227536.10   870072.10  1887747.87  623799.87  2644.00
48    1.00        9.00       54.00      321.00     1847.00     9992.01    50136.03   227536.07   870072.07  1887747.91  623799.91  2644.00
49    1.00        9.00       54.00      321.00     1847.00     9992.01    50136.02   227536.04   870072.05  1887747.94  623799.94  2644.00
50    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.01   227536.03   870072.03  1887747.96  623799.96  2644.00
------------------------------------------------------------------------------------------------------------------------------------------
      1           9          54         321        1847        9992       50136      227536      870072     1887748     623800     2644
------------------------------------------------------------------------------------------------------------------------------------------
51    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.01   227536.02   870072.02  1887747.97  623799.97  2644.00
52    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.01   227536.01   870072.01  1887747.98  623799.98  2644.00
53    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.00   227536.01   870072.01  1887747.99  623799.99  2644.00
54    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.00   227536.01   870072.01  1887747.99  623799.99  2644.00
55    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.00   227536.00   870072.00  1887747.99  623799.99  2644.00
56    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.00   227536.00   870072.00  1887748.00  623800.00  2644.00
57    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.00   227536.00   870072.00  1887748.00  623800.00  2644.00
58    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.00   227536.00   870072.00  1887748.00  623800.00  2644.00
59    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.00   227536.00   870072.00  1887748.00  623800.00  2644.00
60    1.00        9.00       54.00      321.00     1847.00     9992.00    50136.00   227536.00   870072.00  1887748.00  623800.00  2644.00
------------------------------------------------------------------------------------------------------------------------------------------
      1           9          54         321        1847        9992       50136      227536      870072     1887748     623800     2644
------------------------------------------------------------------------------------------------------------------------------------------
```

I didn't do the HTM/QTM matrix like Jaap because that would require some more work and because my presentation would be huge and wouldn't show the evolution so nicely in columns.



Carson said:


> I realize this could potentially be very system intensive



Nah, took about 4.5 minutes on my four years old laptop.


----------



## Stefan (Jun 8, 2012)

The distributions for 11, 15, 20, 25 moves versus the ideal distribution:


----------



## Stefan (Jun 8, 2012)

In my distribution table I just realized that when you ask after how many moves all values become less than 1 off the ideal...


```
1           9          54         321        1847        9992       50136      227536      870072     1887748     623800     2644
------------------------------------------------------------------------------------------------------------------------------------------
41    1.00        9.00       54.00      321.01     1847.05     9992.17    50136.49   227537.03   870073.06  1887746.56  623798.63  2643.99
42    1.00        9.00       54.00      321.01     1847.03     9992.12    50136.33   227536.70   870072.71  1887747.03  623799.08  2643.99
```

... the answer is 42.


----------



## Escher (Jun 8, 2012)

Stefan said:


> ... the answer is 42.



But what is the question?


----------



## Chrisalead (Jun 9, 2012)

Stefan said:


> In my distribution table I just realized that when you ask after how many moves all values become less than 1 off the ideal...
> 
> 
> ```
> ...



Brilliant ^^.


----------

