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.