Twenty-Nine QTM Moves Suffice

With 25,000 QTM cosets proved to have a distance of 25 or less,
we have shown that there are no positions that require 30 or more
quarter turns to solve. All these sets were run on my personal
machines, mostly on a new single i7 920 box.

These sets cover more than 4e16 of the total 4e19 cube positions,
when inverses and symmetries are taken into account, and no new
distance-26 position was found. This indicates that distance-26
positions are extremely rare; I conjecture the known one is the
only distance-26 position.

In order to take the step to a proof of 28, I would need a couple
of CPU years, or improvements in my program or technique or both.
I will continue solving cosets and look for additional opportunities.

I believe a proof of 20 HTM and 26 QTM (or a counterexample!) will
probably happen within the next few years.

Comment viewing options

3 distance-26 positions

The distance-26 position can happen in three different orientation, so there are three positions. If they are the only ones as you seem to conjecture then God's diameter is 26... This is a far jump from your current 29 record:). I doubt however that the cube has that few antipodes... The reason I think this way is that the edges-only group has one antipode while the corners-only group has 6624 antipodes, since the cube group is somehow the product of these two subgroups, I doubt the antipodes will be reduced to 3... But you never know.

The known distance-26 position is the only one?

Hi rokicki,

First, congratulations on this new upper bound!

Second, If we assume that your conjecture is true regarding the distance-26 position, wouldn't that make it an antipode?

We do know that there is no unique antipode for the cube since the only other three positions with the same symmetries as the identity are at lower distances... So in my opinion the known distance-26 position is not the only one.

Sorry If I did not understand what you mean.

Congrats!

Congratulations, Tom, on the new upper bound for QTM.

Since determining the diameter of the cube group (FTM or QTM) appears to require an enormous amount of CPU time, it seems to me to get to the answer in the shortest possible time, we need to have a SETI-style approach. As I understand it, your program needs over 4GB of RAM (or at least over 3.5 GB), which would seem to severely limit the number of computers out on the internet that would be able to run your program.

So I was thinking, couldn't your program be modified so that instead of being based upon the subgroup <U,D,L2,R2,F2,B2>, couldn't it instead be based upon <U,D,L2,R2> or even <U,D,L2>? Wouldn't that reduce the memory requirements by a factor of 6 or 12 so that the program could run with about 800MB or 400MB, respectively?

It appears to me that since <U,D,L2,R2> and <U,D,L2> are subgroups of <U,D,L2,R2,F2,B2>, that the cosets of these subgroups would simply be separate subsets of cosets of <U,D,L2,R2,F2,B2>. So powerful computers could still process <U,D,L2,R2,F2,B2> cosets directly, while less powerful computers could split the work of processing such cosets.

I realize the symmetry of these other subgroups is less than that of <U,D,L2,R2,F2,B2>, but I think the potential to have many more CPUs working on the problem would more than offset the inefficiencies of using the smaller subgroups.

I just tried the subgroup (U,

I just tried the subgroup (U,U2,U',D,D2,D',B2,L2) and only 32,253 positions remained---but this is still too many. (Of course this group has less symmetry than the ones you mentioned.)

I could simply increase the phase 1 distance (at a rather significant increase in CPU time---perhaps 4x) and that would probably resolve all of these issues. Yes, phase one distance of 17 appears to work, at least for (U,U2,U',D,D2,D',L2,R2)---but at this point, the additional CPU time makes it less attractive.

Thanks, Bruce! It may well

Thanks, Bruce!

It may well be that my program can work with smaller subgroups, but the changes may be nontrivial.

If the full set of 18 generators is S, and the smaller set of generators defining the subgroups is A, then my program works by finding all sequences of the form b c where b is a sequence of length 16 or fewer from S, and c is a sequence of 4 or fewer from A, and b lies in the requisite coset.

When A is (U,U2,U',D,D2,D',F2,R2,B2,L2), this almost always yields solutions of length 20 or less for all 19B positions. It is rare that it does not, and when it does not, the remaining positions can be solved independently using Kociemba's two-phase algorithm.

I have modified my program to try the smaller group of the two you give (U,U2,U',D,D2,D',L2,R2); in this case, there were 331,094 positions left without solutions of length 20 or fewer over the six cosets required to match the original version of the program. With the larger group of the two, there were 198,494,130 positions left without solutions of length 20 or fewer over the twelve cosets required.

I may be able to work around this with some more effort, such as only solving the even or odd halves of the large coset at any given time. This was suggested to me years ago by Silviu Radu, and would lower the memory requirements to less than 2GB, easily attainable on almost any reasonably modern machine. Testing this indicates that 2,611,616 would remain, so maybe this is not directly viable.

I would like to mention that Herbert Kociemba has made some very significant suggestions towards speeding up my program, so more efficiency may be just around the corner.

So if I just make the simple modifications to work with larger subgroups and thus smaller cosets, I lose much of the advantage of the Kociemba two-phase approach, which typically finds good solutions very easily; too many remaining positions would require separate handling. But there may be a clever trick I am overlooking to help with this.

In reality, the current version of my program requires only about 3.4GB so it will fit in a 4GB machine if the operating system is willing to give a user process that much memory. 64-bit operating systems are becoming quite common, so I suspect targeting 64-bit machines with 6GB of more of RAM (for Windows) or 4GB or more (for Linux) may be the simplest solution.

Maybe another subgroup

I am thinking about a coset solver that only requires about 500 MB of RAM, of which about 2/3 for a complete ternary prune table and 1/3 for a binary checklist for coset positions. This is because 500MB is not too much for a background process, and therefore the whole world can help solving the cube. A virus that spreads the coset solver would be optimal. ;-)

The subgroup H I am thinking of contains my favorite subgroup (F2,B2,FB',R2,L2,RL',U2,D2,UD'). The cosets are coded as follows:
- Coordinate one: the three color corner cube (opposite colors are equal) modulo color permutation. There are 153090 three color corner cube positions, so 153090/6 = 25515 positions. You enumerate the positions by fixing a corner that remains the same after each turn, by applying the right color permutation afterwards.
- Coordinate two: an edge coordinate with 2956800 positions, stored as a symrep coordinate with 48 symmetries (Cube explorer has a symrep coordinate with about the same number 63k of representants). Again, this coordinate is based on the three color cube, but the association of edge positions is now somewhat more fancy than just color permutation:
(a) Two positions are the same if you get the second from the first by flipping all eight edges originating from two of the three slices,
(b) Two positions are the same if your get the second from the first by first exchanging two of the three colors and then applying superflip.
Here is what you must do to canonize a three color cube edge position. Say the three color cube has colors red (FB), yellow (UD) and blue (RL). Now look at the UF edge. This edge has two of the three colors red, yellow and blue in some order. Now make this edge red at front and yellow on top by applying (a) and/or (b). The UF edge is now "solved". Next, look at the edges of the UD-slice. Order those four edges any way you like, but fix the ordering. Since the UF-edge is red/yellow, not all edges of the UD-slice can be red/yellow. Now pick the first edge of the UD-slice that is not red/yellow (w.r.t. the ordering). Now make this edge solved as well by applying (a) and (b).

The subgroup is not generated by face turns, but I do not know whether that will frustrate optimizations. At least, I do not see suggestions for such subgroups here. Just an idea. One can add superflip to the subgroup to roughly interchange the sizes of the binary check table and the ternary prune table.

My congratualtion once more i

My congratualtion once more in this forum, Tom. I agree with Tom, we should not bother to make the coset solver runnable on 4GB machines. Most people run Windows and without modifications in the boot-process only 2 GB of RAM are allowed for all user processes together. This is definitely not enough to run an effective solver.

In a few years all new machines are 64-bit machine with 12 GB of RAM and here the coset solvers run very effective. In the last months, Tom and I had many discussions how to improve our coset solvers (which are programmed totally independent) on our i7-machines. To solve a whole random coset with about 2*10^10 cubes within 20 moves typically takes for example about 1 minute in the latest version of my solver in HTM - which I think is incredible fast. This speed largely depends on the special structure of the (U,U2,U',D,D2,D',F2,R2,B2,L2) subgroup and we should wait until more machines have the hardware to use such solvers.