Shouldn't 17 Scramble Moves be Enough?

[SF]

I'm new to the forum even though I've been cubing (3x3x3) for almost 2 years. I enjoy practicing solves but don't enjoy the drudgery of doing the scrambles each time, so I tried to figure out the minimum # of scramble moves I can do and still get a good randomized cube to solve. I haven't found anything definitive online, but most things I've read recommend 20+ moves to scramble.

So I did the math myself, trying to remember my statistics from college, and here's what I came up with:

Using the half move metric (with no slice moves), there are 18 possible first moves in any scramble. That's 6 sides times 3 moves (X, X' & X2). Then for each subsequent move, there are 15 possible moves (5 sides x 3) since we never turn the same face consecutively. So using a simple formula, I figured the probabilities of getting two identical cube states after random scrambles of the same length. The formula is:

[# of possible changes in the cube after the 1st scramble move, or 18] X ([# of possible changes in the cube after each scramble move after the 1st, or 15]^[# of total scramble moves after the 1st move, or total scramble moves minus 1])

If I use 16 moves for my scramble length, the formula is 18 X 15^15 = 7,882,090,026,855,470,000, meaning the chances are 1 in 7.88 quintillion that I will end up with a particular cube state.

If I use 17 moves for my scramble length, the formula is 18 X 15^16 = 118,231,350,402,832,000,000, meaning the chances are 1 in 118 quintillion that I will end up with a particular cube state.

Since I know from Wikipedia that there are 43,252,003,274,489,856,000 (43 quintillion) possible Rubik's cube states (not counting rotated center pieces), I'm figuring that 16 scramble moves isn't quite enough but 17 should be plenty. At 17 moves, the odds of reaching a particular cube state is theoretically over 2.5 times higher than the total # of possible cube states.

I know there must be a flaw in my reasoning above, especially since I know from reading that there are many cube states that cannot be solved with less than 20 moves. Plus I recently read (maybe on this website) that random scrambles as long as 35 or more moves have been recommended to create more difficult cases to solve in 3x3x3 competitions.

So I'm guessing that either my math is wrong or I'm applying the formula in a faulty way. Obviously there are cube states that cannot be reached with only 17 scramble moves despite my math showing the 1 in 118 quintillion chance of repeating a cube state. If anyone out there knows why this is and can explain it, I would appreciate it. I suspect it has something to do with moves cancelling each other out. Thanks, and sorry for the long question!

 

[newtonbase]

The scramble isn't just about creating unique states it's about creating a state that is reasonably difficult to solve. I agree that with 17 move scrambles you are not likely to come across the same state twice but you could still end up with a solve shorter than those 17 moves. .

 

[rumarfer28]

You can get two identical cube states with two different sequences. For example: R L and L R let the cube in the same state.
You can't have 1/118 quinillion chances to end up with a particular state because there aren't so many states.

 

[JustinTimeCuber]

I'm new to the forum even though I've been cubing (3x3x3) for almost 2 years. I enjoy practicing solves but don't enjoy the drudgery of doing the scrambles each time, so I tried to figure out the minimum # of scramble moves I can do and still get a good randomized cube to solve. I haven't found anything definitive online, but most things I've read recommend 20+ moves to scramble.

So I did the math myself, trying to remember my statistics from college, and here's what I came up with:

Using the half move metric (with no slice moves), there are 18 possible first moves in any scramble. That's 6 sides times 3 moves (X, X' & X2). Then for each subsequent move, there are 15 possible moves (5 sides x 3) since we never turn the same face consecutively. So using a simple formula, I figured the probabilities of getting two identical cube states after random scrambles of the same length. The formula is:

[# of possible changes in the cube after the 1st scramble move, or 18] X ([# of possible changes in the cube after each scramble move after the 1st, or 15]^[# of total scramble moves after the 1st move, or total scramble moves minus 1])

If I use 16 moves for my scramble length, the formula is 18 X 15^15 = 7,882,090,026,855,470,000, meaning the chances are 1 in 7.88 quintillion that I will end up with a particular cube state.

If I use 17 moves for my scramble length, the formula is 18 X 15^16 = 118,231,350,402,832,000,000, meaning the chances are 1 in 118 quintillion that I will end up with a particular cube state.

Since I know from Wikipedia that there are 43,252,003,274,489,856,000 (43 quintillion) possible Rubik's cube states (not counting rotated center pieces), I'm figuring that 16 scramble moves isn't quite enough but 17 should be plenty. At 17 moves, the odds of reaching a particular cube state is theoretically over 2.5 times higher than the total # of possible cube states.

I know there must be a flaw in my reasoning above, especially since I know from reading that there are many cube states that cannot be solved with less than 20 moves. Plus I recently read (maybe on this website) that random scrambles as long as 35 or more moves have been recommended to create more difficult cases to solve in 3x3x3 competitions.

So I'm guessing that either my math is wrong or I'm applying the formula in a faulty way. Obviously there are cube states that cannot be reached with only 17 scramble moves despite my math showing the 1 in 118 quintillion chance of repeating a cube state. If anyone out there knows why this is and can explain it, I would appreciate it. I suspect it has something to do with moves cancelling each other out. Thanks, and sorry for the long question!

You are assuming that all possible scrambles of length n will give a unique state solvable in n moves. However, you don't have to look far to find a counterexample:
R U R' F' R U R' U' R' F R2 U' R' U' (Jb perm, 14 moves)
A possible solution is:
R U2 R' U' R U2 L' U R' U' L (Jb perm, 11 moves)

Because of this, some scrambles are much more likely to occur than others using that scramble method. It's hard to know which ones, but they are far from equally likely. Some scrambles even have no chance whatsoever of occurring, such as superfilp (U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2) which requires 20 moves optimally, and the ones that are more likely to occur are the ones with lengths probably around 14-16 (when using a 17 move scramble). However, there are computer algorithms that can generate a pseudo-random state and generate an algorithm to reach that state (I think it might have to do with solving that state and inverting, but I'm not sure).

 

[mark49152]

There's no minimum optimal solution for a WCA 3x3 scramble. Technically a scramble could require only 2 moves to solve and still be legal. It's just incredibly unlikely.

The actual scrambles used are "random state". That means a random position (not sequence) is generated, then solved by computer, and the inverse of the solution is used as the scramble.

The problem with sequences of random moves is that they tend to leave blocks and other patterns lying around unless you have a very long sequence. Random state scrambles don't suffer from that problem, and also have the advantage of giving the shortest scramble to achieve a truly random state.

 

[cubernya]

There's no minimum optimal solution for a WCA 3x3 scramble. Technically a scramble could require only 2 moves to solve and still be legal. It's just incredibly unlikely.

The actual scrambles used are "random state". That means a random position (not sequence) is generated, then solved by computer, and the inverse of the solution is used as the scramble.

The problem with sequences of random moves is that they tend to leave blocks and other patterns lying around unless you have a very long sequence. Random state scrambles don't suffer from that problem, and also have the advantage of giving the shortest scramble to achieve a truly random state.

Regs do specify that it must be at least 13 moves IIRC

 

[shadowslice e]

Regs do specify that it must be at least 13 moves IIRC

I thought that was only for FMC

Edit: actually, as far as I can see nothing in article 4b has anything on it for any 3x3 other than the 2 move thing.

 

[JustinTimeCuber]

Regs do specify that it must be at least 13 moves IIRC

It's 2
https://www.worldcubeassociation.org/regulations/#4b3
However, I am pretty sure that the scrambler doesn't allow scrambles with <13 move optimal solutions.

 

[Lucas Garron]

To answer the question from the title: 17 isn't enough because some most states require at least 18 moves to solve.

17 random moves are not enough to give a decent distribution of scrambles. Edge orientation is still really lopsided. It may be possible to determine that random-state scrambles with at most 17-move solutions (either optimal or near-optimal scrambles) give a reasonable distribution for human solvers, but it's much simpler and safer to generate a random state and not worry about the exact movecount.

I'm new to the forum even though I've been cubing (3x3x3) for almost 2 years. I enjoy practicing solves but don't enjoy the drudgery of doing the scrambles each time, so I tried to figure out the minimum # of scramble moves I can do and still get a good randomized cube to solve. I haven't found anything definitive online, but most things I've read recommend 20+ moves to scramble.

Where did you read that recommendation? Even 40 random moves are not enough.

Since I know from Wikipedia that there are 43,252,003,274,489,856,000 (43 quintillion) possible Rubik's cube states (not counting rotated center pieces), I'm figuring that 16 scramble moves isn't quite enough but 17 should be plenty. At 17 moves, the odds of reaching a particular cube state is theoretically over 2.5 times higher than the total # of possible cube states.

You've answered your question yourself:

Obviously there are cube states that cannot be reached with only 17 scramble moves despite my math showing the 1 in 118 quintillion chance of repeating a cube state. If anyone out there knows why this is and can explain it, I would appreciate it. I suspect it has something to do with moves cancelling each other out.

You've probably seen various short algs that lead to the same state (e.g. U' R U L' U' R' U L and L D R D' L' D R' D'). Around 17 moves, the number of algs leading to any given state starts to pile up, because a significant fraction states are reachable now.
But as you've also noticed, some states are not reachable yet (because God's number is 20).

It's 2
https://www.worldcubeassociation.org/regulations/#4b3
However, I am pretty sure that the scrambler doesn't allow scrambles with <13 move optimal solutions.

Where does this misconception come from? TNoodle generates a scramble for a (uniformly) random state from those that takes ≥ 2 moves to solve.

 

[leeo]

For my daily practice, I employ ruwix puzzle scramble generator on my cell phone. For the above-mentioned reasons, for the 3x3x3 I select length 29 random-move scrambles. I find that an optimal-move solver usually resolves this to 18 moves, sometimes 17, occasionally 19, and on rare occasions 16. Part of the practice is following 29 moves perfectly.

 

[Tony Fisher]

I'm new to the forum even though I've been cubing (3x3x3) for almost 2 years. I enjoy practicing solves but don't enjoy the drudgery of doing the scrambles each time, so I tried to figure out the minimum # of scramble moves I can do and still get a good randomized cube to solve. I haven't found anything definitive online, but most things I've read recommend 20+ moves to scramble.

I would have thought trying to count the moves each time to save you the extra drudgery of additional moves far more drudging than spending 1 or 2 seconds longer to make sure. In addition a human is very bad at properly randomise things so addition moves are needed to make sure.

 

[SF]

Thanks for all the great replies. I can see now that the formula I was using is wrong on the probability of two scrambles matching.

Several reasons for this. From rumarfer28's reply pointing out that turning two opposite faces consecutively can occur in either order, I needed to reduce the number of possible moves after the first move from 15 to 13.5 (18 possible moves minus 3 for not repeating the same face twice minus 1.5 to eliminate 1/2 of opposite face turns).

With that one adjustment, the odds of 2 scrambles matching at 17 moves goes from 118 quintillion to 1 down to 21.9 quintillion to 1. So then I was at 18 moves minimum, 295.8 quintillion to 1. But that doesn't take into account the examples given by JustinTimeCuber, Lucas Garron and others that there are many cases of 2 or more unique series of moves that returns the cube to the same relative state.

So the formula I was using is just wrong because it cannot factor in the likelyhood that a shorter series of moves will result in the same ending cube state. I guess any scramble greater than 20 moves would by definition have a shorter algorithm to get to the same state. Also, after reviewing Lucas's "not enough" link, I see that increasing the scramble length, even up to 100 moves, increases the chances of more flipped edges, etc.

My goal in asking my original question was to determine a scramble length that's short enough to save time between solves but also long enough to generate starting cube states that are not marginally less difficult to solve than with truly random cube states (i.e.-really long scrambles). I like Leeo's idea of using longer random scrambles and then applying an optimal-move solver to shorten the scramble. I'm now using Cube Explorer 5.12 to optimize scrambles generated by the Ruwix puzzle scrambler. I started with 99 move scrambles, but it was taking Cube Explorer a couple of minutes to optimize the scramble down to 20 moves or less (usually 17 or 18 moves), so now I'm going to try starting with 50 move scrambles.

Thanks Again and Happy New Year!

I would have thought trying to count the moves each time to save you the extra drudgery of additional moves far more drudging than spending 1 or 2 seconds longer to make sure. In addition a human is very bad at properly randomise things so addition moves are needed to make sure.

I wasn't manually trying to make random moves and I wasn't counting up to 17. I was using the website www.jaapsch.net to generate the scrambles. The site allows you to pick any scramble length. Sorry if I wasn't clear on that.

 

[Lucas Garron]

I'm now using Cube Explorer 5.12 to optimize scrambles generated by the Ruwix puzzle scrambler.

If you want scrambles for real-world uses, there's no point in using the Ruwix scrambler or any other random-move scrambler to pick a random state. The distribution will not be uniform (although I guess 99 moves will be close).

Cube Explorer will generate random scrambles for you. Online timers like qqtimer and timer.cubing.net use also generate random-state scrambles close to 20 moves.

I don't know if it's relevant to you others in this thread, but also note that "how many moves Cube Explorer takes to solve the scramble" is not a good way to tell if a scramble is easy for humans.

 

[mark49152]

I'm now using Cube Explorer 5.12 to optimize scrambles generated by the Ruwix puzzle scrambler. I started with 99 move scrambles

The way a random state scrambler works is by generating a random position, not a random sequence. So it's equivalent to dismantling your cube, and then reassembling the pieces truly randomly, with an even distribution of all (solvable) positions. Then a move sequence is generated using a solver.

Why would you use a solver to shorten compromised scrambles? That doesn't make sense, or maybe I'm missing something.

 

[Antonie faz fan]

Scrambles should be 20 moves so that ANY position that is possible to get by just twisting the cube is able to be the scramble that you get. end of discussion.

 

[guysensei1]

Scrambles should be 20 moves so that ANY position that is possible to get by just twisting the cube is able to be the scramble that you get. end of discussion.

Scrambles should be random state. End of discussion.

 

[shadowslice e]

Scrambles should be random state. End of discussion.

Yeah. I think that how random state scrambles work for 3x3x3 may need to be explained to the op so that they understand why scrambles are the way they are. (forgive me if someone has already done this in the thread)

Firstly, there are a few basic ideas needed to have a simple understanding:
1) if you solve a cube, then do the sequence of moves used to solve it backwards, that will scramble the cube to the same position you started with.
2) The method used to scramble is random state (is there is a completely even chance of getting any of the quadrillions of scrambles that you can get merely by twisting the puzzle as if you took the puzzle apart)
3) The solving method that scramblers use is called kociemba (I believe- it has the same basic concept if not) which uses group theory by having 2 phases: reduce to the <R2, L2, F2, B2, U, D> group which is helpful because that are a lot of symmetries; solve. This means that the scrambler will usually find near optimal solutions by using https://www.speedsolving.com/forum/showthread.php?44421-Kociemba-explained-verbally&p=911291&viewfull=1#post911291(Lucas' explanation of Kociemba/IDA') which concentrates on the branches that seem to be most promising.
4) Not all scrambles are equally likely to come up with a random set of moves as there can be multiple routes to the same scramble. This is why random state is used.

From here, the process is simple: you get the program to generate a scramble which is legal (no parities and such) then use Kociemba/IDA* to generate a relatively short near-optimal solution to that state, then invert the solution to get the scramble (w is what is displayed).

Thus, you get the reason why the scrambles created by the scramblers are usually about 20-25 moves long as the scramblers just get a scramble which is short enough for a human to scramble quickly but not optimal (20-) and also incidentally why many scrambles start with a lot of double moves (ie x2s)

 

[mark49152]

Scrambles should be 20 moves so that ANY position that is possible to get by just twisting the cube is able to be the scramble that you get. end of discussion.

Just because 20 moves is enough to reach every position does NOT mean that you get an even distribution of all positions. Read the post above yours to learn what a random state scramble is.

Edit: @shadowslice: Kociemba is irrelevant and overcomplicates your explanation. The principle is simple. Scrambles are generated as STATES and not as move sequences. That's the principle that seems lost on OP and Antonie. It doesn't matter what solver is used although of course it would be annoying if your scramble sequences were 60 move inverse CFOP solves.

 

[EMI]

Scrambles should be 20 moves so that ANY position that is possible to get by just twisting the cube is able to be the scramble that you get. end of discussion.

Are you aware that, using official scrambles, you will not be able to reach all possible Megaminx states? In fact, you only reach a small fraction. That doesn't make the scrambles any easier for humans though.

 

[shadowslice e]

@shadowslice: Kociemba is irrelevant and overcomplicates your explanation. The principle is simple. Scrambles are generated as STATES and not as move sequences. That's the principle that seems lost on OP and Antonie. It doesn't matter what solver is used although of course it would be annoying if your scramble sequences were 60 move inverse CFOP solves.

Yeah I was trying to explain why the scrambles are longer than 20 mo es most of the time. I guess it could be seen as overcomplicated but i though it may be good as a supplement.

I did also go over the basic principles as well in it.