Three Million Randomly Selected Positions, Optimally Solved

[rokicki]

Using the Mersenne Twister pseudorandom number generator, I picked out
three million cube positions. I then optimally solved each of these in both
the quarter turn metric and half turn metric. From this data, I was able
to calculate an approximate distance distribution, along with confidence
intervals.

All the data is at

http://cubezzz.dyndns.org/drupal/?q=node/view/232

I can make the actual positions and solutions available if anyone is
interested.

I plan to release the actual code as well, but it still needs some additional
documentation.

-tom

 

[teller]

Neat.

Needs some visualization, I think.

 

[qqwref]

Oo, very cool. About how long did this take to generate? (And what are your thoughts on God's quarter-turn Number? )

 

[rokicki]

Fast machine

I got a new, faster machine.

On this machine I can optimally solve positions in the QTM at a rate of about 6 per second, and in the HTM at a rate of about 3.4 per second.

So in total it took about 16 days to run.

And yes, visualization would be nice. I should use the google graph tools for that; they are pretty cool.

I'm running 100 random cosets now in the QTM and the HTM to try to get some estimates for the upper tail of the distribution. I am nearly positive that God's number in the QTM is 26, since only one position is known to be at that distance, and the only known distance-25 positions are its neighbors, and since I've conducted (separately) an intense search for other deep positions in the QTM and found none of distance greater than 24.

It appears that distance-24 positions in the QTM do exist in some reasonable quantity but that they are significantly more rare than distance-20 positions in the HTM.

So the "tail" in the QTM is quite dramatically different from the tail in the HTM.

Part of that is due to the fact that the QTM is bipartite and the HTM is not.

I believe that the *only* distance-26 position in the QTM is the one known.

 

[cuBerBruce]

I note that what rokicki is calling the "only known distance-26 position" is really three symmetrically equivalent positions (if you consider the total number of positions to be 43,252,003,274,489,856,000).

 

[whauk]

I believe that the *only* distance-26 position in the QTM is the one known.

is it the superflip?

 

[Erzz]

is it the superflip?

According to this, superflip is 24 QTM.
Also on that page, "No position has ever been found which requires more moves than this, so many people believe that 20 moves is in fact the maximum number of moves that any 3x3 pattern could take to solve." This should probably be changed now that it has been proven.

 

[rokicki]

is it the superflip?

No, but you're close; it's superflip composed with four spots.

http://www.randelshofer.ch/rubik/patterns/V010.01.html

 

[RyanReese09]

This should probably be changed now that it has been proven.

Nope...20 moves HTM is the most ever needed.

 

[cuBerBruce]

According to this, superflip is 24 QTM.
Also on that page, "No position has ever been found which requires more moves than this, so many people believe that 20 moves is in fact the maximum number of moves that any 3x3 pattern could take to solve." This should probably be changed now that it has been proven.

Nope...20 moves HTM is the most ever needed.

Nope...Erzz meant that phrases such as "No position has ever been found" and "many people believe" are now outdated since we now know the exact number.