cube files
Indexed Cube Lovers Archive
Twenty-Five Random Cosets in the Quarter Turn Metric
Submitted by rokicki on Sun, 03/01/2009 - 13:42.
As the next step in my exploration of the quarter turn metric, after
finishing a proof of an upper bound of 30, I decided to run 25 cosets
all the way (until I have optimal solutions for all positions).
Unlike my runs in the half turn metric in November of 2008, I went
ahead and made the search phase run in parallel. In addition, I
acquired a newer, faster machine (a Dell Studio XPS with an Intel i7
920 processor).
I decided to run the same 25 cosets I ran for the half turn metric. The results are summarized in the table below.
Sequence 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 B3L1F1L2D1B2R1B1L3U2 0 0 20 435 4622 43936 400458 3554875 30726915 256996075 1848319413 7171928278 7868910283 2321690801 5852689 L3F2R1D3U1B3U3F2U3 4 18 128 871 6276 48805 400949 3363941 28420393 235773014 1717097803 6966696841 8001159475 2548330910 7129372 L3F1L2U1B2D2F1D1L2U2 0 2 28 326 3218 29873 269750 2443411 21998773 193687590 1515611814 6774881810 8208751853 2783171388 7578964 F3D2R1D1U3L1B1L2R1U1 0 0 2 108 1306 13748 143140 1446301 14285392 137005569 1184534971 6226351280 8543651779 3389397394 11597810 L3F3D1R2F1U1B3D1U1 0 2 64 552 4407 37681 324904 2824246 24582278 210125809 1586499896 6807864157 8134902424 2733361953 7900427 R3D3B3R1D3L3B2U3R1 0 2 14 120 1353 15271 158651 1592557 15542316 147004809 1249519538 6337847456 8476767605 3267754185 12224923 L3D1L2B1U2R1F2L2R2 0 0 10 165 1849 19252 190649 1837650 17403365 159611091 1305114237 6349921969 8417750315 3242824273 13753975 R3F2R1B1L1U1B2D2R2F3 0 0 16 136 1344 15030 160964 1619156 15853901 149906827 1274339923 6416176539 8453617560 3186496712 10240692 L3U2B1U2L3U1F2U3F1 0 0 12 278 2542 24252 226234 2072000 18834256 168604656 1360216959 6494240351 8363562099 3089272863 11372298 R3U3B3F1L3B2D1U1R1 0 2 8 64 973 11782 123788 1269606 12757460 124710914 1113344522 6107875712 8613765558 3520346320 14222091 F3L1D1U2B3R2D1B1F1U3 0 0 2 48 743 9095 103868 1139279 11966855 120510431 1097528968 6098680603 8631302454 3533874944 13311510 R3U1L3D3B1U1F2R3F2U3 0 0 12 144 1571 16751 171103 1684988 16305044 153021226 1288352531 6403187153 8438268848 3196304138 11115291 F3U3L1R3D3R2D2R1B1 0 2 26 256 2818 27191 258215 2387216 21788701 193356616 1516049613 6761646313 8208096006 2796796806 8019021 L3D2U3R2F3R2B2D1R3F1 0 2 8 94 1357 15388 161328 1636452 16082389 152169746 1284070995 6386845640 8442128854 3213547078 11769469 R3D1F1D2U3L3U2R3B3R1 0 0 0 28 452 5941 74567 858139 9375111 97990667 936309256 5732489523 8790779495 3922870102 17675519 R3U3L3U1F1L1R1D3U2F3 0 2 32 651 6444 55272 452489 3663211 30130097 243818320 1741988126 6979191340 7973086302 2527485604 8550910 R3U3F1D3R3U2L3F1R3U1 0 0 4 76 1154 12122 130610 1328294 13274203 128193269 1129470997 6106442943 8595872682 3518237696 15464750 B3L1R2B1U3B3U2L3U3 0 20 140 956 7571 57105 449289 3610890 29809049 241674619 1741445345 7004878190 7976199085 2503992620 6303921 B3F3D3L3U2F1L3R3U3L2 0 0 6 154 1567 16877 173601 1707376 16407077 153065961 1280208756 6366984112 8444147246 3232439920 13276147 B3D1F1U1F2L3B1U3R3U3 0 0 2 34 606 7637 87012 953861 10176967 104433060 979968969 5823677299 8745900801 3825142509 18080043 F3L2F3D1F3L1U1F3R2 0 0 32 259 2264 21355 198612 1861131 17405107 159635838 1313803665 6418470686 8410951706 3174225131 11853014 F3L3U1F2L2R2D2F1R2 0 0 4 68 981 11807 129580 1362657 13826184 135112316 1189012659 6288524236 8541002353 3329203316 10242639 R3D3R2U3L3D3F1U2F1U2 0 4 38 274 2494 23995 226344 2125096 19534219 175011016 1394117568 6515323270 8328354319 3061730745 11979418 L3D2R3B1L1R2U3L3F1 0 4 54 585 5290 44888 375532 3189104 27138733 226901366 1665321628 6893841573 8054156025 2630236880 7217138 R3B1R2U1F2L3U3L3U1 0 0 28 381 3291 29680 266393 2380842 21349305 187541721 1461764900 6603028442 8260861990 2961233334 9968493Each coset took about five hours to run to a phase one distance of 21 on my new i7 920 box, and left between 104 and 863 positions (an average of 373) unresolved (that could have been distance 24 or distance 22). I solved each of these using my QTM optimal solver; this took an average of about 14 minutes per position single-threaded. (Note that these positions were substantially harder than an "average" position because we knew their distance was at least 22.) Running eight positions at a time on my box meant that finishing each coset took an average of an additional eleven hours, for a total of about sixteen hours per coset.
The big surprise is that *no* distance 24 or greater positions were found. In the corresponding search in the half turn metric, we found eight new positions at a distance of 20 (equal to the furthest-known distance); in this experiment, of the same 487,710,720,000 positions but in a different metric, we did not find even a single position whose distance was within two of the furthest-known distance. Thus, it appears that distance-24 positions in the QTM are probably significantly more rare that distance-20 positions in the HTM.
Also interesting is the fact that in the half-turn metric, the trivial coset had a bound of 18, one less than the bound of the median coset. In the quarter-turn metric, the trivial coset has a bound of 24, one greater than the bound of the median coset.
If we consider the trivial coset, it has a lower bound of 24, and the greatest distance of any other coset from that coset is 13, so we can directly infer a bound on the overall cube group of 37. Yet for most of the cosets above, including the first one, for example, the greatest distance of any other coset to that coset is 11, so we can directly infer a bound on the overall cube group of 34. Further, we can combine the results from the two cosets F3U3L1R3D3R2D2R1B1 and L3F2R1D3U1B3U3F2U3 (combined with a small optimization about which we will not go into detail here) to tighten this bound to 33.
Yet, this is not a good technique to tighten the overall bound, because proving each of these cosets to be 23 takes a long time, primarily because of the hundreds of individual positions that need to be independently optimally solved. It is faster to run more cosets more quickly at a shallower depth and combine those results. At a phase one depth of 19, each coset takes about five minutes and a bound of 25 is found (with some help from a two-phase solver to reduce a few remaining positions from 26 to 24).
In comparing the overall distribution with that of a set of random positions from my position-at-a-time optimal solver, we see these numbers:
25 cosets Rokicki
9 4
10 60
11 690
12 7063
13 66493
14 614734
15 5658030
16 51912279 1
17 474974090 0.001 23 0.001
18 4255862526 0.009 284 0.008
19 34174013052 0.070 2339 0.069
20 162036995716 0.332 11305 0.333
21 208923947117 0.428 14551 0.428
22 77509967622 0.159 5468 0.161
23 276700524 0.001 19 0.001
------------ -----
487710721000 33990
This is very good agreement.
