# Distribution of 20-move strong scrambles



## SenileGenXer (Oct 19, 2013)

I was thinking about the superflip and how any random move theoretically makes it one step closer to solved. I understand this isn't just because it's a 20 move strong scramble but also because it's symmetrical.

I was thinking of these 20 move strong scrambles as about 3 million poles of maximum randomness even though the superflip just isn't that random. Obviously they are all spaced far away from the identity cube in scramble space. Are any of these 3 million poles touching one another? That is can turning a face on a maximally strong scramble generate a different maximally strong scramble? 

Do 20 move strong scrambles share any properties like really bad edges?

Has there been an even partial survey of these strongest scrambles? Are there other maximally strong scrambles of interest besides the super-flip?


----------



## Tim Major (Oct 19, 2013)

So you mean having a 20 move optimal scramble, doing one move and its optimal solution still being 20 moves? I'd say it's nearly impossible to tell.

For scramble: R L, doing R is one move yet it still has the same number of moves for optimal solution.

For scramble: R2, doing R still gives same movecount.

For this reason, I want to say yes. Are their any states (that are 20 moves) that has only one 20 move solution, and other options 21+? If so, do these states' solutions start with a R2/L2/D2/B2/F2?

If so then the answer would be yes.

Still, overall, it'd be very difficult to prove yes/no.


----------



## qqwref (Oct 19, 2013)

This should be equivalent to asking if there are any 20f* positions which do not have an optimal solution starting with every possible move. Two touching poles probably exist, but I don't know any non-symmetric 20f*s off the top of my head to test this out on.

20f*s are generally pretty hard to find, though. I don't think there's been any kind of partial survey done - hell, we don't even know how many there are.


----------



## jaap (Oct 19, 2013)

qqwref said:


> 20f*s are generally pretty hard to find, though. I don't think there's been any kind of partial survey done - hell, we don't even know how many there are.



There are an estimated 490 million. 
In the comments you'll see that Tom Rokicki tested the neighbours of 735000 known distance-20 positions, and found that most, but not all, were isolated. There were only 652 pairs of neighbouring distance-20 positions, and a few larger clusters. The largest cluster of connected distance-20 positions had 8 members.


----------



## Renslay (Oct 19, 2013)

In 2x2x2, yes, once I found 2 states that are next to each other, and both of them needed 11 moves to solve. I assume such states exists on 3x3x3.

Edit: Oh, I just noticed jaap's post, so the answer is yes.


----------



## SenileGenXer (Oct 19, 2013)

Thank you jaap that was interesting reading.


----------



## cuBerBruce (Oct 19, 2013)

In addition to asking about how close together 20f* positions can be, we can also ask about how far apart they can be. It is known that there exists order-3 20f* positions. If we call a particular order-3 20f* position g, then obviously g and g' must be 20f* apart from each other. So we know at least that there are related 20f* positions that are 20f* apart from each other. I suspect there are also unrelated 20f* positions that are 20f* apart from each other. One could try composing superflip with other known 20f* positions to find other examples. (Of course, you could try composing any two known 20f* positions, but the number of such combinations would be huge.)

I don't recall if there are other known cases of 20f* positions being 20f* apart. Maybe someone can find some, or find a reference to known examples.



SenileGenXer said:


> Do 20 move strong scrambles share any properties like really bad edges?



It seems to me that positions having a lot of incorrectly oriented edges have a higher likelihood of being 20f* positions than random positions. I don't really have data to back this up. Generally speaking, it also appears that symmetrical positions have a higher percentage of antipodal positions than randomly chosen positions.



SenileGenXer said:


> Has there been an even partial survey of these strongest scrambles? Are there other maximally strong scrambles of interest besides the super-flip?



Rokicki has been maintaining a list of known 20f* positions (mod M + inverse). The list includes many positions having some amount of symmetry. Reid's web pages on symmetrical positions list a few:

Superfliptwist:
U R F' B U' D' F U' D F L F' L' U R D F U R L (20q*, 20f*) 

Superfliptwist composed with Pons Asinorum:
U F B D R L U' F2 B2 R L D' F B D R L D F' B' (22q*, 20f*) 

Superfliptwist composed with 6 H's (not all such compositions produce a 20f*):
U F B U' R L U F B R2 L2 D' F B U' R L D' R' L' (22q*, 20f*)

The 26q* position:
F U2 R L D F2 U R2 D F2 D F' B' U2 L F2 R2 B2 U' D (20f*, 28q)


----------



## elrog (Oct 19, 2013)

I'm would assume that your using 20f* to indicate a position is 20 moves away from solved in Face-Turn-Metric and that 20q is the same for Quarter-Turn-Metric, but this doesn't make sense because God's Number was proven to be 20 in Half-Turn-Metric. So what does 20f* and 20q mean?


----------



## TDM (Oct 19, 2013)

elrog said:


> I'm would assume that your using 20f* to indicate a position is 20 moves away from solved in Face-Turn-Metric and that 20q is the same for Quarter-Turn-Metric, but this doesn't make sense because God's Number was proven to be 20 in Half-Turn-Metric and you use R and L in succession rather than using M in this case: "The 26q* position: F U2 *R L* D F2 U R2 D F2 D F' B' U2 L F2 R2 B2 U' D (20f*, 28q)". So what does 20f* and 20q mean?


R L can't be solved using the M slice.
20f* means that solution is 20 moves FTM and is optimal. 20q means that solution is 20 moves in QTM.


----------



## cuBerBruce (Oct 19, 2013)

TDM said:


> R L can't be solved using the M slice.



Well we haven't been discussing slice turn metric, so that seems irrelevant. The maneuver I gave for the 26q* position is one that is optimal for FTM. It is obviously not an optimal maneuver for QTM, being 28 quarter turns. There are thousands of maneuvers for it, however, that use only 26 quarter turns. I just didn't bother posting one because the thread is about 20f* positions. The "q" without an asterisk simply implies the maneuver given is not necessarily optimal in QTM (and in fact, it isn't).


----------



## SenileGenXer (Oct 20, 2013)

O.K. I'm trying to envision the cube universe. I picture it as a galaxy. A very massive elliptical galaxy with 43 quintillion or so members. In the middle is the identity cube. Call it RubikusA. A supermassive ideal that defines everything possible in the cube universe. In a half turn metric space there are 18 positions with one side turned in close proximity to RubikusA. They are it's closest neighbors. The space of the galaxy is really curved so that there are scrambles like R2L2 in the same position as L2R2 connected directly to R2 and L2, RubikusA's closest neighbors. The space is also so curved that there is no escape from the cube galaxy. The radius from RubikusA is also the diamater of the galaxy. No two positions are more than 20f from each other.

Obviously this isn't going to be exactly like an elliptical galaxy. It's going to be highly mathematically structured and highly symmetrical. The distribution of scrambles is probably very different than the distribution of stars in an eliptical.

The core of the galaxy is filled with not very random scrambles but there aren't that many of them - the density isn't there or rather isn't any different than anywhere else. The bulk of the population of scrambles lies out at 18f from RubikusA. Pick a random 18f and then pick a random neighbor that scramble is also most likely to be another 18f. Some on the outer edge of the galaxy are are 19f scrambles. When the 19fs cluster up you may get a pit (or viewed from the outside a peak) of a single 20f scramble. Very rarely do you get a peak of with two or more 20f. 

I wonder where the great cluster of 8 20fs is. I'm working on a candidate 20f scramble that has 4 directly connected 20fs, if three of those are also connected to a 20f that would be the cluster of 8. Because the cube galaxy is highly symmetrical are there 48 clusters of 8 20f scrambles? 

I don't have the right computer to do this work, cube explorer is not fun running in wine.

I've randomly gone through some of Tomas Rokicki list and they don't all have all bade edges. Is that list current?


----------



## SenileGenXer (Oct 20, 2013)

Each location would be the optimal solve or optimal generator with some priority to avoid conflicts when there are two equal length optimals. The aforementioned L2R2 and R2L2 are the same 2f scramble and you would need a system to pick a name for the coordinate. 

There are infinite non-optimal paths to meander through the galaxy. Those wouldn't be positions they are paths connecting adjacent scrambles. Identity cube is the solved cube. A heat map with an adjustable color lookup table on just one of the 48 symmetries of the cube universe even the just the 19f, 20f skin of the projection would be enlightening - I think there has to be patterning even if it's mostly single 20f peaks surrounded by 19f's surrounded by???.

Quarter turn galaxy is the same galaxy but a more finely granular space. Not as collapsed and with 2/3rds the connections between scramble locations.


----------



## cuBerBruce (Oct 21, 2013)

SenileGenXer said:


> I wonder where the great cluster of 8 20fs is. I'm working on a candidate 20f scramble that has 4 directly connected 20fs, if three of those are also connected to a 20f that would be the cluster of 8. Because the cube galaxy is highly symmetrical are there 48 clusters of 8 20f scrambles?



Possibly, and possibly even 96 clusters because of antisymmetry. However, I suspect such a cluster may contain some positions having symmetry, so the total clusters may very well be less than 48. I'm also not clear if he is simply counting symmetrically (and antisymmetrically) distinct positions within each cluster, or truly counting all positions within each cluster.



SenileGenXer said:


> I've randomly gone through some of Tomas Rokicki list and they don't all have all bade edges. Is that list current?



I didn't say that all 20f* postions contain incorrectly oriented edges, and yes, I assumed some 20f* positions indeed have none. I only meant that I think there is some degree of statistical correlation. From solved, it takes a few moves to reach a position with 12 bad edges, and this gives a sort of intuitive feeling that positions with many bad edges are generally (but not always) "harder" to reach.

I also note that the file contains only symmetry/antisymmetry representatives, and with <U,D,L,R,F2,B2>-style edge orientation, you may get differing counts of bad edges depending on which faces are considered the F/B faces. So if we want to use the all20.txt file to check for a statistical correlation, we should really consider counting the number of positions represented by each representative, and make sure we correctly count the distribution of bad edge counts within each symmetry/antisymmetry class. (We also, of course, have to recognize that the file is only a sample of the complete set of 20f* positions.)

The all20.txt file that you linked to is old (at least it is at the time I'm posting this), but I don't know if Tom has made a more updated one available. He appears to be claiming to know about 20 times more 20f* positions than that file has (over 735000 vs. 36206, both numbers being mod M + inverse counts).

I just thought I would mention one other little point. A 20f* position can be a neighbor of (i.e. one move away from) another member of its own symmetry/antisymmetry class. For example (for a position at a different distance), can you find a 1f* position that is a neighbor to another element of its own symmetry/antisymmetry class?


----------



## rokicki (Oct 30, 2013)

I posted a 9-position 20f* "cluster" on the cubelovers list.

I'll copy it here. All of these are symmetrical positions, and
there are only six positions mod M+inv.

FL RU BL LU FR RD BR LD UF DF UB DB FDR BRD URB UFR DFL FUL BLU DLB C_4h A 8
FU RU BL LU FD RD BR LD RF LF UB DB FLD BRD URB RFD LFU FRU BLU DLB C_4 A 4
FU RU BD LU FD RD BU LD RF LF LB RB FLD BUR LUB RFD LFU FRU BDL RDB C_4 A 4
FR RU BD LU FL RD BU LD DF UF LB RB FUL BUR LUB DFL UFR FDR BDL RDB C_4 A 4
FR RU BR LU FL RD BL LD DF UF DB UB FUL BLU DLB DFL UFR FDR BRD URB C_4h A 8
FD RU BR LU FU RD BL LD LF RF DB UB FRU BLU DLB LFU RFD FLD BRD URB C_4 A 4
FD RU BU LU FU RD BD LD LF RF RB LB FRU BDL RDB LFU RFD FLD BUR LUB C_4 A 4
FL RU BU LU FR RD BD LD UF DF RB LB FDR BDL RDB UFR DFL FUL BUR LUB C_4 A 4
FU RU BU LU FD RD BD LD RF LF RB LB FLD BDL RDB RFD LFU FRU BUR LUB C_4h A 8

The scrambles are here:

B1L1B3L3F2D3R1B3U1D2B1L1B2R1D1R3B2R2B2R3
L2F3L2D1F2B2L1B3R2B1D3R3F1U1L1R2D2B2L3R2
F3U1B3U3F2L3D1B3L2R1B1U1B2D1L1D3B2D2B2D3
L1B3L3F2D3R1B3U1D2B1L1B2R1D1R3B2R2B2R3F2
L3B2F3L3B1D1L1U3B3R3F3D1L2F1D2F3B2L1D2L2
L3F1L1B2D1R3F1U3D2F3L3F2R3D3R1F2R2F2R1B2
B1U3F1U1B2L1D3F1L2R3F3U3F2D3L3D1F2D2F2D1
L2B1L2D3B2F2L3F1R2F3D1R1B3U3L3R2D2F2L1R2
U1L1U2B2R2F3D1L3F3B3D3F1R3F1B1R2B3D2R2D3

I would be absolutely *delighted* to share my list of 20f*'s with anyone who wants.
It's a pretty big list though; I'll have to put it somewhere other than my DSL line.
I think cube20.org would be appropriate. Does anyone want it?


----------



## cuBerBruce (Nov 1, 2013)

rokicki said:


> I would be absolutely *delighted* to share my list of 20f*'s with anyone who wants.
> It's a pretty big list though; I'll have to put it somewhere other than my DSL line.
> I think cube20.org would be appropriate. Does anyone want it?



I'm interested in it.


----------



## Renslay (Nov 1, 2013)

What is the strangest (most surprising) 20f* state is for you?
Which 20f* state has the least number of symmetries?
I'm just wondering; every 20f* state I've seen has some pattern repetition or some kind of symmetry. Is it true for every 20f*?


----------



## cuBerBruce (Nov 1, 2013)

Renslay said:


> Which 20f* state has the least number of symmetries?
> I'm just wondering; every 20f* state I've seen has some pattern repetition or some kind of symmetry. Is it true for every 20f*?



Among the 20f* positions, there are only 1,091,994 positions having any symmetry at all. The best current estimate is that there are a total of 490 million 20f* positions. This means the vast majority of 20f* positions aren't symmetric at all.

I note that some of the asymmetric ones might have symmetry in the edge pieces or symmetry in the corner pieces (or even both).


----------



## Renslay (Nov 1, 2013)

cuBerBruce said:


> Among the 20f* positions, there are only 1,091,994 positions having any symmetry at all. The best current estimate is that there are a total of 490 million 20f* positions. This means the vast majority of 20f* positions aren't symmetric at all.
> 
> I note that some of the asymmetric ones might have symmetry in the edge pieces or symmetry in the corner pieces (or even both).



Thanks.

Even if there is no symmetry, there is some kind of repeating pattern on the sides or on opposite sides (which is hard to describe in an exact way). I just wondering how many 20f*s are which "looks pretty average and random". Although, I did not see so many 20f*s, so maybe I just missed those.


----------



## rj (Nov 1, 2013)

SenileGenXer said:


> O.K. I'm trying to envision the cube universe. I picture it as a galaxy. A very massive elliptical galaxy with 43 quintillion or so members. In the middle is the identity cube. Call it RubikusA. A supermassive ideal that defines everything possible in the cube universe. In a half turn metric space there are 18 positions with one side turned in close proximity to RubikusA. They are it's closest neighbors. The space of the galaxy is really curved so that there are scrambles like R2L2 in the same position as L2R2 connected directly to R2 and L2, RubikusA's closest neighbors. The space is also so curved that there is no escape from the cube galaxy. The radius from RubikusA is also the diamater of the galaxy. No two positions are more than 20f from each other.
> 
> Obviously this isn't going to be exactly like an elliptical galaxy. It's going to be highly mathematically structured and highly symmetrical. The distribution of scrambles is probably very different than the distribution of stars in an eliptical.
> 
> ...



This is cool.


----------



## rokicki (Nov 5, 2013)

The set of known distance-20 positions is posted at http://cube20.org/distance20s/ for your pleasure.

Please send me email if you have any difficulties.

-tom


----------



## SenileGenXer (Nov 5, 2013)

Thank you so much. Thank you for taking the time to post this and answer my question. I meant to say thank you to you and to cmowla earlier but I felt I don't have anything mathematically interesting to add to the conversation at the moment.


----------



## Renslay (Nov 5, 2013)

rokicki said:


> The set of known distance-20 positions is posted at http://cube20.org/distance20s/ for your pleasure.
> 
> Please send me email if you have any difficulties.
> 
> -tom



Nice results!

And I found some nice 20f*s which seems pretty random.


----------

