# Scrambler algorithm discussion



## gavinmok (Aug 21, 2017)

As we know, there are 2 kinds of scrambler algorithm: random moves & random states. Unfortunately, neither of them is perfect. Random moves makes the scramble sequence long and the scramble result is not good enough. Random states is only available for 'small puzzle', and the generating costs time.
Now everybody believes that random states is better than random moves, but there is still a philosophical question: How do we know the state is random enough? Even for random states algorithms, we cannot be sure that it is fair enough. Maybe we can make it random enough for CFOP (obviously there should not be an entire cross), but how about for Bridge? or Blindfolded? or any unknown solving methods? There is no an objective mathematical standard. (WCA should think of this, I think.)
If we do need one, I think that the minimum moves to solve the cube is a good choice.
What's the meaning by objective mathematical standard? For example, in 100m running, if the speed of the winds is faster than 2 m/s, then the result cannot be a record, even if you were faster than Usain Bolt. Similarly for 3x3x3 cube, if the minimum moves to solve the cube is less than a specific number, like 15 or 18, than the result should not be a record, even if you solve it in 4 seconds.

Besides, is random states the only available choice for scrambler algorithm? What is the comparison standard that we thought it was really better than random moves? How if we do some other thing to improve random moves algorithm? Random states is better only because we thought that random moves is really "random".
Random states will never be available for 'big puzzles' like 5x5x5 until a genius invents a good solver for them. Random moves is different while we can always improve it. For example, we can judge the status of the cube before every moves, and select the better ones.

I implemented a "random moves" scrambler as above when I was developing a cube timer application. I have pushed the scrambler algorithm to Github with my personal account after asking permission, and the address is: https://github.com/gavinmok/CuScrambler . It supports 2x2x2 to 9x9x9. However, it is only in Objective-C, which is maybe one of the worst programming language in the world. I would post a Java (for the Android version or the API) or C# version later, perhaps.

A background story: Why do I post this thread?
I was seeking help opinion for our developing cube timer to Stefan, and he looked down upon the scramble algorithm because it was 'random moves' and suggested me post the discussion to the forum. 

Btw: Do anyone have a good minimum moves cube solver? I wanna do some research and I searched for it but none is good or simple enough. Or I have to implement one by myself.


----------



## Malkom (Aug 21, 2017)

gavinmok said:


> If we do need one, I think that the minimum moves to solve the cube is a good choice.
> What's the meaning by objective mathematical standard? For example, in 100m running, if the speed of the winds is faster than 2 m/s, then the result cannot be a record, even if you were faster than Usain Bolt. Similarly for 3x3x3 cube, if the minimum moves to solve the cube is less than a specific number, like 15 or 18, than the result should not be a record, even if you solve it in 4 seconds.



In 100m running the wind can give the sprinter a direct advantage since the wind could "push" the sprinter forward and thereby increase their speed and ofcourse time, in speedsolving it is not quite the same.
No one can in 15 seconds come up with an optimal 3x3 solution, the scramble can definitely affect the solve e.g. an easy Xcross, a 2 gen cross that eases further planning in inspection or a 3 move FB. But most of it, when it comes to singles is about general luck, not just scramble based luck. Every official sub5 single except Feliks's WR had a PLL skip, something that is in no way related to the scramble but reduced the overall solving time by quite a bit.

It's a little funny you chose 100m sprint as an example since Feliks himself said in an interview that speedsolving is nothing like many other sports due to the big luck factor.


----------



## Ollie (Aug 21, 2017)

Are you sure there's no mathematical standard?

On his website, Stefan Pochmann simulated a bunch of megaminx scrambles and demonstrated that with his megaminx scrambling method (now WCA official) each piece had an pretty much equal probability of ending up in any location once the scramble had been applied. For example, any corner piece had an equal chance of ending up in any corner position in any orientation.

You can do the same for 3x3x3 more easily since there are fewer pieces. I assume that's how scramblers are tested.

Edit: what is "random enough"?


----------



## mark49152 (Aug 21, 2017)

gavinmok said:


> but there is still a philosophical question: How do we know the state is random enough? Even for random states algorithms, we cannot be sure that it is fair enough.


Random state means that there is an equal probability of any legal state of the puzzle being output. That's simple, clear and unambiguous. A cross or LB skip is a valid state, and is a valid and fair output from a scrambler, just very unlikely.



gavinmok said:


> Random states will never be available for 'big puzzles' like 5x5x5 until a genius invents a good solver for them.


That's not entirely true. You can randomise piece types individually. If you randomise pieces twice consecutively with independent scrambles they will still have random distribution, so it's OK to chain together random state scrambles that affect overlapping sets of pieces.

I'm not a scrambler expert, but I suspect that the most practical way to achieve a random state on a 5x5 would be through some combination of random state 3x3 and 4x4 scrambles applied on the inner and outer layers/blocks. Perhaps a good starting point would be 3x3 with wide moves, then 3x3 on outer layers, then 4x4 ignoring middle layers. I'm not sure that would truly randomize the T centres but since there are many equivalent pieces it might be good enough.


----------



## xyzzy (Aug 21, 2017)

I'm _probably_ a bit of a domain expert in this area.



gavinmok said:


> If we do need one, I think that the minimum moves to solve the cube is a good choice.


WCA regs include filtering (4b3), and for the smaller puzzles, the filtering is more or less what you'd expect.

Also, what Malkom said. For the most part, solve times are not strongly correlated to optimal solution lengths. For people using blockbuilding methods like Petrus or Roux (or CFOP with xcross/xxcross, etc.), it's true that there is a very slight correlation between human solution length and optimal solution length, but it's something that's not really exploitable in 99.95% of the scrambles—you might be better off praying to the RNG gods for an LL skip.



gavinmok said:


> Besides, is random states the only available choice for scrambler algorithm? What is the comparison standard that we thought it was really better than random moves? How if we do some other thing to improve random moves algorithm? Random states is better only because we thought that random moves is really "random".


Is it the only choice? Of course not. None of the cubes above 4×4×4 use random-state. Megaminx doesn't either.

(Wall of text below; if you can't be bothered to read it, at least watch Lucas Garron's talk (linked at the bottom).)

Also, I guess the point of confusion here is what the word "random" means. Strictly speaking, "random" by itself doesn't really mean much—it usually comes with the added connotation that we have a _uniform distribution_ over some set. To take an example, if I had a coin that came up heads 75% of the time and tails 25% of the time, the results of flipping the coin would still be _random_. It just wouldn't be _fair_. Randomness and uniformity are different concepts.

(And then there are gigantic caveats all over this, like the fact that for square-1, the distribution of shapes with the standard random-state scramblers might or might not be "uniform", depending on how you want to treat the shapes.)

When we say "random state", we usually imply some kind of uniform distribution over all possible scrambles. That's one way of thinking about it, but as above, it's not always the right way. To begin with, what does it even mean to scramble a puzzle? Let's say you apply some random move, and then another random move, and then another, _ad nauseum_. (We don't care if you happen to make a move that cancels with the immediately preceding move. We don't even care that you use a uniform distribution among possible moves, just that every possible move has some nonzero probability of being used. We _do_ care that the random moves are iid (… although we need some more caveats for squan here)p) This fits the intuitive notion of scrambling, and absent "parity-like" constraints, the distribution of possible states after _n_ moves converges to a fixed distribution (the so-called "stationary distribution") as _n_ tends to infinity. For the puzzles that behave like group cosets (i.e. every WCA puzzle other than squan), a standard exercise is to prove that the stationary distribution is exactly the uniform distribution.

(The caveat for "parity-like" constraints applies when the underlying Markov chain is periodic. For instance, if your random moves are just the quarter turns on a 3×3×3, the permutation parity of the corners is exactly the parity of the number of moves used. In this case, the distribution doesn't converge, but if you smooth out the distribution (a la Cesàro means), the smoothed out distribution does converge. In other words, you also have to randomise the number of moves used in your random-move scrambling. Tl;dr: it's complicated; nobody said it was going to be simple.)

We can generally approximate how quick this convergence is with the tools of linear algebra—at least, for 222/pyra/skewb/clock, and subsets like 333 EO, megaminx centres, etc. I haven't done the actual computation, so let's say that 1000 moves on a 3×3×3 leads to something that's indistinguishably close to a uniform distribution. Would you rather do 1000 random moves, or shortcut it with an almost-optimal solution that's only 20-ish moves? This brings us to random-state scrambling: instead of doing a ton of random moves, we just sample directly from the stationary distribution, solve it, invert the solution, and use that as our scramble sequence.

The crux here is that we can _quickly_ solve the smaller puzzles with _relatively few moves_ (compared to how many are needed to get "near" the stationary distribution). This breaks down for 555 and bigger cubes, as well as for megaminx—exactly the puzzles we currently don't use random-state for.

See also: Lucas Garron's talk at US Nats 2016.



gavinmok said:


> Btw: Do anyone have a good minimum moves cube solver? I wanna do some research and I searched for it but none is good or simple enough. Or I have to implement one by myself.


None of them are good _and_ simple. This is a complicated topic.

It's not so complicated that you need to have a PhD in mathematics to understand, and merely writing a working optimal solver requires just a bit of patience and reading Cube Explorer's documentation and Jaap's Puzzle Page, but you _have_ to use a bunch of nonobvious tricks in order to write an optimal solver that'll compute a solution before the heat death of the universe.



mark49152 said:


> That's not entirely true. You can randomise piece types individually. If you randomise pieces twice consecutively with independent scrambles they will still have random distribution, so it's OK to chain together random state scrambles that affect overlapping sets of pieces.


No, it's actually not! The pieces that overlap are fine (for the reason you mention)—it's the pieces that don't overlap that are problematic. You can't guarantee that those pieces have a jointly uniform distribution.

(In practice, any deviation from uniformity is really tiny, but why do a weird pseudo-random-state when you can get a proper random state?)



mark49152 said:


> I'm not a scrambler expert, but I suspect that the most practical way to achieve a random state on a 5x5 would be through some combination of random state 3x3 and 4x4 scrambles applied on the inner and outer layers/blocks. Perhaps a good starting point would be 3x3 with wide moves, then 3x3 on outer layers, then 4x4 ignoring middle layers. I'm not sure that would truly randomize the T centres but since there are many equivalent pieces it might be good enough.


Shameless plug, for the people who might not have seen this yet: https://www.speedsolving.com/forum/...ith-random-move-scrambles.64312/#post-1227796


----------



## mark49152 (Aug 21, 2017)

xyzzy said:


> No, it's actually not! The pieces that overlap are fine (for the reason you mention)—it's the pieces that don't overlap that are problematic. You can't guarantee that those pieces have a jointly uniform distribution.


I think it depends what the scrambles do to the pieces, which is open to analysis, and doesn't mean that you can't guarantee a particular distribution or at least determine the deviation and assess whether it's acceptable.

For 5x5 let's say we do a 4x4 random state scramble to the outer two layers followed by a 3x3 random state scramble to the outer layers, and let's consider only midges and corners. 

The corners are permuted twice, but both are random permutations with equal probabilities and independent of each other so the result should have no bias to any particular outcome.

The 4x4 scramble moves the midges around in some way that we can't assume to be uniform - it's just a side effect, since the 4x4 scramble does not account for midges. Then the 3x3 scramble applies a second permutation with uniform distribution. I think your point is that the second scramble cannot cancel out any bias that the first scramble introduces, which I agree with.

However, does that make the scrambler impractical, given that the bias may be translated by the second scramble into a statistical anomaly with no practical impact? Let's say the first scramble has a bias in that it's twice as likely to give you less than 6 oriented midges. The joint distribution after both scrambles would not be uniform, but would there be any observable bias towards fewer oriented midges?

The usual complaint against random move scrambles is that you have to do too many moves to resolve problems that do have a practical impact on solving, like bias towards a greater number of oriented edges.

I'm not a mathematician, and am happy to have my mistakes explained to me and learn something new today.



xyzzy said:


> (In practice, any deviation from uniformity is really tiny, but why do a weird pseudo-random-state when you can get a proper random state?)


If the tiny deviation enables the scrambler to become practical for use when solving or delegating, it may be preferable to a very slow "proper" random state scrambler or a fast random-move scrambler with undesirable biases in the distribution.


----------



## xyzzy (Aug 21, 2017)

mark49152 said:


> However, does that make the scrambler impractical, given that the bias may be translated by the second scramble into a statistical anomaly with no practical impact? Let's say the first scramble has a bias in that it's twice as likely to give you less than 6 oriented midges. The joint distribution after both scrambles would not be uniform, but would there be any observable bias towards fewer oriented midges?





mark49152 said:


> If the tiny deviation enables the scrambler to become practical for use when solving or delegating, it may be preferable to a very slow "proper" random state scrambler or a fast random-move scrambler with undesirable biases in the distribution.


Very good points, actually.

We don't currently have any WCA event where this concern is of immediate relevance: either we already have the code to generate random-state scrambles and it's fast+efficient (222/333/444/pyra/skewb/squan/clock), or we don't even have the code to generate "random partial states" that's fast+efficient (555/666/777/mega). I believe that these four remaining puzzles will never have "proper" random-state scramblers with move counts as low as the number of moves used in current random-move scrambles (60/80/100/70, respectively), but moving towards "random partial states" with negligible human-detectable biases and comparable move counts would be a decent compromise.


----------



## Malkom (Aug 21, 2017)

xyzzy said:


> Very good points, actually.
> 
> We don't currently have any WCA event where this concern is of immediate relevance: either we already have the code to generate random-state scrambles and it's fast+efficient (222/333/444/pyra/skewb/squan/clock), or we don't even have the code to generate "random partial states" that's fast+efficient (555/666/777/mega). I believe that these four remaining puzzles will never have "proper" random-state scramblers with move counts as low as the number of moves used in current random-move scrambles (60/80/100/70, respectively), but moving towards "random partial states" with negligible human-detectable biases and comparable move counts would be a decent compromise.


I think Pochmann scrambling is the only good way to scramble a megaminx. Rotationless scrambles would be terribly unergonomic and a rotation "based" would probably require loads of weird rotations and wouldn't be too ergonomic either. Pochmann scrambling combines turning and rotating into a single wrist turn. It's by no means perfect, it's fairly easy to miss scramble and it requires quite a few moves but I don't mind too much.


----------



## xyzzy (Aug 22, 2017)

Malkom said:


> Rotationless scrambles would be terribly unergonomic and a rotation "based" would probably require loads of weird rotations and wouldn't be too ergonomic either.



Have you seen the kinds of scramble sequences my kilominx scrambler spits out? Imagine something like that (only two rotations needed for the whole scramble), but roughly 4 times as long, for a potential megaminx scrambler. Hemisphere notation is a lot better than 12-sided rotationless scrambles, but I'll admit that it's still not as nice as Pochmann scrambles.


----------



## sp3ctum (Aug 28, 2017)

xyzzy said:


> (And then there are gigantic caveats all over this, like the fact that for square-1, the distribution of shapes with the standard random-state scramblers might or might not be "uniform", depending on how you want to treat the shapes.)



Hi, I was very interested in this discussion. I'm really impressed that there are people who have a lot more knowledge in this domain than I do.

Would you mind elaborating on your thoughts about Square-1? I recently wrote a scrambler for my app called Squanmate. Its purpose is to allow the user to choose a *subset* of possible shapes that they want scrambles for. It's working well, but I'm curious what you might have to say about it.

The algorithm for generating the scramble is this, in a nutshell:

from the available shapes (chosen by the user), choose two possible (random) shapes to be generated
construct the shapes with random pieces
generate a solution to this puzzle
reverse the solution to generate its scramble.
I don't understand the solving part yet, as that was written by somebody else, and their license permits using the solver. The topic is very interesting though. I think I'll start reading this thread and your links in more detail to learn more about it.


----------



## xyzzy (Aug 28, 2017)

gavinmok said:


> https://github.com/gavinmok/CuScrambler


I got too caught up in rambling about the One True Way to scramble and didn't notice that this is actually a very interesting concept.

Deliberately forcing pieces to be apart is probably not the right thing to do, because you'll infuriate all the Roux and Petrus users who get ready made pairs less often than they should. However, doing this _at the start of the scramble sequence_, and then following it up with the usual "unbiased" random moves is probably a good idea. (For big cubes, I mean. For 444 and below just use random-state.)

Once neighbouring pieces are appropriately dispersed, the probability that they'll come back together after n random moves (where n is large enough to move pieces around, but not so large that it's effectively a random state scramble on its own) is fairly close to what you'd get with random state scrambles—slightly less, but the deviation here is necessarily smaller in magnitude than the deviation when you start with a fully/almost solved cube because there are so many more states where the pieces are dispersed than there are states where the pieces are clumped together. (Further reading: law of total expectation, entropy.)



sp3ctum said:


> Would you mind elaborating on your thoughts about Square-1?


This 2008 thread seems to be a good resource. However, if you're writing a trainer app or such, having a distribution similar to the stationary distribution is not necessarily a good thing, since rarer shapes will show up more rarely in the trainer (which makes the training less effective).


----------



## sp3ctum (Aug 28, 2017)

xyzzy said:


> This 2008 thread seems to be a good resource. However, if you're writing a trainer app or such, having a distribution similar to the stationary distribution is not necessarily a good thing, since rarer shapes will show up more rarely in the trainer (which makes the training less effective).



Hey, that's a great observation! I'll definitely look into that, thank you.


----------

