How do optimal solvers and random state scramblers work?

[rokicki]

EDIT: nvm I'm wrong

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.

EDIT: everything below this line is incorrect. -tom

You don't need that assumption. His technique does work.
If the input is a randomly distributed edge position, it makes
no difference if the impact of the corner solution on the edges
is deterministic, random, or highly skewed---so long as it does
not depend in any way on the input edge position. That's one
of the nice things about working in a group; the Cayley graph
is vertex-transitive, so things like this work.

Kociemba's algorithm is fast and simple enough though, that
there's no significant reason not to use it. It's probably not
much more complicated than two separate optimal solvers,
one for edges and one for corners.

 

[qqwref]

Lyn, I think you need to go away for a while and learn some basic statistics about discrete random distributions. Then come back and read (at least) Lucas's posts. Then maybe it will make sense. Right now your intuitions about the concepts are just too wrong and it would take a lot of writing and time to fix them, especially since you seem to be skimming over posts.

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

Yes, you're right. But there is no reason why you would ever want to do this, so in practice making one set pure is the real criterion.

 

[Lucas Garron]

EDIT: nvm I'm wrong

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.

You don't need that assumption. His technique does work.
If the input is a randomly distributed edge position, it makes
no difference if the impact of the corner solution on the edges
is deterministic, random, or highly skewed---so long as it does
not depend in any way on the input edge position. That's one
of the nice things about working in a group; the Cayley graph
is vertex-transitive, so things like this work.

Kociemba's algorithm is fast and simple enough though, that
there's no significant reason not to use it. It's probably not
much more complicated than two separate optimal solvers,
one for edges and one for corners.

I'm not sure I follow.
If the action of each corner scramble is non-deterministic and randomly distributes edges, it works. (That's why I've been careful to say "preserves the randomness" rather than "preserves".) But then you might as well run Kociemba on the corners, and ignore the edges.

Depending on your definition, it also works if the scramble for a particular corner state is deterministic, as long as the a priori effect on the edges has a uniform distribution. (Similar to how crypto definitions use "families" of algorithms.)

However, I don't know if vertex transitivity argument makes sense here. Are you saying my proof is invalid?

 

[Lyn Simm]

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

Then no matter how far you branch off from the fully randomized edge state in random moves, you should maintain an Edge state from a uniform distribution. That's because you're branching off a state that was selected from a uniform distribution...Any propagated state is random in the same sense. Not because the final state is directly that of a uniform distribution, but because it's branched from a state from a uniform distribution.

if those random moves just so happen to filter the cube into a state from a random CO/CP distribution, then so be it

Lyn, I think you need to go away for a while and learn some basic statistics about discrete random distributions. Then come back and read (at least) Lucas's posts. Then maybe it will make sense. Right now your intuitions about the concepts are just too wrong and it would take a lot of writing and time to fix them, especially since you seem to be skimming over posts.

read rokicki's post

-Lyn

 

[Lucas Garron]

Then no matter how far you branch off from the fully randomized edge state in random moves, you should maintain an Edge state from a uniform distribution. That's because you're branching off a state that was selected from a uniform distribution...Any propagated state is random in the same sense. Not because the final state is directly that of a uniform distribution, but because it's branched from a state from a uniform distribution.

You are partially correct: the *edge* distribution remains random after branching. The corner distribution will also be random.

However, the *combined* distribution is not necessarily going to be random, for reasons I detailed in my other posts.

Look at the light switch example again. Even if you randomize the right light switch after randomizing the left one, in the end both light switches are going to be random (when you consider them on their own). But the light switches are always going to be in the same state as each other.

 

[rokicki]

You don't need that assumption. His technique does work.
... lots more wrong stuff here ...

I am wrong. Lucas is right. This technique (as stated by itself) does not guarantee
a random scramble.

 

[Lyn Simm]

However, the *combined* distribution is not necessarily going to be random,

ok that's where I am wrong. why didn't you say that in the first place!! (lol) i thought the cube was just a bunch of these substates functioning in parallel (with a single parity flag), when there is actually a lot more interplay between the elements than i thought.

there are a lot more constraints on the second phase. maybe it would be possible require corner solutions that have some consistent arbitrary effect on the edges like you mentioned, but for higher order cubes this probably becomes too much to be worth it, especially when efficient alternatives are available

thanks for the clarifications!!

-Lyn

 

[qq280833822]

A question.
If we prove that the corners of a cube can be solved in 11 moves and the edges can be solved in 14 moves, can we prove that the whole cube can be solved within 25 moves (without the knowledge about the god number)?

 

[tseitsei]

A question.
If we prove that the corners of a cube can be solved in 11 moves and the edges can be solved in 14 moves, can we prove that the whole cube can be solved within 25 moves (without the knowledge about the god number)?

No. Because corners can be solved in 11 moves IF WE DON'T CARE ABOUT THE EDGES. And edges can be solved in 14 moves IF WE DON'T CARE ABOUT THE CORNERS.

Which ever we choose to solve last must be solved while PRESERVING THE OTHER SET OF PIECES. And this will take significantly more moves (for example superflip is 20 moves optimal)

 

[Stefan]

However, the *combined* distribution is not necessarily going to be random

why didn't you say that in the first place!!

That has been said every single time, starting with my "Now the edges scramble was perfect, the corners scramble was perfect, but the overall scramble is crap".

 

[StachuK1992]

Then stop coming back to the thread, Stefan.

 

[Lyn Simm]

Then stop coming back to the thread, Stefan.

no, Stefan is right I am retarded.

"Now the edges scramble was perfect, the corners scramble was perfect, but the overall scramble is crap".

but I thought that you meant that the scramble was bad BECAUSE the edges and corners had the exact same permutation (which is what you said in the original post)...which didn't seem like a valid reason to disqualify a scramble. but now I see what you meant. im sorry


just a lot of people, qqwref included, were taking shots at random state corner scrambles negatively affecting the randomness of previously randomly generated edge states, which I still don't think is true (I might be wrong).

but now I know that just because all the sub-components of a cubestate are completely random state, that doesn't require that the cube be random state. a mod should edit that into the OP so people don't read my garbage posts. thanks

-Lyn

 

[unsolved]

I can't really seem to figure out how random state scramblers work, nor how optimal solvers work. Do optimal solvers just brute force algorithms, or is it a better method? Also, how do random state scramblers work? I am interested in seeing the code to generate good 3x3 scrambles.

I can tell you how my brute force solvers work.

1. I start with a solved cube and generate every possible cube state that is 6 moves away from being solved. I load this into a RAM buffer along with the distance from the solved state (0-6) and the reverse sequence that will solve it.
2. I take the user-scrambled cube and apply 1 move to it.
3. I check to see if the resulting position is in the RAM buffer. If so, I show the solution. If not, I apply a different move and continue.
4. The process repeats until all solutions to a given depth have been explored.

This technique finds solutions at depth "n-6" faster than a search would without the ram buffer. So it only has to generate 9 moves to find an optimal solution 15 moves in length.

 

[cuBerBruce]

A question.
If we prove that the corners of a cube can be solved in 11 moves and the edges can be solved in 14 moves, can we prove that the whole cube can be solved within 25 moves (without the knowledge about the god number)?

No. Because corners can be solved in 11 moves IF WE DON'T CARE ABOUT THE EDGES. And edges can be solved in 14 moves IF WE DON'T CARE ABOUT THE CORNERS.

Which ever we choose to solve last must be solved while PRESERVING THE OTHER SET OF PIECES. And this will take significantly more moves (for example superflip is 20 moves optimal)

(I agree with tseitsei, but I'm giving further information about what we know about move count for such a 2-phase solution.)

Since we know that corners can be solved in 22 quarter turns without affecting edges, we know any state can be solved in 40 quarter turns by first solving edges (18q max), and then solving corners while preserving edges (22q max). This was shown by Silviu Radu in 2005.

In face turn metric we have 14 moves for edges, 20 moves for corners (using God's number) for 34 moves total. If we don't make use of God's number, we still have 14+22 = 36 moves total as an upper bound for solving any cube in this manner.

 

[Lyn Simm]

... for 34 moves total.

If corner solutions are <=11 moves, can't you make the same argument for a 31-move upper bound?

 

[TDM]

If corner solutions are <=11 moves

Are they still 11 moves if you include centres? 11 moves is God's number on a 2x2, but that doesn't include centres.

 

[cuBerBruce]

If corner solutions are <=11 moves, can't you make the same argument for a 31-move upper bound?

Yes, doing corners first, and assuming God's number (for a maximum of 20 for edges, preserving corners), we get 31 moves total.

Are they still 11 moves if you include centres? 11 moves is God's number on a 2x2, but that doesn't include centres.

Yes, it is. I thought even the set of antipodes is the same whether or not you include centers, but the numbers don't quite match. That is true for QTM, though.

 

[molarmanful]

I can tell you how my brute force solvers work.

1. I start with a solved cube and generate every possible cube state that is 6 moves away from being solved. I load this into a RAM buffer along with the distance from the solved state (0-6) and the reverse sequence that will solve it.
2. I take the user-scrambled cube and apply 1 move to it.
3. I check to see if the resulting position is in the RAM buffer. If so, I show the solution. If not, I apply a different move and continue.
4. The process repeats until all solutions to a given depth have been explored.

This technique finds solutions at depth "n-6" faster than a search would without the ram buffer. So it only has to generate 9 moves to find an optimal solution 15 moves in length.

This is actually really cool.

 

[TDM]

Yes, it is. I thought even the set of antipodes is the same whether or not you include centers, but the numbers don't quite match. That is true for QTM, though.

Oh, that's interesting. I never knew that.

 

[adimare]

This is actually really cool.

It's really not

It'd be great if we lived in a time with computers powerful enough to allow such a mindless approach to prove useful in solving any cube bigger than a 2x2x2, but we don't.