Home »

4x4x4 upper bounds: 57 OBTM confirmed; 56 SST and 53 BT calculated.

Submitted by rokicki on Tue, 03/03/2015 - 02:14.
I have replicated Shaung Chen's upper bound result of 57 moves in the OBTM (outer block turn metric), reproducing his numbers and calculating depth counts without symmetry reduction. His results are here: http://cubezzz.dyndns.org/drupal/?q=node/view/525

I have also calculated, with the same code, results in two other metrics: SST (single slice turn) and BT (block turn). The final results lower the upper bounds in these metrics to 56 and 53 (respectively).

The sequence of subsets chosen is identical to that used by Chen. The maximum distance for each stage, the sum, and the current lower bound is shown here: 

          OBT    SST     BT
         ------ ------ ------
Stage 1    8      8      7
Stage 2   14 -1  13     12
Stage 3   16     15     15 -1
3x3       20     20     20
-------  ------ ------ ------
Total     57     56     53
Low Bound 35     32     29
The explanation for the "-1" in stage 2 in the OBT is explained at the above-referenced page. The "-1" in stage 3 of the BT is new and is explained here. Every position that is at distance 16 in the STM in stage 3 is a strict maximum, in the sense that any move allowed in stage 3 will bring you to a distance-15 position (in that stage). Since the final move of a stage 2 solution must be a quarter-move on the left-right axis (since these are the only moves allowed in stage 2 but not in stage 3), for any stage 2 solution that ends in a position that is at distance 16 in stage 3, we can choose the *other* final quarter turn (implicitly combining the original quarter turn with a matching half-turn) to have a stage 2 solution of the same length that ends in a position that is at distance 15 in stage 3.

Specific depth counts for each stage and each metric are given below. This reflect the full space with no reduction for symmetry; the actual calculation was performed with symmetry reduction, and the results adjusted. The symmetry reduction used was identical to that described by Chen, and his numbers were matched exactly. 

  OBT  Stage 1         Stage 2            Stage 3
-----  -------  --------------  -----------------
    0        3               6                  1
    1        6              12                  3
    2      108              48                 34
    3    1,434             381                356
    4   15,210           3,643              3,568
    5  126,306          45,030             34,223
    6  420,312         606,937            331,445
    7  171,204       8,154,706          3,279,289
    8      888     102,867,620         32,869,934
    9            1,114,713,818        322,793,264
   10            8,194,798,024      3,071,165,269
   11           21,637,154,427     28,175,871,844
   12            7,652,855,512    230,035,097,211
   13               49,121,344  1,381,997,542,963
   14                       92  3,877,591,153,596
   15                           1,518,183,963,004
   16                               1,909,413,996
-----  -------  --------------  -----------------
Total  735,471  38,760,321,600  7,041,323,520,000
  Avg    6.016          10.922             13.941

  SST  Stage 1         Stage 2            Stage 3
-----  -------  --------------  -----------------
    0        3               6                  1
    1        6              12                  3
    2      144              78                 40
    3    2,070             736                419
    4   21,984           8,163              4,665
    5  143,040         108,504             52,862
    6  408,672       1,642,541            595,554
    7  159,120      25,051,200          6,828,900
    8      432     354,505,613         78,698,572
    9            3,855,130,124        890,241,566
   10           18,190,204,075      9,649,560,534
   11           15,214,615,212     97,220,792,244
   12            1,119,011,837    796,714,246,234
   13                   43,499  3,582,837,239,094
   14                           2,544,863,842,658
   15                               9,061,416,654
-----  -------  --------------  -----------------
Total  735,471  38,760,321,600  7,041,323,520,000
  Avg    5.954          10.330             13.219

   BT  Stage 1         Stage 2            Stage 3
-----  -------  --------------  -----------------
    0        3               6                  1
    1        6              24                  3
    2      210             126                 49
    3    3,576           1,441                600
    4   49,326          19,227              7,814
    5  334,302         334,248            102,809
    6  340,776       6,154,548          1,348,606
    7    7,272     112,313,065         17,868,420
    8            1,741,855,110        234,452,146
    9           14,780,736,610      2,974,523,970
   10           21,220,484,824     35,959,010,450
   11              898,419,145    380,135,222,472
   12                    3,226  2,571,726,262,872
   13                           3,958,934,429,976
   14                              91,340,289,756
   15                                          56
-----  -------  --------------  -----------------
Total  735,471  38,760,321,600  7,041,323,520,000
  Avg    5.405           9.543             12.523
Thanks to Shaung Chen for discussions on this work.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

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

4x4x4 new upper bound: 55 OBTM

Submitted by CS on Sat, 03/07/2015 - 01:34.
In the previous proof, the edge-pairing procedure consists 2 phases: mapping edges into high/low edges, and then place high/low edges in high/low positions. For a specific edge pairing state, there are 2048 different ways of edge mapping. In other word, the number of moves required by stage 2 can be decreased if we skip edge-mapping procedure. However, the number of different edge pairing states is 23!! (23*21*...*3*1, more than 300 billion), which cannot be processed with centers in stage 2.

Therefore, I tried to redefine stage 1 and stage 2 as follows.

Enhanced stage 1 + (edge mapping + stage 2)

Enhanced stage 1: In the previous stage 1, we only care about R/L centers, while in the enhanced stage 1, we solve centers of stage 2 simultaneously. Thus, U/D centers are placed in U/D faces, F/B centers are placed to F/B faces and R/L centers are placed to R/L faces and the state of R/L centers is in one of 6/35 solvable states in stage 3. Furthermore, the parity of all edges is also solved in the enhanced stage 1.

Therefore, after enhanced stage 1, stage 2 is almost finished but the unpaired edges, which is about 23!! (or about 19 billion with symmetry reduction) states. For each state, we try 2048 different ways to mapping edges, and for each way, the number of moves required can be directly derived from the calculation of stage 2 (e.g. for a given edge mapping, as the centers have been solved, there're only 6 possible states in stage 2. We can use the maximum value of these states.)

After calculation, the enhanced stage 1 can be solved in 12 moves and edge mapping + stage 2 can be solved in 7 moves. Therefore, the upper bound is decreased to 12 + 7 + 16 + 20 = 55 moves.

Appendix: depth distribution of enhanced stage 1: 

depth	number of states
  0                 18
  1                 69
  2              1,065
  3             14,568
  4            189,681
  5          2,537,226
  6         33,898,614
  7        447,656,853
  8      5,687,780,520
  9     59,648,805,336
 10    224,177,549,964
 11     41,293,642,932
 12            835,104
total  331,292,911,950
» login or register to post comments

4x4x4 new upper bound: 53 SSTM

Submitted by CS on Mon, 03/09/2015 - 10:43.
I've done the same work in SSTM. The results show that the upper bound can be decreased to 53 in SSTM. Wherein enhanced stage 1 <= 11 moves, edge mapping + enhanced stage 2 <= 7 moves. Therefore, the upper bound will be 11 + 7 + 15 + 20 = 53 moves.

Appendix: depth distribution of enhanced stage 1 in SSTM: 

depth	number of states
  0                 18
  1                 69
  2              1,389
  3             25,518
  4            453,927
  5          7,727,601
  6        126,786,132
  7      1,950,578,616
  8     23,270,432,490
  9    144,462,585,438
 10    158,996,852,112
 11      2,477,468,640
total  331,292,911,950
» login or register to post comments

How do you do stage 2 without

Submitted by charlie on Sat, 03/07/2015 - 16:32.
How do you do stage 2 without breaking up the work you did on the centers in enhanced stage 1? Can you provide an example solution showing your enhanced stage 1 and stage 2 to help illustrate?
» login or register to post comments

I don't do stage 2 without br

Submitted by CS on Sat, 03/07/2015 - 22:04.
I don't do stage 2 without breaking up the centers of enhanced stage 1. The stage 2 is the same as previous. However, due to the solved centers and different edge mappings, we can prove that 8~14-move states won't occur.
» login or register to post comments