Inaccuracy of scrambling using a random sequence of moves

[Stefan]

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]

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]

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]

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.

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]

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

 

[Stefan]

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]

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

Yes, that is exactly what I mean.

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.

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]

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.

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.

the editor will not allow me to ...

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

 

[Stefan]

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.

I realize this could potentially be very system intensive

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

 

[Stefan]

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

 

[Stefan]

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]

... the answer is 42.

But what is the question?

 

[Chrisalead]

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.

Brilliant ^^.