Home »

FTM Antipodes of the Edge Group

Submitted by Bruce Norskog on Tue, 07/21/2009 - 11:23.

I have done my own independent breadth-first search of the edge group using the face-turn metric. I used symmetry/antisymmetry equivalence classes to reduce the number of elements in the search space. I confirm the "Unique mod M+inv" values for this group/metric that Rokicki reported in 2004.

I reduced the "coordinate space" for the search to 5022205*2048=10285475840 elements by using symmetry/antisymmetry equivalence classes of the edge permutation group. (This gives a much more compact overall coordinate space than using an edge orientation sym-coordinate, at a cost of more time required to calculate representative elements. This allowed me to keep track of reached equivalence classes with a ~1.3 GB bitvector in RAM and 5022205 KB disk files to keep track of distances.)

Below is a summary of the 24 symmetry/antisymmetry equivalence classes representing the antipodes at distance 14 from Start. I include a move sequence to generate one element of the equivalence class, along with the number of elements in that equivalence class, and the order of each element (how many repetitions of the sequence gets all edge pieces back to their starting positions, including orientation).

Representative move sequence               elements  order
U  D  L  F  D  R  F  B' L' F' B  D  B  L       1       2
U  D  L  F2 D2 L  F' B' D  B2 D2 L' R  B       3       2
U  D  F' L' D  B  U' D2 L2 R' B  L  U  F2     12       4
U  D2 F  R' U' R' F2 B2 R' U' R' B' U' F2      6       2
U  D  L' F2 U2 L' F  B  U  L' R  B2 D2 F       3       2
U  D' F  U2 F2 L  R' U  L2 D2 F' B  R' B2     12       4
U  D  L2 F' L' U2 B2 D2 L' U2 D' B' R' F'     24       4
U  D  F  L  R  D' R2 U' F' B  R  U2 F2 L      12       4
U  D  L  F' B' R' U' F' U2 R2 F2 D  R2 F'     12       4
U  D  F2 B' L2 B2 D' L' B' L  B2 U' L  R'     12       4
U  D  R' F2 D' F  D' B' U2 R  F2 R2 F' L      24       4
U  D  F' L  U' R' B2 L' B  R2 D' L  F  B2      6       2
U  D2 L' F2 U' R  B' L' D  F2 R  U2 D' L2      6       2
U  D  L  F  U  F' B  D  F2 B  R' U' D' L'      6       2
U  D  R2 F' L' D2 F' R  U  L' B  D2 R  F'      6       2
U  D  L' U  F  R  B' D' L  F2 U2 R2 B  D2     24       6
U  D  L' U  F' D' L2 F' R' U  L' F2 U2 D      24       4
U  D' L2 F  L' U  R  B2 U  F  L' B  U2 L'     12       4
U  D  F  D2 L' F2 U  F' R' B' R2 D' L  D'      6       4
U  D' L  D2 B  R  F' U' B2 L' D2 R  F  L2      1       2
U  D  L' F2 U' D  R2 B' L  R  D' R2 B2 U       6       2
U  D  L' U2 B2 L' U  D  B  D2 B2 L  R' U       6       2
U  D' F' L  R  D2 B2 U  F2 B  L' F  D2 R      16       6
U  D  L  U' D  B2 L2 F  L' R' U  L2 F2 D       8       6
» 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.

even order

Submitted by Rafoo on Mon, 07/27/2009 - 05:38.
Was it predictable that the order of each antipode was an even number ?
Is it also true for local maxima ?
» login or register to post comments

Re: even order

Submitted by Bruce Norskog on Mon, 07/27/2009 - 21:20.

I don't see any particular reason the antipodes would necessarily have even order. Rokicki's analysis indicated that there were 24 antipodes "mod M" and also 24 antipodes "mod M+inv." One might guess from that fact that each antipode might be its own inverse (hence, order 2), but that is only the case for 11 of the 24 antipode equivalence classes. But it really only means that each antipode's inverse must be within its own "mod M" equivalence class, and that doesn't imply it must be even order.

I looked at the cycle structures of each of the antipodes. At the cubie level (that is, ignoring orientation) only the 16th one in my list contains any odd-length cycles (other than 1-cycles). That one contains two 3-cycles, but those 3-cycles are really 6-cycles if you take orientation into account.

So if you look at the cycle structure (including orientation), none of the antipodes have any odd-length cycles, except for 1-cycles (which would represent solved edges). And only the fourth (4) and the tenth (2) have any solved edges.

As for local maxima, I don't know if they would be of even order. Since there are presumably a lot more local maxima than antipodes, my guess is that some will have odd order. I note also that we're talking face-turn metric here, and not quarter-turn metric.

» login or register to post comments

neighboring antipodes

Submitted by Bruce Norskog on Thu, 07/30/2009 - 16:48.

I looked a little bit more at the antipodes of the edge group (face-turn metric). I observed that of the 24 equivalence classes, 20 of them had all neighboring positions being 13 moves from solved. Four of them had neighboring positions that were also antipodes. Those are the 6th, 9th, 21st, and 22nd in the list. Elements of the 6th and 9th equivalence classes have three neighbors that are antipodes (one in the same equivalence class, two in the other). Elements of the 21st and 22nd equivalence classes have two neighbors that are antipodes, both in the other equivalence class.

I'll give examples of these antipode relationships below.

From a solved cube, do the 21st sequence: U D L' F2 U' D R2 B' L R D' R2 B2 U
Then do: R2.
Then do the 22nd sequence: U D L' U2 B2 L' U D B D2 B2 L R' U
The edges will now be solved.

From a solved cube, do the inverse of the 6th sequence: B2 R B' F D2 L2 U' R L' F2 U2 F' D U'
Then do: R2
Note that the position after applying R2 is symmetric to the position before applying R2.

Do the inverse of the 6th sequence: B2 R B' F D2 L2 U' R L' F2 U2 F' D U'
Then do: R'
Now do the 9th sequence: U D L F' B' R' U' F' U2 R2 F2 D R2 F'
The edges will now be solved.

I hope to do a search for all strong and weak local maxima positions, too.

» login or register to post comments

Order

Submitted by rokicki on Mon, 07/27/2009 - 13:03.
Actually, the low order numbers are quite interesting! I went ahead and calculated the order of all 36,971 distance-20 positions known to me, and got the following results. For these, while the order is lower than average, it's not as striking as for the above results. (Of course these are corners and edges, not just edges.) Note the high peak at 12, and the significant number of order 2 positions. More than half the positions have an order of 12 or less. By comparison, the median order for a random position is 70, and the most common order is 60 (about 9.5%). 
count order
 2569   2
   61   3
 2554   4
 4182   6
 2441   8
   79   9
   64  10
13750  12
    1  14
 1029  18
  272  20
 4329  24
    8  28
  823  30
 1942  36
  191  40
  162  42
    4  45
   43  56
  565  60
  783  72
  179  84
  358  90
    1 105
  124 120
   47 126
    1 144
   60 168
  125 180
   95 210
   38 252
   23 360
   45 420
   23 630
» login or register to post comments