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

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.

## Comment viewing options

### 4x4x4 new upper bound: 55 OBTM

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
```

### 4x4x4 new upper bound: 53 SSTM

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```

### How do you do stage 2 without

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?

### I don't do stage 2 without br

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.