1,000,000 cubes optimally solved

Using my relatively new Core i7 920 CPU machine (Linux 64-bit with 12GB of RAM) I solved 1,000,000 random cubes optimally at a rate of about 20 cubes per minute. The computation took about four weeks (I also used a few other slower boxes to do some of them). I got the following results:

12f*: 1
13f*: 14
14f*: 172
15f*: 2063
16f*: 26448
17f*: 267027
18f*: 670407
19f*: 33868

No 20f* cube was encountered, which is as expected. No symmetrical or anti-symmetrical positions were encountered.

These results are very close to Kociemba's results for 100,000 cubes; much closer to his overall predictions than those extrapolated from the 250 cosets I ran completely. This seems to indicate that running random cubes may be a more effective way to get a distribution estimate than by running many fewer random cosets (but which contain collectively many more individual positions).

This is a brand new solver I have written to replace my old one (from about a decade ago when machines were much smaller). It can use a number of different pruning tables, including a relatively large one of about 7.5GB; that's the primary distinction between this solver and Kociemba's that allows it to get the speed it does.

It's interesting to note that optimal solvers for these types of puzzles improve in speed according to roughly the square of Moore's law, if you make the assumption that the computational power of a CPU tracks Moore's law and the memory density also tracks Moore's law. This explains why I can now optimally solve nearly 30,000 arbitrary cubes a day on a single machine, where in 1997 when Korf introduced his pattern databases it took approximately a day to optimally solve a single cube. That's about 15 doublings in speed, which would be expected to take 22 1/2 years, but it only took 13. Essentially, my pruning tables are *much* larger, and thus deeper, than Korf's.

I'm continuing to develop the optimal solver, and will probably release it sometime this year.

Looking at the distribution of moves in the optimal sequences, we see:

 906229 L2
 908341 B2
 915963 D2
 938310 R2
 961584 F2
 968523 L+
 970285 L-
 972663 B+
 975297 B-
 979308 D+
 980406 D-
 997651 R+
1003344 R-
1009747 U2
1019854 F+
1030443 F-
1070441 U+
1098603 U-

The square moves are somewhat underrepresented. The U and F moves are slightly overrepresented because in general my search tried the moves in the order U3, U2, U1, F3, F2, F1, R3, R2, R1, D3, D2, D1, B3, B2, B1, L3, L2, L1. But perhaps I should consider using U1, U3, U2, ... or even postpone square moves until last in general to try to get a bit more speed.

I am using several tricks I have not heard of before in this new solver. I will enumerate them in a separate posting.