# Random 20 move scramble



## IQubic (Nov 14, 2012)

If 20 is god's number, I wonder what the chance is of a completely random 20 QTM scramble, gettiing you the Superflip pattern (all edges fliped incorrectly). My way of getting a random scarmble is this: Pick a random number 1 - 18.
1. F
2. F'
3. F2
4. R
5. R'
6. R2
7. U
8. U'
9. U2
10. L
11. L'
12. L2
13. B
14. B'
15. B2
16. D
17. D'
18. D2
Find the number you picked and preform that move, now pick another number 1 - 18, do that move, then repeat until 20 moves have been done. If you have a better way of getting a random scramble then please share.


----------



## cannon4747 (Nov 14, 2012)

http://www.cubetimer.com/
and then i just press spacebar every time i want a new one...
for serious timing though, id use this:
http://cubemania.org/


----------



## AustinReed (Nov 14, 2012)

Humans are never random. That's not going to be a "random" scramble. 

Plus, what if you pick 16, then 18?


----------



## qqwref (Nov 14, 2012)

IQubic said:


> If 20 is god's number, I wonder what the chance is of a completely random 20 QTM scramble, gettiing you the Superflip pattern (all edges fliped incorrectly).


Pretty low. You'd have to know the exact number of 20-move superflip solutions to calculate this though.

In general, if you scramble with 20 random moves, positions that require 20 moves are much less likely than positions that can be solved in fewer moves. If you're going to generate random moves, you should absolutely use more than 20 moves. 25 moves is typical.



IQubic said:


> My way of getting a random scarmble is this: Pick a random number 1 - 18. [...] Find the number you picked and preform that move, now pick another number 1 - 18, do that move, then repeat until 20 moves have been done. If you have a better way of getting a random scramble then please share.


This is an extremely poorly thought out method since it is very likely to give you moves that can be easily combined, such as B B2 or L R L. Any acceptable scrambling program will use a better method where those sequences aren't allowed. And a *good* scrambling program won't generate random moves, but will actually choose a random position and then give you a sequence of moves that gets there.


----------



## IQubic (Nov 14, 2012)

Okey, so any better ways? As for my method, I thought of it in 20 minutes, so the flaws have not been worked out


----------



## Ranzha (Nov 14, 2012)

It would be (# of 20-move superflip solutions)/(# of 20-move sequences)


----------



## ben1996123 (Nov 14, 2012)

gods number is 24qtm iThink.


----------



## IQubic (Nov 14, 2012)

ben1996123 said:


> gods number is 24qtm iThink.


So 20 is another metric?


----------



## ben1996123 (Nov 14, 2012)

IQubic said:


> So 20 is another metric?



20 is HTM


----------



## JonnyWhoopes (Nov 14, 2012)

IQubic said:


> So 20 is another metric?



[wiki]HTM[/wiki]

Also see [wiki]Metric[/wiki].


----------



## qqwref (Nov 14, 2012)

IQubic said:


> Okey, so any better ways?


Just use the standard way everyone else uses. This problem has been solved for years. Look at the code of basically any scrambler.


----------



## whauk (Nov 14, 2012)

if you find one solution you can easily create 960 using symmetries (some of them might be the same though).
factor 24 by conjugating with cube rotations, factor 2 by inverting the sequence, factor 20 by cycling the moves (or if you like this better: conjugating with the inverse of some moves at the beginning (which then obviously cancels out))

so i guess the number of superflip solutions is significantly higher than any other position with distance 20 from solved.


EDIT: i also do not understand why everyone wants to block the "hidden identities/shortcuts" in the move sequence. its very unlikely that you get a position that really requires 20 moves to solve in the end, so what is the point of filtering 1- or 2-move identities?

imo the number (#20-move-sequences that solve 20-move positions)/(#20-move-sequences that solve the superflip) is far more interesting. (and probably unsolvable without using computers)


----------



## rokicki (Nov 14, 2012)

ben1996123 said:


> gods number is 24qtm iThink.



We know of a position that requires 26 moves in the quarter turn metric to solve,
so it must be at least 26.


----------



## CubeRoots (Nov 14, 2012)

theres more than superflip thats 20 moves away. superflip is just the famous one


----------



## ben1996123 (Nov 14, 2012)

CubeRoots said:


> theres more than superflip thats 20 moves away. superflip is just the famous one



iirc there are about 300 million 20HTM positions.


----------



## cuBerBruce (Nov 14, 2012)

whauk said:


> if you find one solution you can easily create 960 using symmetries (some of them might be the same though).
> factor 24 by conjugating with cube rotations, factor 2 by inverting the sequence, factor 20 by cycling the moves (or if you like this better: conjugating with the inverse of some moves at the beginning (which then obviously cancels out))



Superflip has all 48 symmetries of the cube, not just the 24 pure rotational symmetries. So you can also use mirroring. This would seem to make a multiplying factor of 48*2*20 = 1920. Because of adjacent commuting moves, I believe you can get more than a factor of 20 from cyclic shifting. I also note that arbitrary cyclic shifting only works because superflip commutes with every other position.

Mike Reid's web site claims that there are only two "distinct" optimal maneuvers for superflip in face turn metric:

U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2 (20f*)
U R2 F B R B2 R U2 L B2 R U' D' R2 F D2 B2 U2 R' L (20f*)

It may be an interesting project to see exactly how many distinct variants you can produce from these two maneuvers.


----------



## qqwref (Nov 14, 2012)

Don't forget we can also invert the sequences


----------



## cuBerBruce (Nov 14, 2012)

qqwref said:


> Don't forget we can also invert the sequences



We didn't. symmetries: 48, inversion: 2, cyclic shift 20.


----------



## qqwref (Nov 14, 2012)

Ah, okay. So are we sure those two are the only ones up to symmetries?


----------



## IQubic (Nov 15, 2012)

So, hiw many ways to get Superflip? Would there be 43 Quintillion 20 move, because every scramble takes at least 20 moves to solve.


----------



## cuBerBruce (Nov 15, 2012)

IQubic said:


> So, hiw many ways to get Superflip? Would there be 43 Quintillion 20 move, because every scramble takes at least 20 moves to solve.



It's incorrect to say that every scramble takes 20 moves to solve. But none require more than that (in face turn metric). Of course, the number of 20-move scrambles is more than 43 quintillion.

First, we could consider *arbitrary* 20-move sequences, such as what would be generated by IQubic's simple scramble algorithm in the initial post. The number of such sequences is 18^20 = 12748236216396078174437376. This is enough to generate each position about 294743 times, but of course there will be a wide variation in the number for individual positions. But each position will be generated at least once. I think the number of these sequences producing superflip would be about 2*48*2*20*(2^3) = 30720. This is about 1 in 400 quintillion.

Second, we can consider "canonical" sequences only where we don't allow trivial redundancies like R R2 or L R L, and commuting moves are always in a specific order (as in U D but not D U). A recurrence formula gives the number of such 20-move canonical sequences to be 43946585901564160587264. This is enough to generate each position about 1016 times, but again the count for individual positions will vary. I think the number of times superflip would be generated by canonical sequences would be about 2*48*2*(20+3) = 4416. This is about 1 in 10 quintillion.

We would need to determine exactly the number of superflip maneuvers to get exact answers, but someone correct me if you think I've made any gross error in my estimates.

And I would be very surprised if Mike Reid's assertion would turn out to be incorrect about there being only 2 such optimal maneuvers, up to cyclic shifting, inversion, and conjugation by symmetries of the cube (and ordering of commuting moves, I might add). I note he also claims essentially only 4 optimal maneuvers in QTM. (link)


----------



## stannic (Nov 15, 2012)

Sorry if I am speaking out of ignorance, but what is the simple proof that picking up *exactly 20* random moves in HTM can give you any reachable Rubik's Cube configuration?

Of course it's not true in QTM because half of all the configurations is at even distance, and other half is at odd distance. So if you do, say, 26 random QTM moves, you cannot get position solvable in 25 QTM moves.

*Edit*: And what if only "canonical" sequences are allowed? Can any configuration be reached in this case?

- Bulat


----------



## Ton (Nov 15, 2012)

AustinReed said:


> Humans are never random. That's not going to be a "random" scramble.
> 
> Plus, what if you pick 16, then 18?



Very true, that was one of the reason the Brits broke the German Enigma code , the key was generated by the operator....
To generate a real random sequence is not that simple as it sounds.... even the basic random generators are not random enough


----------



## cuBerBruce (Nov 15, 2012)

stannic said:


> Sorry if I am speaking out of ignorance, but what is the simple proof that picking up *exactly 20* random moves in HTM can give you any reachable Rubik's Cube configuration?
> 
> Of course it's not true in QTM because half of all the configurations is at even distance, and other half is at odd distance. So if you do, say, 26 random QTM moves, you cannot get position solvable in 25 QTM moves.
> 
> ...



If a position is 20f*, it obviously can be generated by a 20f maneuver. If a position is less than 20f*, you can expand it using trivial identies (e.g. U = U' U2) to get to 20 moves. And no position is more than 20f*. I made no claim that the same goes for canonical maneuvers, or even if just consecutive moves of the same layer are disallowed. And, of course, it's definitely not the case for QTM.


----------



## IQubic (Nov 16, 2012)

But, CubeTimer give hard enough scrambles for me to solve.


----------



## qqwref (Nov 16, 2012)

cuBerBruce said:


> If a position is 20f*, it obviously can be generated by a 20f maneuver. If a position is less than 20f*, you can expand it using trivial identies (e.g. U = U' U2) to get to 20 moves. And no position is more than 20f*. I made no claim that the same goes for canonical maneuvers


I would be quite interested in seeing a 19f* (or less? 19 seems the most plausible) position with no 20f solutions. I wonder if there's any way of trying to search for this other than by generating random scrambles and exhaustively checking all 20-move solutions.



IQubic said:


> But, CubeTimer give hard enough scrambles for me to solve.


Sure they might be "hard enough", but it's still true that the hardest scrambles are less likely, so your times might be better than they should be. It really starts to matter when you can build blocks and plan two steps ahead in inspection, so it makes sense that you wouldn't be at this level yet.


----------



## IQubic (Nov 16, 2012)

Well alright, Can you refer me to a good scambler and timer.


----------



## qqwref (Nov 16, 2012)

I personally use http://www.qqtimer.net/ but there are plenty of others out there. Search around


----------



## Herbert Kociemba (Nov 16, 2012)

cuBerBruce said:


> Second, we can consider "canonical" sequences only where we don't allow trivial redundancies like R R2 or L R L, and commuting moves are always in a specific order (as in U D but not D U). A recurrence formula gives the number of such 20-move canonical sequences to be 43946585901564160587264. This is enough to generate each position about 1016 times, but again the count for individual positions will vary. I think the number of times superflip would be generated by canonical sequences would be about 2*48*2*(20+3) = 4416. This is about 1 in 10 quintillion.
> 
> We would need to determine exactly the number of superflip maneuvers to get exact answers, but someone correct me if you think I've made any gross error in my estimates.



I used my Cube Explorer program to generate all essential different maneuvers for superflip. Cube Explorer reduces the search space by the symmetries of the position, but not really strict. So I had to remove some of the generated positions manually. I hope I did nothing wrong here. What remains is a list of 108 maneuvers, lexicographically sorted in the order U,R,F,D,L,B. Each of these maneuvers can be expanded to 48 different maneuvers by applying the 48 symmetries. So there should be 108*48 =5184 different canonical sequences which give superflip, considerably more than the 4416 of your estimation.

U R U2 R F2 L U2 R F' B' R2 D R' L U2 F2 D2 F R2 D (20f*) 
U R U2 R F2 L U2 R F' B' R2 D B2 U2 F2 R' L F R2 D (20f*) 
U R D2 R B2 L D2 R F' B' R2 U R' L D2 B2 U2 B R2 D (20f*) 
U R D2 R B2 L D2 R F' B' R2 U F2 D2 B2 R' L B R2 D (20f*) 
U R D2 F B D B2 D R2 U B2 D R' L' D2 F L2 B2 R2 D' (20f*) 
U R D2 F' B' D L2 U F2 D L2 D R L D2 F R2 F2 L2 D' (20f*) 
U R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 (20f*) 
U R L U2 F L2 F2 R2 U' D L U2 F' B' U R2 D F2 U R2 (20f*) 
U R L U2 B U' D B2 L2 F2 R U2 F' B' U L2 D B2 U L2 (20f*) 
U R L U2 B R2 B2 L2 U' D R U2 F' B' U L2 D B2 U L2 (20f*) 
U R L' U2 B2 D2 F L2 U' D' L B2 R U2 L B2 L F B L2 (20f*) 
U R L' D2 F2 U2 F L2 U D L D2 L F2 R D2 L F' B' L2 (20f*) 
U R2 U R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 (20f*) 
U R2 U R L U2 F L2 F2 R2 U' D L U2 F' B' U R2 D F2 (20f*) 
U R2 U B2 D R2 U F' B' U2 L U' D R2 B2 L2 B U2 R L (20f*) 
U R2 U B2 D R2 U F' B' U2 L F2 R2 B2 U' D B U2 R L (20f*) 
U R2 U2 L2 F' B R F2 U' D' F L2 B U2 F L2 F R L F2 (20f*) 
U R2 F U2 F2 D2 R' L U R2 F' B' R D2 L F2 R D2 R D (20f*) 
U R2 F R' L F2 D2 B2 U R2 F' B' R D2 L F2 R D2 R D (20f*) 
U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2 (20f*) 
U R2 F B R B2 R U2 L B2 R U' D' R2 F D2 B2 U2 R' L (20f*) 
U R2 F2 L2 F D2 R L D R2 D F2 U R2 D F' B' D2 L D' (20f*) 
U R2 F2 L2 F' U2 R' L' U' R2 U' F2 D' R2 U' F B U2 L' D' (20f*) 
U R2 F2 L2 B D2 R' L' D F2 U R2 D F2 D F B D2 R D' (20f*) 
U R2 F2 L2 B' U2 R L U' F2 D' R2 U' F2 U' F' B' U2 R' D' (20f*) 
U R2 F' U2 B2 D2 R L' D' R2 F' B' R' B2 R' D2 L' B2 R' D (20f*) 
U R2 F' R L' B2 D2 F2 D' R2 F' B' R' B2 R' D2 L' B2 R' D (20f*) 
U R2 F' B' R D2 L F2 R D2 R U D R2 F U2 F2 D2 R' L (20f*) 
U R2 F' B' R D2 L F2 R D2 R U D R2 F R' L F2 D2 B2 (20f*) 
U R2 D F2 U R2 U R L U2 F U' D F2 R2 B2 L U2 F' B' (20f*) 
U R2 D F2 U R2 U R L U2 F L2 F2 R2 U' D L U2 F' B' (20f*) 
U R2 D F2 U R' L' U2 B U' D F2 R2 B2 R U2 F B U F2 (20f*) 
U R2 D F2 U R' L' U2 B L2 F2 R2 U' D R U2 F B U F2 (20f*) 
U R2 D F2 D F B D2 R U D' R2 F2 L2 B D2 R' L' D F2 (20f*) 
U R2 D F2 D F B D2 R B2 R2 F2 U D' B D2 R' L' D F2 (20f*) 
U R2 D F' B' D2 L U D' R2 F2 L2 F D2 R L D R2 D F2 (20f*) 
U R2 D F' B' D2 L B2 R2 F2 U D' F D2 R L D R2 D F2 (20f*) 
U R2 D2 L2 F B' L B2 U D B D2 B L2 F D2 B R' L' B2 (20f*) 
U R2 B R' L B2 U2 F2 D R2 F' B' R U2 L B2 R U2 R D (20f*) 
U R2 B D2 B2 U2 R' L D R2 F' B' R U2 L B2 R U2 R D (20f*) 
U R2 B' R L' F2 U2 B2 U' R2 F' B' R' F2 R' U2 L' F2 R' D (20f*) 
U R2 B' D2 F2 U2 R L' U' R2 F' B' R' F2 R' U2 L' F2 R' D (20f*) 
U R' U2 F B U' L2 D' F2 U' L2 U' R' L' U2 F' R2 F2 L2 D' (20f*) 
U R' U2 F' B' U' B2 U' R2 D' B2 U' R L U2 F' L2 B2 R2 D' (20f*) 
U R' F2 L' D2 R' F2 R' F' B' R2 D' R L' D2 F2 U2 B' R2 D (20f*) 
U R' F2 L' D2 R' F2 R' F' B' R2 D' B2 D2 F2 R L' B' R2 D (20f*) 
U R' L U2 F2 D2 B R2 U' D' R F2 L U2 R F2 R F B R2 (20f*) 
U R' L D2 B2 U2 B R2 U D R D2 R B2 L D2 R F' B' R2 (20f*) 
U R' L' U2 F U' D B2 L2 F2 L U2 F B U B2 U L2 D B2 (20f*) 
U R' L' U2 F R2 B2 L2 U' D L U2 F B U B2 U L2 D B2 (20f*) 
U R' L' U2 B U' D F2 R2 B2 R U2 F B U F2 U R2 D F2 (20f*) 
U R' L' U2 B L2 F2 R2 U' D R U2 F B U F2 U R2 D F2 (20f*) 
U R' B2 L' U2 R' B2 R' F' B' R2 U' R L' U2 B2 D2 F' R2 D (20f*) 
U R' B2 L' U2 R' B2 R' F' B' R2 U' F2 U2 B2 R L' F' R2 D (20f*) 
U D R U2 R F2 L U2 R F' B' R2 D R' L U2 F2 D2 F R2 (20f*) 
U D R U2 R F2 L U2 R F' B' R2 D B2 U2 F2 R' L F R2 (20f*) 
U D R2 F U2 F2 D2 R' L U R2 F' B' R D2 L F2 R D2 R (20f*) 
U D R2 F R' L F2 D2 B2 U R2 F' B' R D2 L F2 R D2 R (20f*) 
U D R2 F' U2 B2 D2 R L' D' R2 F' B' R' B2 R' D2 L' B2 R' (20f*) 
U D R2 F' R L' B2 D2 F2 D' R2 F' B' R' B2 R' D2 L' B2 R' (20f*) 
U D R' F2 L' D2 R' F2 R' F' B' R2 D' R L' D2 F2 U2 B' R2 (20f*) 
U D R' F2 L' D2 R' F2 R' F' B' R2 D' B2 D2 F2 R L' B' R2 (20f*) 
U D R' B2 L' U2 R' B2 R' F' B' R2 U' R L' U2 B2 D2 F' R2 (20f*) 
U D R' B2 L' U2 R' B2 R' F' B' R2 U' F2 U2 B2 R L' F' R2 (20f*) 
U D' R D2 F B D B2 D R2 U B2 D R' L' D2 F L2 B2 R2 (20f*) 
U D' R D2 F' B' D L2 U F2 D L2 D R L D2 F R2 F2 L2 (20f*) 
U D' R2 F2 L2 F D2 R L D R2 D F2 U R2 D F' B' D2 L (20f*) 
U D' R2 F2 L2 B D2 R' L' D F2 U R2 D F2 D F B D2 R (20f*) 
U2 R U D R2 B R' L B2 U2 F2 D R2 F' B' R U2 L B2 R (20f*) 
U2 R U D R2 B D2 B2 U2 R' L D R2 F' B' R U2 L B2 R (20f*) 
U2 R U' D R2 B2 L2 F U2 R' L' U B2 D R2 U B2 U F B (20f*) 
U2 R U' D L2 F2 R2 F U2 R L U L2 U F2 D L2 U F' B' (20f*) 
U2 R F2 U D F D2 F R2 B D2 F R' L' F2 U F' B D2 R2 (20f*) 
U2 R F2 R F B R2 U R' L U2 F2 D2 B R2 U' D' R F2 L (20f*) 
U2 R F2 R F B R2 U B2 U2 F2 R' L B R2 U' D' R F2 L (20f*) 
U2 R F2 R2 B2 U' D F U2 R' L' U B2 D R2 U B2 U F B (20f*) 
U2 R F2 L U2 R F' B' R2 D R' L U2 F2 D2 F R2 U D R (20f*) 
U2 R F2 L U2 R F' B' R2 D B2 U2 F2 R' L F R2 U D R (20f*) 
U2 R F2 L U2 L U D L2 F R L' F2 U2 B2 D L2 F' B' L (20f*) 
U2 R F2 L U2 L U D L2 F D2 F2 U2 R L' D L2 F' B' L (20f*) 
U2 R F2 L U' D' L2 B R L' F2 U2 B2 U L2 F B L F2 L (20f*) 
U2 R F2 L U' D' L2 B D2 F2 U2 R L' U L2 F B L F2 L (20f*) 
U2 R F' B' R2 D R' L U2 F2 D2 F R2 U D R U2 R F2 L (20f*) 
U2 R F' B' R2 D B2 U2 F2 R' L F R2 U D R U2 R F2 L (20f*) 
U2 R L U R2 U B2 D R2 U F' B' U2 L U' D R2 B2 L2 B (20f*) 
U2 R L U R2 U B2 D R2 U F' B' U2 L F2 R2 B2 U' D B (20f*) 
U2 R L U L2 U F2 D L2 U F' B' U2 R U' D L2 F2 R2 F (20f*) 
U2 R L U L2 U F2 D L2 U F' B' U2 R B2 L2 F2 U' D F (20f*) 
U2 R L U' F2 D' R2 U' F2 U' F' B' U2 R' U D' R2 F2 L2 B' (20f*) 
U2 R L U' F2 D' R2 U' F2 U' F' B' U2 R' B2 R2 F2 U D' B' (20f*) 
U2 R L U' B2 D' L2 U' B2 U' F' B' U2 L' U D' L2 B2 R2 F' (20f*) 
U2 R L U' B2 D' L2 U' B2 U' F' B' U2 L' F2 L2 B2 U D' F' (20f*) 
U2 R L' U L2 F B L F2 L U2 R F2 L U' D' L2 B D2 F2 (20f*) 
U2 R L' U' R2 F' B' R' F2 R' U2 L' F2 R' U D R2 B' D2 F2 (20f*) 
U2 R L' D L2 F' B' L U2 R F2 L U2 L U D L2 F D2 F2 (20f*) 
U2 R L' D' R2 F B R' U2 L' F2 R' U2 R' U' D' R2 F' D2 F2 (20f*) 
U2 R B2 U' D' B L2 F D2 B L2 B R L B2 D F B' D2 L2 (20f*) 
U2 R B2 L2 F2 U' D F U2 R L U L2 U F2 D L2 U F' B' (20f*) 
U2 R2 U B2 R L B L2 B U2 F L2 B U' D' B2 R F B' L2 (20f*) 
U2 R2 F B' R B2 U D B U2 B R2 F U2 B R' L' B2 D L2 (20f*) 
U2 R2 F B' R' F2 U' D' F' U2 F' R2 B' U2 F' R L F2 D' L2 (20f*) 
U2 R2 F B' L B2 U' D' B R2 F U2 B R2 B R L B2 U L2 (20f*) 
U2 R2 F B' L' F2 U D F' R2 B' U2 F' R2 F' R' L' F2 U' L2 (20f*) 
U2 R2 D B2 R' L' B U2 F L2 B U2 B U D B2 L F B' L2 (20f*) 
U2 R2 D2 R B2 U D B U2 B R2 F U2 B R' L' B2 D F B' (20f*) 
U2 R2 D2 F B' U B2 R' L' B D2 F R2 B D2 B U D B2 R (20f*) 
U2 R2 D2 F B' D B2 R L B R2 B D2 F R2 B U' D' B2 L (20f*) 
U2 R2 D2 L B2 U' D' B R2 F U2 B R2 B R L B2 U F B' (20f*)


----------



## cuBerBruce (Nov 17, 2012)

Herbert Kociemba said:


> So there should be 108*48 =5184 different canonical sequences which give superflip, considerably more than the 4416 of your estimation.


I think Herbert's value of 5184 is an overcount. I think the sequences starting with U D and U D' may lead to duplicates (after canonicalization) when expanding by symmetries. It's not clear to me that accounts for the difference between my 4416 and Herbert's 5184, though. I will try to analyze this further.


----------



## qqwref (Nov 17, 2012)

Every sequence Kociemba posted is equivalent to either U2 R2 D2 F B' D B2 L R B R2 B D2 F R2 B D' U' B2 L or U2 R2 D2 F B' U B2 L' R' B D2 F R2 B D2 B D U B2 R by move cycling, rotation, mirroring, inversion, and swapping two adjacent moves on the same axis. (Also, Reid's two sequences are equivalent to those two.)


----------



## IQubic (Nov 17, 2012)

qqwref said:


> I personally use http://www.qqtimer.net/ but there are plenty of others out there. Search around


Okey, now I would like to get Sub 20, so any hints?


----------



## cuBerBruce (Nov 17, 2012)

I have generated the 5184 sequences generated by applying the 48 cube symmetries to the 108 sequences posted by Herbert. After canonicalizing these sequences, my code indicates there are 768 duplicates among these. 5184 - 768 = 4416, so I am pretty confident that the 4416 canonical optimal maneuvers I estimated for superflip is in fact the correct number.


----------



## Herbert Kociemba (Nov 17, 2012)

cuBerBruce said:


> I have generated the 5184 sequences generated by applying the 48 cube symmetries to the 108 sequences posted by Herbert. After canonicalizing these sequences, my code indicates there are 768 duplicates among these. 5184 - 768 = 4416, so I am pretty confident that the 4416 canonical optimal maneuvers I estimated for superflip is in fact the correct number.


It would be very helpful for me to understand where my reasoning went wrong if you name a few duplicates.

Edit1: Ok, I found at least one error, indeed concerning maneuvers starting with UD.

U D R' F2 L' D2 R' F2 R' F' B' R2 D' R L' D2 F2 U2 B' R2 (20f*)
and
U D R' B2 L' U2 R' B2 R' F' B' R2 U' R L' U2 B2 D2 F' R2 (20f*)
are for example equivalent by CR2 rotation.
Will have to look where the other 15 duplicates are...

Edit2: I really took a closer look, especially at the sequences starting U D.. and U D' . 

I found another pair 
U D R' F2 L' D2 R' F2 R' F' B' R2 D' B2 D2 F2 R L' B' R2 (20f*)
and
U D R' B2 L' U2 R' B2 R' F' B' R2 U' F2 U2 B2 R L' F' R2 (20f*)
also related by CR2
but still 14 duplicates are missing. Bruce maybe you can give me a hint.


----------



## cuBerBruce (Nov 17, 2012)

Herbert Kociemba said:


> It would be very helpful for me to understand where my reasoning went wrong if you name a few duplicates.


OK, I get the following as the first duplicate pair:

Line 7: U R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 (20f*)
Line 9: U R L U2 B U' D B2 L2 F2 R U2 F' B' U L2 D B2 U L2 (20f*)

The full list of duplicate pairs are the following:
(7, 9)
(8, 10)
(11, 47)
(12, 48)
(49, 51)
(50, 52)
(61, 63)
(62, 64)
(85, 87)
(86, 88)
(89, 91)
(90, 92)
(93, 94)
(95, 96)
(100, 101)
(102, 103)


----------



## Herbert Kociemba (Nov 17, 2012)

cuBerBruce said:


> OK, I get the following as the first duplicate pair:
> 
> Line 7: U R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 (20f*)
> Line 9: U R L U2 B U' D B2 L2 F2 R U2 F' B' U L2 D B2 U L2 (20f*)



You are totally right. I forgot lots of situations where two moves like RL commute.
I just thought for example that two different maneuvers which both start with U R cannot be equivalent because U R itself has no symmetry. Which is not true.
Thanks for the correction. 
The following list of 92 maneuvers should be ok now and should expand indeed to 92*48 = 4416 different maneuvers. Maybe you can run your program again over this set to doublecheck the result.



Spoiler



U R U2 R F2 L U2 R F' B' R2 D R' L U2 F2 D2 F R2 D (20f*) 
U R U2 R F2 L U2 R F' B' R2 D B2 U2 F2 R' L F R2 D (20f*) 
U R D2 R B2 L D2 R F' B' R2 U R' L D2 B2 U2 B R2 D (20f*) 
U R D2 R B2 L D2 R F' B' R2 U F2 D2 B2 R' L B R2 D (20f*) 
U R D2 F B D B2 D R2 U B2 D R' L' D2 F L2 B2 R2 D' (20f*) 
U R D2 F' B' D L2 U F2 D L2 D R L D2 F R2 F2 L2 D' (20f*) 
U R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 (20f*) 
U R L U2 F L2 F2 R2 U' D L U2 F' B' U R2 D F2 U R2 (20f*) 
U R L' U2 B2 D2 F L2 U' D' L B2 R U2 L B2 L F B L2 (20f*) 
U R L' D2 F2 U2 F L2 U D L D2 L F2 R D2 L F' B' L2 (20f*) 
U R2 U R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 (20f*) 
U R2 U R L U2 F L2 F2 R2 U' D L U2 F' B' U R2 D F2 (20f*) 
U R2 U B2 D R2 U F' B' U2 L U' D R2 B2 L2 B U2 R L (20f*) 
U R2 U B2 D R2 U F' B' U2 L F2 R2 B2 U' D B U2 R L (20f*) 
U R2 U2 L2 F' B R F2 U' D' F L2 B U2 F L2 F R L F2 (20f*) 
U R2 F U2 F2 D2 R' L U R2 F' B' R D2 L F2 R D2 R D (20f*) 
U R2 F R' L F2 D2 B2 U R2 F' B' R D2 L F2 R D2 R D (20f*) 
U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2 (20f*) 
U R2 F B R B2 R U2 L B2 R U' D' R2 F D2 B2 U2 R' L (20f*) 
U R2 F2 L2 F D2 R L D R2 D F2 U R2 D F' B' D2 L D' (20f*) 
U R2 F2 L2 F' U2 R' L' U' R2 U' F2 D' R2 U' F B U2 L' D' (20f*) 
U R2 F2 L2 B D2 R' L' D F2 U R2 D F2 D F B D2 R D' (20f*) 
U R2 F2 L2 B' U2 R L U' F2 D' R2 U' F2 U' F' B' U2 R' D' (20f*) 
U R2 F' U2 B2 D2 R L' D' R2 F' B' R' B2 R' D2 L' B2 R' D (20f*) 
U R2 F' R L' B2 D2 F2 D' R2 F' B' R' B2 R' D2 L' B2 R' D (20f*) 
U R2 F' B' R D2 L F2 R D2 R U D R2 F U2 F2 D2 R' L (20f*) 
U R2 F' B' R D2 L F2 R D2 R U D R2 F R' L F2 D2 B2 (20f*) 
U R2 D F2 U R2 U R L U2 F U' D F2 R2 B2 L U2 F' B' (20f*) 
U R2 D F2 U R2 U R L U2 F L2 F2 R2 U' D L U2 F' B' (20f*) 
U R2 D F2 U R' L' U2 B U' D F2 R2 B2 R U2 F B U F2 (20f*) 
U R2 D F2 U R' L' U2 B L2 F2 R2 U' D R U2 F B U F2 (20f*) 
U R2 D F2 D F B D2 R U D' R2 F2 L2 B D2 R' L' D F2 (20f*) 
U R2 D F2 D F B D2 R B2 R2 F2 U D' B D2 R' L' D F2 (20f*) 
U R2 D F' B' D2 L U D' R2 F2 L2 F D2 R L D R2 D F2 (20f*) 
U R2 D F' B' D2 L B2 R2 F2 U D' F D2 R L D R2 D F2 (20f*) 
U R2 D2 L2 F B' L B2 U D B D2 B L2 F D2 B R' L' B2 (20f*) 
U R2 B R' L B2 U2 F2 D R2 F' B' R U2 L B2 R U2 R D (20f*) 
U R2 B D2 B2 U2 R' L D R2 F' B' R U2 L B2 R U2 R D (20f*) 
U R2 B' R L' F2 U2 B2 U' R2 F' B' R' F2 R' U2 L' F2 R' D (20f*) 
U R2 B' D2 F2 U2 R L' U' R2 F' B' R' F2 R' U2 L' F2 R' D (20f*) 
U R' U2 F B U' L2 D' F2 U' L2 U' R' L' U2 F' R2 F2 L2 D' (20f*) 
U R' U2 F' B' U' B2 U' R2 D' B2 U' R L U2 F' L2 B2 R2 D' (20f*) 
U R' F2 L' D2 R' F2 R' F' B' R2 D' R L' D2 F2 U2 B' R2 D (20f*) 
U R' F2 L' D2 R' F2 R' F' B' R2 D' B2 D2 F2 R L' B' R2 D (20f*) 
U R' L' U2 F U' D B2 L2 F2 L U2 F B U B2 U L2 D B2 (20f*) 
U R' L' U2 F R2 B2 L2 U' D L U2 F B U B2 U L2 D B2 (20f*) 
U R' B2 L' U2 R' B2 R' F' B' R2 U' R L' U2 B2 D2 F' R2 D (20f*) 
U R' B2 L' U2 R' B2 R' F' B' R2 U' F2 U2 B2 R L' F' R2 D (20f*) 
U D R U2 R F2 L U2 R F' B' R2 D R' L U2 F2 D2 F R2 (20f*) 
U D R U2 R F2 L U2 R F' B' R2 D B2 U2 F2 R' L F R2 (20f*) 
U D R2 F U2 F2 D2 R' L U R2 F' B' R D2 L F2 R D2 R (20f*) 
U D R2 F R' L F2 D2 B2 U R2 F' B' R D2 L F2 R D2 R (20f*) 
U D R2 F' U2 B2 D2 R L' D' R2 F' B' R' B2 R' D2 L' B2 R' (20f*) 
U D R2 F' R L' B2 D2 F2 D' R2 F' B' R' B2 R' D2 L' B2 R' (20f*) 
U D R' F2 L' D2 R' F2 R' F' B' R2 D' R L' D2 F2 U2 B' R2 (20f*) 
U D R' F2 L' D2 R' F2 R' F' B' R2 D' B2 D2 F2 R L' B' R2 (20f*) 
U D' R D2 F B D B2 D R2 U B2 D R' L' D2 F L2 B2 R2 (20f*) 
U D' R D2 F' B' D L2 U F2 D L2 D R L D2 F R2 F2 L2 (20f*) 
U D' R2 F2 L2 F D2 R L D R2 D F2 U R2 D F' B' D2 L (20f*) 
U D' R2 F2 L2 B D2 R' L' D F2 U R2 D F2 D F B D2 R (20f*) 
U2 R U D R2 B R' L B2 U2 F2 D R2 F' B' R U2 L B2 R (20f*) 
U2 R U D R2 B D2 B2 U2 R' L D R2 F' B' R U2 L B2 R (20f*) 
U2 R U' D R2 B2 L2 F U2 R' L' U B2 D R2 U B2 U F B (20f*) 
U2 R U' D L2 F2 R2 F U2 R L U L2 U F2 D L2 U F' B' (20f*) 
U2 R F2 U D F D2 F R2 B D2 F R' L' F2 U F' B D2 R2 (20f*) 
U2 R F2 R F B R2 U R' L U2 F2 D2 B R2 U' D' R F2 L (20f*) 
U2 R F2 R F B R2 U B2 U2 F2 R' L B R2 U' D' R F2 L (20f*) 
U2 R F2 R2 B2 U' D F U2 R' L' U B2 D R2 U B2 U F B (20f*) 
U2 R F2 L U2 R F' B' R2 D R' L U2 F2 D2 F R2 U D R (20f*) 
U2 R F2 L U2 R F' B' R2 D B2 U2 F2 R' L F R2 U D R (20f*) 
U2 R F2 L U2 L U D L2 F R L' F2 U2 B2 D L2 F' B' L (20f*) 
U2 R F2 L U2 L U D L2 F D2 F2 U2 R L' D L2 F' B' L (20f*) 
U2 R F2 L U' D' L2 B R L' F2 U2 B2 U L2 F B L F2 L (20f*) 
U2 R F2 L U' D' L2 B D2 F2 U2 R L' U L2 F B L F2 L (20f*) 
U2 R F' B' R2 D R' L U2 F2 D2 F R2 U D R U2 R F2 L (20f*) 
U2 R F' B' R2 D B2 U2 F2 R' L F R2 U D R U2 R F2 L (20f*) 
U2 R L U R2 U B2 D R2 U F' B' U2 L U' D R2 B2 L2 B (20f*) 
U2 R L U R2 U B2 D R2 U F' B' U2 L F2 R2 B2 U' D B (20f*) 
U2 R L U' F2 D' R2 U' F2 U' F' B' U2 R' U D' R2 F2 L2 B' (20f*) 
U2 R L U' F2 D' R2 U' F2 U' F' B' U2 R' B2 R2 F2 U D' B' (20f*) 
U2 R L' U L2 F B L F2 L U2 R F2 L U' D' L2 B D2 F2 (20f*) 
U2 R L' D L2 F' B' L U2 R F2 L U2 L U D L2 F D2 F2 (20f*) 
U2 R B2 U' D' B L2 F D2 B L2 B R L B2 D F B' D2 L2 (20f*) 
U2 R B2 L2 F2 U' D F U2 R L U L2 U F2 D L2 U F' B' (20f*) 
U2 R2 U B2 R L B L2 B U2 F L2 B U' D' B2 R F B' L2 (20f*) 
U2 R2 F B' R B2 U D B U2 B R2 F U2 B R' L' B2 D L2 (20f*) 
U2 R2 F B' L B2 U' D' B R2 F U2 B R2 B R L B2 U L2 (20f*) 
U2 R2 D B2 R' L' B U2 F L2 B U2 B U D B2 L F B' L2 (20f*) 
U2 R2 D2 R B2 U D B U2 B R2 F U2 B R' L' B2 D F B' (20f*) 
U2 R2 D2 F B' U B2 R' L' B D2 F R2 B D2 B U D B2 R (20f*) 
U2 R2 D2 F B' D B2 R L B R2 B D2 F R2 B U' D' B2 L (20f*) 
U2 R2 D2 L B2 U' D' B R2 F U2 B R2 B R L B2 U F B' (20f*)


----------



## cuBerBruce (Nov 17, 2012)

Herbert Kociemba said:


> Maybe you can run your program again over this set to doublecheck the result.



Done. With the new list, I do not find any duplicates, 4416 total after expanding by symmetries.

I think many scramble programs may generate adjacent commuting moves in either order, as in U D2 or D2 U, but never the same layer twice before switching axis. This would result with yet a different ratio for superflip maneuvers vs. total 20-moves scrambles.


----------



## qqwref (Nov 17, 2012)

Good point. Random-move scramblers usually don't regularize their output, they just choose possible moves one at a time, so U D2 and D2 U are both possible.

It's probably reasonable to conclude that the superflip is by far the most likely 20f* position to pop up if you do 20 random moves on the cube.


----------



## Stefan (Nov 17, 2012)

qqwref said:


> It's probably reasonable to conclude that the superflip is by far the most likely 20f* position to pop up if you do 20 random moves on the cube.



Might even beat many 19f* positions...


----------



## IQubic (Nov 18, 2012)

Yes, But are the chances of getting it?


----------



## qqwref (Nov 18, 2012)

4416/43946585901564160587264 ~= 1.005 * 10^-19


----------



## IQubic (Nov 18, 2012)

How in the world did you manege to get that number?!?!?!?


----------



## cubernya (Nov 18, 2012)

IQubic said:


> How in the world did you manege to get that number?!?!?!?



Number of scrambles that lead to superflip divided by the number of 20 move scrambles


----------



## cuBerBruce (Nov 18, 2012)

qqwref said:


> 4416/43946585901564160587264 ~= 1.005 * 10^-19





theZcuber said:


> Number of scrambles that lead to superflip divided by the number of 20 move scrambles



I note that it assumes that the 20-move scrambles would each have the same chance of occurring.

If the typical way scrambles are generated allows commuting moves in either order, then the numbers are somewhat different.

The total number of 20-move scrambles then is then 211768161058569529589760. (At least that's what I get.) The number of 20-move superflip maneuvers allowing commuting moves in either order I believe is: 48*((92-24)*(2^3) + 24*(2^2)) = 30720. That gives about 1 chance in 6.89 quintillion.

But that's not really the correct number because the possible scrambles do not have equal probabilities of occurring. What you really must do is add up the probabilities for each of the 30720 superflip scrambles. (Symmetry considerations can simplify this calculation quite a bit.)


----------



## qqwref (Nov 19, 2012)

I spent a little time thinking about scrambling probabilities and came to the conclusion that we can figure out the probabilities for an N-move sequence or its equivalent (e.g. LR or RL are both acceptable) being generated by a normal random-move scrambler is:
1/6 * 1/5^(N-1) * 5/4^(number of adjacent same-axis move pairs not at the very end of the sequence) * 2^(number of adjacent same-axis move pairs).

So if we consider R U R' L U L' R, its probability of its being generated from a 7-move scrambler is 1/6 * 1/5^(6) * 5/4^(1) * 2^(2) = 1/18750. Note that that number allows both ...R L'... and ...L' R...

If we want to know the exact probability of one of a given list of N-move sequences being generated, we can just sum the probability of each one (which only really requires knowing how many same-axis move pairs are in each one, and whether any of those are at the very end of the sequence). It won't be as easy as just dividing two numbers, but fortunately we don't have to actually work out the number of sequences of that length.


----------



## IQubic (Nov 19, 2012)

Can someone give me the source code of a scrambler, so I can work out the chances of getting the superflip?


----------



## peterbone (Nov 19, 2012)

IQubic said:


> Can someone give me the source code of a scrambler, so I can work out the chances of getting the superflip?


What are you thinking of doing? Generating random scrambles and counting how many superflips you get? I don't think that will work even for a super-computer. Maybe you have something else in mind?


----------



## cuBerBruce (Nov 20, 2012)

OK, I believe I have the actual probability for the supewrflip position being generated by a 20-move scramblebeing for a typical scramble program that generates commuting moves in either order, but avoids trivial redundancies.

The 92 cases Herbert listed can be partitioned into three sets:
1) those that start and end with commuting moves
2) those that end with a pair of commuting moves
3) all others

For these categories, the following table gives:
1) the number of cases (out of the total of 92)
2) a miultipler (how many variations you can generate by swapping adjacent commuting moves)
3) a symmetry multiplier (48 in each case)
4) the probability of a scramble matching the maneuver (not including multiplier effects)


```
Category   cases   mult.   sym. mult.        probability

    1        24      4        48       (1/18)*(1/15)^17*(1/12)^2
    2        12      8        48       (1/18)*(1/15)^17*(1/12)^2
    3        56      8        48       (1/18)*(1/15)^16*(1/12)^3
```
Multiplying out the values in the three categories, and summing, this yields a value of 376 / 2660205384063720703125. This is about 1 in 7.075*(10^18).

Of course, this assumes the scramble generator uses a random number generator (PRNG plus scaling logic) with ideal characteristics.


----------



## Carrot (Nov 20, 2012)

IQubic said:


> Can someone give me the source code of a scrambler, so I can work out the chances of getting the superflip?





```
,/("FRUDLB"@{#&(=':x),2_&':5=+':x}{25?6}/2#2),'25?" ","'2",'" "
```
(language: K; written by: qqwref)


----------



## IQubic (Nov 20, 2012)

peterbone said:


> What are you thinking of doing? Generating random scrambles and counting how many superflips you get? I don't think that will work even for a super-computer. Maybe you have something else in mind?


I will have Guy, the guy guy get me a programming/mathematics guy. We will tackle the problem together.


----------

