Probability Thread

[marfer]

(CFOP) Probabilities for 1LLL

Hello speedcubers,
I know that there slightly more than 1000 legal configurations for the last layer (don't have the exact number right now but it's there somewhere in the wiki), but has anybody estimated what are the probabilities of getting each of them after Cross + F2L ? I suspect (hope) it's not an uniform distribution, so perhaps the most probable 30 configurations make up for 80% of the probability. That would mean that in 80% of the solves one could do a 1LLL (greatly lowering the turn count), and then the for the rest use classical OLL and PLL. Has this path been investigated too optimize CFOP ?
Thanks.

 

[waffle=ijm]

As far as I know, any speedsolvers will tend to sway against 1LLL (though it be nice) for speed due to recognition. Though in terms of pure optimization there's Dr. Morley Davidson who knows full ZBLL and knows some 1LLL for the maths and FMC.

EDIT - He also knows Anti-ZBLL (correct me if I'm wrong on the name of this) which is ZBLL for when edges aren't oriented.

 

[TDM]

If the case has rotational symmetry (you can do U2 then the same alg, and it will still solve the same case) then it has either half or a quarter of the chance of a case without symmetry (whether it's a half or a quarter depends on if it's just U2 symmetry, or if it's for all four AUFs i.e. H perm, N perms, skip, and those cases with a 4-edge flip). So for most cases, the probability of getting them is 1/3888. For some it's 1/7776, and for a couple it's 1/15552.

 

[stoic]

Ah, Pareto's principle.
Nice idea

 

[Bindedsa]

I suspect (hope) it's not an uniform distribution, so perhaps the most probable 30 configurations make up for 80% of the probability. That would mean that in 80% of the solves one could do a 1LLL (greatly lowering the turn count)

This can't possible be true because I always pay attention to the permutation of my LL while doing OLL, and I'm pretty sure I would have notice this by now. That being said I do find that some cases seem to come up more commonly, but not enough that I feel it would be worth focusing on them. It's much better to look for cases that are reasonably fast and easy to recognize.

As far as I know, any speedsolvers will tend to sway against 1LLL (though it be nice) for speed due to recognition.

Not necessarily, if you get used to recognizing cases while doing your AUF, you don't lose that much time. It just means every now and then you'll end up doing U2 U' U' or something. It means I miss a lot of 1LLLs, but I don't I waste much time trying to recognize a case I don't know

 

[irontwig]

I suspect (hope) it's not an uniform distribution, so perhaps the most probable 30 configurations make up for 80% of the probability.
Thanks.

No, that's not how it works, most LL cases are equally likely to occur.

 

[marfer]

No, that's not how it works, most LL cases are equally likely to occur.

Too bad. The initial idea is interesting, but unless the statistical distribution is quite far from the uniform, one will end up needing a few hundred LL patterns to cover the 80% probability mass and that's not practical. I might end up simulating by computer the Cross + F2L stages just too see what exactly is this distribution. I am quite a lazy person though, so don't count on it Plus I get the feeling that it's not so easy to program, otherwise someone would have already done it.

 

[guysensei1]

As far as I know, any speedsolvers will tend to sway against 1LLL (though it be nice) for speed due to recognition. Though in terms of pure optimization there's Dr. Morley Davidson who knows full ZBLL and knows some 1LLL for the maths and FMC.

aaaaaaand then there's Bindedsa

EDIT - He also knows Anti-ZBLL (correct me if I'm wrong on the name of this) which is ZBLL for when edges aren't oriented.

Isn't AntiZBLL the set where corners are oriented but edges not (all) oriented?

 

[Musicalboy2]

Hello speedcubers,
I know that there slightly more than 1000 legal configurations for the last layer (don't have the exact number right now but it's there somewhere in the wiki), but has anybody estimated what are the probabilities of getting each of them after Cross + F2L ? I suspect (hope) it's not an uniform distribution, so perhaps the most probable 30 configurations make up for 80% of the probability. That would mean that in 80% of the solves one could do a 1LLL (greatly lowering the turn count), and then the for the rest use classical OLL and PLL. Has this path been investigated too optimize CFOP ?
Thanks.

They should be evenly distributed.

Remember that permutation and orientation are separate.

aaaaaaand then there's Bindedsa


Isn't AntiZBLL the set where corners are oriented but edges not (all) oriented?

I heard the same thing that waffo did about anti-ZBLL; I'm pretty sure anti-ZBLL is no edges oriented but otherwise the same idea as ZBLL.

 

[cuBerBruce]

If the case has rotational symmetry (you can do U2 then the same alg, and it will still solve the same case) then it has either half or a quarter of the chance of a case without symmetry (whether it's a half or a quarter depends on if it's just U2 symmetry, or if it's for all four AUFs i.e. H perm, N perms, skip, and those cases with a 4-edge flip). So for most cases, the probability of getting them is 1/3888. For some it's 1/7776, and for a couple it's 1/15552.

Precisely:

Number of cases with probability 1/3888: 3864
Number of cases with probability 1/7776: 44
Number of cases with probability 1/15552: 8 (including solved case)

Total cases: 3916

When marfer was talking about the number of cases being about 1000, I believe he(?) was thinking of the number of cases if you count mirrors and inverses as the same case. Then the total number of cases is 1212 (or 1211 if you don't count the solved case).

 

[TDM]

What's the probability of not having at least one 1x1x2 pair (not calling centre+edge a pair) on a random state 3x3 scramble?

 

[cmhardw]

What's the probability of not having at least one 1x1x2 pair (not calling centre+edge a pair) on a random state 3x3 scramble?

I know I've attempted this one before in this thread. Searching... I used inclusion/exclusion, but perhaps it was argued (Stefan?) that this is not a valid way to count these cases?

--edit--
Lucas answers the question here

 

[TDM]

I know I've attempted this one before in this thread. Searching... I used inclusion/exclusion, but perhaps it was argued (Stefan?) that this is not a valid way to count these cases?

--edit--
Lucas answers the question here

Thanks! I'm not looking for a very specific answer so Lucas' estimate is fine, I just wanted to know whether I was getting really unlucky in my Roux solves or not

 

[obelisk477]

I remember seeing someone brute force this a while ago, and for some reason it was suspiciously close to 1÷e=.368 . Can't remember where I saw it though

 

[FJT97]

I just had 3 times in a row sure into the same R-Perm.
How is the probability for that?

 

[obelisk477]

Depends on if you're using beginners or edge control or something like that, where you always do OCLL then PLL, or if you do no edge control and standard OLL to PLL

 

[ryanj92]

Too bad. The initial idea is interesting, but unless the statistical distribution is quite far from the uniform, one will end up needing a few hundred LL patterns to cover the 80% probability mass and that's not practical. I might end up simulating by computer the Cross + F2L stages just too see what exactly is this distribution. I am quite a lazy person though, so don't count on it Plus I get the feeling that it's not so easy to program, otherwise someone would have already done it.

I'd argue that a simulated distribution isn't that useful - CFOP solvers rarely solve F2L in a 'blind' way and so we would expect the distribution to vary in some way from solver to solver. For instance of one uses basic edge control then all the LL cases with zero edges oriented don't show up...

 

[FJT97]

Depends on if you're using beginners or edge control or something like that, where you always do OCLL then PLL, or if you do no edge control and standard OLL to PLL

I use zz, so thats in fact with a higher chance..
So, i use zz but no wv and no sun colls...

 

[marfer]

Precisely:

Number of cases with probability 1/3888: 3864
Number of cases with probability 1/7776: 44
Number of cases with probability 1/15552: 8 (including solved case)

Total cases: 3916

When marfer was talking about the number of cases being about 1000, I believe he(?) was thinking of the number of cases if you count mirrors and inverses as the same case. Then the total number of cases is 1212 (or 1211 if you don't count the solved case).

Thanks for the precise numbers. The mirrors I gather they correspond to the four axes of symmetry of a square (Left-Right, Up-Down and diagonals), but what is an inverse of a LL pattern ?

I wrote a small computer simulation to test the probabilities, following strictly the CFOP method: a hand coded cross (not optimal ~average to 10 moves to solve) and then plug in the F2L algorithms from the wiki. Cube solves are started from a scrambled state with 30 random moves. Statistics on 1,000,000 cube solves produce the expected distinct 3916 cases (patterns) after the F2L (any color permutation, U, U2 or U' operatios are considered the same case). To further reduce these I consider equivalent all symmetric patterns on the four symmetry axes of the U face (vertical, horizontal and diagonals). After this step the 3916 cases reduce to 2054, still far from the expected 1212. What am I missing ?

So far, for the 2054 cases, the probability distribution looks depressingly uniform in average (see the attached ). That means there are some patterns that are more probable than others but to reach for example 50 percent probability one need to add about half of the cases. The cumulative distribution function is very close to the main diagonal of the graph (attached ).

For information, here is the probability distribution and cumulative distribution function for the 3916 cases without counting symmetrics as the same case. Still very close to uniform distribution.

If someone helps with the missing symmetries, I would like to produce graphs for the fully reduced situation with 1212 cases, so that we can safely conclude that the probabilistic attack on the last layer is doomed to failure because of the uniform probability distribution.

 

[cuBerBruce]

I wrote a small computer simulation to test the probabilities, following strictly the CFOP method: a hand coded cross (not optimal ~average to 10 moves to solve) and then plug in the F2L algorithms from the wiki. Cube solves are started from a scrambled state with 30 random moves. Statistics on 1,000,000 cube solves produce the expected distinct 3916 cases (patterns) after the F2L (any color permutation, U, U2 or U' operatios are considered the same case). To further reduce these I consider equivalent all symmetric patterns on the four symmetry axes of the U face (vertical, horizontal and diagonals). After this step the 3916 cases reduce to 2054, still far from the expected 1212. What am I missing ?

Yes, I agree that 2054 is correct number of cases when mirror symmetry is considered in addition to rotational symmetry.

What you are missing is antisymmetry, or considering inverses to be the same case. Then, the case generated by L F2 R' F' R F' L' and the case generated by L F R' F R F2 L' would be considered the same case, for example. From a speedsolving perspective, I don't know if it's practical to use this, other than rote memorization of what patterns are inverse cases of each other.

If someone helps with the missing symmetries, I would like to produce graphs for the fully reduced situation with 1212 cases, so that we can safely conclude that the probabilistic attack on the last layer is doomed to failure because of the uniform probability distribution.

I think I can pretty much guarantee that the inclusion of antisymmetry is not going to change the overall look of the graphs very much (except for scaling factors). The 1212 cases are dominated by 801 cases each having a probability of 1/972.