System for Backtracking Game on a Physical Cube

[Kryptonite]

Hey guys! I've always loved backtracking, like you can do here. Essentially it's applying a scramble of just a few moves, then trying to undo the scramble.

In some ways it's linear FMC lite, but where you can actually achieve an optimal result. The thing is, I MUCH prefer to do this on a real physical cube, which presents some difficulties. I also wanted to create a way this could be competitive or cooperative, in the sense that you can share scrambles, whether it's to challenge (on pass/fail or time/DNF) or teach others with a scramble you've done.

The easiest way to do this, is just have another person mix the cube for you, so you gain no information from the scramble, since you've never seen it. But that's a limitation I'd like to remove. Also, I'd like this process to be automated, so many scrambles can be generated easily without human interaction.

So my recent idea was this: "encode" the BT scramble with another scramble, then the solver "decodes" it with the inverse of that scramble. My thinking is that if the length of the optimal solution to the BT and the length of the optimal solution of the encoding scramble was longer than gods number, then the optimal solution to the combination of both scrambles shouldn't give away information about the BT scramble, since it will never be in the form (encoding scramble)'(BT)'. However, the solver can easily access to the BT state by knowing the encoding scramble.

So we're doing this:

A (5f*)
B (20f*) <- Encoder
C (<=20f*) = AB <- Encoded
A = CB' <- Decoded

Specifically, the encoding scramble I've chosen is the Super Flip, because it requires gods number to solve, it's order 2, it can be generated easily, and it commutes with all other cube states. This means that it can be applied before or after the solver applies the encoded scramble, and it is encoded with the same algorithm it's decoded with, reducing complexity. Also the Super Flip can be applied with an extremely simple algorithm ((MU')^4 yz')^3, and it's easy to identify if you've done it correctly.

So my question now is, if the length of the encoded scramble is shorter than the optimal length of the BT scramble and the optimal encoding scramble, does this effectively obscure all useful information about the BT scramble from the solver? Meaning that the best way to solve the BT scramble is to actually backtrack? (Ignoring all obvious attempts to actively "cheat" using a computer)

Here's a few random scrambles I've encoded that all are (5f*) after applying the super flip--or if the super flip is applied before hand.
1) U L U' F B2 D2 R2 B L' D2 L2 B2 U' L' B2 L D2 B2
2) U F' R2 B' U2 F' R L F2 D' F B' U2 R2 D2 R' F
3) U2 L2 B U2 F2 U D' R2 F L' U R B R2 L2 U D'
4) U2 B R' L U R2 U' F B' U D R2 F' R L' D L
5) L' F B U R L' U2 F2 R2 D2 F' R2 B D2 F R2 D

Also, bonus question:
Is there an algorithm for other cube sizes that is as useful as super flip for the 3x3? It should:
A) Be as close as possible to gods number, so nearly any length BT can be used.
B) Be Order 2 so it is the same to encode as decode.
C) Commutes with all other cube states, so when it's applied is trivial.
D) Have a simple sequence, for convenience of the solver.

 

[Kirjava]

superflip application isn't needed at all

B' R2 D' F2 L2 U' L2 D L2 F U B2 L2 D L2 U2 R2 D' R2 D' F2 R2 D (5f*)

 

[qqwref]

It's an interesting idea, although as Kirjava pointed out, it's probably better to just generate a very suboptimal scramble. Not sure what the best way to do that is though (you can use Cube Explorer but there is no guarantee it won't find the optimal solution quickly).

Is there an algorithm for other cube sizes that is as useful as super flip for the 3x3? It should:
C) Commutes with all other cube states, so when it's applied is trivial.

Unfortunately, the only 3x3x3 states that commute with everything are the solved state and the superflip.

 

[Kryptonite]

superflip application isn't needed at all

B' R2 D' F2 L2 U' L2 D L2 F U B2 L2 D L2 U2 R2 D' R2 D' F2 R2 D (5f*)

How did you generate this exactly, and can it be done without giving away information to the solver every time?

 

[Kryptonite]

Unfortunately, the only 3x3x3 states that commute with everything are the solved state and the superflip.

Good to know, though I was more curious about fulling commuting states for other cube sizes, specifically the 2x2x2, maybe bigger cubes too.

 

[cuBerBruce]

On even size cubes, only identities commute with every maneuver.

On odd size cubes, I believe that besides identities, only maneuvers that leave all pieces in place and flip all middle edge pieces commute with every maneuver.

I note that for 4x4x4 and larger, we don't know God's number, so we don't know any proven antipodal positions.

 

[Kryptonite]

On even size cubes, only identities commute with every maneuver.

On odd size cubes, I believe that besides identities, only maneuvers that leave all pieces in place and flip all middle edge pieces commute with every maneuver.

I note that for 4x4x4 and larger, we don't know God's number, so we don't know any proven antipodal positions.

And this is due to the super flip having full symmetry right? Just did the super flip on my 5x5x5, it seems so innocuous to its equivalent on the 3x3x3!

Given that, for this encoding method, I think one of the best candidates for the 2x2x2 is the "1 Brick" state, which is order 2, God's number to reach, and can easily be reached by R (F R)^7. The commutation for the super flip is definitely cool though, too bad even cubes don't have an equivalent.

 

[Kirjava]

How did you generate this exactly, and can it be done without giving away information to the solver every time?

By hand, and probably. You just need to add some kind of arbitrary subphase to the alg generation to obfuscate things like this.

 

[Kryptonite]

You just need to add some kind of arbitrary subphase to the alg generation to obfuscate things like this.

Apologies if I'm being thick, but would you mind giving a step by step, or a mathematical explanation? Given knowledge of the arbitrary subphase you chose, could I then "decode" the scramble? And vice versa, given the BT scramble, could I decode the subphase you used?

Partly, I've posted this in Puzzle Theory, because I'm more interested in this from a theoretical perspective. I'm less interested in an answer simply being right or wrong, and more interested in exactly why those answers do or don't work based on the mathematics of the cube. I'm curious to find a perfect procedural method for this, not just to have it, but to understand it.

 

[Renslay]

superflip application isn't needed at all

B' R2 D' F2 L2 U' L2 D L2 F U B2 L2 D L2 U2 R2 D' R2 D' F2 R2 D (5f*)

Spoiler: solution

B2 D' F' U2 R2

Hm, nice.

 

[SenileGenXer]

Don't mean to diminish the theoretical discussion but I was thinking of hardware that could cheat... Not to actually cheat but to think of how it could be done.

I was thinking of six networked little machines that could fit under the center caps, had a led and knew their relative positions to each other and had a limited (20 move) memory. Each would record how many times it was turned and broad-cast it to the others. When it was scrambled they all have the scramble. When triggered by a bluetooth or other signal the last one turned would flash it's led 1, 2, or 3 times indicating the way it was to be turned. When you undid that face the previous face turned before would signal, etc back to solved

I guess they don't even need to be that intelligent. The could just be six bluetooth sensors that sense their relative position to each other and have a LED. The "program" could be executed on a smartphone or laptop they are all paired to.

No way to do a particularly great time and the light would be generally be visible to others and especially a camera without some different tricks.

For your stated purposes they wouldn't need the LEDs they would just need to record the scramble (or transmit it to a host) and you could compare your solution to the scramble. There may be a small button battery operated development board that is close to this already.

 

[Kirjava]

Apologies if I'm being thick, but would you mind giving a step by step, or a mathematical explanation? Given knowledge of the arbitrary subphase you chose, could I then "decode" the scramble?

No (the solution path is different), but why not just throw it in a solver if you're actively trying to cheat?

And vice versa, given the BT scramble, could I decode the subphase you used?

Depending on the phase, not unless you have a large enough quantity of scrambles and time on your hands. (Afterthought; the subphase can be randomly generated {not a position, specific piece rules} and therefore defeat any attempt to discover it)

Although, I don't really think any of that is important. Surely this doesn't need to be bulletproof and only good enough that executing it or reading it doesn't give away the solution.

Any computer solver can defeat any serious attempt to obfuscate the scramble.

I'm curious to find a perfect procedural method for this, not just to have it, but to understand it.

It's easiest to think of my idea in contrast to Kociemba; the subphase is a reduction to <UDF2R2B2L2> as an intermediate state and brings the cube closer to solved. To generate obfuscation from a 5 move scramble, you can set the intermediate state to bring the cube closer to some arbitrary position (misperm/orient certain pieces) then solve it in the next phase, and invert the moves. I think some restrictions may be required to avoid cancellations in certain cases.

 

[Kryptonite]

I was thinking of six networked little machines that could fit under the center caps....

That would be pretty intense! It's hard to imagine someone ever doing this, but I do like thinking about what it would take to thwart given system. Also, if you had small vibrating units like it cellphones use in each cap--as opposed to leds, this could actually be pretty stealthy.

Surely this doesn't need to be bulletproof and only good enough that executing it or reading it doesn't give away the solution.

Any computer solver can defeat any serious attempt to obfuscate the scramble.

No, it doesn't have to be bulletproof, but I can't help but be curious if it could be, what that would look like, and could it be practically executed.

You're right in that any computer cheating would render this challenge useless; that's definitely a given. And you're absolutely right, that the goal is that the written scramble should obfuscate the BT scramble in a way that the solver has no advantage by reading it or executing it. However, I'm curious about extremes. Not because they're practical, but because I'm curious. What if I was significantly dedicated to learning how to reduce written scrambles by reading them? Surely I could defeat F D R2 B R B' D' R2 B' U' D' (5f*) after recognizing F D R2 B R B' D' R2 as an expanded form of R F, giving the solution: D U B F' R'. Practical to memorize all such combos? Not really, however the cubing community is built heavily on memorizing and recognizing patterns to compete. And in execution, if I were watching what I was doing, I'd notice eventually passing through the state R F anyway. The scramble is expanded, but ineffectually. So what makes it ineffectual vs effectual? This is just an interesting question to me.

It's easiest to think of my idea in contrast to Kociemba; the subphase is a reduction to <UDF2R2B2L2> as an intermediate state and brings the cube closer to solved. To generate obfuscation from a 5 move scramble, you can set the intermediate state to bring the cube closer to some arbitrary position (misperm/orient certain pieces) then solve it in the next phase, and invert the moves. I think some restrictions may be required to avoid cancellations in certain cases.

I think I understand what you mean about adding an arbitrary subphase now, this is quite clever. Let me see if I've got this right,

So if...
where e is the identity,
for A (xf*)
where B = CD
and C(A(i)) = e(i) for all i contained in {some random set of, but not all, cubies}, or C solves certain pieces if A has been applied.
and D = C'A', or D is the solution to the state generated by AC
then A = B'

The C(A(i)) = e(i), of course, can be omitted and all of the above is still true, however, this is the operation that hopefully keeps A masked by B.

 

[cuBerBruce]

And this is due to the super flip having full symmetry right?

Not exactly. Pons Asinorum also has such symmetry, but does not commute with everything.

Because of the many ways elements of the cube group may move pieces around, to commute with all these elements basically means your maneuver must leave every piece in place, although it can affect orientation. But you basically must have the same orientation change for every piece of a given type. Twisting all 8 corners clockwise violates the laws of the cube (and similarly for twisting counterclockwise), so it can't change orientation of corners either. Hence, only superflip and identity maneuvers work.

Just did the super flip on my 5x5x5, it seems so innocuous to its equivalent on the 3x3x3!

I am not sure what you mean by "super flip on the 5x5x5." If you mean the state achieved by a maneuver that flips the 12 middle edge pieces without affecting any other piece types (so that it commutes with any other 5x5x5 maneuver), I am curious how you performed that. You could do six pure 2-flips, but that would seem pretty inefficient. Building one from 4-flips, 6-flips, and/or 8-flips could be more efficient, although I'm not really aware of any good algs. I thought of (M' U)4 U2 (U' M)4 U2 as a 4-flip, but that also permutes some plus-centers that would have to be restored. (I'm using M to mean a single-layer move, not 3 layers.)

 

[Kryptonite]

Not exactly. Pons Asinorum also has such symmetry, but does not commute with everything.

Because of the many ways elements of the cube group may move pieces around, to commute with all these elements basically means your maneuver must leave every piece in place, although it can affect orientation. But you basically must have the same orientation change for every piece of a given type. Twisting all 8 corners clockwise violates the laws of the cube (and similarly for twisting counterclockwise), so it can't change orientation of corners either. Hence, only superflip and identity maneuvers work.

Gotcha, makes sense; thanks for the break down!

I am not sure what you mean by "super flip on the 5x5x5." If you mean the state achieved by a maneuver that flips the 12 middle edge pieces without affecting any other piece types (so that it commutes with any other 5x5x5 maneuver), I am curious how you performed that. You could do six pure 2-flips, but that would seem pretty inefficient. Building one from 4-flips, 6-flips, and/or 8-flips could be more efficient, although I'm not really aware of any good algs. I thought of (M' U)4 U2 (U' M)4 U2 as a 4-flip, but that also permutes some plus-centers that would have to be restored. (I'm using M to mean a single-layer move, not 3 layers.)

Ah, well, efficiency wasn't quite the goal, haha, I was just curious to do it. I tried (M'U)4, but as you said, you permute other pieces, so I decided to just keep doing it to see what the order of (M'U) is on the 5x5x5--which turns out to be 40, because after (M'U)20, you get the 4-flip that's similar to the (M'U)4 on the 3x3x3. From there I just did 2-flips to finish what I started, since it's more efficient than the M' U route--even if it's still dreadfully suboptimal.

 

[SenileGenXer]

That would be pretty intense! It's hard to imagine someone ever doing this, but I do like thinking about what it would take to thwart given system. Also, if you had small vibrating units like it cellphones use in each cap--as opposed to leds, this could actually be pretty stealthy.

You need half of this sensor board's functionality and size. Then you need a battery and accelerometer and time to program.

It's not that far fetched. This was an 800 node network in 2001. Darpa has poured in money. Consumer electronic demand has shrunk wireless and accelerometer size and prices. There is an open source OS for this. You only need need a six node network.

 

[Kryptonite]

You need half of this sensor board's functionality and size. Then you need a battery and accelerometer and time to program.

It's not that far fetched. This was an 800 node network in 2001. Darpa has poured in money. Consumer electronic demand has shrunk wireless and accelerometer size and prices. There is an open source OS for this. You only need need a six node network.

Since you have accelerometers, you could use cube rotations to signal the cube to record moves and when to start playing back the reverse or optimal solve sequence that it recorded. It would be pretty easy to make it look like you were just toying with or examining the cube to toggle the states, and could potentially eliminate any additional hardware.. That'd be a hell of a party trick!

 

[SenileGenXer]

Not so much cheating but someone has already designed and built a bluetooth enabled cube that transmits the face turns to a computer. Looks like it transmits rotations as well. Check out the "interface cube" on this project. Doesn't look stock and I have no idea how it feels.

I was thinking of custom things to fit under the center caps. Retrofit a commercially available cube.

 

[Lucas Garron]

Reminder: Void cubes have a lot of free space for placing one piece of equipment, and turn reasonably well.

 

[Kryptonite]

Self Solving Cubes

Not so much cheating but someone has already designed and built a bluetooth enabled cube that transmits the face turns to a computer. Looks like it transmits rotations as well. Check out the "interface cube" on this project. Doesn't look stock and I have no idea how it feels.

I was thinking of custom things to fit under the center caps. Retrofit a commercially available cube.

That's a really cool project! The cube is definitely oversized, but the tech could probably be smaller now, and definitely in the future!

Reminder: Void cubes have a lot of free space for placing one piece of equipment, and turn reasonably well.

That's true, could be a pretty useful starting place for such a project.

Back to the Theoretical
Not to quash this line of discussion--because it's definitely interesting to think about! But I'd like to move back towards the theory and towards my original question. After thinking about Kirjava's suggestion, I think I was able to show that our methods our basically synonymous mathematically. Ultimately both use some encoding scramble (C) that after being applied to the BT scramble (A) can be solved with sequence (D). Given this, there is an encoded scramble (B) that's in the form (D'C'), which is equal to (A), but hopefully is dissimilar enough that it couldn't be recognized for A.

The difference in our methods is choosing the encoding scramble (C). For my method, it's a fixed set of moves, and I originally suggested the Super Flip, given some convenient properties. For Kirjava's method, C is dependent on A, where specific pieces must be in specific places and oriented in certain ways after the initial scramble, so that C(A(i)) = e(i), where i is a set of pieces, and e is the identity*.

From here, I argue that my method is actually simpler than Kirjava's, because Kirjava's method involves two solving phases, where as mine involves only a single solving phase. In the first phase, my method involves simply appending moves, whereas Kirjava's involves searching for a solution that satisfies C(A(i)) = e(i), requiring additional computing power. Both methods involve solving the cube in the second phase.

I don't mean to undermine Kirjava here (especially given the chance that I've missed something!), because the method presented is still quite clever, and interesting from a theoretical stand point. He was also able to show, that using the Super Flip to encode probably leads to an unreasonably long encoded scramble--17 moves + the super flip is likely excessive. Also Kirjava brought up a point I'd missed, which is that cancellations are a critical consideration to avoid a case that clearly simplifies to the original A.

Based on this, I've updated my assumptions. Essentially, if the length of A plus the length of C minus the length of cancellations between the two is greater than gods number, the resulting encoded scramble (B) will have a shorter than, meaning it (will?/might?) obfuscate every time. There's an additional catch here, where this should apply for all AiCj. Meaning that there may be many scrambles equivalent to A or C that use different move sequences to get there, so any combination of them could cancel down to fewer moves than god's number, meaning it may itself represent the optimal solution--which certainly would not obfuscate.

Mathematically speaking:

Spoiler

(if someone has more experience with set theory btw, please step in to correct any mistakes)
(note: I have left off many 1 < i < n, hopefully to keep it more readable)
M = {all face turns}
A = {all A[SUB]i[/SUB] generated by elements in set M | A[SUB]1[/SUB] = A[SUB]i[/SUB] and A[SUB]i[/SUB](k) != A[SUB]j[/SUB](k) for any k}
C = {all C[SUB]i[/SUB] generated by elements in set M | C[SUB]1[/SUB] = C[SUB]i[/SUB] and C[SUB]i[/SUB](k) != C[SUB]j[/SUB](k) for any k}
D = A[SUB]i[/SUB]C[SUB]j[/SUB]
B = DC[SUB]1[/SUB]'
A[SUB]i[/SUB] = B
where
A[SUB]i[/SUB] = A[SUB]ia[/SUB]YX and C[SUB]j[/SUB] = X'YC[SUB]ja[/SUB]
then
D = A[SUB]ia[/SUB]YXX'YC[SUB]ja[/SUB] => D = A[SUB]ia[/SUB]Y[SUP]2[/SUP]C[SUB]ja[/SUB]
when n(Z) means the number of elements used from set M to generate Z,
if n(Ai) + n(C[SUB]j[/SUB]) - 2*n(X) - n(Y) > 20, it will always be < n(D) if D is optimal

Defining Obfuscation
Whether the above assumption is correct in that B obfuscates A is still a remaining question. To address obfuscation--which is still only vaguely defined, I had an insight, and think it could be defined as avoiding as many possible vertices on the Cayley Graph that are used in all optimal paths of A. Essentially meaning, never put the cube in a state generated during the course of any optimal algorithm for reaching A if it can possibly be avoided. A secondary goal, should be to make the length of B as short as possible, simply for convenience. Perhaps a computer search for B that satisfies this quality would be the best way to do this.

Mathematically speaking:

Spoiler

(This is really testing my knowledge here, feel free to correct any errors or lend a hand!)
(note: I have left off many 1 < i < n, hopefully to keep it more readable)
M = {all face turns}
A = {all Ai generated by elements in M | A[SUB]1[/SUB] = A[SUB]i[/SUB] and n(A[SUB]i[/SUB]) = n(A[SUB]k[/SUB]) where A[SUB]k[/SUB] is optimal}
A[SUB]ij[/SUB] = {A[SUB]i[/SUB](1), A[SUB]i[/SUB](2)...A[SUB]i[/SUB](j)}
A[SUB]v[/SUB] = {v | v is an element in A[SUB]ij[/SUB]}
B = A[SUB]1[/SUB] where B is generated by elements of M
B[SUB]i[/SUB] = {B(1),B(2)...B(i)}
B[SUB]v[/SUB] = {v | v is an element in B[SUB]i[/SUB]}
n(A[SUB]v[/SUB] intersects B[SUB]v[/SUB]) should be minimal

Ironically, given the ability to do this perfectly every time (as in, the only shared states between the two scrambles are the identity and the end state), the solver would always know that the first move of his/her solve could never be the inverse of the last move in the scramble, so some information can be gained. However, maybe this is better than possibly passing through the state yielded by the correct application of the solvers first move, as that might be recognized for a simpler scramble.

Whew, long post, sorry, I had a lot to think about! I'm very curious for feedback on this though, especially I'm interested what people think of how we could effectively define obfuscation.



*technically, C(A(i)) = X(i) also satisfies this, meaning the rule set of what pieces can move where doesn't mean it must move pieces of the cube towards the solved state, but to any given state.