Lucas Garron
Administrator
Okay, this just hit me:
I have a great idea for WCA scramblers. though I'm not sure how effective an implementation will be.
Unlike what has been assumed, we do not seek to generate a random state and then solve it. That's just a convenient way to do it for 3x3x3.
However, we are actually only interested in generating a random state.
The key:
We can randomize different factors of the scramble separately: Orbits, orientations, etc.
The other important thing:
In scrambling such a factor, all other factors may be disregard.
I'm using "factor" to stand for any aspect of a puzzle that in a sense contributes a number to the total number of of factors in the number of states. That's mostly permutations and orientations, but you can, for example, split permutation into even permutation + parity.
This is big.
Consider 3x3x3: We can scramble orientation randomly, and then permutation. This will give us a random state.
We can scramble orientation randomly, ignoring permutation, then scramble permutation randomly, and still get a random state.
Even better! We can scramble orientation randomly, ignoring permutation, then scramble permutation randomly, ignoring orientation and STILL get a random state.
This is easy to prove
You can take this simple proof: Noise+anything=noise (assuming that the "anything" is not constructed to cancel the noise).
I believe Huffman proved that no information can be communicated in binary over a channel that switches each bit with 50% chance (noise). Here, the noise cancels order/non-order/anything as likely as not, so you can't even prevent the noise (unless you know exactly what the noise is going to be, in which case it's not noise)
If you record noise, and combine it with silence, you get noise.
If you record noise, and combine it with order, you get noise.
If you record noise, and combine it with noise, you get noise.
Note: This is complete noise, not something like background noise that weak and possibly non-random.
Mathematically:
Consider the permutation of an orbit. If you randomly permute (apply a random element of the set of possible permutations, with equal weight to each) it with an algorithm, it is in a random state.
Now let's say you added some moves before. The cube sill still in a random state at the end. Whatever the previous moves were, they placed it in a certain arbitrary state, but the random permutation now randomly placed it into one of the possible states.
It is an an elementary result of number theory that if you compose an arbitrary permutation R with any permutation P to get Q, any different values of P will give you a different value of Q. Thus, if R is a random permutation, Q is a random element of of the set of potential permutations (all of them, in fact). Applying P is an isomorphism on that set, so you still get Q as random element of that same set!
Even better! It does not matter if P is done before or after Q, or if there are multiple such permutations P(i) that get thrown onto both sides of Q. They can even be random each, as long as their randomness is independent of Q (i.e. not made to cancel the specific random element Q).
If you wanna go really formal, ask qqwref and Stefan.
I'm sure people will try to argue against this. Let's try:
Suppose that you scramble edges while ignoring corners. Suppose also that all the algs use to do this happen either to leave corners unaffected, or, say, switch each corner with its opposite (you can substitute a lot of things, like "misorient all corners"). Doesn't this weird distribution bias the final scramble?
It does not, I assure you. Try this on a deck of cards. If you change the order in some way and the shuffle, it'll be randomly ordered. Now let's say that after shuffling, you do something, anything that could easily have been chosen independent of the shuffle (and perhaps determined before the shuffle), like cutting the deck after the 8th card. The deck will still be in a random order.
(Note: It will not be in a random order if you, say, cut after the first jack, or move the final ace to the top. But all we have to avoid is something biased like that.)
So, the procedure for a multi-stage random-state scrambler is simple: Apply a set of algorithms, each of which randomizes a factor, until all factors have been accounted for.
The different factors can be any groups in any order, and with all the choices, there should be some best (shortest-output) ones.
The process is analogous to a solver, but more generous at each step, so I hope that it will allow us to get significantly short scrambles. I know of (and have used) an optimal 4x4x4 solver for 77 STM, and current WCA scrambles are 40 outer-block-turn moves. If this turns out to give quick scrambles under 50 twists, this may be worth pursuing for improvement.
If the output has a large standard deviation, we might also be able to generate a few too many, and pick the few shortest ones (though this probably messes with randomness, so I will not recommend it unless someone has a good reason to show that this is negligible).
As an example, for 4x4x4 the simplest scheme might be: x-centers, wings, then corners
5x5x5 might be: p-centers, x-centers, midges, wings, corners.
Pyraminx: Edges, centers (trivial), tips (trivial)
...
You can easily condense these, and the order can be switched: 5x5x5 could also be: centers, midges+corners (i.e. 3x3x3, which may even be done with double-layer turns), wings.
It might also be worth trying to reduce steps, or use a flexible program, if output is promisingly short and fast.
Also note that if you do edges, corners, and x-centers (I'll just include them, in case of supercubes) separately, you may introduce parity to one, any, or all of them.
IMPORTANT NOTE:
Centers are indistinguishable on big cubes. However, having one orbit of centers randomly arranged before permuting it -as if each side were originally a solid color- is inappropriate. By the design of this system, we don't know which centers to treat the same, so we have to randomly permute all 24 pieces, not 6 sets of 4.
This is best resolved by scrambling centers first. The first set of centers will not have this problem. We can also design our algs not to scramble certain other orbits of centers, which may then treated as 6 sets of 4. Experimentation will show the shortest schemes for each cube, if there is a significant difference.
Also, note that on cubes we cannot automatically turns slice turns into block turns, or else we could turn outer turns as multi-layer by the same token, and would thus be able to fairly scramble a 5x5x5 with double-layer turns, which is simply absurd. I have a feeling that making only slice turns into block turns might have a negligible effect on the fairness (I've said "negligible" before - with this I mean allowing the distribution of scrambles to skew microscopically in exchange for much easier, faster scrambling), but I don't have any good reason at all.
I propose and suggest that any work on this should be in outer-block half-turn metric, representing the way most cubes are scramblable (hey, this word is not in the dictionary!). It doesn't matter if some people's cubes can do slice turns, block turns are safer and easier. It also continues the current style of scrambling, and allows us to compare scrambling time easily by comparing the number of moves.
So, this is my idea. I hope that some programmers and mathematicians pick this up (I also want to see what kind of bounds we get on this), and really hope that this turns out useful and practical enough for the WCA to use and/or consider for future puzzles.
It might not turn out so necessary or useful, but we won't see until we try. I think 4x4x4 may be worth it, but if we don't save any moves we'd have to investigate the distributions of the current scrambler to see if it's worth it.
I've posted this here and not on the WCA forum because it's an idea and will require at least a few months of research/development, and I think this would be the best place to discuss it and reach appropriate, interested cubers (I might also post something about this on the Yahoo group). In particular, I'd like to hear Stefan's ad Chris H's ideas and comments on this.
-Lucas Garron
EDIT: Please don't reply to this with a short, useless comment (whether positive or negative). This is a very serious idea, and a clogged thread would not help at all.
I have a great idea for WCA scramblers. though I'm not sure how effective an implementation will be.
Unlike what has been assumed, we do not seek to generate a random state and then solve it. That's just a convenient way to do it for 3x3x3.
However, we are actually only interested in generating a random state.
The key:
We can randomize different factors of the scramble separately: Orbits, orientations, etc.
The other important thing:
In scrambling such a factor, all other factors may be disregard.
I'm using "factor" to stand for any aspect of a puzzle that in a sense contributes a number to the total number of of factors in the number of states. That's mostly permutations and orientations, but you can, for example, split permutation into even permutation + parity.
This is big.
Consider 3x3x3: We can scramble orientation randomly, and then permutation. This will give us a random state.
We can scramble orientation randomly, ignoring permutation, then scramble permutation randomly, and still get a random state.
Even better! We can scramble orientation randomly, ignoring permutation, then scramble permutation randomly, ignoring orientation and STILL get a random state.
This is easy to prove
You can take this simple proof: Noise+anything=noise (assuming that the "anything" is not constructed to cancel the noise).
I believe Huffman proved that no information can be communicated in binary over a channel that switches each bit with 50% chance (noise). Here, the noise cancels order/non-order/anything as likely as not, so you can't even prevent the noise (unless you know exactly what the noise is going to be, in which case it's not noise)
If you record noise, and combine it with silence, you get noise.
If you record noise, and combine it with order, you get noise.
If you record noise, and combine it with noise, you get noise.
Note: This is complete noise, not something like background noise that weak and possibly non-random.
Mathematically:
Consider the permutation of an orbit. If you randomly permute (apply a random element of the set of possible permutations, with equal weight to each) it with an algorithm, it is in a random state.
Now let's say you added some moves before. The cube sill still in a random state at the end. Whatever the previous moves were, they placed it in a certain arbitrary state, but the random permutation now randomly placed it into one of the possible states.
It is an an elementary result of number theory that if you compose an arbitrary permutation R with any permutation P to get Q, any different values of P will give you a different value of Q. Thus, if R is a random permutation, Q is a random element of of the set of potential permutations (all of them, in fact). Applying P is an isomorphism on that set, so you still get Q as random element of that same set!
Even better! It does not matter if P is done before or after Q, or if there are multiple such permutations P(i) that get thrown onto both sides of Q. They can even be random each, as long as their randomness is independent of Q (i.e. not made to cancel the specific random element Q).
If you wanna go really formal, ask qqwref and Stefan.
I'm sure people will try to argue against this. Let's try:
Suppose that you scramble edges while ignoring corners. Suppose also that all the algs use to do this happen either to leave corners unaffected, or, say, switch each corner with its opposite (you can substitute a lot of things, like "misorient all corners"). Doesn't this weird distribution bias the final scramble?
It does not, I assure you. Try this on a deck of cards. If you change the order in some way and the shuffle, it'll be randomly ordered. Now let's say that after shuffling, you do something, anything that could easily have been chosen independent of the shuffle (and perhaps determined before the shuffle), like cutting the deck after the 8th card. The deck will still be in a random order.
(Note: It will not be in a random order if you, say, cut after the first jack, or move the final ace to the top. But all we have to avoid is something biased like that.)
So, the procedure for a multi-stage random-state scrambler is simple: Apply a set of algorithms, each of which randomizes a factor, until all factors have been accounted for.
The different factors can be any groups in any order, and with all the choices, there should be some best (shortest-output) ones.
The process is analogous to a solver, but more generous at each step, so I hope that it will allow us to get significantly short scrambles. I know of (and have used) an optimal 4x4x4 solver for 77 STM, and current WCA scrambles are 40 outer-block-turn moves. If this turns out to give quick scrambles under 50 twists, this may be worth pursuing for improvement.
If the output has a large standard deviation, we might also be able to generate a few too many, and pick the few shortest ones (though this probably messes with randomness, so I will not recommend it unless someone has a good reason to show that this is negligible).
As an example, for 4x4x4 the simplest scheme might be: x-centers, wings, then corners
5x5x5 might be: p-centers, x-centers, midges, wings, corners.
Pyraminx: Edges, centers (trivial), tips (trivial)
...
You can easily condense these, and the order can be switched: 5x5x5 could also be: centers, midges+corners (i.e. 3x3x3, which may even be done with double-layer turns), wings.
It might also be worth trying to reduce steps, or use a flexible program, if output is promisingly short and fast.
Also note that if you do edges, corners, and x-centers (I'll just include them, in case of supercubes) separately, you may introduce parity to one, any, or all of them.
IMPORTANT NOTE:
Centers are indistinguishable on big cubes. However, having one orbit of centers randomly arranged before permuting it -as if each side were originally a solid color- is inappropriate. By the design of this system, we don't know which centers to treat the same, so we have to randomly permute all 24 pieces, not 6 sets of 4.
This is best resolved by scrambling centers first. The first set of centers will not have this problem. We can also design our algs not to scramble certain other orbits of centers, which may then treated as 6 sets of 4. Experimentation will show the shortest schemes for each cube, if there is a significant difference.
Also, note that on cubes we cannot automatically turns slice turns into block turns, or else we could turn outer turns as multi-layer by the same token, and would thus be able to fairly scramble a 5x5x5 with double-layer turns, which is simply absurd. I have a feeling that making only slice turns into block turns might have a negligible effect on the fairness (I've said "negligible" before - with this I mean allowing the distribution of scrambles to skew microscopically in exchange for much easier, faster scrambling), but I don't have any good reason at all.
I propose and suggest that any work on this should be in outer-block half-turn metric, representing the way most cubes are scramblable (hey, this word is not in the dictionary!). It doesn't matter if some people's cubes can do slice turns, block turns are safer and easier. It also continues the current style of scrambling, and allows us to compare scrambling time easily by comparing the number of moves.
So, this is my idea. I hope that some programmers and mathematicians pick this up (I also want to see what kind of bounds we get on this), and really hope that this turns out useful and practical enough for the WCA to use and/or consider for future puzzles.
It might not turn out so necessary or useful, but we won't see until we try. I think 4x4x4 may be worth it, but if we don't save any moves we'd have to investigate the distributions of the current scrambler to see if it's worth it.
I've posted this here and not on the WCA forum because it's an idea and will require at least a few months of research/development, and I think this would be the best place to discuss it and reach appropriate, interested cubers (I might also post something about this on the Yahoo group). In particular, I'd like to hear Stefan's ad Chris H's ideas and comments on this.
-Lucas Garron
EDIT: Please don't reply to this with a short, useless comment (whether positive or negative). This is a very serious idea, and a clogged thread would not help at all.
Last edited: