Optimal solutions for two important subgroups

Now when I am thinking closer, I realise that I might have some error since you clearly found more positions then I did. I will look at the problem as soon as possible.
Have you verified the other depths?
Have you verified the group that fixes cubies?

I'm working on the other depths. It may take me several (days/weeks/months). I haven't verified the group that fixes cubies (I'm not using GAP; perhaps I should learn?)

The face turn metric computation took me 4 days on 10 computers.

I dont have a clue why. But let us do following test. I got following for the face turn metric:

19f 216 (7 unique w.r.t M + inv)
18f 827386
17f 20029566
16f 16944222
15f 4905894
14f 1084624
13f 217374
12f 72008
11f 5220
10f 2521
9f 360
8f 528
7f 0
6f 0
5f 0
4f 0
3f 0
2f 0
1f 0
0f 1


The positions needing 19f in generator form:
F U D2 R2 L2 F2 B' U' L2 B U B D L2 F2 D2 L2 F2 U2
R2 B' R2 L2 U2 B2 D' B2 D2 F' R2 L2 D' R2 U2 B2 U B2 D'
R U R' B2 L U' R2 L U' F2 R L2 B2 U' R2 D2 R2 D B2
U2 B R2 B2 U R2 U B' D F2 L2 B D' R2 F2 R2 L2 D' F2
R' U D' L B2 R' L U' B2 D B2 R' D R2 F2 D F2 L2 U
U B2 D2 R2 D' R2 B2 D' F' U L2 D B' R2 U2 B U' L2 F'
R2 D L2 D' L2 F D F' R2 F U' B' L2 B L2 B' U L2 F'

Can you see if you get the same for this?

I confirm all those numbers:

dep	arrangements	M	M+inv
0	1	1	1
8	528	11	6
9	360	8	5
10	2521	63	43
11	5220	117	68
12	72008	1541	821
13	217374	4584	2378
14	1084624	22743	11690
15	4905894	102419	51896
16	16944222	353629	178786
17	20029566	418360	212304
18	827386	17502	9419
19	216	7	7
	44089920	920985	467424

Hello,

Nice to see this confirmed. I was thinking of putting the table on the main window so that everybody can see it. I hope it's ok with you. How long did it take to compute this table?

With my silly algorithm, it took a bit more than three days on an old 2.8GHz P4. All I do is find all edge solutions of a given length, and see what they do to the corners, and repeat until all corner arrangements are found. The last few take the longest, so I should replace the end phase with a straight use of an optimal solver.

Feel free to put it any of this stuff on the main page as you will.

We agree up to 17f; I haven't run 18f or 19f yet myself.

How did you run that so fast, BTW?

Nice to see that we agree on this one.

I have an own algorithm that I will publish everything about as soon as possible and I have also used several powerful computers on this task.

I dont't think the numbers are wrong it might only be the adding that is incorrect. Do you have any idea how many equivalence classes unique M there are for this group? Or a fast way to compute those?
I am almost sure that GAP has a way to do it. I will try to find something in the manual.

I haven't really played with GAP enough to useful calculations with it. But Martin Schoenert posted information a long time ago on how calculate conjugacy classes.

http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Martin_Schoenert__Re__The_real_size_of_cube_space.html

I estimate 20-25 days for the group that fixes cubies on one computer with a program in GAP (20 times slower than C++). But i used 10 computers so the calculation was finished in 2-3 days. I have not done the face turn metric yet but the time would be aproximately the same. For the group that fixes edges it took me approx 70 days on one computer. But as usual i used more computers.

I really would be interested, if all cubes that fix edges could be solved within 20 moves in FTM , how many and which cubes need 20 moves and which symmetries these cubes have.
I myself have optimized the maneuvers for all symmetric cubes of kind O_h, D_3d, T_h, C_3v, T, D_4h, D_3, D_4, D_2d, C_4v, C_4h (see Cube Explorer for the definitions of these symmetries) and found 42 cubes which need 20 moves ( and no which need more). I used a new optimal solver for this purpose , which optimally solves a random cube in less than two minutes on my PC on average.

I've got a set of 74 positions (unique wrt M) that require 20 moves in the face turn metric. I am currently trying to prove that they are local maxima, but it looks like this may take a week or so, and I'm not sure I want to wait that long.

Dr. Kociemba, would you be willing to share the information on the space that your huge (3GB) pruning table uses? I may write a Linux version of that so I can optimize these things faster.

Are those all the positions requiring 20f? Have you computed optimal solutions for the group that fixes edge cubies and orientation i.e. for a space containing 2048*44089920 positions?

They are all the positions requiring 20f such that the edge cubies are M-symmetric; this is (I believe) 4*44M positions. Is this what you meant? I don't understand the factor of 2048. Maybe I'm missing something?

I need a better optimal solver; this one is taking forever to prove these positions.

When Herbert asked me for optimal solutions in the group that fixes edges we kind of missunderstood each other because by group that fixes edges I meant the group that fixes edge cubies and orientation and he meant the group that only fixes cubies but not necesarily their orientation. This gives 2048 times more cubes because there are 2048 possible orientations if the edge cubies are in place. So when you wrote about the 20f cubes I thought that you maybe understood him right.

By the way does my depths for QTM agree with yours now?

Though it would be nice, its just Mr. Kociemba, not Dr. Kociemba...

Ok, The idea of the very huge solver is quite simple. In addition to the standard optimal solver coordinates (see my homepage for details) I added a fourth coordinate which describes the positions of four corners (ignoring their order). This coordinates range is from 0..69.
Instead of building a huge pruning table of more than 2 GB (this actually would not work well because you hardly will find a continuous block of memory of this size) I use 70 tables of the size of the standard optimal solver. When generating the pruning table I need 2 bits/entry, so the standard optimal solver size is 64430*2187/4 byte, which is about 35 MB, so the total memory when generating the table is about 70*35 MB which is less than 2.5 GB. After generating the tables they are compressed to 1.6 bits/entry, so the table saved to and loaded from the hard disk is about 2 GB and they also only use about 2 GB of memory.
The additional coordinate must be "compatible" with the transformation done by the 16 symmetries (let's call this group M0 here) which preserve the UD-axis, so you cannot use any 4 corners for this purpose. I tried two different possibilities:
a) four corners on a tetraeder e.g. URF,UBL,DLF and DRB and
b) four corners of the U-face: URF, UFL, ULB and UBR
The number of positions wrt to M0 (not the number of internal states of the pruning table) and their distances in FTM are
in case a)

0 1
1 2
2 8
3 62
4 649
5 7829
6 96900
7 1201690
8 14742203
9 172627707
10 1640065078
11 6132445955
12 1739371520
13 316350

and for case b)

0 1
1 2
2 13
3 111
4 1268
5 15415
6 192929
7 2403941
8 29400724
9 335538985
10 2772495855
11 6049092242
12 511363027
13 2117

So in other words you could say that in 13 FT-moves you can fix the orientations of corners and edges, put the edges of the UD-slice into their slice and put the corners into their tetraeder (case a) or the UD-face corners into the UD-face (case b).

On first glance it seems, that case a) is superior to b), because pruning table has more entries with high distances. But when applying the optimal solver, it is applied in three directions, and then b) is faster. Because when you apply an arbitrary move on the ID-cube, for one of the directions the distance will stay 0 with this coordinates (for example an U-move applied on the ID-cube does not change the orientations of the corners and edges, the UD-slice edges stay in their slice and the U-face corners stay in that face).
And now, if your pruning table gives for example distance 12 in all three directions, you know that the true distance is at least 13, which improves speed considerably.
Another convenient property is, that if the U- face corners are in the U-Face, the R-face corners are in the R-face and the F-corners are in the F- face simultanously, all corners are in place.

I just today finished the optimal maneuvers for all cube positions which *exactly* have symmetry S_6 (three fold symmetry along a long diagonal + point symmetry to the cube center, 3870 cases unique wrt M) and found 88 positions that need 20 moves here. I will give the detailed results on my homepage when I have some time. Computation for this symmetry class took several days.

Wow, 2minutes is fast. How long does it take to optimally solve a 19f* position? I can send you a bunch to try if you want. Is the new optimal solver available anywhere?

The new solver is available on my homepage. If you want, you can send me a bunch of positions.

Hi I have redone depth 16 and got exactly the same number as you did.

The solver will be available very soon. A friend of mine is almost finished writing a C++ version. I estimate 1 month maximum until it will be available.

This is an incredible result for a completely random position. I have developed several versions of my algorithm and it seems to be finished now. If you want me to I can try to put some computers at work on "the group that fixes edges" for the face turn metric and send you the maneuvers. I forgot to thank you personally in the previous message for sharing your Cube Explorer. This is probably the best solver for the face turn metric and it helped me a lot with the 28f proof.

If you have the possibility to do the computation, this would be great! I hope you can publish the results soon.

I will start working on the problem tomorrow. If we are lucky I will have the results next week.

I'm pretty sure that by "Group that fixes cubies," Silviu means the group where the locations of all cubies are fixed, but their orientations may change (as long as the conservation of flips and conservation of twists are satisfied). There are 2048*2187 = 4,478,976 total positions in that group, in agreement with Silviu's data.

My analysis of the permutations of the cubies showed that the cubies can be placed in the correct positions (but not necessarily in the proper orientation) in 18 quarter turns or less. The cubies can then be oriented using no more than 24 additional quarter turns. Thus, this provides a way of solving the cube with no more than 42 quarter turns. (Of course, Silviu had already found that solving edges first, then solving the corners without any net effect on the edges, is another two-phase method that is superior in terms of the number of quarter turns required.)

- Bruce Norskog

We give a proof below that any cube can be solved in 40q using the above analysis:

You can take each position that requires 24q and compute 12 different solutions, each of this 12 solutions ending with one of the 12 generators {U,L,F,B,R,D,U^-1,L^-1,F^-1,B^-1,R^-1,D^-1}. And when you want to solve an arbitrary element g in the cube group you first multiply it by B^-1 from the right and take it to the "group that fixes cubies" and then multiply it by an element in that group to take it to the identity.

So g*B^-1*A^-1=id ->g=A*B.

If A requires 22q or less then then the length of g is 40 or less.

If A requires 24q then we write B as X*C where X is one of the twelve generators. And C is an element of length 17 or less.

We assumed that A can be written as D*X^-1 and D is of length 23. That is because we assumed we have a solution that ends with any generator. And when combining solutions we get that g=AB=D*X^-1*X*C. We get cancellation which shows that any cube can be done in 40q max.

Thus the only thing we have to show is that the 24q positions are local maxima. For that we need to take each position g in the "group that fixes cubies" that requires 24q, multiply it by each generator from the right, and check if the new position requires 23q. The total number of positions are 4 and multiplied by each generator gives 48 positions needed to be solved optimally. One such position requires typically 10-20 hours on Michael Reids solver so it is not unreasonable.

The method above is just a special case of the method i used to show that any cube can be solved in 28f.

In case someone wants to do this analysis i give the 24q positions:

1.) F R' U B2 U R D F U' B R B2 D B R' U' F' B R U2 D' (24q*,21f)
2.) F R' F2 R' U F U L B2 R B D2 F R' B' D B L' D' R' U' (24q*, 21f)
3.) F R D2 B' R' F R' D2 B' D' L F L2 U B' U F L2 U' B' (24q*, 20f)
4.) superflip

The superflip is already known to be a local maxima so no investigation is needed for that one.

I have also computed optimal solutions in the face turn metric for this particular positions and two of them required 20f and one 19f.

I've been using a slightly different technique for proving local maxima; it's quite a bit faster (usually).

Given a sequence s that you believe is a local maxima, build a list of all sequences s.a where a is one of the moves (for q, that's a list of 12 sequences each one longer). Now start with length len=2. For each element in the list, find the optimal solution to the suffix of length len of that element, and solve that suffix optimally. If there is a shorter solution, then you can discard that element from the list; it is not optimal. After you are done, you have a new (hopefully shorter) list; increase len to 3, and continue.

BTW, in the face turn metric, is a local maxima "strict" (i.e., every position one move away is strictly closer to start than the original position), or "not strict" (some positions one move away may be at the same distance as the original position)?

I've proved that the three sequences given above are local maxima.

It took 13 hours and 51 minutes on a 2.8GHz P4.

I used the technique above. The list started out with 36 entries. Three were eliminated at length 2, one at length 3, one at length 4, 9 at length 22, and the remaining 22 at length 23. So the longest solutions I had to find for this proof were of length 22, which are far easier to find than solutions at length 23. (It took my old optimal solver less than 12 minutes on average to find each solution of length 22; I'm sure Reid's or Kociemba's would have been much faster than that.)

Cube Lovers adopted the convention that both kinds of local maxima were called local maxima. A "strict" local maximum was then called a strong local maximum, and a "not strict" local maximum was then called a weak local maximum. You could call a local maximum just a "local maximum" if you didn't know for sure if it was strong or weak. Your terminlogy of strict and "not strict" is probably just as good or better than strong and weak.