# Is 20 turns enough for a scramble?

#### peterbone

##### Member
I wrote some code to analyse this. I tested scrambles from 0 turns to 50 and counted the average number of joined corner-edge pairs after the scramble. I tested each scramble number 100,000 times to get an accurate average.

The results are shown in the graph below. The average number of corner-edge pairs converges to 1 for a fully random scramble because there are 24 possible corner edge pairs and each one has a 1 in 24 chance of being joined (12 edge positions * 2 possible edge orientation for each).

The average number of corner-edge pairs for a 20 move scramble is 1.92 - almost double the value for a fully random scramble. Admittedly, by scramble algorithm doesn't avoid cancellations, so the actual value would be slightly less.

The more corner-edge pairs you have, the easier it will be to perform an x-cross or block build and get a quick solve.

Sorry if this has been done before and is already well known. Obviously increasing the number of turns for a scramble would be annoying, but increasing it to only 30 brings the value down to 1.23 - much closer to a fully random scramble. I wonder who chose 20 in the first place and what did they base it on?

So, what are people's thoughts on this?
Also, has anyone derived formula for calculating the above data mathematically?

Peter

#### stannic

##### Member
20 is based on God's number.
I think he knows it.

@Peter: Interesting analysis. I do not know, though, how the scrambles are selected "officially". Maybe they are using something like Cube Explorer to generate truly random positions and then find generators for them? In this case, all positions can be picked with equal probability.

- Bulat

#### peterbone

##### Member
20 is based on God's number.
I agree that it should be at least God's number since this is the minimum required to reach any state. However, only an infinite move scramble would ensure a fully random solve (probability of corner-edge pair = 1). There has to be a compromise between practicality and randomness. Maybe 20 is it, but to me it looks too far from random.

I think he knows it.

@Peter: Interesting analysis. I do not know, though, how the scrambles are selected "officially". Maybe they are using something like Cube Explorer to generate truly random positions and then find generators for them? In this case, all positions can be picked with equal probability.

- Bulat
OK, I hadn't considered that. If that is the method they use for generating scrambles in competitions then obviously the scrambles are fully random but still only 20 moves long, which is ideal.

Last edited by a moderator:

#### Kirjava

##### Colourful
Competition scrambles are suboptimal random state, and checking ce pairs solved is a poor method of testing scramble randomness.

#### qqwref

##### Member
Admittedly, by scramble algorithm doesn't avoid cancellations, so the actual value would be slightly less.
Okay, so that definitely needs to be fixed to get useful results. I think that move cancellation is definitely contributing to the high number of c/e pairs you found.

And 25 moves (not 20) was the standard before we implemented random-state scrambles, which are now used in competitions as well as good scrambling programs.

#### Zarxrax

##### Member
There is a difference between a truly random scramble and a scramble that meets the arbitrary measure of randomness that you have proposed.
Having corner edge pairs that match up might make a solve easier. But they have nothing to do with the random state of the cube. You could have a fully solved cube that is still a random state.

#### qqwref

##### Member
Having corner edge pairs that match up might make a solve easier. But they have nothing to do with the random state of the cube. You could have a fully solved cube that is still a random state.
Uh what? He's measuring averages. If we know that doing X random moves gives you more corner-edge pairs on average than a random-state scramble, that means that X random moves is noticeably easier than a random-state scramble.

#### CarlBrannen

##### Member
I would like to know what a " suboptimal random state" is, or failing that, an "optimal random state" might be enough.

And I'd also like to see the graph when the moves are prevented from cancelling each other. In addition to stuff like L L'.
And there's one more addition to the random scramble I'd like to see and that is to avoid consecutive moves like LR. The reason for avoiding this is because LRLR doesn't do anything.

So given that the most recent move was U, the next move can be: F, B, R, L, or these with ' or 2. So there are a total of 12 possible next moves.

With this restriction, I wonder what the shortest identity is? Sexy move 6 times would be length 24, (i.e. RLRL RLRL RLRL RLRL RLRL RLRL) but I bet there's one of length around 9.

#### qqwref

##### Member
"Suboptimal random state" = generate random cube position, generate a short but not necessarily optimal scramble for that position.
"Optimal random state" = generate random cube position, generate an optimal scramble for that position.

And there's no reason to exclude stuff like LR, just exclude stuff like LRL. I don't know why people are acting like the problem of randomly generating non-canceling moves hasn't been solved, because it has, for many years. Jaap's scrambler did it for all cube sizes in 2006, and I wouldn't be at all surprised if someone had written a proper scrambler several years before that.

Last edited by a moderator:

#### Stefan

##### Member
I would like to know what a " suboptimal random state" is
It's a quote taken out of context. The "suboptimal" (I still prefer "near-optimal") referred to the scramble, not the state.

And there's one more addition to the random scramble I'd like to see and that is to avoid consecutive moves like LR. The reason for avoiding this is because LRLR doesn't do anything.
LRLR is bad, but LR is good and shouldn't be avoided.

#### Stefan

##### Member
The average number of corner-edge pairs converges to 1 for a fully random scramble because there are 24 possible corner edge pairs and each one has a 1 in 24 chance of being joined
I'm wondering whether that's true. The 24 possible pairs aren't fully independent (for example it's impossible to have exactly 23 pairs), so I have doubts whether we can just add the 24 values of 1/24. Thoughts?

#### qqwref

##### Member
We could generate a whole bunch of random scrambles and check how many c/e pairs they have. I would think the expected value would be near 1, although it may not be exact.

#### CarlBrannen

##### Member
I'm wondering whether that's true. The 24 possible pairs aren't fully independent (for example it's impossible to have exactly 23 pairs), so I have doubts whether we can just add the 24 values of 1/24. Thoughts?
Nice observation!

Maybe here's a way of getting around it...

Unassemble a cube. Pick a corner and an edge at random. Now assemble the rest of the cube randomly. Is the expected number of edge matches equal to 21/24? (I'm guessing that the number will depend on whether or not the corner and edge happen to match, but that the expected number of matches will be 21/24.) Now you can get a random cube position by inserting the two missing pieces in only one of the six possible ways. And I think it's possible to figure out the expected number of matches.

But to do the problem, maybe you have to sum over all possible relative choices of the separate cube and edge and it might be hard to do.

#### Stefan

##### Member
I would think the expected value would be near 1, although it may not be exact.
The thing is, it might be exact and I just don't understand why, so maybe some theory master can help me out

Consider the 2x2x1 and its corner-corner pairs. It has six states, one with four pairs, one with zero pairs, four with one pair. So an average of 8/6=4/3 pairs. On the other hand, there are four possible pairs, each with 1/3 chance. Which also leads to 4/3.

Last edited:

#### peterbone

##### Member
Stefan, yes, I did wonder why it was exactly 1 despite the non-independence between pairs. It does seem to be exactly 1 from my results though. I also tested a 1000 move scramble 100000 times and it came to 1 to three decimal places. It's no wonder that colour neutral solvers have an advantage when there's a 50/50 chance that they'll get a corner-edge pair that they can make full use of.

qqwref, I may re-run my program with cancellations then. Do you just have to check cancellations between consecutive pairs of turns or is it more complex than that?

#### qqwref

##### Member
Do you just have to check cancellations between consecutive pairs of turns or is it more complex than that?
The rule is, you can't use the same face twice in a row, and if you use one face and then the opposite face you can't immediately use the first face again. So you don't need to check for cancellations, just avoid anything of the form FF or RLR.

#### Stefan

##### Member
The thing is, it might be exact and I just don't understand why, so maybe some theory master can help me out
Oh well, just needed some non-busy time to think.

It's exactly 1.

The obvious way to determine the average number of connected pairs is to look at each state, count the connected pairs, sum it all up, and divide by the number of states. Like so:

Code:
counter = 0
for each possible state:
for each possible pair:
if the pair is connected in that state:
increase counter by 1
print counter / numberOfAllStates
When looking at some state, the pairs indeed aren't independent. If the first 23 pairs are all connected, then the last one must be connected as well. For other constellations of the first 23 pairs, the last one must *not* be connected.

But here's the thing: The set of possible states and the set of possible pairs are fixed, they don't depend on each other. So I can switch the loops without changing the result:

Code:
counter = 0
[COLOR="#FF0000"]for each possible pair:
for each possible state:[/COLOR]
if the pair is connected in that state:
increase counter by 1
print counter / numberOfAllStates
Here it is clear that the pairs don't influence each other, because we're looking at them one after the other without context, not inside the context of a specific state. In terms of the 2x2x1 I looked at earlier: The original perspective, counting pairs for each state, gives 4+0+1+1+1+1, which is complicated. The other perspective, counting states for each pair, gives 2+2+2+2, which is much nicer. For each of the 4 pairs, 2 out of the 6 states have that pair connected. So the average is 4*(2/6) (or (4*2)/6, reflecting the above program more closely). And for the 3x3x3, we can indeed say 24*(1/24). Considering all possible states, the average number of connected pairs is exactly 1.

Last edited:

#### Stefan

##### Member
It's no wonder that colour neutral solvers have an advantage when there's a 50/50 chance that they'll get a corner-edge pair that they can make full use of.
With the average being 1, I doubt that's a 50/50 chance. How did you get this?