# How do optimal solvers and random state scramblers work?



## JustinTimeCuber (Jul 26, 2015)

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 (Jul 26, 2015)

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 (Jul 26, 2015)

adimare said:


> 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 (Jul 26, 2015)

Lyn Simm said:


> 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 (Jul 26, 2015)

adimare said:


> 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



adimare said:


> 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 (Jul 26, 2015)

Lyn Simm said:


> 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 (Jul 26, 2015)

adimare said:


> 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 (Jul 26, 2015)

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 (Jul 26, 2015)

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 (Jul 26, 2015)

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


----------



## qqwref (Jul 26, 2015)

Lyn Simm said:


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


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 (Jul 26, 2015)

qqwref said:


> 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 (Jul 26, 2015)

Lyn Simm said:


> 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 (Jul 26, 2015)

Jakube said:


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



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 (Jul 26, 2015)

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 (Jul 26, 2015)

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 (Jul 26, 2015)

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 (Jul 26, 2015)

adimare said:


> 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 (Jul 26, 2015)

Lyn Simm said:


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



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 (Jul 26, 2015)

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.


----------



## Lyn Simm (Jul 26, 2015)

y235 said:


> 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 (Jul 26, 2015)

Lyn Simm said:


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



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


----------



## adimare (Jul 26, 2015)

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 (Jul 26, 2015)

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 (Jul 26, 2015)

Lyn Simm said:


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


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 (Jul 26, 2015)

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.



Lyn Simm said:


> 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 (Jul 26, 2015)

qqwref said:


> 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 (Jul 26, 2015)

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 (Jul 26, 2015)

Lucas Garron said:


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



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


----------



## Lyn Simm (Jul 27, 2015)

Stefan said:


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



adimare said:


> 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



qqwref said:


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



Lucas Garron said:


> 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 (Jul 27, 2015)

JustinTimeCuber said:


> 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 (Jul 27, 2015)

Lyn Simm said:


> 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 (Jul 27, 2015)

Lyn Simm said:


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



Lyn Simm said:


> 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 (Jul 27, 2015)

Lucas Garron said:


> 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 (Jul 27, 2015)

Lyn Simm said:


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



Lyn Simm said:


> 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 (Jul 27, 2015)

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 (Jul 27, 2015)

Lucas Garron said:


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



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 (Jul 27, 2015)

Lyn Simm said:


> 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 (Jul 27, 2015)

Lucas Garron said:


> 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 (Jul 27, 2015)

Lyn Simm said:


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


----------



## rokicki (Jul 27, 2015)

y235 said:


> 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 (Jul 27, 2015)

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.



Lucas Garron said:


> 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 (Jul 27, 2015)

rokicki said:


> y235 said:
> 
> 
> > EDIT: nvm I'm wrong
> ...



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 (Jul 27, 2015)

Lucas Garron said:


> 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



qqwref said:


> 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 (Jul 27, 2015)

Lyn Simm said:


> 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 (Jul 27, 2015)

rokicki said:


> 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 (Jul 27, 2015)

Lucas Garron said:


> 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 (Jul 27, 2015)

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 (Jul 27, 2015)

qq280833822 said:


> 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 (Jul 27, 2015)

Lyn Simm said:


> Lucas Garron said:
> 
> 
> > However, the *combined* distribution is not necessarily going to be random
> ...



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 (Jul 27, 2015)

Then stop coming back to the thread, Stefan.


----------



## Lyn Simm (Jul 27, 2015)

StachuK1992 said:


> Then stop coming back to the thread, Stefan.



no, Stefan is right I am retarded.



Stefan said:


> _"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 (Jul 27, 2015)

JustinTimeCuber said:


> 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 (Jul 27, 2015)

qq280833822 said:


> 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 said:


> 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 (Jul 27, 2015)

cuBerBruce said:


> ... for 34 moves total.



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


----------



## TDM (Jul 27, 2015)

Lyn Simm said:


> 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 (Jul 27, 2015)

Lyn Simm said:


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



TDM said:


> 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 (Jul 27, 2015)

unsolved said:


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


This is actually really cool.


----------



## TDM (Jul 27, 2015)

cuBerBruce said:


> 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 (Jul 29, 2015)

molarmanful said:


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


----------



## TheSquareOne (Jul 29, 2015)

adimare said:


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



Technically we do, though Google call it ‘trespassing’.


----------



## Lucas Garron (Jul 29, 2015)

TheSquareOne said:


> Technically we do, though Google call it ‘trespassing’.



From what Tom Rokicki has estimated, Google could maybe solve a single 4x4x4 optimally, but not *much* more.

We live in a time with very powerful computers. The problem here is that the problem fundamentally gets very difficult very quickly for larger cubes (as far as we know). We're never going to be able to solve a 100x100x100 using the current approach. It doesn't have to do with our computers; it's purely a matter of the math.

However, it *would* be cool if we lived in a time/universe where we found a way to completely shortcut the search using clever math.


----------



## AlphaSheep (Jul 29, 2015)

JustinTimeCuber said:


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



http://www.qqtimer.net/scramble_333_edit.js
Good luck...


----------



## Lucas Garron (Jul 29, 2015)

AlphaSheep said:


> http://www.qqtimer.net/scramble_333_edit.js
> Good luck...



How about looking at the source instead?


----------



## Renslay (Jul 29, 2015)

Lucas Garron said:


> From what Tom Rokicki has estimated, Google could maybe solve a single 4x4x4 optimally, but not *much* more.
> 
> We live in a time with very powerful computers. The problem here is that the problem fundamentally gets very difficult very quickly for larger cubes (as far as we know). We're never going to be able to solve a 100x100x100 using the current approach. It doesn't have to do with our computers; it's purely a matter of the math.
> 
> However, it *would* be cool if we lived in a time/universe where we found a way to completely shortcut the search using clever math.



The diameter of the nxnxn cube has the order of n^2 / log(n), so that's how fast God's number is increasing with bigger cubes.


----------



## Lucas Garron (Jul 29, 2015)

Renslay said:


> The diameter of the nxnxn cube has the order of n^2 / log(n), so that's how fast God's number is increasing with bigger cubes.



Indeed. Unfortunately, we don't know any optimal solving approaches better than O(n) ^ O(diameter).


----------



## StachuK1992 (Jul 30, 2015)

What is 'n' and 'diameter' in this context?


----------



## Lucas Garron (Jul 30, 2015)

StachuK1992 said:


> What is 'n' and 'diameter' in this context?



The usual meanings: dimension and God's number.


----------



## cuBerBruce (Jul 30, 2015)

Lucas Garron said:


> The usual meanings: dimension and God's number.



Technically, the diameter is the maximum distance between any two positions, and I think God's number is generally regarded to mean the maximum distance from the solved position. (We expect these to be about the same value, of course.)


----------

