Home »

Antisymmetry, Corners of the 3x3x3 Cube, quarter turn metric

Submitted by Jerry Bryan on Thu, 06/21/2007 - 12:18. 
Distance  Positions  Positions   Positions
 from                 reduced     reduced
 Start                  by           by
                      Symmetry    Symmetry
                                    and
                                 Anti-Symmetry

  0             1          1          1
  1            12          1          1
  2           114          5          5
  3           924         24         17
  4          6539        149         96
  5         39528        850        469
  6        199926       4257       2289
  7        806136      16937       8768
  8       2761740      57848      29603
  9       8656152     180787      91688
 10      22334112     466220     235710
 11      32420448     676786     342593
 12      18780864     392342     199610
 13       2166720      45600      23818
 14          6624        163        110

Total    88179840    1841970     934778

As I have written before, my programs have seldom worked with positions. They have nearly always worked with representative elements of M-conjugate classes. In the table above, the summary of representative elements is labeled "Positions Reduced by Symmetry". The goal of this approach is to obtain a 48 times speedup in processing time, and also to obtain a 48 times reduction in storage requirements.

Four or five years ago I did write a little program that dealt with all 88179840 positions of the corners of the 3x3x3 cube instead of just dealing with representative elements. The program was intended as a proof of concept, using a bijection to map between the positions of the corners and a table of lengths for each position. The table contained 88179840 cells to store the lengths. This is an old, old concept and has been done many times before. I do note that the running time was about 15 minutes, whereas when the problem was first solved back in the 1980's the running time was over 24 hours. That's a reflection of the improvements in computer hardware rather than a reflection of improvements in algorithm.

The next step in the "proof of concept" was to reduce the problem by symmetry, working only with representatives of M-conjugate classes. This time, there were only 1841970 positions to deal with. But I stored the length information for those 1841970 positions in the same table of lengths as before (the table containing 88179840 cells). Using the same table worked because the representative elements are positions. So I continued to use the same bijection to map between the representative elements and the table as I had used when I was using all 88179840 positions. I suppose that strictly speaking, we should now call the bijection a function because it's no longer a bijection, but it's still exactly the same computer code.

This approach is a very inefficient use of space, with only about 1/48 of the table cells being used. That means that 47/48 of the table is wasted. However, there was a tremendous speedup in running time. The whole thing ran in just over 20 seconds. It's not quite a 48 times speedup, but it's close. You can't get the full 48 times speedup because of the extra processing associated with calculating symmetry.

I don't think it's ever possible to achieve a complete 48 times reduction in storage by using symmetry. When you don't reduce the problem by symmetry, you don't have to store any positions at all, you just have to store lengths. But when you do reduce the problem by symmetry, you either have to store the representative elements plus their lengths, or else you have to use a hashing technique such as symmetry coordinates. In the case of representative elements, you have to store additional information about each position. In the case of symmetry coordinates, the hash table is not 100% efficient (if I understand correctly how it works). So either way, you don't get quite the complete 48 times reduction in storage.

In any case, my next step was to move from storing the lengths of the representatives sparsely within the table of 88179840 lengths to storing the representatives themselves plus their lengths in a variety of data structures, mostly binary trees of various kinds. I sort of ran out of interest at that point.

I recently resurrected the same program to calculate the corners of the 3x3x3 reduced by both symmetry and antisymmetry. In a perfect world, I think you should strive for both a 96 times speed up and also a 96 times reduction in storage. In this case, I just did a quick and dirty hack of the program and there was no speedup over the speedup I had already obtained from symmetry, and there was no storage reduction over the storage reduction I had already obtained from symmetry. I just added a counting routine for antisymmetry.

The quick and dirty counting routine works as follows. It is assumed that if I did a proper program taking full advantage of antisymmetry, I would work with antisymmetry representatives. Namely, if I had a position x, I would calculate the symmetry representatives y=Rep(x) and z=Rep(x-1). The antisymmetry representative would then be the minimum of y and z. For most positions, this approach will reduce the size of the search space by 2 because y and z will not be equal. But occasionally y and z will be equal. In these cases, there is no reduction. Therefore, in order to count antisymmetry representatives, as symmetry representatives were being identified a counter for the antisymmetry case was incremented any time Rep(x) was less than or equal Rep(x-1). It only took five or six extra lines of code to include this calculation.

I've been thinking about what would be required to take full advantage of antisymmetry, rather than just accounting for it in a quick and dirty fashion. With respect to storage, I would store antisymmetry representatives as described above, yielding about a 2 times storage reduction on top of the storage reduction from symmetry. But I can't convince myself that antisymmetry would provide any processing speedup at all. Here's what I think the problem is.

For each symmetry representative x, I calculate all the neighboring positions as y=Rep(xq) for all q in Q (the set of quarter turns), and similarly for the face turn metric. Each x has 12 neighboring positions (or 18 in the face turn metric). But if I were working with antisymmetry representatives, it seems to me that it would be necessary to calculate for each representative x not only y=Rep(xq) for all q in Q, but also y=Rep(x-1q) for all q in Q. So the number of representatives would be cut in half, but the number of neighbors that would have to calculated would have to be doubled from 12 to 24 (and from 18 to 36 in the face turn metric). Therefore, there would be no speed up at all. Am I missing something?

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Antisymmetry, Corners of the 3x3x3 Cube, face turn metric

Submitted by Jerry Bryan on Tue, 06/26/2007 - 11:32.
Distance  Positions  Positions   Positions
 from                 reduced     reduced
 Start                  by           by
                      Symmetry    Symmetry
                                    and
                                 Anti-Symmetry

  0             1          1          1        
  1            18          2          2        
  2           243          9          8       
  3          2874         71         48       
  4         28000        637        365      
  5        205416       4449       2395      
  6       1168516      24653      12699     
  7       5402628     113073      57692     
  8      20776176     433709     219100    
  9      45391616     947300     479239    
 10      15139616     316616     162327    
 11         64736       1450        902  

Total    88179840    1841970     934778
As a point of clarification, the only results that are new are for anti-symmetry. The symmetry results and position results have all been known for a rather long time. This clarification is for both the quarter turn metric and for the face turn metric.
» login or register to post comments

reduction using sym-coordinates

Submitted by Bruce Norskog on Sat, 06/23/2007 - 19:27.

My response is mainly in reply to Jerry Bryan's paragraph:

I don't think it's ever possible to achieve a complete 48 times reduction in storage by using symmetry. When you don't reduce the problem by symmetry, you don't have to store any positions at all, you just have to store lengths. But when you do reduce the problem by symmetry, you either have to store the representative elements plus their lengths, or else you have to use a hashing technique such as symmetry coordinates. In the case of representative elements, you have to store additional information about each position. In the case of symmetry coordinates, the hash table is not 100% efficient (if I understand correctly how it works). So either way, you don't get quite the complete 48 times reduction in storage.

I agree that when using sym-coordinates (for symmetry only, not antisymmetry), you can't reduce such "cube" problems by more than 48x. Basically, you won't reduce the problem space to a smaller space than the number of equivalence classes you can get using symmetry. So if M is the applicable symmetry group (| M | = 48), then a sym-coordinate won't achieve a full factor of 48 reduction for the same reason you can't get a full 48x reduction in the number of symmetry equivalence classes with respect to the number of positions in the problem. Typically sym-coordinates are used for a sub-space of the entire problem you are working with, and in that case the reduction factor will be even less. In addition, you use space for mapping tables to convert between the regular coordinates and sym-coordinates.

If using sym-coordinates for symmetry and antisymmetry, then there is potential for storage savings approaching 96x. This is what I see as the advantage of antisymmetry. You can handle larger problem spaces directly in memory, and for problems where you resort to using disk storage, the disk space requirements can be reduced by a factor approaching 2, over using symmetry alone.

A sym-coordinate can be thought of as a pair (c,s) where c represents an equivalence class and s represents an element of some applicable symmetry group. So a coordinate x can be converted to a sym-coordinate (c,s) such that c is an index for the symmetry equivalence class for x, and s represents which element of the symmetry group that the representative element of the symmetry class is conjugated by to get the position x. Generally mapping tables are produced so this conversion can be done fast, and with no gaps in the indices of the equivalence classes. This can result in huge mapping tables if one is trying to reduce a large problem space directly with a sym-coordinate, so you usually use a sym-coordinate for only a portion of the problem space.

Note that some values of (c,s) will produce the same position x (same c, but different s), because of symmetrical positions. Thus, the sym-coordinate space is actually larger than the original space. But when dealing only with representives, s can be assumed to be 0, so you get a 48x reduction. But that reduction is from this "increased space," not the original coordinate space.

When I did my "3-coordinate" God's algorithm calculation (the cube ignoring edge permutation, so to speak), I created a sym-coordinate for the corners. Initially this used a lookup table of 88,179,840 4-byte integers (352,719,360 bytes) to convert the regular corner coordinate into a sym-coordinate (1,841,970 elements * 48 symmetries), and a reverse-direction lookup table of 1,841,970*48 4-byte integers (353,658,240 bytes). (I note that I found a way to convert between the regular coordinates and the sym-coordinates using smaller tables, so I would have adequate memory for the "distance table," although what I stored in memory was not actually the distance). Anyway, my sym-coordinate provided the same reduction factor (in terms of the number of elements in the problem space) that Jerry Bryan got for his corners-only analysis (88,179,840/1,841,970 = 47.87257...).

Now, what I probably should have done was to use a sym-coordinate based upon corner permutation only. Now the 8! = 40,320 corner permutations map to a mere 984 equivalence classes. This allows you to represent the corner permutations using a (c,s) pair where c is 0..983 and s is 0..47. For representatives, you can assume s=0, so you only need a number 0 to 983 to specify a representative. But this represents corner permutation only. So we also need to consider 2187 orientations with respect to each representative. This would make the reduction ratio go down to approx. 41.08468 instead of 47.87257, but much less space would be needed for the mapping tables.

The table below indicates how various choices of sym-coordinates reduce the problem space for the 3x3x3 corners. CP = corner permutation; CO = corner orientation; (c,s) indicates the use of a sym-coordinate. I also indicate the amount of space a straightforward implementation of mapping tables would require (not including any lookup tables for performing symmetry conjugation operations on CP or CO). Note the size/48 in the first row (1,837,080) indicates the number of elements to be achieved for a full 48x reduction, if that were possible. Of course, that first row indicates the size using regular coordinates (no sym-coordinate), and so no reduction from the 88,179,840 positions is achieved.

                    1st         2nd                               mapping table
coordinates     coordinate   coordinate        size     size/48  storage (bytes)
-----------     ----------   ----------        ----     -------  ---------------

CP, CO           40,320      *  2,187 =  88,179,840   1,837,080             0
CP+CO(c,s)    1,841,970 * 48          =  88,414,560   1,841,970   706,377,600
CP(c,s), CO         984 * 48 *  2,187 = 103,296,384   2,152,008       175,104
CO(c,s), CP          66 * 48 * 40,320 = 127,733,760   2,661,120        10,710
(I hadn't done the CO sym-coordinate calculation before. I think the 66 is correct based upon a calculation I did today.)
» login or register to post comments

CO sym-coordinate

Submitted by Herbert Kociemba on Sun, 06/24/2007 - 02:09.
I wonder how you to define CO(c,s) for all 48 symmetries. I am very sure that it is not possible to apply all 48 symmetries to reduce *only* the CO-coordinate. The CO-coordinate describes the 2187 cosets of a subgroup H of the cube where H is defined to be all cube positions where the corner orientations are correct. No matter how you define the corner orientations, this subgroup is not invariant under conjugation by the 48 symmetries and hence it is not possible to define the sym-coordinates.
With the usual definition for the corner orientation, H is only invariant under conjugation by the 16 symmetries which preserve the UD-axis, so you can only reduce by 16 symmetries.
» login or register to post comments

Re: CO sym-coordinate

Submitted by Bruce Norskog on Sun, 06/24/2007 - 10:44.
When I did my CO calculation, I (mistakenly) calculated conjugation by symmetries assuming cubies were positioned in their correct cubicles. For applying symmetry for CO only, this is invalid, of course, as Herbert Kociemba pointed out. 16-fold symmetry is the best you can achieve for CO-only, I think. It appears to me antisymmetry is not applicable to this case either. So an anywhere near 48x reduction is not possible with a CO-only sym-coordinate.
» login or register to post comments

Using antisymmetry

Submitted by Herbert Kociemba on Sat, 06/23/2007 - 15:16.
I think you do not miss anything. Using antisymmetry in distance tables complicates the matter. And in most situations we deal with distance tables for cosets. I do not see any way here at all to use antisymmetry, because it is not possible to define the "inverse" of a coset. This is because the target subgroup usually is not normal.
» login or register to post comments

Inverse of a coset

Submitted by Jerry Bryan on Sun, 07/01/2007 - 17:48.
It's certainly the case that the target subgroup is usually not normal. That means that the cosets of a subgroup of the cube usually do not form a group. But is that the same thing as saying that the coset cannot have an inverse? Here's the way I think about it. I may not be thinking about it correctly. If so, please let me know.

Let's use Singmaster notation. He defines permutations on cubicles, for example as uf ->ur (the content of the uf cubicle is moved to the ur cubicle), fdl ->fur, (the content of the fdl cubicle is moved to the fur cubicle), etc.

Normally, a permutation on the cube lists what happens to each of the 12 edge cubicles and each of the 8 corner cubicles. But if what is listed is not all of the cubicles, then we can think of what's happening as a partial permutation (I term I have used) or as an incomplete cube (a term used by Cube Explorer). And of course a partial permutation or an incomplete cube can be thought of as a coset representative.

I think the following is obvious to everybody, but let me make it explicit anyway. Let's suppose that we have a partial permutation that fixes whatever cubicles are included in the partial permutation. For example, what if the partial permutation consists only of uf ->uf. In this particular case, we could say that the partial permutation uf ->uf represents the subgroup H of G where H consists of all permutations in G that fix the uf cubicle. So the index of H in G would be 24. Then, the 24 coset representatives would be of the form uf ->??, for example uf ->ru.

We could find a minimal process to create the uf ->ru partial permutation, namely FR. FR is of length 2 in either the quarter turn metric or the face turn metric. That means that if we think of uf ->ru as a coset, then 2 is a lower limit on the number of moves required to solve every single position in the coset.

Finally, why can't we think of the inverse of the coset uf ->ru as being the coset ru ->uf ? A minimal process to create the ru ->uf coset would then be R-1F-1, which is precisely the inverse of the minimal process for creating an element of the uf ->ru coset. Therefore, the R-1F-1 process would solve the
uf ->ru coset, so the ru ->uf coset must be the inverse of the uf ->ru coset.
» login or register to post comments

A Clarification

Submitted by Jerry Bryan on Mon, 07/02/2007 - 09:39.
I asked, why can't we think of the inverse of the coset uf ->ru as being the coset ru ->uf ?

We may think of ru ->uf as a coset, but of course it's not a coset of the subgroup defined as uf ->uf.  Rather, ru ->uf is a coset of the subgroup defined as ru ->ru.  So there may be a reasonable objection to describing ru ->uf and uf ->ru as "inverse cosets". And this objection ties back to the fact that the subgroups defined as ru ->ru and uf ->uf are not normal. But I still think that uf ->ru and ru ->uf are "inverses" of each other in the sense of doing the opposite things as each other.  And uf ->ru and ru ->uf really are both cosets.  It's just that they are not cosets of the same subgroup.
» login or register to post comments