# System for Backtracking Game on a Physical Cube



## Kryptonite (Jan 10, 2014)

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 (Jan 10, 2014)

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 (Jan 10, 2014)

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).



Kryptonite said:


> 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 (Jan 10, 2014)

Kirjava said:


> 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 (Jan 10, 2014)

qqwref said:


> 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 (Jan 10, 2014)

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 (Jan 10, 2014)

cuBerBruce said:


> 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 (Jan 10, 2014)

Kryptonite said:


> 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 (Jan 10, 2014)

Kirjava said:


> 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 (Jan 10, 2014)

Kirjava said:


> 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 (Jan 10, 2014)

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 (Jan 10, 2014)

Kryptonite said:


> 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?



Kryptonite said:


> 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 (Jan 10, 2014)

SenileGenXer said:


> 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.



Kirjava said:


> 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.



Kirjava said:


> 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 (Jan 11, 2014)

Kryptonite said:


> 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.



Kryptonite said:


> 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 (Jan 11, 2014)

cuBerBruce said:


> 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!



cuBerBruce said:


> 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 (Jan 11, 2014)

Kryptonite said:


> 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 (Jan 11, 2014)

SenileGenXer said:


> 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 (Jan 11, 2014)

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 (Jan 11, 2014)

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


----------



## Kryptonite (Jan 12, 2014)

*Self Solving Cubes*


SenileGenXer said:


> 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!



Lucas Garron said:


> 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.


----------



## IQubic (Jan 12, 2014)

Lucas Garron said:


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


Heck let's put the electronic unit in Oskar's Treasure Chest.

-IQubic


----------



## Kryptonite (Jan 12, 2014)

Huzzah! I think I have developed an effective definition of obfuscation of cube states from their optimal solutions that can be mathematically supported.

Thinking about obfuscation, the idea is that you force the solver to address the state given by the scramble, but that the scramble is unhelpful in his/her endeavor. The solver has a choice: they can "attack the state" generated by the scramble, or they can "attack the scramble" itself. A state is truly obfuscated when an attack mounted on the state is always more effective than an attack mounted on the scramble.

I've shown some anecdotal cases of "attacking a scramble," but I can put forth a formal definition, which I'll do shortly. But ultimately, the goal is simply to shorten move sequences until you have a scramble of the goal length. The simplest scramble to attack, is of course the scramble being the length of the goal solve. Why would you attempt to solve the state when the scramble has given you the answer? Also, the scramble could have "garbage" in it, which ultimately performs no state change. By identifying and removing this "garbage," a solver might find a solution of the goal length, without attacking the state itself.

Formally, attacking the scramble involves breaking it into simpler subproblems, solving those, and removing excess moves in the process. If this subproblem attack can reduce the scramble to the length of the goal solve, n(A), it is not obfuscated. Each subproblem is each combination of moves of the scramble (we'll call B). B[SUB]ij[/SUB] represents any given subproblem:

B[SUB]ij[/SUB] = {B[SUB]i[/SUB], B[SUB]i+1[/SUB], B[SUB]i+2[/SUB]...B[SUB]j[/SUB] for i <= j <= n(B)}, where B[SUB]1k[/SUB] is the entire problem if k = n(B)

For example, if B = R F' D L F' can be broken into:
B[SUB]11[/SUB] = R
B[SUB]12[/SUB] = R F'
B[SUB]13[/SUB] = R F' D
...
B[SUB]34[/SUB] = D L
B[SUB]35[/SUB] = D L F'
...
B[SUB]55[/SUB] = F'

Even ignoring possible heuristic improvements, a brute force of the subproblem approach is more effective than it seems at first glance because of the of the exponential growth of the possible nodes when adding moves. Searching all nodes of length n takes ~13.33 times longer than searching all nodes of length n-1. And no matter the length of the subproblem, we never have to search for solutions longer than n(A)-1 (note: that assertion probably needs a proof).

The complexity does increase as we make B larger because it adds subproblems, and when n(B) > n(A) + 3, we eliminate the usefulness of a purely brute force attack. However, there are definitely heuristic approaches that can be coupled with brute force to improve its effectiveness.

Heuristic approaches may have limits in effectiveness, where even if the scramble can be attacked effectively, the best heuristics still fail to improve upon an attack on the state. However, I'm more curious in a method that could beat all heuristic approaches, making the search moot.

This method is (nearly) as I proposed in my previous post, which is searching for a B where each intermediate state of B (or the vertices it passes through on the Cayley Graph) is never equal to an intermediate state (or vertex) in any optimal solution to A--identity state and ending point excluded, of course.

If we can find a B that satisfies this, an attack on the scramble will not only be less effective than an attack on the state, it will be futile. A given subproblem B[SUB]ij[/SUB] may be suboptimal, and therefore have moves removed when solved, but n(B[SUB]ij[/SUB]) = n(A) only if B[SUB]ij[/SUB] is the entire problem B[SUB]1k[/SUB].

The proof is actually fairly simple, as it's basically the triangle inequality, which essentially states that the shortest point between to points is a straight line.

Proof:


Spoiler



n[SUB]o[/SUB](X) = optimal number of moves to bring X to the identity
M = {all face turns}
B[SUB]ij[/SUB] = {B[SUB]i[/SUB], B[SUB]i+1[/SUB], B[SUB]i+2[/SUB]...B[SUB]j[/SUB]}
A[SUB]ij[/SUB] = {A[SUB]i1[/SUB], A[SUB]i2[/SUB]...A[SUB]ij[/SUB] | A[SUB]i[/SUB] = {a[SUB]i[/SUB] generated by M| n[SUB]o[/SUB](a[SUB]i[/SUB]) = x}} (note that the subscripts here have different meanings from B[SUB]ij[/SUB])
if n[SUB]o[/SUB](B[SUB]1i[/SUB]A[SUB]km[/SUB]') > 0, meaning B[SUB]1i[/SUB] is not a point on any optimal path
n[SUB]o[/SUB](B[SUB]1i[/SUB]) + n[SUB]o[/SUB](B[SUB]i+1,j[/SUB]) > n[SUB]o[/SUB](A[SUB]kx[/SUB])
meaning no subproblem can reduce the scramble to length x.


The only consideration is that if for (A), there is no (B) where the intersection of states is only the identity and the resulting state of A. A simple example of where this might happen is if A is the super flip. The first move of B will always be on an optimal path, since any move on the identity moves the cube closer to the super flip. If passing through a state on the optimal line is a must, the poles should be prefered, since longer subproblems are more complex than combining multiple short subproblems.

Anyway, I hope this is interesting, and that I haven't left any glaring errors! Kinda cool to be able show whether or not a scramble is "bulletproof" in its obfuscation. What do you guys think?


----------



## 161803398874989 (Jan 15, 2014)

What's wrong with taking an arbitrary (say, 10 moves away from solved) state and then solving that into the position to backtrack? It'll yield a 30-scramble with an n-move solution, where n is the number of moves to backtrack. Maybe you could use even shorter obfuscating state to reduce the scramble length. You can also take the same obfuscating scramble every time.

No need to overcomplicate things.


----------



## Kryptonite (Jan 15, 2014)

161803398874989 said:


> What's wrong with taking an arbitrary (say, 10 moves away from solved) state and then solving that into the position to backtrack? It'll yield a 30-scramble with an n-move solution, where n is the number of moves to backtrack. Maybe you could use even shorter obfuscating state to reduce the scramble length. You can also take the same obfuscating scramble every time.



What's interesting about the method you're suggesting, is that it's ultimately identical in form to Kirjava's and my suggested methods. You have an encoding scramble (C) that is the ten-mover you're applying to the solved state. Then you do a solving pass (D'), which instead of giving the identity, it moves the cube from the state generated by (C) to the state generated by the scramble we're trying to obfuscate (A), thereby turning it into the encoded scramble (B).

So we can say,
A = CD' = B, meaning D = AC'

And you can see the similar form to the previous suggestions.

What really remains is to ask: is there a simple way to find an encoding scramble (C), that creates a new scramble (B), that always satisfies my definition of obfuscation (no shared intermediate states) for every optimal A?



161803398874989 said:


> No need to overcomplicate things.



I like hard questions


----------



## rokicki (Jan 21, 2014)

If you want to use existing software, this is what I'd do.

Assume your input scramble is "A".

1. Generate a totally new random position, "B".
2. Find a reasonably short solution to "B" (two-phase algorithm) (C).
3. Find a reasonably short solution to B'A (two-phase algorithm) (D).

At this point the concatenation of the two (CD) is probably about a 40-move
scramble for A, and there's no remnant of data about A in either the
first part or the second part (only in their combination).

This may seem inconveniently long. You can try to shorten some internal
subsequence if you want (with an optimal or suboptimal solver) but you run
the risk of finding a solution that catastrophically cancels. You might be
able to take it down to 30 moves fairly easily.


----------

