10 ms·

Checking whether a cube is valid is effectively a random-state generator; i.e. it randomly chooses one of the 43 quintillion possible states. Generating random

Checking whether a cube is valid is effectively a random-state generator; i.e. it randomly chooses one of the 43 quintillion possible states. Generating random moves biases towards certain scrambles. This is why the World Cube Association generates random states of the cube with their library TNoodle, rather than random sequences of moves.

deleted 8y ago
[deleted]
Retric 8y ago
Citation needed on that. It’s trivial to do 10k random rotations in memory. At which point you have something indistinguishable from random.
- perfect_wave 8y ago
  Except that simply isn't true. When randomly performing rotations you're much more likely to end up in certain states (as I mentioned in my other comment). Whether you make 10k random rotations or 20 random rotations you're still more likely to end up in a certain state.
  - Retric 8y ago
    In theory I agree with you, in practice I don’t. Sum 20 coin flips mod 3 and you can find the bias in the output. It’s hard with a small sample set, but you could do it. Sum 10k coin flips and it’s a different situation. Eventually you fall through the noise floor for any reasonable sample size.
    - bunderbunder 8y ago
      It's almost certainly less effort (though arguably also less fun) to write a valid state checker than it is to prove that N random cube operations will yield something that's within some tolerance of a uniform distribution across all legal cube states.
- seaneganx 8y ago
  https://www.worldcubeassociation.org/regulations/#4b3 https://www.worldcubeassociation.org/regulations/#4b3 The World Cube Association requires "equal probability for each state" by scramble programs used for their events. You're right that a large number of rotations will result in something indistinguishable from random by an individual, but that is not sufficient according to WCA regulations as it's not uniformly random.
  - Retric 8y ago
    That’s not supporting your point, a solution that’s harder to mess up is suggested. Secondly, they specifically don’t want a truely ranodm sequence as they require a minimum number of moves from a solution. If I can hand you multiple sets of 10^10 cubes and you can’t tell which method was used that’s what I mean from indistinguishable not simply humans can’t tell.
- Someone 8y ago
  Depends on what you call a ‘rotation’. After 10k random 90 degree turns of a face, you have an even permutation on both corners and edges, which means you can’t reach half the positions. That’s easily corrected (e.g: flip a coin first to determine whether to do 10k or 10k+1 random rotations), but this shows it is easy to make slip ups solving such a seemingly trivial problem.
  - Retric 8y ago
    What you’re describing falls under rotational symmetry. Rotating top side left one is the same as rotating bottom 2 sides right. But, more generally limiting rotations to 90 degrees slows things down as 90 or 180 degree rotations can be directly computed with the same overhead.
- mturmon 8y ago
  You have been down voted, but I think this is a reasonable point and a reasonable question. It seems to me that the method of iterated transformation you suggest will indeed yield a random draw. My analogy is to Markov chain Monte Carlo. It is well known that MCMC on a discrete space will converge to the desired distribution (we’ll get to that in a second) if the chain is irreducible and aperiodic. Irreducible means any state can eventually transition to any other state using the permutations allowed. This is easy to validate if we just use the various face rotations. Aperiodic essentially means that there is no fixed “loop” from one state back to itself that occurs with probability one. (The even parity issue that @someone raised comes in here. An absolute fix in the lack of full understanding of all possible such issues is to allow null moves with some low probability.). For a simple state space like this, the main thing is to make the permutations chosen in such a way that all states are reachable. OK, iterated permutations converge in distribution, but to what? All the states in the target distribution here have equal probability, so (in MCMC terms) the posterior is totally flat: P(s) / P(s’) = 1 for all states s, s’. This means that a reversible Metropolis-Hastings sampler that just accepts every proposed move will converge to a flat posterior. OK, so we just need to make the permutations we propose reversible. What is reversible? It means that, if you are at state s, you are just as likely to go to s’ as if you are at s’ and going to s. [1] The easy way to ensure this is to make “clockwise twist of left face” chosen with the same probability as “counterclockwise twist of left face”. This is the obvious strategy anyway, which is why reversible samplers are popular. So in sum, the recommended algorithm is to start from any legal state and perform “N” permutations randomly chosen from clockwise/counterclockwise (50/50 chance) rotations of a randomly chosen face. To accomplish the null moves, just subtract a small random number from N. On a discrete state space, you will get exponentially fast convergence to the desired distribution. The space is strongly connected, because you can get from any state to any other state with at most 40 moves. I don’t see the problem here. [1] https://en.m.wikipedia.org/wiki/Metropolis–Hastings_algorithm#Formal_derivation https://en.m.wikipedia.org/wiki/Metropolis–Hastings_algorith..., A(x, x’) = 1.

deleted 8y ago

[deleted]

Retric 8y ago

Citation needed on that. It’s trivial to do 10k random rotations in memory. At which point you have something indistinguishable from random.

perfect_wave 8y ago
Except that simply isn't true. When randomly performing rotations you're much more likely to end up in certain states (as I mentioned in my other comment). Whether you make 10k random rotations or 20 random rotations you're still more likely to end up in a certain state.
- Retric 8y ago
  In theory I agree with you, in practice I don’t. Sum 20 coin flips mod 3 and you can find the bias in the output. It’s hard with a small sample set, but you could do it. Sum 10k coin flips and it’s a different situation. Eventually you fall through the noise floor for any reasonable sample size.
  - bunderbunder 8y ago
    It's almost certainly less effort (though arguably also less fun) to write a valid state checker than it is to prove that N random cube operations will yield something that's within some tolerance of a uniform distribution across all legal cube states.
seaneganx 8y ago
https://www.worldcubeassociation.org/regulations/#4b3 https://www.worldcubeassociation.org/regulations/#4b3 The World Cube Association requires "equal probability for each state" by scramble programs used for their events. You're right that a large number of rotations will result in something indistinguishable from random by an individual, but that is not sufficient according to WCA regulations as it's not uniformly random.
- Retric 8y ago
  That’s not supporting your point, a solution that’s harder to mess up is suggested. Secondly, they specifically don’t want a truely ranodm sequence as they require a minimum number of moves from a solution. If I can hand you multiple sets of 10^10 cubes and you can’t tell which method was used that’s what I mean from indistinguishable not simply humans can’t tell.
Someone 8y ago
Depends on what you call a ‘rotation’. After 10k random 90 degree turns of a face, you have an even permutation on both corners and edges, which means you can’t reach half the positions. That’s easily corrected (e.g: flip a coin first to determine whether to do 10k or 10k+1 random rotations), but this shows it is easy to make slip ups solving such a seemingly trivial problem.
- Retric 8y ago
  What you’re describing falls under rotational symmetry. Rotating top side left one is the same as rotating bottom 2 sides right. But, more generally limiting rotations to 90 degrees slows things down as 90 or 180 degree rotations can be directly computed with the same overhead.
mturmon 8y ago
You have been down voted, but I think this is a reasonable point and a reasonable question. It seems to me that the method of iterated transformation you suggest will indeed yield a random draw. My analogy is to Markov chain Monte Carlo. It is well known that MCMC on a discrete space will converge to the desired distribution (we’ll get to that in a second) if the chain is irreducible and aperiodic. Irreducible means any state can eventually transition to any other state using the permutations allowed. This is easy to validate if we just use the various face rotations. Aperiodic essentially means that there is no fixed “loop” from one state back to itself that occurs with probability one. (The even parity issue that @someone raised comes in here. An absolute fix in the lack of full understanding of all possible such issues is to allow null moves with some low probability.). For a simple state space like this, the main thing is to make the permutations chosen in such a way that all states are reachable. OK, iterated permutations converge in distribution, but to what? All the states in the target distribution here have equal probability, so (in MCMC terms) the posterior is totally flat: P(s) / P(s’) = 1 for all states s, s’. This means that a reversible Metropolis-Hastings sampler that just accepts every proposed move will converge to a flat posterior. OK, so we just need to make the permutations we propose reversible. What is reversible? It means that, if you are at state s, you are just as likely to go to s’ as if you are at s’ and going to s. [1] The easy way to ensure this is to make “clockwise twist of left face” chosen with the same probability as “counterclockwise twist of left face”. This is the obvious strategy anyway, which is why reversible samplers are popular. So in sum, the recommended algorithm is to start from any legal state and perform “N” permutations randomly chosen from clockwise/counterclockwise (50/50 chance) rotations of a randomly chosen face. To accomplish the null moves, just subtract a small random number from N. On a discrete state space, you will get exponentially fast convergence to the desired distribution. The space is strongly connected, because you can get from any state to any other state with at most 40 moves. I don’t see the problem here. [1] https://en.m.wikipedia.org/wiki/Metropolis–Hastings_algorithm#Formal_derivation https://en.m.wikipedia.org/wiki/Metropolis–Hastings_algorith..., A(x, x’) = 1.