# Shouldn't 17 Scramble Moves be Enough?



## SF (Dec 30, 2015)

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 (Dec 30, 2015)

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 (Dec 30, 2015)

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 (Dec 30, 2015)

SF said:


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


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 (Dec 30, 2015)

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 (Dec 30, 2015)

mark49152 said:


> 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 (Dec 30, 2015)

theZcuber said:


> 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 (Dec 30, 2015)

theZcuber said:


> 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 (Dec 30, 2015)

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.



SF said:


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



SF said:


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



SF said:


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



JustinTimeCuber said:


> 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 (Dec 31, 2015)

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 (Dec 31, 2015)

SF said:


> 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 (Jan 1, 2016)

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!



Tony Fisher said:


> 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 (Jan 1, 2016)

SF said:


> 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 (Jan 1, 2016)

SF said:


> 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 (Jan 1, 2016)

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 (Jan 1, 2016)

Antonie faz fan said:


> 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 (Jan 1, 2016)

guysensei1 said:


> 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 (Jan 1, 2016)

Antonie faz fan said:


> 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 (Jan 1, 2016)

Antonie faz fan said:


> 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 (Jan 1, 2016)

mark49152 said:


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


----------



## SF (Jan 1, 2016)

OK I think I get it now. Not all scrambles are alike. With just random moves, you'd need a whole bunch to create a "random state" cube. I wasn't aware that some programs produce random state scrambles that aren't just a series of n random moves but are really a much longer series of random moves then partially or fully optimized into an "algorithm" of n moves.

I see that Cube Explorer (a very cool program btw) has an option to generate WCA scrambles. I'm assuming these are random state. So I had the program produce 5 WCA scrambles. They are all in the low 20s in terms of the length of the algorithm, but they still aren't fully optimized. So I'm wondering why that is? I had the Cube Explorer program optimize the 5 scrambles (which takes a while), and ended up with four 18 move scrambles and one 17 move scramble.View attachment 5777

Is the reason why the WCA scrambles aren't fully optimized because of a concern that some competitors could actually memorize the series? That seems far-fetched. Or is there a concern that the length of the scramble would give away the difficulty level of the solve? If that's the case, why not make all WCA scrambles exactly 20 moves in length? If the fully optimized algorithm is only 16 or 17 moves for example, I'm sure the computer could figure out a way to add additional cancelling moves to reach the same cube state (pretty sure anyway).

With random state scramble generators (which admittedly I only found out existed as of yesterday) & optimizer programs, I just don't understand why we would ever have to do practice scrambles of greater than 20 moves (since we know that any cube state can be reached with <=20 moves and we know that we can mimic & optimize random move scrambles of any length, even into the hundreds of moves, using optimized algorithms). I practice solving the cube sometimes 2 or 3 hours in a day. Being able to do all my scrambles at between 16 & 20 moves seems like a really big time-saver and hassle-saver vs. doing 22 to 25 moves or more. It makes practicing more fun and leaves more time for actually solving the cube.

Please tell me if I'm missing something and if anyone knows where to find these shorter random state scrambles without having to wait for Cube Explorer to fully optimize the WCA scrambles.


----------



## shadowslice e (Jan 1, 2016)

SF said:


> OK I think I get it now. Not all scrambles are alike. With just random moves, you'd need a whole bunch to create a "random state" cube. I wasn't aware that some programs produce random state scrambles that aren't just a series of n random moves but are really a much longer series of random moves then partially or fully optimized into an "algorithm" of n moves.
> 
> I see that Cube Explorer (a very cool program btw) has an option to generate WCA scrambles. I'm assuming these are random state. So I had the program produce 5 WCA scrambles. They are all in the low 20s in terms of the length of the algorithm, but they still aren't fully optimized. So I'm wondering why that is? I had the Cube Explorer program optimize the 5 scrambles (which takes a while), and ended up with four 18 move scrambles and one 17 move scramble.View attachment 5777
> 
> ...



See my post above. In essence it is dwon to computer power and speed. The program uses Kociemba and IDA* to create a realtively short scramble so that the state can be reached more quickly when a human scrambles.

It does not need to create optimal scrambles as this uses more processing power and hence takes longer with little (if any) benefit. The point is, finding more optimal solutions would take longer than it would for you to do maybe 2-6 more moves.

This is also why the WCA uses random move scrambles on larger cubes and megaminx because no one has developed a program or method which can efficiently get to each state quickly (or in the amount of time a person would want to wait for new scrambles in a session) without a large amount of processing power.


----------



## SF (Jan 1, 2016)

Thanks shadowslice. I did read your earlier post and it was very helpful, especially in defining "random state." I just don't know if I can fully buy-in to the argument about computer processing speed. On my generic 2 year-old home pc, I'm sure I could generate a few hundred fully optimized random state scrambles per day using Cube Explorer. (Actually, strike that, I guess the website is doing the processing, not my computer.) At any rate, while I agree it isn't worth it for me to spend the time and energy to have Cube Explorer generate marginally shorter scrambles for my own use, why can't some bright kid write a program that "stockpiles" these scrambles? Or why doesn't the Cube Explorer guy do it? He could be generating these shorter algorithms 24 hours a day and always have a huge stockpile for users to draw upon online. It wouldn't matter to me that the scrambles aren't being generated in real time since, to quote Allen Iverson, "we're talking about practice here."

Am I the only one out there who sees value in making scrambles shorter? If we do thousands of practice scrambles per year, then wouldn't lowering the average length from, say, 25 to 18 be a huge benefit? That's a 28% reduction in scramble moves. Even for the fastest cubers, that's a significant percentage reduction in the time spent scrambling their cubes.


----------



## shadowslice e (Jan 1, 2016)

SF said:


> Thanks shadowslice. I did read your earlier post and it was very helpful, especially in defining "random state." I just don't know if I can fully buy-in to the argument about computer processing speed. On my generic 2 year-old home pc, I'm sure I could generate a few hundred fully optimized random state scrambles per day using Cube Explorer. (Actually, strike that, I guess the website is doing the processing, not my computer.) At any rate, while I agree it isn't worth it for me to spend the time and energy to have Cube Explorer generate marginally shorter scrambles for my own use, why can't some bright kid write a program that "stockpiles" these scrambles? Or why doesn't the Cube Explorer guy do it? He could be generating these shorter algorithms 24 hours a day and always have a huge stockpile for users to draw upon online. It wouldn't matter to me that the scrambles aren't being generated in real time since, to quote Allen Iverson, "we're talking about practice here."
> 
> Am I the only one out there who sees value in making scrambles shorter? If we do thousands of practice scrambles per year, then wouldn't lowering the average length from, say, 25 to 18 be a huge benefit? That's a 28% reduction in scramble moves. Even for the fastest cubers, that's a significant percentage reduction in the time spent scrambling their cubes.



Because if you want optimal scrambles for all states you would need a few petabytes of space.

There was a team (which incidentally included the "cube explorer guy") who proved God's number was 20 by generating solutions for all the scrambles and they had to use google's supercomputer.

And no your computer is actually doing the processing.

Also, a "few hundred optimal scrambles" is nothing to the quadrillions of possible permutations.


----------



## mark49152 (Jan 1, 2016)

SF said:


> I wasn't aware that some programs produce random state scrambles that aren't just a series of n random moves but are really a much longer series of random moves then partially or fully optimized into an "algorithm" of n moves.


No you still don't get it - perhaps go back and read the thread again.


----------



## shadowslice e (Jan 1, 2016)

mark49152 said:


> No you still don't get it - perhaps go back and read the thread again.



He's since reread some of the other posts since the I think.


----------



## mark49152 (Jan 1, 2016)

shadowslice e said:


> He's since reread some of the other posts since the I think.


According to his post, despite all the explanations in this thread, he still thinks a random state scramble is when you take a really long sequence of say 50 moves for "better randomness" and use a solver to shorten it.

Here's another attempt to explain random state scrambles in even simpler terms.

1. Take your cube and pull it apart. Put all the pieces in a bag and shake to mix.

2. Now, decide which cubie position you're going to fill first. Let's say it's the FB edge. Put your hand in the bag, pull out some random edge, and put it in the FB position. Make sure you insert it in a random orientation too! Maybe flip a coin, or don't look at the colours until after you've inserted it.

3. Continue until you've fully reassembled the cube with all pieces in random positions and orientations.

4. Go to Cube Explorer and input the colour pattern of your randomised cube. Click solve. The resulting solution will solve your random cube state, and thus the inverse of that solution will scramble a solved cube back to your random state. This is what is called a "random state scramble".

5. Only about 1/12 of your randomly reassembled cubes will be solvable, due to parities and twists. If unsolvable, go back and start again. When you are expert (like scrambling software) you can take care when inserting the last three pieces to make sure the cube is solvable.


----------



## SF (Jan 1, 2016)

mark49152 said:


> According to his post, despite all the explanations in this thread, he still thinks a random state scramble is when you take a really long sequence of say 50 moves for "better randomness" and use a solver to shorten it.
> 
> Here's another attempt to explain random state scrambles in even simpler terms.
> 
> ...



OK thanks. I do get that a random state scramble is one in which there is essentially an equal probability that any one of the 43 quintillion possible cube states will result, and your example of disassembling and reassembling the cube seems like a good intuitive way to get there (at least 1 in 12 times). What I'm not sure of is how many random turns on a solved cube is enough to get there. Maybe it's hundreds, maybe it's thousands, maybe many more than that. But as long as we have software programs that can virtually disassemble and reassemble the cube to a random state, it doesn't matter if I know the answer. Because I can rely on these programs to create algorithms to get me to true random states. 

What I wasn't getting before is that the scrambler programs (at least the good ones) aren't just returning a series of random moves, they're returning an algorithm that's an efficient way to get to the random cube state they've already picked. So they don't just take the letters "LRUDFB" (adding a 2, a prime, or nothing) and pick one randomly for each step in the scramble, thereby getting to the cube state that would result. Instead, it's the reverse - they're starting with the random cube state and then arranging the moves to arrive at that cube state.

Big difference, and there are some interesting consequences to this. Like now I'm going to be more careful that I don't make careless errors in performing my scrambles. Before, I felt it really didn't matter if I accidentally did a B' instead of a B as long as I was doing the same number of moves. Now I realize that a single error will most likely invalidate the "random state" of the scrambled cube.

I guess another consequence is that I need to start with a solved cube before performing the scramble. In the past, if I screwed up a solve & didn't feel like completing it I would just do the scramble on a partially solved cube. Seems like that would also invalidate the random state.


----------



## mark49152 (Jan 1, 2016)

SF said:


> What I'm not sure of is how many random turns on a solved cube is enough to get there. Maybe it's hundreds, maybe it's thousands, maybe many more than that.


It's an interesting question anyway and I don't know the answer, although I would hazard a guess that you would never actually reach an even distribution, just asymptotically converge on it. You would also need to make sure that scramble lengths are evenly distributed between odd and even numbers of quarter turns. As you point out though, it doesn't really matter, because there are quicker and more accurate ways to ensure an even distribution of random states.



SF said:


> What I wasn't getting before is that the scrambler programs (at least the good ones) aren't just returning a series of random moves, they're returning an algorithm that's an efficient way to get to the random cube state they've already picked. So they don't just take the letters "LRUDFB" (adding a 2, a prime, or nothing) and pick one randomly for each step in the scramble, thereby getting to the cube state that would result. Instead, it's the reverse - they're starting with the random cube state and then arranging the moves to arrive at that cube state.


Correct, you got it now .



SF said:


> Big difference, and there are some interesting consequences to this. Like now I'm going to be more careful that I don't make careless errors in performing my scrambles. Before, I felt it really didn't matter if I accidentally did a B' instead of a B as long as I was doing the same number of moves. Now I realize that a single error will most likely invalidate the "random state" of the scrambled cube.
> 
> I guess another consequence is that I need to start with a solved cube before performing the scramble. In the past, if I screwed up a solve & didn't feel like completing it I would just do the scramble on a partially solved cube. Seems like that would also invalidate the random state.


That's another interesting question. I don't think this kid of error impacts on the randomness of the scramble. Think of it this way: a single quarter turn does a 4-cycle of corners and a 4-cycle of edges. So if you make a single quarter-turn error, what you end up with is a random cube state with 4 edges and 4 corners cycled (not necessarily on the same face any more, of course). Is that any less random? As far as I can see, no, as long as the error is genuinely random and not derived from the state of the cube at the time. If I take a random cube state, and apply two random 4-cycles, the result is still random. 

Compare to this: I have a random number generator that gives me an even distribution of numbers between 1 and 10. Occasionally, randomly, I add 1 to the result (modulo 10). The result is still a random number, with the same distribution. The randomness would only be compromised if the act of adding 1 is derived somehow, for example by adding 1 iff the initial value is <5.

The same logic applies to your second example. The new scramble isn't designed to manipulate the specific unsolved cube state, so how could any of the randomness be invalidated?


----------



## SF (Jan 1, 2016)

Thanks Mark. Had to look up some of the words in your explanation, but it definitely makes sense! 



shadowslice e said:


> Because if you want optimal scrambles for all states you would need a few petabytes of space.
> 
> There was a team (which incidentally included the "cube explorer guy") who proved God's number was 20 by generating solutions for all the scrambles and they had to use google's supercomputer.
> 
> ...



I may have overestimated the difference in length between Cube Explorer's instant scramble vs. their optimal scramble for a given random cube state. After using the program a little more, I'm seeing that most of the instant scrambles are averaging between 20 & 21 moves, while most of the optimized scrambles are between 17 & 18 moves. So I'm really only saving about 3 moves between the two (about 15% fewer moves). And it does take a long time to resolve the optimal scrambles, especially if I do a large block simultaneously.


----------



## campos20 (Jan 2, 2016)

It takes at most 20 moves for solving the cube, therefore, some combinations can't be solved with 17 moves. This means that there would be no scramble for this positions. If you allow only 17 moves, you could get about 15 out of 43*10^18 possibilities. It's about 30%.


----------



## shadowslice e (Jan 2, 2016)

campos20 said:


> It takes at most 20 moves for solving the cube, therefore, some combinations can't be solved with 17 moves. This means that there would be no scramble for this positions. If you allow only 17 moves, you could get about 15 out of 43*10^18 possibilities. It's about 30%.



Yeah the OP gets it now. He was working on the assumption that most 17 move scrambles are no harder than the 20 move scrambles and there are far too many to memorise them all.

It was cleared up after the random state was explained and how scramblers work.


----------



## Lucas Garron (Jan 3, 2016)

mark49152 said:


> That's another interesting question. I don't think this kid of error impacts on the randomness of the scramble. Think of it this way: a single quarter turn does a 4-cycle of corners and a 4-cycle of edges. So if you make a single quarter-turn error, what you end up with is a random cube state with 4 edges and 4 corners cycled (not necessarily on the same face any more, of course). Is that any less random?



Yes. Yes, it is less random. Suppose you're scrambling a 1x3, and the scrambles are: L, L R, L R2, L R', L2, L2 R, L2 R2, L2 R', L', L' R, L' R2, L' R', R, R2, R'

Now suppose you "accidentally" do an R turn instead of an L turn sometimes. In those cases, you'll never scramble the left layer!

The same is the case if you accidentally do an R' turn instead of an R turn sometimes. The effect is much, much smaller, but you're almost certainly going to bias the outcome.



mark49152 said:


> As far as I can see, no, as long as the error is genuinely random and not derived from the state of the cube at the time. If I take a random cube state, and apply two random 4-cycles, the result is still random.



Only if the combined effect of the 4-cycles is independent of the cube state.

Doing a certain wrong turn is *not* independent of the scramble (which is clearly not independent of the cube state). Perhaps you mix up the direction of D sometimes. Maybe R turns. The frequency of D turns or of double turns now affects your chance of biasing the scramble. Same reasoning as above.



mark49152 said:


> The randomness would only be compromised if the act of adding 1 is derived somehow, for example by adding 1 iff the initial value is <5.



This is mostly just reiteration, but this is the core of the problem. Doing certain scramble turns wrong is biased exactly like adding 1 iff the initial value is <5. It just has an effect that is not practical to measure concretely.


----------



## mark49152 (Jan 4, 2016)

Lucas Garron said:


> Doing certain scramble turns wrong is biased exactly like adding 1 iff the initial value is <5. It just has an effect that is not practical to measure concretely.


True, but that's not a random error. I did say random error. You are correct that if you apply some rule, consistently, like always inverting B/B', you may well skew the distribution.

Actually scramblers could address that by choosing the solution to a given random state randomly rather than deterministically. I don't know if any do, since it's really far too tiny an issue to care about .


----------



## Lucas Garron (Jan 4, 2016)

mark49152 said:


> True, but that's not a random error. I did say random error. You are correct that if you apply some rule, consistently, like always inverting B/B', you may well skew the distribution.



My argument shows that i's problematic even if you do it consistently. If you make it a "random" error, that doesn't make it better.



mark49152 said:


> Actually scramblers could address that by choosing the solution to a given random state randomly rather than deterministically. I don't know if any do, since it's really far too tiny an issue to care about .



... read the rest of this thread? ;-)


----------



## SF (Jan 4, 2016)

Since I've been using Cube Explorer to generate random state scrambles, my average solve time has gone up by about two seconds (about 43 vs. 41 seconds). We're only talking about 100 solves or so since I made the change from 17 moves on the jaapsch.net site to the CE site, so maybe the two things aren't related. But maybe they are, since I could be getting more flipped edges, etc. 

The jaapsch site says in the help section, "The scrambles will not contain any moves that cancel each other, nor moves that simplify to a cube rotation." I wonder what that means. Is he saying he's generating something like random state scrambles, or just that he never repeats turning the same face twice in a row? Not that important that I find out the answer since I'm now using Cube Explorer, but my (unscientific) results so far are telling me that if I do true random state scrambles (and I'm careful not to make mistakes), the solutions are a little more difficult.


----------



## CubeWizard23 (Jan 4, 2016)

SF said:


> Since I've been using Cube Explorer to generate random state scrambles, my average solve time has gone up by about two seconds (about 43 vs. 41 seconds). We're only talking about 100 solves or so since I made the change from 17 moves on the jaapsch.net site to the CE site, so maybe the two things aren't related. But maybe they are, since I could be getting more flipped edges, etc.
> 
> The jaapsch site says in the help section, "The scrambles will not contain any moves that cancel each other, nor moves that simplify to a cube rotation." I wonder what that means. Is he saying he's generating something like random state scrambles, or just that he never repeats turning the same face twice in a row? Not that important that I find out the answer since I'm now using Cube Explorer, but my (unscientific) results so far are telling me that if I do true random state scrambles (and I'm careful not to make mistakes), the solutions are a little more difficult.



Basically the jaapsch site is saying it won't do R R' or say you are doing 2x2 U D' etc. 

e: to answer your question the solves may be harder but a 2 second jump when averaging sup 40 isn't too uncommon, plus these are the types of scrambles you will get in competitions so its best to practice with these


----------



## mark49152 (Jan 4, 2016)

Lucas Garron said:


> My argument shows that i's problematic even if you do it consistently. If you make it a "random" error, that doesn't make it better.


Let's take scrambles for all 43 quintillion states. Now apply an error to each scramble. In effect, you are now selecting a new random state 43 quintillion times, and can expect some duplicates, meaning some other states are never reached. I don't have time to do the math so it is likely wrong but let's assume 30% of states are never reached. 

Now let's take the same set of scrambles and apply the same errors, because we consistently forget which way round B/B' are on the first B turn, etc. You will end up with the same set of states never being reached. So you have indeed skewed the distribution. Those 30% of states are never reachable. Unless I misunderstood you, this is the point I thought you were trying to make above about errors biasing the outcome.

Now let's take the same set of scrambles and apply a different (random) set of errors. Again, 30% of states won't be reached, but this time, because they are different errors, it's not the same set of states. It's a different 30%. Repeat ad infinitum and observe that the distribution evens out. Nothing you have said so far has convinced me that random + random != random.

You could of course analyze every possible error to each of those 43 quintillion scrambles and plot the frequency at which each state occurs and show that they are no longer evenly distributed, but the margins of error are becoming increasingly irrelevant to practical cubing.



Lucas Garron said:


> ... read the rest of this thread? ;-)


I've been reading and posting since the start so maybe you can be more specific about what I've missed. However, I'll also try to explain better what I meant. A random state scrambler generates a random state and then finds a solution to that state, returning the inverse as its output. However, there are many possible solutions to each state, as you know. The effect described in my second para above, where we apply the same errors and get the same set of unreachable states, depends on the same set of scrambles being used. If the scrambler were to instead choose randomly from the set of possible solutions to each random state, then we would get different scrambles each time, even for the same random state, and the effect of the errors would therefore be different.


Anyway... I think this is getting somewhat distanced from the question, which was whether an error in scrambling can compromise the "randomness" of a scramble. Defining randomness in terms of distribution is fine from a theoretical viewpoint but I guess what most people are thinking when they ask that question is whether an error is likely to make the scramble easier to solve, meaning more blocks or pairs already formed, or whatever, which depends on event and method anyway. There's a tendency to think that each move in a scramble is performing some direct function in mixing up the cube and if that function is impaired the cube will not be properly mixed. That was what I was thinking of when I made my original comment about 4-cycles, and to me it's a more interesting and pragmatic question, although I have no better ideas on how to answer it.


----------



## Lucas Garron (Jan 5, 2016)

mark49152 said:


> Anyway... I think this is getting somewhat distanced from the question, which was whether an error in scrambling can compromise the "randomness" of a scramble.



The only correct answer is "yes, it does".



mark49152 said:


> Repeat ad infinitum and observe that the distribution evens out.



This is where your argument fails. Unless you do something specific and systematic (e.g. randomly add a U turn at the end half of the time after generating a scramble), there is absolutely no guarantee that the distribution "evens out" if you make different kinds of errors.

As I've pointed out above, the (possible, and therefore actual) errors depend on the scramble, which depends on the state.
I don't think you can come up with a good way to characterize the random errors humans make while scrambling, but you cannot assume that the distribution evens out until a) you do come up with a way to characterize the errors, and b) prove that it the distribution evens out for the scramble programs you care about.



mark49152 said:


> You could of course analyze every possible error to each of those 43 quintillion scrambles and plot the frequency at which each state occurs and show that they are no longer evenly distributed, but the margins of error are becoming increasingly irrelevant to practical cubing.



Ah, yes. The margins may be very small. But can you prove it?

(I suspect not. And if not, you should not assume they're small.)


----------



## mark49152 (Jan 5, 2016)

Lucas Garron said:


> The margins may be very small. But can you prove it?


As I said, I'm not inclined to, because I don't think it's practically relevant. The question of whether errors skew scramble distribution is purely academic because what most people care about is one scramble and one error at a time. Oops, I think I did a B instead of a B' there, does that mean there is now something inherently unfair about the state of my cube such that I should exclude this solve from my average? The fact that if I deliberately made that same error on every scramble I might only be seeing a possible 30 quintillion cube states instead of all 43 is nothing more than a mathematical curiosity.



Lucas Garron said:


> The only correct answer is "yes, it does".


Maybe the question should be whether it affects it in a meaningful way, and indeed how we define randomness for the purpose of the question.


----------



## Lucas Garron (Jan 5, 2016)

mark49152 said:


> Maybe the question should be whether it affects it in a meaningful way, and indeed how we define randomness for the purpose of the question.



I don't think it's useful to try to define "meaningful" in order to make yourself feel better about miss-scrambles. If you know you made a mistake while scrambling, you should not treat it as any more random than a hand scramble.

And I insist that you cannot call it "purely academic" until you've (academically?) determined how bad the error is.
20-move random-move scrambles seem fine, but turn out to have a bad edge distribution that definitely affects solves, especially record times. You cannot simply dismiss the effect of scrambling errors out of hand, regardless of how deliberate or accidental they are.


----------



## mark49152 (Jan 6, 2016)

Lucas Garron said:


> 20-move random-move scrambles seem fine, but turn out to have a bad edge distribution that definitely affects solves, especially record times.


A study of how edge distribution is affected by inserting errors into random state scrambles would be interesting to see.


----------



## SF (Jan 8, 2016)

It turns out that Mr. Kociemba from Cube Explorer actually provides a list of 100,000 optimal solutions to random state cubes on his website (http://kociemba.org/cube.htm). They're in a text file in the "God's Number is 20" section under the first "Optimal Cube Solver" graph. His average number of moves was 17.7. There were no 20-move solutions in the 100,000 solves, which makes sense since the odds of getting a random cube state with a 20 move optimal solution is only about 1 in 88 billion.

Anyway, I'm assuming I can just apply his solution moves to a solved cube and end up with a random cube state each time. I'm going to start with number 1 and just go down the list. In this way, I'll get the shortest possible scrambles which will save time, and because there are less moves, it should reduce the chances of my making errors and invalidating the random cube state.

Very happy about this! Just hope I'm not missing something that would invalidate my assumption that these would be true random state scrambles.


----------



## shadowslice e (Jan 8, 2016)

They may be fairly random scrambles if you choose them randomly but as you are limiting yourself to 100,000 scrambles (some of which may be pretty easy) they you only have a 1/100,000 chance of getting any scramble as opposed to the 1/43 quadrillion with a truly random state scrambler. In addition, it is entirely possible that all of those scrambles have an element in common hence why Kociemba uploaded those specific one as they may have been the first few scrambles he generated (this is also likely why there are no 20 move solutions cause they didn't get to solving most of those until later because that used exponetially more processing power and time).


----------



## AlphaSheep (Jan 8, 2016)

As far as I know, they are randomly generated, so they should be fine. Although shorter doesn't necessarily mean faster to scramble. Often a longer scramble that has easier move combinations will be faster than a shorter one with awkward move combinations. I think you're worrying about optimisation beyond what is reasonable. Rather solve faster to save time - it is more directly relevant to your end objective.


----------



## SF (Jan 8, 2016)

AlphaSheep said:


> As far as I know, they are randomly generated, so they should be fine. Although shorter doesn't necessarily mean faster to scramble. Often a longer scramble that has easier move combinations will be faster than a shorter one with awkward move combinations. I think you're worrying about optimisation beyond what is reasonable. Rather solve faster to save time - it is more directly relevant to your end objective.



True dat. Especially your last sentence. 

Wouldn't it be fun though if some of the really fast speedcubers out there had an informal competition using the Kociemba list? Obviously, each person would be self-policing their times, DNFs, etc., but they could report their stats for the first 100 scrambles, the first 500, or any series in the list of 100,000. You can copy the text from the Kociemba file, paste it into Excel, and number the algs from 1 to 100,000 (I did this last night). Then you can add a column to the right for recording solve times for each row.

Since each person would be solving the identical cube states, the results would be a true apples to apples comparison. The benefit for me and maybe for others who are trying to improve is that we could compare our much slower times on a line-by-line basis to see if there is any correlation between the relative difficulty of each solve for the experts vs. the relative difficulty for us.

I guess we'd have to determine certain things in advance, like color orientation during the scrambles.


----------



## Herbert Kociemba (Jan 17, 2016)

I just read this discussion about the 100000 scrambles. Yes, these are random positions using the Mersenne-Twister random number generator.


----------



## SF (Jan 19, 2016)

Thanks Mr. Kociemba. I appreciate your replying and confirming these are a random sample. I've been using the 100M scrambles for practicing solves (just going in order, I'm on #374). I did a little bit of analysis of the scrambles (I should say "solutions"), and the moves are very evenly spread throughout each series. I did notice that there is a slightly heavier weighting on D, L, & B moves as the first move, and a significantly heavier weighting on the U moves as the last step in the longest solutions (19 moves). Of the 3,303 19-move solutions, 2,900 are U', 332 are U2, 52 are U, 15 are R', 3 are R2, and 1 is B'. I find that interesting since I know your program for finding optimal solutions doesn't use the CFOP method that many of us humans use. Yet, using CFOP, I most often end up with a U (AUF) move at the end of solves, especially if I don't do the AUF prior to the PLL (though obviously not as often as your 19 move solutions do). 

The other thing that surprised me (and maybe it shouldn't have) was how often two opposing faces are turned consecutively. I just assumed optimal scrambles would have fewer of these since I figured they'd be less efficient in solving the cube. Though now that I think about it there are quite a few OLL & PLL algs that contain either slice moves or consecutive opposing face moves.


----------



## Herbert Kociemba (Jan 19, 2016)

SF said:


> I did notice that there is a slightly heavier weighting on D, L, & B moves as the first move, and a significantly heavier weighting on the U moves as the last step in the longest solutions (19 moves).


In principle, the optimal solver generates all possible maneuvers for depth 1, 2, 3, 4 ... in the lexicographical order U, R, F, D, L B. Most cubes are solvable within <= 18 moves, but there are so many 19 move maneuvers that for those cubes which need 19 moves there usually are many solutions, surely evenly distributed concerning the first move. But my program just takes the first solution which then of course often happens to be an U-move.


----------



## SF (Jan 19, 2016)

Thanks for the explanation. Interesting.


----------



## efattah (Apr 17, 2016)

For what its worth, I found this discussion interesting, and I usually scramble my cubes manually (no PC generated scrambles). So I tried doing an average with cube explorer generated scrambles and guess what: the cubes were easier to solve. One average isn't enough, but this is what I noticed:
1. When I scramble my cubes manually, I use around 40 moves, but I watch the cube and I purposely and deliberately break up any patterns or clusters that I see. This means when I actually start the solve, I rarely can find anything to work with in terms of pre-built sections.
2. When I used the PC generated scrambles, there were VERY OFTEN pieces together, making the start of each solve easier.

This reminds me of when I watched Chris Olsen's video on making efficient 2x2 faces. I think in 11 of 12 example solves (each with PC generated scrambles), the cube started with a random bar of two face pieces or more. I was rolling my eyes in his 'luck' since when I scramble my own cubes I never get those 'lucky' situations because I purposely break up any patterns or blocks.

I think it also goes without saying that one person's 'lucky' scramble is another person's nightmare; depending on which method they use, which color(s) they prefer, and so on. A CFOP solver could be given a cube with all the corners already solved, and they would gain nothing from that, whereas a corners first solver would be a third through his solve. Or vice versa in terms of pre-built crosses.

Eric Fattah
Vancouver, BC


----------



## 00 (Apr 18, 2016)

EminentCuber said:


> Every single scramble can be done in 20 or fewer moves. The way the WCA (and the general cubing community) agreed that a 20 move scramble was enough is because it was god's number.



no.



EminentCuber said:


> For this very reason, scrambles are easier and not the difficulty wished upon by the WCA. If the WCA was okay with excluding the permutations that take 18 or more moves to create, than they would make the scrambles 17 moves. In essence, the WCA is controlling the difficulty by changing the number of moves.



no.

_


EminentCuber said:



If they made a scramble 17 moves, it would be easier, and not what the WCA wants.

Click to expand...

_
no.

I suggest you look up what random state scrambles are.


----------

