• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Optimal 2x2x2 Solver in MATLAB

Renslay

Member
Joined
Aug 1, 2011
Messages
1,716
Location
Hungary
WCA
2005HANT01
YouTube
Visit Channel
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
 
Last edited:
Joined
Nov 29, 2008
Messages
214
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

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
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.
 
Last edited:
Joined
Nov 29, 2008
Messages
214
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.
 
Last edited:

Renslay

Member
Joined
Aug 1, 2011
Messages
1,716
Location
Hungary
WCA
2005HANT01
YouTube
Visit Channel
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] ?
 
Joined
Nov 29, 2008
Messages
214
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.
 
Last edited:

Renslay

Member
Joined
Aug 1, 2011
Messages
1,716
Location
Hungary
WCA
2005HANT01
YouTube
Visit Channel
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)?
 
Joined
Nov 29, 2008
Messages
214
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).
 
Last edited:

Renslay

Member
Joined
Aug 1, 2011
Messages
1,716
Location
Hungary
WCA
2005HANT01
YouTube
Visit Channel
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.
 
Last edited:
Joined
Nov 29, 2008
Messages
214
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

Member
Joined
Aug 1, 2011
Messages
1,716
Location
Hungary
WCA
2005HANT01
YouTube
Visit Channel
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...
 
Joined
Nov 29, 2008
Messages
214
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
 
Last edited:

Renslay

Member
Joined
Aug 1, 2011
Messages
1,716
Location
Hungary
WCA
2005HANT01
YouTube
Visit Channel
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.
 
Top