System for Backtracking Game on a Physical Cube

[IQubic]

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]

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]

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]

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?

No need to overcomplicate things.

I like hard questions

 

[rokicki]

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.