# Three Million Positions in Four Metrics

Submitted by rokicki on Mon, 04/23/2018 - 10:52.

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.796For 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.3742In 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.