# Optimal 2x2x2 Solver in MATLAB



## Renslay (Oct 16, 2013)

Finally, I finished my optimal 2x2x2 solver. It is written entirely in MATLAB.

The software can build and use an optimal table, which contains all the necessary information for solving the 2x2x2 optimally.

*The interesting fact about the table is that it requires only 734832 bytes to store, which is 1.6 bit information for a cube state, and still can be used as a look-up table directly.*

This little project is the result of the conversation started here:
http://www.speedsolving.com/forum/showthread.php?43928-Which-Moves-in-20-Minimum&p=904485&viewfull=1#post904485

Storing the optimal table requires 1.6 bits per state, however, the software uses more memory for generating and using the table. This is only for keeping the runtime low and the source code short, managable and understandable.

The optimal table is pre-built and stored, however, the functions provide its generation. On my laptop it takes about 7 seconds.

Many thanks for Stefan Pochmann for inspiration and Tom Rokicki for the table building strategy! (And making possible the _7 seconds_ runtime instead of the original _30 minutes._)

You can download the package here.
Or if that doesn't work, try here.

You can find some interesting data here, resulted by the modifications of this software.

The comments are possibly full of typos.
Any bug report or suggestion is welcomed!

Renslay


----------



## Jakube (Oct 16, 2013)

The download link doesn't work.


----------



## Renslay (Oct 16, 2013)

Jakube said:


> The download link doesn't work.



It works for me; however, I put there an other link for downloading.


----------



## Herbert Kociemba (Oct 26, 2013)

Renslay said:


> *The interesting fact about the table is that it requires only 734832 bytes to store, which is 1.6 bit information for a cube state, and still can be used as a look-up table directly.*
> 
> Any bug report or suggestion is welcomed!



Because you work with only 7!*3^6 different positions, you leave one corner fixed, for example the DBL-corner and use only the moves U, R and D. There are 6 symmetries of the cube which keep the DBL-corner in place (rotations by 120 degrees along the diagonal URF-DBL +reflection), so symmetry reduction and using "sym-coordinates" will reduce the table size by another factor of approx. 6 without any negative impact on the performance.

Since you have the choice which corner to fix an additional reduction factor of about 8 might be possible, giving an overall reduction factor of about 48. But because I have no clear idea how to implement this, this is speculation.


----------



## cuBerBruce (Oct 27, 2013)

One way to get the additional symmetry reduction is to start with 6-gen model (88,179,840 positions) and use 48 symmetries and 24 cube orientations to reduce the positions by a factor of (almost) 1152. Using antisymmetry can give another factor of 2 reduction.

See:
http://www.math.rwth-aachen.de/~Mar...od's_Algorithm_for_the_2x2x2_Pocket_Cube.html
http://www.math.rwth-aachen.de/~Mar..._1152-fold_Symmetry_and_24-fold_Symmetry.html
http://cubezzz.duckdns.org/drupal/?q=node/view/79

This can reduce the table to 40296 logical elements or 8060 bytes. But to do the symmetry reduction efficiently, you're going to have additional lookup tables that will reduce that savings significantly. When I did this type of reduction, I simply used a sym-coordinate covering the entire 88,179,840 positions. So I was actually using much more memory overall. My sym-coordinate conversion tables for both directions used over 700 megabytes! But I wasn't attempting to minimize memory usage, obviously.

I think the 6x reduction suggested by Herbert Kociemba will probably result in the less overall memory usage than using the methods of reducing from the set of 88,179,840 positions. The lookup tables for symmetry reduction should be a lot smaller when the symmetry reduction is based on a fixed DBL corner model.


----------



## Herbert Kociemba (Oct 27, 2013)

In the 6x reduction model there is the possibility to define the orientations of the corners so that they are completely independent of the corner positions and compatible with the 6-fold symmetry. The "standard"-orientation model , where the U and D facelets are the reference for the corner orientation does respect the 16-fold symmetry around the UD-axis, but not the rotation along the URF-DLB-axis.
The new model gives the changes of the orientation of the corners for the U, R and F move modulo 3:

U: URF -> +2 -> UFL -> +1 -> ULB -> +1 -> UBR -> +2 -> URF
R: URF -> +2 -> UBR -> +1 -> DRB -> +1 -> DFR -> +2 -> URF
F: URF -> +2 -> DFR -> +1 -> DLF -> +1 -> UFL -> +2 -> URF 

URF -> +2 -> UFL means for example, that the orientation of an arbitrary corner in the URF position is incremented by 2 when it moves to the UFL position.
I do not see any need for lookup tables concerning the orientations if defined like this.


----------



## Renslay (Oct 27, 2013)

Okay, I have a slight idea how these symmetries work. So, for example, the cube after an R' U2 F is equivalent to the cube after an L U2 F' because of symmetry (through mirroring). But if we fix the DBL corner, the scramble L U2 F' is equivalent to [y'] F U2 R' [y]. Therefore, R' U2 F and F U2 R' are somehow eqivalent (throgh symmetry). So, only one of them is needed to store in the look-up table.

My question is:
Given a cube state X, how can you tell what g and Y is, so that X = g(Y), where g is mirroring or rotating through UFR-DBL axis (or something like that, so g tells the equivalency between X and Y), and Y is the cube state that stored in the (reduced) look-up table?

So, how these sym-coords work in the implementation level? How can I use them as a function, or how can I build them as a look-up table? E.g, I have cube, which has the ordinal number / coordinate (3423), how can I tell it is equivalent to [y'] (4543) [y] ?


----------



## Herbert Kociemba (Oct 27, 2013)

R' U2 F is not equivalent to L U2 F' in this context, because it uses a mirror plane that does not fix DBL. You may only use the 3 rotations and the 3 mirror planes that fix DBL, which give the 6 possible symmetries here. So R' U2 F is for example eqivalent to F' R2 U (rotation about URF-DLB axis) or F U2 R' (reflection plane that fixes URF,ULB,DBL).

You need sym-coordinates only for the permutations, not for the orientations. For each permutation rank 0<=x1<7! - we may also call this the permutation coordinate - you compute the ranks x2,x3,x4,x5 and x6 of the corresponding equivalent positions. Then you can take for example min(x1,x2,x3,x4,x5,x6) as the representative of these equivalent positions. At the end you will have a bit more than 7!/6 representatives, I do not know the exact number, but lets call it N, I assume N<900.
You now reindex those N representatives such that they have numbers from 0<=y<N.
Let rep(y) := min(x1,x2,x3,x4,x5,x6) the mapping between the new number y and the old permutation coordinate of the representative. Now the sym-coordinate of the permutation coordinate x with 0<=x<7! is a pair (y,s) with 0<=y<N and 0<=s<6, where s is the symmetry which transforms rep(y) to x. You should built a table T which maps x -> (y,s).
To built such a table you take an y, look up rep(y) and apply all 6 symmetries to rep(y). In this way you usually get 6 entries in T. 


If you have an arbitrary cube position p(x,o) with permutation coordinate x and orientation o, you rewrite this position to p((y,s),o). If you apply the inverse symmetry s^-1 to this cube, you get an equivalent cube p((y,id),o'). id is the do nothing symmetry and (y,id) is just the representative which has the new index y. The distance of this cube you can look up in a table of size N*3^6. In other words the distance table just holds the distances of all representatives of the permutations combined with all 3^6 possible orientations.


----------



## Renslay (Oct 27, 2013)

So, I'm going to repeat you, just for clarifications. 

Let's take an example x = R' U2 F, then:
x1 = R' U2 F // identical
x2 = F' R2 U // xy rotation
x3 = U' F2 R // y'x' rotation
x4 = F U2 R' // BL-FR plane mirroring
x5 = U R2 F' // BL-FR plane mirroring + xy rotation
x6 = R F2 U' // BL-FR plane mirroring + y'x' rotation

Let's say the permutation numbers of xi are 25,12,4,6,7,9, respectively. Then rep(xi) = 4 (its the minimum; let's assume we don't have gaps, so 0 <= y < N). Then the sym-coordinate of 12 is (4,xy), which means xy 4 y'x' is equivalent to 12.

I'm looking for the distance of the cube scrambled by F' R2 U. It has the permutation coord 12 and the orientation coord 199 (for example). Then, originally, I would look at the distance table p(12,199)-th entry, which is the 12*3^6+199 = 8947-th entry. So, instead, I rewrite the position p(12,144) into p((4,xy),199) using the sym-table T. (T has 7! rows and 6 columns, contains the x -> (y,s) mapping)

Aaaand I'm lost here. I don't really understand the next step. What does p((4,xy),199) means, which entry contains the distance information in the new table (which has N*3^6 entries)?


----------



## Herbert Kociemba (Oct 27, 2013)

You got most of it. If you do the conjugation y'x'*p(12,199)*xy , you get p(4,o) with some new orientation o instead of 199. But 4 has has some index y you know, so the index in the table is y*3^6+o.
Edit: I just saw some point, which you seem to have misunderstood. The sym coordinate of 12 is not (4,xy) but the *index* of the equivalence class, where 4 is the representative, so lets better say (idx(4),xy).


----------



## Renslay (Oct 27, 2013)

Oh, I see. So, if I want to know the distance value of F' R2 U,

1) get the permutation coord and the orientation coord of the scramble: p = 12, o = 199.
2) Using the table T, get the sym coord of 12, which is (4,xy). Also, get the shifted index of 4, which is (for example) 2. (So we have the reduced permutation coords without gaps, from 0 to N). So, technically, T will return with (2,xy).
3) Apply y'x' on the original cube (12,199), and recalculate the orientation. This leads to the cube (4,923), where is 923 is the new orientation.
4) Look at the 2*3^6+923-th entry in the new table. It has the distance value 3 (or 0 if we store the modulo 3 values).

Am I right?

Edit: I noticed your edit. Indeed, sym-coord returns with not the original min(x1,...,x6), but the (shifted) index of that value, because we don't want gaps between the sym-coords, they must be between 0 and N. In the example above, idx(4) = 2.


----------



## Herbert Kociemba (Oct 27, 2013)

Yes, this is absolutely right. Just one important point if you build the distance table. If p(x,o) describes some cube and the permutation x has some symmetry itself, then the sym-coordinate of x may be (y,s1) and (y,s2) with different symmetries s1 and s2. The recalculated cube then has two different representations, (y,o1) and (y,o2). o1 and o2 usually are different except for the case that o exhibits the same symmetry as x. In the distance table you then have to take care of both entries y*3^6+o1 and y*3^6+o2.
Or in other words: In the distance table there are different entries, which belong to the same cube position.


----------



## Renslay (Oct 27, 2013)

Herbert Kociemba said:


> Yes, this is absolutely right. Just one important point if you build the distance table. If p(x,o) describes some cube and the permutation x has some symmetry itself, then the sym-coordinate of x may be (y,s1) and (y,s2) with different symmetries s1 and s2. The recalculated cube then has two different representations, (y,o1) and (y,o2). o1 and o2 usually are different except for the case that o exhibits the same symmetry as x. In the distance table you then have to take care of both entries y*3^6+o1 and y*3^6+o2.
> Or in other words: In the distance table there are different entries, which belong to the same cube position.



I see. So technically, I should treat every state x like they have 6 different symmetries, even if they don't have.

A bit of a calculation about the memory usage of the tables:

The sym-table requires 7!*( log2(N) + log2(6) ) ~= 7!*13 bits of memory (or 7!*16 bits if we want to simplify the implementation a little).
The lookup table requires about ((7!*3^6)/6)*1.6 bits of memory. Probably a little more, but not much.

The sum of the two is less than the original lookup table (7!*3^6*1.6 bits) by a factor of about 5.6 or 5.5. Neat!

Next question: should I generate the sym-table and the new lookup table from the old lookup table (i.e., the algorithm generates the full lookup table first), or it should be more elegant if I generate them directly? But that could be a bit complicated to implement...


----------



## Herbert Kociemba (Oct 27, 2013)

There are no memory restrictions which force to generate the table directly. So I would use the old table in this case. And now I think it was an mistake to think that we have to change the definition of the orientations. The standard definition should work as well.
Though the direct way should not be too complicated. Start with the id cube, apply the 9 possible moves, compute all recalculated cubes (in principle there could be even more than 9 as I said before, though in this special case there is only 1) and set the corresponding depth to one. In the next step look for all entries in the table with depth 1. For each such entry construct the corresponding cube, apply all 9 moves to it.... It is almost the same procedure as it is with the old table.

Edit: ... though in this special case there are only 2


----------



## Renslay (Oct 27, 2013)

Herbert Kociemba said:


> There are no memory restrictions which force to generate the table directly. So I would use the old table in this case. And now I think it was an mistake to think that we have to change the definition of the orientations. The standard definition should work as well.
> Though the direct way should not be too complicated. Start with the id cube, apply the 9 possible moves, compute all recalculated cubes (in principle there could be even more than 9 as I said before, though in this special case there is only 1) and set the corresponding depth to one. In the next step look for all entries in the table with depth 1. For each such entry construct the corresponding cube, apply all 9 moves to it.... It is almost the same procedure as it is with the old table.



And with that, the sym-table can be also constructed as well. Hm, I'll give it a try.


----------

