How do optimal solvers and random state scramblers work?

[JustinTimeCuber]

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.

 

[adimare]

Check out http://kociemba.org/cube.htm for a very good explanation of how cube explorer works. As for scramblers, the idea is to generate a random position that follows a few rules to make it solvable, then figure out the solution of said position, and use the inverse of that solution as the presented scramble.

 

[Lyn Simm]

Check out http://kociemba.org/cube.htm for a very good explanation of how cube explorer works. As for scramblers, the idea is to generate a random position that follows a few rules to make it solvable, then figure out the solution of said position, and use the inverse of that solution as the presented scramble.

I dont think you need to actually solve a "random state." I think you just need to generate a scramble that causes a state with an equal distribution of all possible EP/EO/CP/CO states.

-Lyn

 

[adimare]

I dont think you need to actually solve a "random state." I think you just need to generate a scramble that causes a state with an equal distribution of all possible EP/EO/CP/CO states.

-Lyn

How can a single state have a distriburion of states?

 

[Lyn Simm]

You need to solve it to figure out the moves to get to it.

true, but the goal doesnt have to be a CUBE state. it only has to be a combination of edge/corner permutation/orientation "substates"

i think that simplifies the generation :confused:

-Lyn

How can a single state have a distriburion of states?

easy, just solve for a random EO, EP, CO, and CP. and then put the solutions in sequence. right?

the whole problem with random move scrambles is that they don't give an equal chance for each state. doesn't this avoid that problem?

-Lyn

 

[adimare]

true, but the goal doesnt have to be a CUBE state. it only has to be a combination of edge/corner permutation/orientation "substates"

i think that simplifies the generation :confused:

-Lyn

Yeah, and once you generate that combination, you need to figure out how to get to it from a solved cube. That can be done by solving the generated state and presenting the reverse of the solution as the scramble (that's how qqtimer does it, as an example)

 

[Lyn Simm]

Yeah, and once you generate that combination, you need to figure out how to get to it from a solved cube. That can be done by solving the generated state and presenting the reverse of the solution as the scramble (that's how qqtimer does it, as an example)

why can't you just use the generator? it's a scramble...

basically generate 4 mini, easy scrambles and put them together...

-Lyn

 

[adimare]

I'm not following. What generator? 4 mini scrambles put together? If you mean one scramble for eo only, one for ep, one for cp and one for co, such a scramble would probably be huge.

 

[Lyn Simm]

sure, i didnt say it would be small!! but it will still work without "solving a random state," and it will be much faster!! not that speed matters...

you can also combine EO and EP / CO and CP,

or you can require that the EP move sequence be translated to an orientation so that the last move of the EP sequence cancels with the first move of the EO sequence, etc.

there are many tricks that I can think of to shrink the scrambles...

keep an open mind!!

-Lyn

 

[JustinTimeCuber]

I'm gonna look at the code of qqtimer or something tomorrow and maybe I'll understand better

 

[qqwref]

sure, i didnt say it would be small!! but it will still work without "solving a random state," and it will be much faster!! not that speed matters...

you can also combine EO and EP / CO and CP,

or you can require that the EP move sequence be translated to an orientation so that the last move of the EP sequence cancels with the first move of the EO sequence, etc.

there are many tricks that I can think of to shrink the scrambles...

All your ideas would just make longer scrambles. Sure, it could be faster to generate, but a normal 3x3x3 random state scramble is pretty fast already - and only about 20 moves each. Even in javascript (a slow language), on Firefox (and not the even faster Chrome), my computer can generate 100 random state scrambles in ~2 seconds.


But yeah, what it does is randomly choose a cube position and then use a version of Kociemba's 2-phase algorithm to find a short solution. Optimal scramblers have to do a bunch more work, because they need to check a lot more possibilities if they want to ensure that no shorter solution exists. The code in qqTimer is written by Shuang Chen, and it's pretty long and complex, so I don't recommend trying to figure it all out unless you have a really good reason to.

 

[Lyn Simm]

All your ideas would just make longer scrambles. Sure, it could be faster to generate, but a normal 3x3x3 random state scramble is pretty fast already - and only about 20 moves each. Even in javascript (a slow language), on Firefox (and not the even faster Chrome), my computer can generate 100 random state scrambles in ~2 seconds.

CO and CP can be solved in <=11 moves every time (most in <=9)
EO and EP can be solved in <=14 moves every time (most in <=12)

just translate and mirror to cancel the last move of CO/CP with the first move of EO/EP, and you'll get a 20 move scramble most of the time...

i'm guessing that would be faster than Kociemba...:confused:

-Lyn

 

[Jakube]

CO and CP can be solved in <=11 moves every time (most in <=9)
EO and EP can be solved in <=14 moves every time (most in <=12)

EO and EP can only be solved in <= 14 moves every time, if we don't care about the state of the corners.
and
CO and CP can only be solved in <= 11 moves every time, if we don't care about the state of the edges.

So you will very likely mess up the corners again, when you apply a <= 14 edge alg.

Just take a look at the E-Perm (https://www.speedsolving.com/wiki/index.php/PLL#E_Permutation). It's optimal solution is 14 moves, not 11.

 

[Lyn Simm]

EO and EP can only be solved in <= 14 moves every time, if we don't care about the state of the corners.
and
CO and CP can only be solved in <= 11 moves every time, if we don't care about the state of the edges.

So you will very likely mess up the corners again, when you apply a <= 14 edge alg.

Just take a look at the E-Perm (https://www.speedsolving.com/wiki/index.php/PLL#E_Permutation). It's optimal solution is 14 moves, not 11.

I know. But for a scrambler, it doesn't matter that the CP/CO alg destroys the EP/EO state. the objective is not to solve a specific combined state, but to allow an equal distribution of EP/EO/CP/CO substates to be possible.

obviously for an optimal solver, this makes no sense. but i'm not arguing that

-Lyn

 

[Jakube]

Not so sure if you still have an equal distribution of CO/CP, if you scramble it again in the EO/EP phase.

 

[Lyn Simm]

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

 

[adimare]

The question was "how do random state scramblers work?" not "how do you think random state scramblers should work?". As far as I know, there is no random state scrambler that "concatenates 4 mini scrambles and translates and mirrors the last move of CO/CP with the first one of EO/EP maintaining a normal distribution of EO/EP/CO/CP in under 20 moves".

 

[Lyn Simm]

The question was "how do random state scramblers work?" not "how do you think random state scramblers should work?". As far as I know, there is no random state scrambler that "concatenates 4 mini scrambles and translates and mirrors the last move of CO/CP with the first one of EO/EP maintaining a normal distribution of EO/EP/CO/CP in under 20 moves".

ok then its probably impossible sorry

-Lyn

 

[y235]

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

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.

 

[adimare]

If you think you're on to something by all means try it. But for now it just seems like you're slowly talking yourself into writing a random move scrambler.