Randomness of altered scrambles

[JediJupiter]

If you took a random state scrambler for 3x3 or 2x2, and then altered the scramble so that any 180 moves (F2, R2 etc.) were turned into 90 clockwise moves (F, R ...), how random would the altered scramble be? Could the scramble still be considered legitimate at all?

 

[mDiPalma]

i think superflip requires 24 quarter turn moves to be solved, but only 20 half turn moves. also there are some states that need 26 qtm;

so if you're only using 20-move scrambles, you might not reach all states.

not sure though

 

[TMOY]

You don't need to be able to reach every possible state. For example, the Pochmann megaminx scrambler can generate only 10^21 or so states out of 10^68, but is still considered good enough for competition purpose.

Of course, if you start from a random state scrambler and alter it, the result will be less random. The loss of randomness depends on the scrambler, though (for exemple, for 2^3, the loss with an optimal scrambler will probably be greater than with a 11-move scrambler).

 

[qqwref]

It won't be as good as an actual scramble, for sure. As mDiPalma points out you can only ever do 20 quarter turns so many positions will be unreachable, and that's silly for such a small puzzle. Plus, since you're modifying scrambles that are not random-move but were created to solve random positions, you could get all kinds of weird biases which we can't really anticipate without testing. Anyway, I don't know why you'd do this, is it really so hard to do 3x3x3 scrambles as written?

@TMOY: Megaminx scrambles are actually pretty bad (both in terms of reachable states and in terms of metrics like average corner-edge pairs, star length, etc.) but because the puzzle has so many sides and requires so many turns already there is really no other practical option for scrambling it. Oh well.

 

[Lucas Garron]

If you took a random state scrambler for 3x3 or 2x2, and then altered the scramble so that any 180 moves (F2, R2 etc.) were turned into 90 clockwise moves (F, R ...), how random would the altered scramble be? Could the scramble still be considered legitimate at all?

As others have pointed out, it could be altered a lot.

Consider a (uniform) random state scrambler for 3x3x3 that always generates 22-move scrambles. If you replace all the double turns with single turns, you will only ever generate scrambles with even permutation parity!

You don't need to be able to reach every possible state. For example, the Pochmann megaminx scrambler can generate only 10^21 or so states out of 10^68, but is still considered good enough for competition purpose.

This was something I didn't understand well enough when we the Megaminx scrambler was first discussed, but what we want has an exact similar notion in cryptography called semantic security.

Basically, it doesn't matter if you can't generate nearly all possible states, as long as the scrambler doesn't have any bias that a human can use to their advantage.


A bit more detail: Suppose someone has a scrambler that's biased, and asks you to come up with a strategy. They'll either give you an output from their biased scrambler, or they'll give you a truly random scramble – and you have to use your strategy tell which one was used.

Supposed the biased scrambler is a 3x3x3 scrambler that only generates even permutations. A good strategy would be to guess that:

• even permutation => always guess that the biased scrambler was used
• odd permutation => always guess that the scramble is truly random

When the biased scrambler is used, your strategy guesses correctly 100% of the time. If the position is truly random, your strategy is right 1/2 of the time. That's a pretty large difference – cryptographers would say you can distinguish the biased scrambles with an "advantage" of 1 - 1/2 = 1/2. (Even if you try modifying the strategies, it turns out that's the best you can do given the information in this situation.)
Now, just because you can distinguish the scrambles from truly random doesn't guarantee that you can use your advantage to chop time off your solve (although it would help a little bit for BLD).
However, look at the opposite: if the advantage is close to 0 (for any reasonable strategy), we can be confident that no one can get an advantage out of the bias of the scrambler. To a human, the position is indistinguishable from random!

The best way to do this is to generate truly random scrambles whenever possible, so that the advantage is actually 0. But it's still possible to generate scrambles "as good as random" even if the scrambler can't output every possible scramble.

Let's take Megaminx as an example. For normal Megaminx methods, most people start solving the star on one side. If we can show that the WCA scrambler scrambles each star about as well as a truly random scrambler, then people who use such a method are will not have much of advantage (assuming 1. they won't switch methods, and 2. the state of the rest of the puzzle after making the star isn't biased in some other way unless the solver was doing it on purpose).
But it's also possible that the scrambler doesn't quite separate all stars very well. Maybe starting on a certain side means the star pieces will usually be a bit closer to where they started. This means that there is a slight advantage that might let you chop off a little time.
I've been meaning to do an analysis to see if this is the case, similar to Stefan's analysis for 3x3x3.

We can probably also do something similar for 5x5x5 – check if the random moves of our scramble mix up each center well enough.

Exercise: Come up with a 3x3x3 scrambler that can only generate one out of every million possible states, yet no one can get any significant advantage out of it. (Hint: use a hash function.)

 

[Stefan]

Exercise: Come up with a 3x3x3 scrambler that can only generate one out of every million possible states, yet no one can get any significant advantage out of it. (Hint: use a hash function.)

all = 43252003274489856000
few = all / 1000000
state = sha1(random(few)) % all
scramble = generator(state)

 

[Lucas Garron]

all = 43252003274489856000
few = all / 1000000
state = sha1(random(few)) % all
scramble = generator(state)

Yep; clean and efficient solution!