• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Is 20 turns enough for a scramble?

peterbone

Member
Joined
Jun 22, 2006
Messages
210
Location
Lewes, England
YouTube
Visit Channel
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.

resized_prob.png


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
Joined
Jun 16, 2010
Messages
120
Location
The country of riddles
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
Joined
Jun 22, 2006
Messages
210
Location
Lewes, England
YouTube
Visit Channel
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:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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
Joined
Jan 7, 2009
Messages
1,282
Location
North Carolina
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
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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
Joined
May 6, 2012
Messages
367
Location
Pullman, WA
WCA
2013BRAN01
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
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
"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
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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?
 

CarlBrannen

Member
Joined
May 6, 2012
Messages
367
Location
Pullman, WA
WCA
2013BRAN01
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
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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
Joined
Jun 22, 2006
Messages
210
Location
Lewes, England
YouTube
Visit Channel
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
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
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
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
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:
Top