Optimal solver for QTM

Not at all! -- it found a non-trivial identity for you; i.e., one that doesn't depend simply on the commutativity of turns on the same axis.
Can be useful.

It failed to find the minimum length solution, which is no turns.

The no turn solution is quite easy to find even without a PC, so whoever takes the trouble to feed the identity cube into the optimal solver should be rewarded with an interesting solution ;-)

I ran a few more this weekend, and this is the distribution I have so far:

      7 18
     52 19
    227 20
    278 21
    107 22

The quarter-turn distribution appears to be fairly long-tailed, if positions 23+ are all <1% (extrapolating from this) and yet we have a known position at 26.

(This distribution is not from independent, random positions; rather, it is from optimal solutions from a random walk, so the samples are not independent. Yet it's probably still a pretty good sample of the distribution.)

This is a slightly larger sample size than my original sample, again with random positions being created with Cube Explorer.  It's not as large a sample size as Tom Rokiki's.

Both this sample and Tom's sample suggest what I was calling a "tri-modal" distribution overall rather than a bimodal one, with the overall mode at 21q, with 21q also serving as the one and only mode for the odd positions, and with the even positions being more or less bimodal at 20q and 22q.  Well, I suppose one could quibble with calling the even positions bimodal because the number of positions at 20q and at 22q aren't really the same.  But comparing the number of even positions at 20q and 22q (which are somewhat close) is a very different thing than comparing (for example) the number of odd positions at 19q and 21q (which are not even remotely close).

 9  19q*
29  20q*
44  21q*
18  22q*

I'm not sure what algorithm Cube Explorer uses for random positions.  Tom used a random walk.  The speed cubists seem to have spent a lot of time studying the creation of random positions for competitions, but I'm not sure what conclusions they have come to.  Because they are working with physical cubes, they are inevitably led to random walk solutions.

I agree with Tom that the quarter turn distribution seems very long tailed.  In general, increasing the sample size by an order of magnitude should cause a new, shorter distance to appear in the distribution.  For example, Tom's larger sample size has positions of length 18q and my smaller sample size does not.  But it is not at all clear how large the sample size would have to be in order for positions of length 23q to appear on a regular basis.  The sample size might have to be rather large indeed in order for this to happen.

I changed my program to do 1000 random moves for each position solved (so it's not *absolutely* random, but it's probably very very close), and let it run for a while, and this is what it looks like so far:

      1 17
     13 18
     66 19
    399 20
    489 21
    184 22
      1 23

So not only did I get (a) 23, but I also got (a) 17! Wow. I'll probably let it run a bit longer. I wouldn't be at all surprised if there are additional 26's. Using a coset solver would probably be the best way to find them. I'm very interested in Herbert's results; I hope he lets them continue.

If you did exactly 1000 random moves for each position, wouldn't you end up with all even positions?  Did you maybe randomize 1000 moves vs. 1001 random moves for each position (or something like that) in order to get both even and odd positions?

Actually, I did 1000 random moves in the FTM (even though the solver works in the QTM). This means for every move there is a 1/3 probability of getting an even move and a 2/3 probability of getting an odd move. Since I'm here, these are the latest numbers:

      2 17
     20 18
    102 19
    621 20
    772 21
    294 22
      1 23

No particular reason not to let this one keep churning for a while.

It just passed 6400 cubes, and the distribution looks like this:

      6 17
     42 18
    435 19
   2207 20
   2744 21
    967 22
      1 23

Yes, I have some more results now.

depth 12          11,152
depth 14         762,312
depth 16      23,104,558
depth 18     665,649,794
depth 20   7,677,782,428
depth 22   1,386,903,800
depth 24 or more     356 

What is quite interesting compared to the even depths of the random distribution is that the relative number of depth 22 elements in this coset which contains the known 26q* is smaller than in the random distribution. It took about 90 hours to complete depth 22. I let the program continue with depth 24 (which was not very wise after all because now it is hard to identify the bits set for elements <=22q* any more and I cannot make a "linear scan" for the 24q* elements).
Within 35 additional hours I got the following 24q* solutions up to symmetry and inversion. I post then here because there are not too many 24q* known yet - as far as I know at least:

U U R U U R D' B U' D' B U F' U B D' B R' U' L' U' B' D R  ( 24q*) 
U U R U U R L F' U' D' R' F B' L' U D' F' D B D B D' L F'  ( 24q*) 
U U R U U F R' L' U R' L U R D D R' L F D L' B' U' D' L  ( 24q*) 
U U R U U F B' R R U R' L' F B U U F U D' F B' D F' B'  ( 24q*) 
U U R U U F B' R R U R' L' F B U U B U D' F' B D F' B'  ( 24q*) 
U U R U U L D B L' B R' D F' L D' R' B' U F B' U' R' B D'  ( 24q*) 
U U R U U B U' L U F F U U L' D' F L B B U' F' L' B R  ( 24q*) 
U U R U R U' L' U' L' F R' U' B D' L F' L D' R L' D F' U F  ( 24q*) 
U U R U R R L' U F' B R F' B' U U D F' B U' F' D' F D' B  ( 24q*) 
U U R U R D' R D' B' U' B R' D F' R B' U L' U D' F' D D R'  ( 24q*) 
U U R U R L F' L D B L D F' D' F' L D' R' D' L F L' D L'  ( 24q*) 
U U R U R L' U' F U' R L D' B D' R' L D R' F B' R L D D  ( 24q*) 
U U R U R' L' B' D L F' R D' L' B' L D' F' R U B R' B' U F'  ( 24q*) 
U U R U F U B B L' D B R' B' R' U D R' D' B' L D F' B R  ( 24q*) 
U U R U F U B' U R' D' B' R D L' B' U L U' R L U B' L B'  ( 24q*) 
U U R U F U' F' B' U F R' D B' U' F D' F R' F' D F L F' L  ( 24q*) 
U U R U F R R D' B U L' F U' R L U R' U' R' D L L B L  ( 24q*) 
U U R U F D' B' U' B R' D L' U' D L' U B U B L' F' B' L' F'  ( 24q*) 
U U R U F L' D F' B U D' B B L U' D L' D F F D R U B'  ( 24q*) 
U U R U F B D L U' L U' F D' B' U L F' B' L U L' D' F R'  ( 24q*) 
U U R U F' L D' L' F' U D F' D L F' U F' U B L L U L F  ( 24q*) 
U U R U F' B R U' D' F B' D D F D' R' L L B D R D L' B  ( 24q*) 
U U R U F' B D' R U' B U' D' B R F U' F L D L U' F L B'  ( 24q*) 
U U R U D R' F B R' U' D' R' F B R' U D L' F B U D F B  ( 24q*) 
U U R U D R' F' U' D R' L U D B' R R U' F' R' B L' D' F U  ( 24q*) 
U U R U D' F R D R' U R U' F' D' R U' R B D' F' R B D' L'  ( 24q*) 
U U R U D' B R U' B' L U R U' B L' F U' D F' D B D' F R  ( 24q*) 
U U R U D' B D B U D F' D B' L F R B U D L U' F R' F'  ( 24q*) 
U U R U L U R' F L D L F' R' U' B' L B R' L D B' L F' D'  ( 24q*) 
U U R U L' U R F' B R' L' F D' F B R L D' B B L U R' F'  ( 24q*) 
U U R U L' U F D L L F R' F R L F' B D L' F' U F' U' L'  ( 24q*) 
U U R U L' U D' R' B' D R' B' L' F D B D' R' U' F R' F D' R'  ( 24q*) 
U U R U L' U B' L' D' B D F U D B U F U' R' F' D R' D L  ( 24q*) 
U U R U L' U' F B' L' D B U B' R' D' F' D R U' B' U L L D  ( 24q*) 
U U R U L' F' R U' B D' F U' B D' R B U' L B U' B' U R' U'  ( 24q*) 
U U R U B' R D F R' U' R L F B R L D' L B' D' L' F U' L'  ( 24q*) 
U U R U' R L U' B R' F' B' R' L' U' F' U B D' L' F' U F B R  ( 24q*) 
U U R U' R' U R U' R' L' B' D B' R F' U L' F R F' L' D L B'  ( 24q*) 
U U R U' F D D R' D' L' B U' R B' R B U U F' B B D F D'  ( 24q*) 
U U R U' F D' L U' B U' F' B R B' R F B L' D R L F D B'  ( 24q*) 
U U R U' F' D D R L U L B' L U D' B D R' B' R' F' D B R  ( 24q*) 
U U R U' D' R' L' D B D' R' D' L' D' L D' F R D' R' U B U R'  ( 24q*) 
U U R U' D' L' D' F U F L' D R D' L' D' B L F' L U D B' R'  ( 24q*) 
U U R U' L F' R' D B' L F' L D F' L D R' F' L L D' R B B  ( 24q*) 
U U R U' L' U B L D' R B U D L F B' U L B' D L' U' R' B  ( 24q*) 
U U R R U B' U L B' R' U D' B R B R D R R U R F' B' R'  ( 24q*) 
U U R R F U L' D' B B R' B' U' R L B' D B U R D' L' F' L'  ( 24q*) 
U U R R D R' F' U R' B D D L' U L D' F' U' F F U' R' L D  ( 24q*) 
U U R F U' R F' U D R' D F U R F B' D F R U D L B' R  ( 24q*) 
U U R F D' R B' L L B B R' U U R' U' L' D' L D' B D' R L'  ( 24q*) 
U U R F L U L U' F B D' F' R' L F' U' F B D' L D L F R  ( 24q*) 
U U R F L D L F R L' D' F R D L' F' B U R D F D L D'  ( 24q*) 
U U R F' U F B' L' F R U' D' R' B' D' R B L' U' F' U R F' R  ( 24q*) 
U U R F' U' D' B U' R D B' U B' U' R' D' L L F D' R L D B  ( 24q*) 

The now still remaining 33 cubes reduce to 9 cubes up to symmetry and inversion, including the 26q* case. The remaining 8 cubes I try to solve with my optimal solver, which takes quite some time.
I solved 3 positions with 24q* up to now, so 5 cubes are remaining.
I will change my coset explorer in a way that it automatically appends UD, UD', U'D, U'D' and all half-turn moves when depth 22 is finished to reduce the number of positions which have to be examined for >=24q*.

I now have finished the computation for the 26q* coset. The eigth remainig positions also are solvable in 24 moves. Just for completeness:

U U R F' D F' U B' D' R' L' U L U' B' L B' D F' L L D D L' ( 24q*) 
R U U R' L L U U D' L' F U' B L U' B' U B' R U' F U D' F  ( 24q*) 
U R U U F B' R R U R' L' F B U U B U D' F' B D F' B' D  ( 24q*) 
R' U U F B L' D L' U R' L' U' B D' L B' R D' B' U' D' F D R  ( 24q*) 
U R U F D' F B' R F D F F B' U' B' L U' R' F L' D' R' D' L'  ( 24q*) 
U R R U R' L F' D D F B U D' L F B' D B B U F F B B  ( 24q*) 
U U F R' F D' R' U' D R L U' R U B' U' D F' D' B' R' B R' D'  ( 24q*) 
U R U R D' L L D' F' D R U' D B L B' U' R' F' U' B' L' U R'  ( 24q*)

So we have

depth 24             355
depth 26               1 

Up to symmetry there are 62 24q* cubes, including antisymmetry does not reduce this number because all 62 cubes are antisymmetric(!). Only three cubes of these 62 have no symmetry:

U U R U' F' D D R L U L B' L U D' B D R' B' R' F' D B R  ( 24q*)   //C1{C2(a)}
U U R U U L D B L' B R' D F' L D' R' B' U F B' U' R' B D'  ( 24q*)   //C1{Cs(a)}
U U R U L U R' F L D L F' R' U' B' L B R' L D B' L F' D'  ( 24q*)   //C1{Cs(b)}

So it seems to be really difficult to find another 26q*.

The random generator of Cube Explorer generates every possible cube with the same probability using the Rnd() function. Concerning the distribution it might be better to run a coset-explorer on some random cosets. I finished writing a coset-explorer for the <U,D,R2,F2,L2,B2> subgroup (only the even permutations of corners/edges) which has 9,754,214,400 elements two days ago and ran it for the coset which contains the known 26q* position.
I do not know if Tom already did this computation (maybe even for the twice as large coset without the even-permutation-restriction). It is still running in depth 22, the results so far:

depth 12          11,152
depth 14         762,312
depth 16      23,104,558
depth 18     665,649,794
depth 20   7,677,782,428

Of the remaining elements all but about 800 already are solved in 22 moves. I wonder how many elements are left if depth 22 has completed in a few days.

Have you compared this on random positions with my solver?
Maybe we should do a bake-off. :-)

Mine does require a bit more memory (646M) but it's pretty old.

http://tomas.rokicki.com/rubsolv163.c

-tom

Would be interesting to compare. But I cannot compile your source with gcc, seems to need some more includes maybe, because gcc does not understand memcpy, memset, strlen. Nor do I know your input format. Seems easier if *you* run both programs with a few random instances...

I thought I would compare with Mike Reid's optimal solver program (compiled for QTM). I compiled using Visual C++.NET (2003). I used a random scramble that turned out to be 21q*. Both programs reported the same 13 optimal solutions. Note, I did not compile Herbert's program, but used the Windows executable he provided. Computer: 2.4GHz P4, 533MHz FSB. I also compare stats for the search at depth 19. Herbert's program needed to generate less than 10% the number of nodes than Mike Reid's program.

Mike Reid's optimal solver program (compiled for QTM):
31h 0m
depth 19q completed  (  1,954,922,425 nodes,         266,692 tests)

Herbert Kociemba's QTM optimal solver program:
4h 52m
depth 19 completed,      148129725 nodes,         269352 tests

I think I have Tom's program successfully built and figured out how to run it. I'll try the same position with it.

I've now run Tom's program. I measured a time of 1h 57m for the same position I used for the other programs. However, the program reported it took only 4999 seconds (1h 23m 19s). Excellent work!

The reason my measured time was longer is that it included the time to generate the pruning table. I needed to regenerate the pruning table instead of reading it from a file, because the program was using "w" instead of "wb" for the fopen call to create the file. On UNIX, that may work fine, but it does not work on a Windows computer for creating a binary file. (Similarly, fopen for reading the file should use "rb".)

So Tom's program took 1h 23m while Herbert's took 4h 52m to search for all optimal solutions to the test case I used (about 3.5 times faster). Tom's program reported 7,664,266,323 evals, while Herbert's program reported 13,321,016,290 nodes and 26,051,386 tests for the depth 21 search.

Cool beans!

Some notes about my program:

1. It works for halfturn or quarter turn; modify the first macro definition (#define HALFTURN or #undef HALFTURN).

2. I really should write up some documentation, a makefile, and perhaps fix the -Wall output.

3. The -a option says give me all solutions; the -s option means analyze the position for symmetry before solving and then only print out representative solutions.

4. You can either give the "position" on the command line, or through stdin; if through stdin, you can give many positions.

5. The input syntax is a sequence of [UFRDBL][+-123']? *moves*. I do not read positions yet. [Although I do have a small program that takes a position and returns a "stupid" long sequence; I should integrate that.]

6. The program has some novel features; I should write them up some time. I solve based on a pruning table that's constructed from the group of cubies on one *face* (four corners and four edges), and I apply this up to six times.

Nice work! I'm really not surprised that Tom's solver is faster because he always pulls some clever idea out of his hat. It would be nice if we could get some more detailed description on the algorithm.