2x2 Scrambler Obfuscator

[Renslay]

This is my proposal how to obfuscate a 2x2 scrambling sequence. By that, I mean, if the scramble is extremely short (for example, 4 moves), a solution is immediate for the scrambler. This is not a problem in a competition where you cannot see the scrambling sequence, but when you practice at home, it can be a problem: if the scrambling sequence is too short, a solution is immediate even for the untrained eyes.

So, how to make the scrambling sequence long, while we still maintain that every cube state has an equal chance to appear?
Easy: we still pick a random state, but we artificially bloat the scrambling sequence itself.

This is how such a scrambling program should operate under the hood:

First, let's pick our randomly generated state normally. For the sake of this example, let's say that is something you can reach by applyling these moves on the solved cube:
G = R U R' F2. Now, quite obviously, our program would pick a scrambling sequence that generates this state, and show it to us:

scramble = R U R' F2

 Twizzle link 

 Setup 

R U R' F2

 Moves 

The problem is obvious: if you are not a highly skilled cuber, you might miss the chance to see a 4 move solution, but if you do the scramble yourself, it's clear:

solution = F2 R U' R'

 Twizzle link 

 Setup 

R U R' F2

 Moves 

F2 R U' R'

Let's hide that! Take the following, random series of moves. We can actually use this for every single scrambling obfuscation.
A = R U2 F R' U2 F' R2

Now we generate a new state: A*G, which we can see if we concatenate the two moves:
A*G = R U2 F R' U2 F' R2 R U R' F2

Never mind if cancellation happens in the middle, we don't care about it. What we care is a solution to this new state, which our program easily can generate:
S = F2 R F U2 F2 U' F' U

Note that since S is a solution, obviously S inverse is the same as A*G:
S' = A*G

Therefore, we can express the original state G as:
A'*S' = G

And A'*S' is:
(R U2 F R' U2 F' R2)' (F2 R F U2 F2 U' F' U)' =
R2 F U2 R F' U2 R' U' F U F2 U2 F' R' F2

This is a long scramble, but the solution is still the same: F2 R U' R'!

 Twizzle link 

 Setup 

R2 F U2 R F' U2 R' U' F U F2 U2 F' R' F2

 Moves 

F2 R U' R'

Note that our original scramble (R U R' U2) nowhere appears in this sequence. If it appears, that is by pure coincidence.

One extra note: it might be a problem that A'*S' produces some cancellations in the middle; which in edge cases can shorten the solution drastically. If this happens, we just have to select a different sequence of turns for A, for example:
A_ = U' R' U' R F' U

This is the same cube state as the other A, so the end result is the same:
A_'*S' =
(U' R' U' R F' U)' (F2 R F U2 F2 U' F' U)' =
U' F R' U R U U' F U F2 U2 F' R' F2

As we see, in this case this version causes cancellations. But it's true that only one of A or A_ can have this problem (since they start/end with different moves)! Nonetheless, the solution is still F2 R U' R'.

 Twizzle link 

 Setup 

U' F R' U R U U' F U F2 U2 F' R' F2

 Moves 

F2 R U' R'

There you go! The random state selection is the same, and the solution is guaranteed to be 6 or 7 moves (depends on A or A_) and plus an average of 9 moves (the plus is the usual distribution of the optimal scrambles).

Additionally, there can be other obfuscating pairs other than A and A_.

No, I don't have an implementation, but if you are familiar with such softwares, this is an easy extension for you.

 

[acrystal]

This is my proposal how to obfuscate a 2x2 scrambling sequence. By that, I mean, if the scramble is extremely short (for example, 4 moves), a solution is immediate for the scrambler. This is not a problem in a competition where you cannot see the scrambling sequence, but when you practice at home, it can be a problem: if the scrambling sequence is too short, a solution is immediate even for the untrained eyes.

So, how to make the scrambling sequence long, while we still maintain that every cube state has an equal chance to appear?
Easy: we still pick a random state, but we artificially bloat the scrambling sequence itself.

This is how such a scrambling program should operate under the hood:

First, let's pick our randomly generated state normally. For the sake of this example, let's say that is something you can reach by applyling these moves on the solved cube:
G = R U R' F2. Now, quite obviously, our program would pick a scrambling sequence that generates this state, and show it to us:

scramble = R U R' F2

 Twizzle link 

 Setup 

R U R' F2

 Moves 

The problem is obvious: if you are not a highly skilled cuber, you might miss the chance to see a 4 move solution, but if you do the scramble yourself, it's clear:

solution = F2 R U' R'

 Twizzle link 

 Setup 

R U R' F2

 Moves 

F2 R U' R'

Let's hide that! Take the following, random series of moves. We can actually use this for every single scrambling obfuscation.
A = R U2 F R' U2 F' R2

Now we generate a new state: A*S, which we can see if we concatenate the two moves:
A*G = R U2 F R' U2 F' R2 R U R' F2

Never mind if cancellation happens in the middle, we don't care about it. What we care is a solution to this new state, which our program easily can generate:
S = F2 R F U2 F2 U' F' U

Note that since it a solution, obviously S inverse is the same as A*G:
S' = A*G

Therefore, we can express the original state G as:
A'*S' = G

And A'*S' is:
(R U2 F R' U2 F' R2)' (F2 R F U2 F2 U' F' U)' =
R2 F U2 R F' U2 R' U' F U F2 U2 F' R' F2

This is a long scramble, but the solution is still the same: F2 R U' R'!

 Twizzle link 

 Setup 

R2 F U2 R F' U2 R' U' F U F2 U2 F' R' F2

 Moves 

F2 R U' R'

Note that our original scramble (R U R' U2) nowhere appears in this sequence.

One extra note: it might be a problem that A'*S' produces some cancellations in the middle; which in edge cases can shorten the solution drastically. If this happens, we just have to select a different sequence of turns for A, for example:
A_ = U' R' U' R F' U

This is the same cube state as the other A, so the end result is the same:
A_'*S' =
(U' R' U' R F' U)' (F2 R F U2 F2 U' F' U)' =
U' F R' U R U U' F U F2 U2 F' R' F2

As we see, in this case this version causes cancellations. But it's true that only one of A or A_ can have this problem! Nonetheless, the solution is still F2 R U' R'.

 Twizzle link 

 Setup 

U' F R' U R U U' F U F2 U2 F' R' F2

 Moves 

F2 R U' R'

There you go! The random state selection is the same, and the solution is guaranteed to be longer by 6 or 7 moves! (The length of A or A_).

Additionally, there can be other obfuscating pairs other than A and A_.

No, I don't have an implementation, but if you are familiar with such softwares, this is an easy extension for you.

This is really helpful! But alas, I'm not lucky enough to get a 4-move scramble

 

[Renslay]

Even the identity (no-scramble) can be obfuscated.

Let's follow the steps according to the program logic:

G = (nothing)

Let's pick our usual A as the obfuscator:
A = R U2 F R' U2 F' R2

The new state:
A*G = R U2 F R' U2 F' R2

The solution to that:
S = R2 F U2 R F' U2 R'

What we want:
A'*S' = G

But A'*S' would cause some cancellations, so instead of A', we use A_':

A_'*S' =
(U' R' U' R F' U)' (R2 F U2 R F' U2 R')' =
U' F R' U R U R U2 F R' U2 F' R2

And that is our obfuscated scramble for the identity!

 Twizzle link 

 Setup 

U' F R' U R U R U2 F R' U2 F' R2

 Moves 

 

[acrystal]

Even the identity (no-scramble) can be obfuscated.

Let's follow the steps according to the program logic:

G = (nothing)

Let's pick our usual A as the obfuscator:
A = R U2 F R' U2 F' R2

The new state:
A*G = R U2 F R' U2 F' R2

The solution to that:
S = R2 F U2 R F' U2 R'

What we want:
A'*S' = G

But A'*S' would cause some cancellations, so instead of A', we use A_':

A_'*S' =
(U' R' U' R F' U)' (R2 F U2 R F' U2 R')' =
U' F R' U R U R U2 F R' U2 F' R2

And that is our obfuscated scramble for the identity!

 Twizzle link 

 Setup 

U' F R' U R U R U2 F R' U2 F' R2

 Moves 

Technically, that doesnt count,you cant solve a cube in 0 moves?!

 

[Renslay]

Technically, that doesnt count,you cant solve a cube in 0 moves?!

According to the WCA rules, every valid state must require at least 4 moves if I recall well. So no, you cannot have a no-move identity scramble, and any sane scrambler program should reject such a state immediately (and simply generate a new random state and scramble).

This is more like just a demonstration on my side, showing that the obfuscating method works on even the most extreme case too.

 

[CrossPetrus]

This is an awesome idea!! I’ll be honest and say that my pb single on 2x2 was caused by a short scramble, which let me see a 4 move solution. I hope this becomes widespread, because this is just genius.

 

[xyzzy]

The standard scramble generators already have scramble obfuscation/padding by default for 2/skewb/pyra. E.g. for 2³, csTimer forces the scramble sequence to be at least 9 moves, while TNoodle forces 11 moves.

 

[Renslay]

The standard scramble generators already have scramble obfuscation/padding by default for 2/skewb/pyra. E.g. for 2³, csTimer forces the scramble sequence to be at least 9 moves, while TNoodle forces 11 moves.

Oh? Didn't know that!

I tested it, and confirmed, csTimer gave me this scramble:

And the optimal solution is indeed shorter than the scramble:

 Twizzle link 

 Setup 

R2 F R2 F R2 F2 R2 F' U2 // 9 moves

 Moves 

U2 F' R2 F R2 F' R2 // 7 moves

I wonder, how do they work algorithmically?

 

[LeszekK]

In Magic Cube, the 2x2 scrambles (and all other 'small' puzzles - i.e. puzzles with less than 15 million states - and the 2x2 has only 7!*3^6 = 3674160 states) are done via a tablebase.
I.e. : a table of all positions and their distances from the solved state(s) is precomputed, and scrambles are done by

1) randomizing an integer from the set 0..<numPositions
2) checking this position's distance from the nearest solved state (there can be many)
3) doing the above until we find a position 'deep' enough
4) coming up with a solution to this position by coming down the table all the way down to the solved state
5) inverting the solution.

This way, there's a guarantee that we do not get any 'lucky' scrambles.
This also gives us a perfect solver.

Actually the topic of scrambling is quite hard and, after 5 years of working on the app, I still haven't solved it in a satisfactory way for all the puzzles. For example shapeshifting, bandaged cuboids are very hard to scramble correctly.

 

[acrystal]

Oh? Didn't know that!

I tested it, and confirmed, csTimer gave me this scramble:

View attachment 48924

And the optimal solution is indeed shorter than the scramble:

 Twizzle link 

 Setup 

R2 F R2 F R2 F2 R2 F' U2 // 9 moves

 Moves 

U2 F' R2 F R2 F' R2 // 7 moves

I wonder, how do they work algorithmically?

Not related, but i was doing 1x1x1 solves on CsTimer, got got a scramble "y x2 z2 y x'. I can cancel it into just "x". I dont know if it was on purpose or anything though.

 

[Renslay]

In Magic Cube, the 2x2 scrambles (and all other 'small' puzzles - i.e. puzzles with less than 15 million states - and the 2x2 has only 7!*3^6 = 3674160 states) are done via a tablebase.
I.e. : a table of all positions and their distances from the solved state(s) is precomputed, and scrambles are done by

1) randomizing an integer from the set 0..<numPositions
2) checking this position's distance from the nearest solved state (there can be many)
3) doing the above until we find a position 'deep' enough
4) coming up with a solution to this position by coming down the table all the way down to the solved state
5) inverting the solution.

This way, there's a guarantee that we do not get any 'lucky' scrambles.
This also gives us a perfect solver.

Actually the topic of scrambling is quite hard and, after 5 years of working on the app, I still haven't solved it in a satisfactory way for all the puzzles. For example shapeshifting, bandaged cuboids are very hard to scramble correctly.

As far as I understand, this is fairly similar to my approach; except I used a fix, chosen state instead of searching for a random-but-deep-enough state as the middle ground. Still, it's good to know that such a solution already exists!