Lucas Garron
Administrator
In the WCA forum, here and http://www.worldcubeassociation.org/forum/viewtopic.php?f=4&t=449, Prusak's lucky scramble brought up the issue of fair scrambling.
(Skip to the big headline below for the more interesting stuff.)
In the same way that it makes most sense by solving into cube shape, and then within, it's most logical to consider scrambling as random cube-shape and random permutation of pieces in the cube shape.
Permutation of the pieces, WLOG in cube shape, is a relatively simple problem.
However, the shapes are a funnier issue. There are two ways to define "random cube shape," if you consider only the piece arrangements on top and bottom. AUF, AUD, and middles don't really matter, and can at worst just be dealt with at the end of a scramble.
So, you can consider a "random shape" to be a random choice of one of the 170 configurations. Problem is, why not choose among the 90 shapes that you'll count if you consider shapes that are z2-flips of each other as the same? The distribution is now different.
I think the "best" way to do it is to improve our current idea of scrambling: Do random moves for a really long while (rather, do something that produces equivalent scrambles). The current scrambler doesn't nearly scramble to an even distribution, though.
So, I took the following definition: In any state, the top position can be turned a certain number of ways to realign a twistable crack, and you rotate to a random one of each. Same for the bottom. Then you do a /, and continue. Over time, the probabilities even out. Permutation of pieces within the shapes becomes, random (I'm pretty sure, but I don't want to think of an argument, and I don't even want to think about what happens if it isn't).
The shapes eventually reach a distribution that doesn't change.
Some of you will probably recognize this as a random walk of the Square-1 shape graph. Each shape has one edge connecting to another for each way to get from it to the other (you can consider it undirected).
So, I have a 170x170 matrix (symmetric). Each row corresponds to a shape, has a sum of 1, and each entry is weighted by the number of ways it's possible to get to the column's shape. So, pretend you know how Markov stuff works, raise the matrix to a sufficiently high power, and you get a stable distribution.
More important stuff
So, after that long introduction: As far as I know, no one has ever actually calculated the probability distributions of the nodes in a random walk of the Square-1 shape graph. So I thought I'd do it.
I tried to take the most justifiably natural way to calculate the distributions, and computed everything in Mathematica. The results are at http://cube.garron.us/sq1/sq1graph.csv. If you want to look at the shapes, I've rendered them and put them in a zip.
So, if we're ever going to do random-state scrambling for Square-1, shapes should probably be chosen by weighing according to this distribution. (Or we could do something like generating 1000 random moves, and sending it to Jaap's solver to be optimized.)
So, I've posted here to see what other mathematically inclined people think about it. Are there good arguments for another scheme? Does anyone actually know about how random the pieces should eventually be within the shapes? Does anyone really care about the eventual shape distribution?
I can also give you the Mathematica source code and a more explicit method definition if you want.
(Skip to the big headline below for the more interesting stuff.)
In the same way that it makes most sense by solving into cube shape, and then within, it's most logical to consider scrambling as random cube-shape and random permutation of pieces in the cube shape.
Permutation of the pieces, WLOG in cube shape, is a relatively simple problem.
However, the shapes are a funnier issue. There are two ways to define "random cube shape," if you consider only the piece arrangements on top and bottom. AUF, AUD, and middles don't really matter, and can at worst just be dealt with at the end of a scramble.
So, you can consider a "random shape" to be a random choice of one of the 170 configurations. Problem is, why not choose among the 90 shapes that you'll count if you consider shapes that are z2-flips of each other as the same? The distribution is now different.
I think the "best" way to do it is to improve our current idea of scrambling: Do random moves for a really long while (rather, do something that produces equivalent scrambles). The current scrambler doesn't nearly scramble to an even distribution, though.
So, I took the following definition: In any state, the top position can be turned a certain number of ways to realign a twistable crack, and you rotate to a random one of each. Same for the bottom. Then you do a /, and continue. Over time, the probabilities even out. Permutation of pieces within the shapes becomes, random (I'm pretty sure, but I don't want to think of an argument, and I don't even want to think about what happens if it isn't).
The shapes eventually reach a distribution that doesn't change.
Some of you will probably recognize this as a random walk of the Square-1 shape graph. Each shape has one edge connecting to another for each way to get from it to the other (you can consider it undirected).
So, I have a 170x170 matrix (symmetric). Each row corresponds to a shape, has a sum of 1, and each entry is weighted by the number of ways it's possible to get to the column's shape. So, pretend you know how Markov stuff works, raise the matrix to a sufficiently high power, and you get a stable distribution.
More important stuff
So, after that long introduction: As far as I know, no one has ever actually calculated the probability distributions of the nodes in a random walk of the Square-1 shape graph. So I thought I'd do it.
I tried to take the most justifiably natural way to calculate the distributions, and computed everything in Mathematica. The results are at http://cube.garron.us/sq1/sq1graph.csv. If you want to look at the shapes, I've rendered them and put them in a zip.
So, if we're ever going to do random-state scrambling for Square-1, shapes should probably be chosen by weighing according to this distribution. (Or we could do something like generating 1000 random moves, and sending it to Jaap's solver to be optimized.)
So, I've posted here to see what other mathematically inclined people think about it. Are there good arguments for another scheme? Does anyone actually know about how random the pieces should eventually be within the shapes? Does anyone really care about the eventual shape distribution?
I can also give you the Mathematica source code and a more explicit method definition if you want.