Three Million Positions in Four Metrics

I optimally solved three million positions in four distinct metrics. These positions are distinct from the three million positions I ran some years back. Random numbers were generated with the Mersenne Twister algorithm. The four metrics I ran were quarter-turn metric, half-turn metric, slice-turn metric, and axial-turn metric (equivalent to the robot-turn or simultaneous-turn metric on the 3x3 cube). The generators for each metric are strict super- or sub-sets of the generators for the other metrics. The quarter-turn metric has 12 generators, the half-turn metric has 18 generators, the slice-turn metric has 27 generators, and the axial-turn metric has 45 generators. The distance distributions for each metric were as follows:
    quarter    half   slice   axial
  9       -       -       -       1
 10       -       -       -      39
 11       -       -       5     992
 12       -       3      86   26515
 13       -      34    1369  582531
 14       5     477   22313 2362388
 15      34    6349  307728   27534
 16     323   79841 1943071       -
 17    2798  801642  725418       -
 18   25377 2011479      10       -
 19  206335  100175       -       -
 20  993235       -       -       -
 21 1289020       -       -       -
 22  481228       -       -       -
 23    1645       -       -       -
 av  20.663  17.706  16.123  13.796
For the last three metrics there is a single distance that is significantly more common than any of the other distances. This is also true for each parity of the quarter-turn metric (where exactly half the positions are an odd distance from solved). We know God's Number in the first two metrics (26 and 20, respectively). For STM and ATM, we expect God's Number to be the same as the known lower bounds of 18 and 16, respectively. For the quarter-turn metric, this large sample did not encounter any positions within two of God's Number. For the other three metrics we found positions within one of the known or expected God's Number. The positions we ran for all four metrics were identical, so we can calculate correlations between the metrics.
         q       h       s       a
 q       -  0.2222  0.1532  0.0636
 h  0.2222       -  0.3072  0.1193
 s  0.1532  0.3072       -  0.2177
 a  0.0636  0.1193  0.2177       -
These correlations seem surprisingly low, but this may reflect the significant different means the different metrics attain. These calculations were performed with my nxopt optimal solver that supports a variety of pruning table sizes and metrics, as well as some new techniques to speed solves. The following table shows the average number of pattern table probes, node evaluations, and core-seconds for each solve, using a 176GB pruning table.
    probes   evals coresec
 q 3209268 1227121  0.3162
 h 4428078 1817477  0.4477
 s 5267871 2269920  0.4874
 a 3959741 2096065  0.3742
In total, on a 16-core machine, these runs took a total of 3.5 real-time days plus 8.2 hours to generate the 4 huge pruning tables; that's an average of 39 optimal solves per second. I will have more to say about the optimal solver in a follow-up note. I plan to extend my implementation of Kociemba's two-phase solver, as well as mycoset solver to support the axial-turn metric. Thanks to Andrew Gould for inspiring me to do this work.

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

10M more

I've run another 10M positions in all four metrics, and will be posting a summary of the aggregates including confidence intervals for counts.

16ATM positions?

What 16ATM positions are known? I made an ATM solver last year with ksolve++ but it's not really optimized enough for 3x3x3 so I could only solve a few positions. I found a few 15ATM positions but nothing more than that.

16 ATM positions

I found six 16ATM while solving symmetric states (I solved all symmetric states that are distance 20FTM and all with a symmetry reduction factor of at least high symmetry), and made a comment over here:

I didn't realize that God's N

I didn't realize that God's Number for the quarter turn metric had been determined. It has long been suspected that God's number for the quarter turn metric was 26, but I must have missed the announcement. Could you provide a link to the announcement? Much thanks.

Here you go

Nearly everything (code, approach) was the same as for the half-turn metric result.


Just an idle thought...

Why restrict yourself to 196GB pruning table if this assists greatly in your calculations, e.g. 1TB or more? .It surely wouldn't matter up front if this took a while to set up as the program wouldn't be distributed over the web for other users to run. This could be kept on a fast external HDD.

My largest machine has only 2

My largest machine has only 256GB of RAM and the pruning table must be kept in memory, otherwise access time skyrockets.

Intel's XPoint memory may help if the technology matures to the hype, but it's not quite there yet (at least not at a price point I can afford).

But absolutely, if you have 1TB of RAM, and want to solve a whole lot of random positions optimally, spend the time to generate a huge pruning table. The table generation can take advantage of many cores so it's not that slow.