How do optimal solvers and random state scramblers work?

[Lyn Simm]

Yes, Yes, but then - NO. Because you assume the action of the CO/CP scrambles on the edges is randomly distributed which is a non-trivial assumption.

the CO/CP scrambles dont have to cause randomly distributed effects on the edges. the CO/CP scrambles have no intentional effect on the edges. that means that whatever tendency that the CO/CP scramble generator has on the edges (which i agree is certainly nontrivial) will be applied on the already randomly distributed edges.

that means that the distribution of the EO/EP in the EO/EP scramble will stay random after application of any move sequence that does not deliberately affect the EO/EP in a particular way. im certain of that

-Lyn

edit:

for example, if I apply an F premove on a kociemba random state scramble (which will affect the EO), that doesn't mean that the scramble is no longer random state

 

[y235]

the CO/CP scrambles dont have to cause randomly distributed effects on the edges. the CO/CP scrambles have no intentional effect on the edges. that means that whatever tendency that the CO/CP scramble generator has on the edges (which i agree is certainly nontrivial) will be applied on the already randomly distributed edges.

that means that the distribution of the EO/EP in the EO/EP scramble will stay random after application of any move sequence that does not deliberately affect the EO/EP in a particular way. im certain of that

-Lyn

edit:

for example, if I apply an F premove on a kociemba random state scramble (which will affect the EO), that doesn't mean that the scramble is no longer random state

Yes, you're correct. I was wrong, sorry.

 

[adimare]

Ok then. Ignore EO/CO/CP, just for EP, how do you generate moves in a way that any of the possible EPs is equally likely to be reached by a scramble generated by your algorithm?

 

[Stefan]

Lyn Simm: Imagine a simpler puzzle, one with eight "edges" and eight "corners" which can only be permuted, there's no orientation. But it has overall even permutation parity, just like the 3x3.

To scramble the edges, just do a Fisher–Yates shuffle, which swaps two edges at a time. Because of the parity, we can't just swap edges i and j, so as a side effect, we also swap corners i and j.

To scramble the corners, do the same, just with roles reversed.

Now the edges scramble was perfect, the corners scramble was perfect, but the overall scramble is crap, because edges and corners are permuted exactly the same.

 

[qqwref]

if you have a cube that you scramble to have a random EO and EP state, then you do an R move, it will still have a random distribution of EO and EP

same thing if you do R U after every scramble

same thing if you do R U F' B2 L D2 M' y z R' B' L after every scramble

same thing if you apply a random CO/CP scramble after every scramble. right?? :confused:

-Lyn

Unfortunately, the logic doesn't quite work out. Each of them might individually be randomized, but your corner algorithms will affect edges in a non-random way, and your edge algorithms will affect corners in a non-random way. The only way to avoid this is to ensure that at least one of the algorithm sets is pure - that is, solving either edges or corners in such a way that the other pieces remain solved. Of course, the problem is that pure corner or edge algs can be quite long, such as superflip (20* htm) or an 8-corner twist D2 L2 D U2 F D B2 F' D F2 R2 B2 F D F D' U2 F (18* htm).

As a trivial example, suppose instead of corners and edges you are scrambling two sets of corners, and all moves have the same effect on both sets. So you first randomly scramble the first cube (doing the same thing to the second cube as a side effect), then randomly scramble the second cube (doing the same thing to the first cube as a side effect). Each cube itself is scrambled, but of course they are still in the same position, so the whole thing is not scrambled.

 

[Lucas Garron]

A random-state scramble is a move sequence that, a priori, is equally likely to be any valid state of the puzzle.
(There are some puzzles for which this you don't want an equal distribution over all states, or for which the distribution is not obvious. But it's obvious for all official puzzles except Square-1.)

One way to generate a random scramble that obviously works is:
- generate a random state of the puzzle, then
- generate a move sequence that scrambles the puzzle to that state.

This move sequence doesn't need to be optimal. For example, the official scramble program (TNoodle) doesn't use optimal scrambles for any puzzle but clock.
It can actually generate optimal scrambles for 2x2x2, Pyraminx, and Skewb, too. But to mask the fact that some scrambles for these puzzles can be very short, TNoodle finds longer scrambles for the same positions instead.

Of course, you *could* use an optimal solver to find the scramble for this. Other in this thread have linked to Kociemba's page. I've also given a simplified explanation of how Kociemba works in this post.

However, it doesn't really matter if we know which state we are going to generate "ahead of time", as long as it's random. A good example is clock: If you go through the full pin sequence and do a random turn each time, the entire clock will be in a random state. In fact, basically all clock scramblers do this.

The first official random-state scrambler for Pyraminx also used such an approach. I proposed and described it here in 2009, although it was replaced with an optimal scrambler in 2010 (and by TNoodle in 2013).

However, there is a caveat.

the CO/CP scrambles dont have to cause randomly distributed effects on the edges. the CO/CP scrambles have no intentional effect on the edges. that means that whatever tendency that the CO/CP scramble generator has on the edges (which i agree is certainly nontrivial) will be applied on the already randomly distributed edges.

that means that the distribution of the EO/EP in the EO/EP scramble will stay random after application of any move sequence that does not deliberately affect the EO/EP in a particular way. im certain of that

This is definitely, completely, 100% wrong. I once made the same mistake. I was hoping to find a fix, but I don't think there is one.

If you randomize edges (ignoring corners), then the whatever you do to the corners must preserve the random distribution of the edges.
If you use 4 stages, the fourth stage has to preserve the randomization of the first three.

To borrow Stefan's example, suppose you have two light switches set to "off", and you are trying to randomize them.

• Here's one way to randomize the left one: randomly either leave both switches alone, or flip both of them.
• Here's one way to randomize the right one: randomly either leave both switches alone, or flip both of them.

But if you use this to randomize the left one and then the right one, they will always stay in the same state!
In this case, it's obvious to see how to make the randomization independent. But the point still stands: it's not enough to randomize each part while *ignoring* the others. You have to take into account the parts you've already scrambled.

There are ways to modify any of these approaches so that they still give a random state. Your F premove example works. If you randomize edges ignoring corners, then randomize corners while flipping every edge but keeping every edge in its place, that also works. But these are non-trivial mathematical facts, and the reasoning doesn't extend to other ideas.



To give an explicit 3x3x3 example, suppose you're randomizing edges (EO + EP) and corners (CO + CP) independently. Then there are 12! * 2^11 edge scrambles and 8! * 3^7 corner scrambles. Because of parity, there should be exactly two combinations of (edge scramble + corner scramble) that result in any given output position. Suppose:
- The edge scrambles include (do nothing) and U2, as well as U and U'. Each of these provides a different, valid permutation of edges.
- The corner scrambles include (do nothing) and U2, as well as U and U'. Each of these provides a different, valid permutation of corners.

However, there four different scrambles that can result in the same state:

• (do nothing) U2
• U U
• U2 (do nothing)
• U' U'

This is too many. It means that there is some other overall outcome that has *fewer* than 2 possible combinations (possibly 0), and is therefore less likely than it should be. The overall distribution of the outcome cannot be uniformly random-state.

I'm sorry if this is a bit disappointing, but that's how the math works out. :-(

 

[Lucas Garron]

The only way to avoid this is to ensure that at least one of the algorithm sets is pure - that is, solving either edges or corners in such a way that the other pieces remain solved.

Not quite. The other set doesn't have to remain solved in that case, as long as you have the same effect on the other set.
(Such as the F premove or the superflip examples I just mentioned.)

 

[JustinTimeCuber]

I want to see the code for a random-state scrambler in JavaScript so that I can understand better. What I can understand is it's generating a state, applying some rules to make it solvable, making it solvable in <R2,L2,F2,B2,U,D>, then solving it from there, and then inverting the scramble. I want to see code for it to know how it is applied.

 

[Stefan]

To give an explicit 3x3x3 example, suppose you're randomizing edges (EO + EP) and corners (CO + CP) independently. Then there are 12! * 2^11 edge scrambles and 8! * 3^7 corner scrambles. Because of parity, there should be exactly two combinations of (edge scramble + corner scramble) that result in any given output position. Suppose:
- The edge scrambles include (do nothing) and U2, as well as U and U'. Each of these provides a different, valid permutation of edges.
- The corner scrambles include (do nothing) and U2, as well as U and U'. Each of these provides a different, valid permutation of corners.

However, there four different scrambles that can result in the same state:

• (do nothing) U2
• U U
• U2 (do nothing)
• U' U'

This is too many.

An explicit example using the real case... this is awesome.

 

[Lyn Simm]

Now the edges scramble was perfect, the corners scramble was perfect, but the overall scramble is crap, because edges and corners are permuted exactly the same.

i dont see the argument...

Ok then. Ignore EO/CO/CP, just for EP, how do you generate moves in a way that any of the possible EPs is equally likely to be reached by a scramble generated by your algorithm?

you optimally/suboptimally solve to it...or you use a "pattern" of moves that you know always gives a random state

Unfortunately, the logic doesn't quite work out. Each of them might individually be randomized, but your corner algorithms will affect edges in a non-random way, and your edge algorithms will affect corners in a non-random way.

but it doesnt matter what the effect of the corner alg is on the edge state...because we're just basically doing "post-moves" to a random state. A random state followed by any sequence should still be a random state.

i dont understand...

This is definitely, completely, 100% wrong. I once made the same mistake. I was hoping to find a fix, but I don't think there is one.

If you randomize edges (ignoring corners), then the whatever you do to the corners must preserve the random distribution of the edges.
If you use 4 stages, the fourth stage has to preserve the randomization of the first three.

i dont understand. we're just pushing a solved cube through 2 (or 4, if uncombined) filters...

first filter: force the solved cube to have a random EP & EO
second filter: force the messed up cube to also have a random CP & CO...

the second filter isn't intentionally solving or unsolving any EP/EO elements...the effect on the edges is therefore trivial.

sure i get it that the CP/CO alg is moving the edges around...obviously...but that effect should just be considered "post-moves" on the edge state scramble.


For example, (assuming parity was not selected for this cubestate) if my random EP/EO state was generated by R U R' U'

and my random CP/CO state was generated by B'

then the total EP/EO scramble can actually be considered R U R' U' B'

this still gives the same likelihood for every EP/EO configuration, because it's just a move AFTER a random state...

if you agree that F premove + (kociemba random state scramble) is a random state, then you must also concede that (kociemba random state scramble) + F' post move is a random state.

and that concession also applies to randomly generated substates

right?? maybe im just retarded

-Lyn

 

[00]

I want to see the code for a random-state scrambler in JavaScript so that I can understand better. What I can understand is it's generating a state, applying some rules to make it solvable, making it solvable in <R2,L2,F2,B2,U,D>, then solving it from there, and then inverting the scramble. I want to see code for it to know how it is applied.

https://github.com/cubing/qqTimer/blob/mzrg/scramble_333_edit.js

 

[Lucas Garron]

this still gives the same likelihood for every EP/EO configuration, because it's just a move AFTER a random state...

As we're trying to explain, this reasoning makes some intuitive sense, but it is completely wrong.

Do our proofs make sense to you? If not, what's the first part that doesn't?

 

[Stefan]

right?? maybe im just retarded

If those are the only two options, then it's the latter

Lucas even gave you an explicit example of bias for the actual case that will actually happen unless you intentionally use longer-than-necessary scramble parts and get lucky or something like that.

the second filter isn't intentionally solving or unsolving any EP/EO elements...the effect on the edges is therefore trivial.

Just because it's not "intentional", doesn't mean it's not happening. And what do you mean with "trivial"?

 

[Lyn Simm]

As we're trying to explain, this reasoning makes some intuitive sense, but it is completely wrong.

Do our proofs make sense to you? If not, what's the first part that doesn't?

nothing nothing = nothing
nothing U = U
nothing U' = U'
nothing U2 = U2
U nothing = U
U U = U2
U U2 = U'
U U' = nothing
U2 nothing = U2
U2 U = U'
U2 U2 = nothing
U2 U' = U
U' nothing = U'
U' U = nothing
U' U2 = U
U' U' = U2

# nothing = 4
# U = 4
# U2 = 4
# U' = 4

who cares that there are redundant states in your example...its an equal probability

plus your example is rigged for overlap. sure that the CP/CO scramble might cause overlapping states with regards to EP/EO... but that EO/EP branch state was chosen RANDOMLY...so any "duplicates" along that branch are inherently random...

-Lyn

 

[Lucas Garron]

who cares that there are redundant states in your example...its an equal probability

Those four states have the same probability, but *that probability is too high*. There are 43 quintillion other states, and some of those will have have to have a lower probability instead.

Did the part about the number of edge scrambles and corner scrambles make sense?

The edges of a cube have be in |E| = 12! * 2^11 possible states.
The corners of a cube have be in |C| = 8! * 3^7 possible states.
The entire cube has |E| * |C| / 2 ≈ 43.25 quintillion possible states. (You have to divide by 2 due to parity.)

Suppose you pick a scramble sequence for each of the |E| edge states and each of the |C| corner states. This means you have |E| * |C| ≈ 86.50 quintillion possible overall scrambles.
To be uniformly random state, each of the 43.25 quintillion cube states has to happen equally likely among those 86 quintillion scrambles. This means that there have to be exactly 2 scrambles that produce any particular state of the cube. Any more or less, and the outcome is no longer random-state.

In my example, the choice of a few particular scrambles for the edge part and the corner part produced a state that had a probability of at least 4 / (86.50 quintillion), which simplifies to about 1/(21.6 quintillion). This probability is too high, no matter what we would do for other edge and corner states.

In this particular case, we can pick different scrambles for the edge and corner parts so that the probability of each U state is 1 / (43.25 quintillion). But you have to be careful that you your choices don't cause *another* state to be too likely. And you have to make sure that this is the case for every combination of your choices for each edge state and each corner state. All the practical ways can think of... basically require that the corners preserve edge randomization.

It might feel like you can get around this by using different sequence for an edge/corner state each time you generate it. But that will only make things a bit better. To get a true random state, you *still* have to make sure that corner distribution evens out with the edge distribution. The approach would be similar to making sure that corners don't affect edges, and you won't get any good move savings.

plus your example is rigged for overlap. sure that the CP/CO scramble might cause overlapping states with regards to EP/EO... but that EO/EP branch state was chosen RANDOMLY...so any "duplicates" along that branch are inherently random...

The example is not rigged for overlap any more than a scrambler that tries to generate an edge state efficiently and a corner state efficiently. In fact, such a scrambler would make these exact choices.
You could try to avoid this by *not* trying to use the most efficient choices. But then you still have to be very careful to make sure nothing can get "rigged". And the most practical way to do this is for one part to preserve the randomization of the other part.

It also doesn't matter that these four states are a small fraction of all the possible outcomes. The fact that the scrambler is too likely to produce these states already means that the outcome distribution is out of whack.
It can only get worse from there.
If you tried to write a 3x3x3 scrambler based on this, you would find that the scrambles would probably still look pretty random to a human – but 30 independent random moves look random to a human, too. You would lose the mathematical random-state guarantee, which is the whole point here.

 

[cubernya]

Of note, if you have an edge scramble followed by a corner scramble, after the first one the expected number of oriented edges is exactly 6. However, scrambling the corners with disregard for the edges shifts that number slightly less (I know Stefan has posted on this in the past regarding the former WCA scrambler). If that doesn't make sense, he just ran a simulator that found EO for loads of scrambles of different lengths. Not until the scramble reached around 35 moves did it get *close* to being even.

 

[Lyn Simm]

Those four states have the same probability, but *that probability is too high*. There are 43 quintillion other states, and some of those will have have to have a lower probability instead.

Did the part about the number of edge scrambles and corner scrambles make sense?

The edges of a cube have be in |E| = 12! * 2^11 possible states.
The corners of a cube have be in |C| = 8! * 3^7 possible states.
The entire cube has |E| * |C| / 2 ≈ 43.25 quintillion possible states. (You have to divide by 2 due to parity.)

Suppose you pick a scramble sequence for each of the |E| edge states and each of the |C| corner states. This means you have |E| * |C| ≈ 86.50 quintillion possible overall scrambles.
To be uniformly random state, each of the 43.25 quintillion cube states has to happen equally likely among those 86 quintillion scrambles. This means that there have to be exactly 2 scrambles that produce any particular state of the cube. Any more or less, and the outcome is no longer random-state.

In my example, the choice of a few particular scrambles for the edge part and the corner part produced a state that had a probability of at least 4 / (86.50 quintillion), which simplifies to about 1/(21.6 quintillion). This probability is too high, no matter what we would do for other edge and corner states.

In this particular case, we can pick different scrambles for the edge and corner parts so that the probability of each U state is 1 / (43.25 quintillion). But you have to be careful that you your choices don't cause *another* state to be too likely. And you have to make sure that this is the case for every combination of your choices for each edge state and each corner state. All the practical ways can think of... basically require that the corners preserve edge randomization.

It might feel like you can get around this by using different sequence for an edge/corner state each time you generate it. But that will only make things a bit better. To get a true random state, you *still* have to make sure that corner distribution evens out with the edge distribution. The approach would be similar to making sure that corners don't affect edges, and you won't get any good move savings.



The example is not rigged for overlap any more than a scrambler that tries to generate an edge state efficiently and a corner state efficiently. In fact, such a scrambler would make these exact choices.
You could try to avoid this by *not* trying to use the most efficient choices. But then you still have to be very careful to make sure nothing can get "rigged". And the most practical way to do this is for one part to preserve the randomization of the other part.

It also doesn't matter that these four states are a small fraction of all the possible outcomes. The fact that the scrambler is too likely to produce these states already means that the outcome distribution is out of whack.
It can only get worse from there.
If you tried to write a scrambler based on this, you would. For a 3x3x3, the scrambles would probably still look pretty random to a human – but 30 independent random moves look random to a human, too. You would lose the mathematical random-state guarantee, which is the whole point here.

so youre saying that the set of cubes defined by (every single random state) + (F move) is not a uniform distribution of states

-Lyn

 

[Lucas Garron]

so youre saying that the set of cubes defined by (every single random state) + (F move) is not a uniform distribution of states

No, I am not saying that. I would be wrong if I said that.

 

[Lyn Simm]

No, I am not saying that. I would be wrong if I said that.

are you saying that (every single EP/EO state) + F move is not a uniform distribution of EP/EO states?

 

[Lucas Garron]

are you saying that (every single EP/EO state) + F move is not a uniform distribution of EP/EO states?

No, I am not saying that. I would be wrong if I said that.