7
$\begingroup$

Take a normal 3x3 rubiks cube (the Classic unmodded cube). I know the WCA method for scrambling is to pick a random (valid) cube state and calculate a sequence of moves to go from solved to that state, for the convenience of the competition scramblers.

AFAIK, this is a very hard thing to implement (I want to make my own scrambler). So I thought "Hey, I'll just print out 20 random moves from the set [F,F',F2,U,U',U2,L,L',L2,R,R',R2,D,D',D2,B,B',B2] and I'll make sure that no face is turned consecutively". But would this actually generate a high quality scramble? Or would it be indistinguishable from a normal WCA scramble?

EDIT

Would there be certain characteristics to my scramble method? And would using mine instead of the WCA page's be detrimental to my WCA performance on real scrambles?

My thinking was that because 20 moves is God's Number for the Rubiks Cube, less would be too easy of a scramble (too little "randomness") and more would be pointless (just like shuffling a deck of cards too much is pointless).

$\endgroup$
  • $\begingroup$ 20 moves is probably going to favour around 10-15 move scrambles, as there would be a large overlap of different paths to the same state, but that’s just my intuition. $\endgroup$ – micsthepick Jul 16 at 22:41
  • $\begingroup$ My thinking was that because 20 moves is God's Number for the Rubiks Cube, less would be too easy of a scramble (too little "randomness") and more would be pointless (just like shuffling a deck of cards too much is pointless). EDIT I put this comment in the question $\endgroup$ – mackycheese21 Jul 16 at 23:16
  • $\begingroup$ I agree with @micsthepick. You might want to try a new method, or maybe just do more scrambles. $\endgroup$ – Don Thousand Jul 16 at 23:19
  • $\begingroup$ Ah, I haven't tried a method yet. Right now my scramble method is "hold it behind the back and turn it randomly for 2 minutes", but I suspect that can be improved on algorithmically in a computer program. What is the simplest, acceptable scramble algorithm that doesn't require a reverse solve? If my described (in the question) algorithm just needs slight modifications, how could I do that? $\endgroup$ – mackycheese21 Jul 16 at 23:29
  • 1
    $\begingroup$ The following observation has essentially nothing to do with the real question you're asking, but: Your proposed method can't possibly, however many turns you do, give results exactly equivalent to the WCA method, because theirs samples uniformly from the set of all configurations, whose size is a multiple of 11, and yours -- always picking uniformly from 18 possible moves -- makes the probability of any particular configuration something with only factors of 2 and 3 in the denominator. $\endgroup$ – Gareth McCaughan Jul 16 at 23:35
8
$\begingroup$

For a scramble to be any good, at the very least you would want every pair of adjacent pieces to become separated at least once during the scramble. You don't want any blocks to remain unscrambled, because that would make it slightly too easy. Here is a very rough calculation of how many moves this takes.

There are $48$ pairs of adjacent pieces ($6$ cutting planes with $8$ pairs of pieces on either side). Imagine you cover it all with sellotape to bind it all together. Every time before you do a move, you use a box cutter to cut along the seam through any tape that blocks the move. The more moves you do, the fewer bits of uncut tape are left. How many moves does it take for there to be none left?

You start with $48$, and before each move you cut along $1/6$th of them, leaving $5/6$th intact. After $n$ moves, you therefore have approximately $48(\frac{5}{6})^n$ pieces of uncut tape left. This only drops below $1$ when $n\ge22$, so if you do fewer than $22$ moves there is a good chance that you have at least one pair of pieces that have never been separated.

Of course this is a very crude calculation, and it assumes that the bits of tape get nicely mixed by the scramble. Nevertheless, it illustrates the point that just because every position can be reached in 20 moves, this does not mean that 20 random moves makes every position equally likely. Positions with some clusters of pieces are more likely than other positions. Any particular position that needs 17 moves to solve is more likely than any particular position that needs 20 moves to solve. This is because there are more ways to reach the former in 20 moves than there are to reach the latter - you can meander and still reach the depth 17 position, or overshoot it and come back a bit, but to reach the depth 20 position you have to move forward with every move. With randomly chosen moves that is not likely.

The WCA used to use 25-move scrambles, but it was found that even that was not quite enough. I've been told that when they switched to a randomly chosen state instead of randomly chosen moves, speedcubers actually noticed a very slight increase in difficulty, as matching pairs of pieces and pairs that can be matched by one move occurred less often.

In practice, scrambles of 25 to 30 random moves are perfectly acceptable provided that they are randomly generated by computer (humans are very bad at random), and that simple move cancellations are avoided. So never turn the same face twice in a row, and after a pair of opposite faces the next move must be different (to avoid RLR for example). While there will be some bias, some positions being more likely than others, you are unlikely to notice any difference in solving difficulty.

$\endgroup$
  • $\begingroup$ Thanks for the answer! I appreciate the mathematical reasoning behind it. Does this mean that a 100% random move scramble as described in my question with around 28 moves would be acceptable? $\endgroup$ – mackycheese21 Jul 16 at 23:33
  • 1
    $\begingroup$ @mackycheese21 In practice, $25$ to $30$ moves is acceptable provided that they are randomly generated by computer (humans are bad at random), and that simple move cancellations are avoided. So never turn the same face twice in a row, and after a pair of opposite faces the next move must be different (to avoid RLR for example). $\endgroup$ – Jaap Scherphuis Jul 16 at 23:38
  • $\begingroup$ Thanks for the help! Marking as accepted and upvoting $\endgroup$ – mackycheese21 Jul 17 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.