- Joined
- Dec 24, 2015

- Messages
- 1,459

- Likes
- 912

Thread starter
#1

(Has anyone else attempted such computations before? I didn't find anything.)

tl;dr: 143 OBTM 141 OBTM 135 OBTM (2017-10-31) 134 OBTM (2018-05-15) 130 OBTM (2018-05-20).

I finished writing a 5x5x5 solver about three weeks ago, and in the time since I've mostly been working on trying to get a "good" upper bound for the 5x5x5 God's number in OBTM. I'm not entirely satisfied with this analysis, because according to this older thread with move counts of human solves, reduction can and should take much fewer moves than the upper bound I got, but anyway.

We divide the solving process into seven main phases, the last of which is a 3x3x3 solve. Some of these phases will in turn be divided into subphases that are easier to analyse. The division of phases is largely based on Charles Tsai's documentation of his 4x4x4 solver.

(Side note: the code I use for generating these tables is mostly not shared with the solver, apart from trivial utility functions like calculating binomial coefficients and such, so I'm not fully certain the numbers are correct. Independent confirmation would be awesome. Also, the solver itself usually finds a reduction in around 70 to 75 moves with about a minute of CPU time, which is… very far from the bound presented here, to say the least.)

E: Obsolete; see post #7 by qq280833822.

Someone with more disk space to spare (and using a programming language where accessing hundred-gigabyte arrays isn't a PITA) could probably do a breadth-first search on the whole state space of C(24,8)^2 ~ 541 billion states, but that someone is unfortunately not me. This is split into two subphases, where the first subphase solves the T-centres and the second subphase solves the X-centres. As an optimisation, we can reduce the move count by one if we skip the last move of the first subphase before proceeding to the second subphase.

Spoiler: phase 1.1 depth distribution
Spoiler: phase 1.2 depth distribution

Upper bound: 7 + 11 = 18 12 moves.

Spoiler: phase 2 depth distribution

Upper bound: 13 moves.

Cumulative upper bound: 31 25 moves.

Note that no restriction is placed on the centres in this phase, unlike the corresponding phase in Tsai's solver. We allow either all the edges to be oriented, or all the edges to be flipped.

Spoiler: phase 3 depth distribution

Upper bound: 15 13 moves.

Cumulative upper bound: 46 44 38 moves.

(See post #5 in this thread for how the upper bound was reduced from 15 moves to 13 moves.)

Again, no restriction is placed on the centres here. This is divided into two subphases. In the first subphase, the pieces needed to form four tredges are placed in the L and R layers. (This takes no moves at all ~52% of the time, or ~78% of the time if we get to do a z rotation as well, but we're doing a worst-case analysis, not an average-case analysis.)

Spoiler: Further explanation for phase 4.1

In the second subphase, four tredges are formed out of the pieces chosen in the previous subphase, and these tredges are placed in the E slice positions (FL, BL, BR, FR). The moves used here are almost the same as in phase 5, but off by a z rotation.

Spoiler: phase 4.1 depth distribution
Spoiler: phase 4.2 depth distribution

Upper bound: 6 + 14 = 20 moves.

Cumulative upper bound: 66 64 58 moves.

In this phase, all the tredges are formed; the centres remain in a "3-colour solved" state.

Spoiler: phase 5 depth distribution

Upper bound: 15 moves.

Cumulative upper bound: 81 79 73 moves.

Three subphases: one for the U and D centres, one for the R and L centres, and one for the F and B centres. The depth distributions are identical for all three.

Partially obsolete.

Spoiler: phase 6 depth distribution

Upper bound: 3⋅14 = 42 27 + 14 = 41 moves.

Cumulative upper bound: 123 121 115 114 moves.

Upper bound: 20 moves.

Cumulative upper bound: 143 141 135 134 moves.

tl;dr: 143 OBTM 141 OBTM 135 OBTM (2017-10-31) 134 OBTM (2018-05-15) 130 OBTM (2018-05-20).

I finished writing a 5x5x5 solver about three weeks ago, and in the time since I've mostly been working on trying to get a "good" upper bound for the 5x5x5 God's number in OBTM. I'm not entirely satisfied with this analysis, because according to this older thread with move counts of human solves, reduction can and should take much fewer moves than the upper bound I got, but anyway.

We divide the solving process into seven main phases, the last of which is a 3x3x3 solve. Some of these phases will in turn be divided into subphases that are easier to analyse. The division of phases is largely based on Charles Tsai's documentation of his 4x4x4 solver.

(Side note: the code I use for generating these tables is mostly not shared with the solver, apart from trivial utility functions like calculating binomial coefficients and such, so I'm not fully certain the numbers are correct. Independent confirmation would be awesome. Also, the solver itself usually finds a reduction in around 70 to 75 moves with about a minute of CPU time, which is… very far from the bound presented here, to say the least.)

**Phase 1: Solving the UD centres to the UD faces**E: Obsolete; see post #7 by qq280833822.

Someone with more disk space to spare (and using a programming language where accessing hundred-gigabyte arrays isn't a PITA) could probably do a breadth-first search on the whole state space of C(24,8)^2 ~ 541 billion states, but that someone is unfortunately not me. This is split into two subphases, where the first subphase solves the T-centres and the second subphase solves the X-centres. As an optimisation, we can reduce the move count by one if we skip the last move of the first subphase before proceeding to the second subphase.

Obsoleted by later analysis; preserved for posterity.

Moves allowed: U, D, R, L, F, B, Uw, Dw, Rw, Lw, Fw, Bw

Moves allowed: U, D, R, L, F, B, Uw, Dw, Rw, Lw, Fw, Bw

Code:

```
0 5
1 66
2 900
3 9626
4 80202
5 329202
6 302146
7 13324
```

Obsoleted by later analysis; preserved for posterity.

Moves allowed: U, D, R, L, F, B, Uw, Dw, Rw, Lw, Fw, Bw

Moves allowed: U, D, R, L, F, B, Uw, Dw, Rw, Lw, Fw, Bw

Code:

```
0 -
1 1
2 -
3 8
4 64
5 363
6 3604
7 27752
8 159086
9 392648
10 151261
11 684
```

Upper bound: 7 + 11 = 18 12 moves.

**Phase 2: Solving the RL centres to the RL faces; FB centres to the FB faces; and wing parity**Moves allowed: U, D, R, L, F, B, Uw, Dw, Rw2, Lw2, Fw2, Bw2

Code:

```
0 1
1 2
2 33
3 374
4 3848
5 40230
6 409051
7 3816922
8 27309148
9 108088828
10 153042267
11 38271627
12 291452
13 17
```

Upper bound: 13 moves.

Cumulative upper bound: 31 25 moves.

**Phase 3: Orienting all midges and separating wings into two orbits**Note that no restriction is placed on the centres in this phase, unlike the corresponding phase in Tsai's solver. We allow either all the edges to be oriented, or all the edges to be flipped.

Obsoleted by later analysis; preserved for posterity.

Moves allowed: U, D, R, L, F, B, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2

Moves allowed: U, D, R, L, F, B, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2

Code:

```
0 1
1 2
2 33
3 382
4 3920
5 45980
6 515594
7 4882282
8 37725852
9 214944909
10 748549490
11 1177896283
12 541147752
13 43045056
14 297920
15 288
```

Upper bound: 15 13 moves.

Cumulative upper bound: 46 44 38 moves.

(See post #5 in this thread for how the upper bound was reduced from 15 moves to 13 moves.)

**Phase 4: "Domino" reduction**Again, no restriction is placed on the centres here. This is divided into two subphases. In the first subphase, the pieces needed to form four tredges are placed in the L and R layers. (This takes no moves at all ~52% of the time, or ~78% of the time if we get to do a z rotation as well, but we're doing a worst-case analysis, not an average-case analysis.)

In phase 3, we have the wings separated into two orbits (each of 12 pieces), such that within each orbit, each wing has a different pair of colours. (To borrow terminology from earlier work, arbitrarily call one of the orbits "low" and the other "high".) The low orbit has eight wings in the L, R layers, as does the high orbit.

Let A be the set of colour pairs of the eight wings in the low orbit and the L, R layers, and B be the set of colour pairs of the eight wings in the high orbit and the L, R layers. We have |A| = |B| = 8 and |A∪B| ≤ 12 (there are only 12 possible colour pairs), so by inclusion-exclusion, |A∩B| ≥ 4, i.e. there are at least four colour pairs shared between A and B. We can choose any four such colour pairs, and then move the midges and wings with those colour pairs onto the L and R layers.

This has C(8,4) ⋅ C(8,4) ⋅ C(12,4) cases to consider, where the four low wings are already in the L, R layers, the four high wings likewise, and the four midges can be anywhere. We do not constrain the four low wings or the four high wings to stay in the L and R layers throughout the subphase; we only require that they end up there.

(The actual computation was done with a BFS through the C(12,4)^3 cases with the wings being anywhere, and then filtered to include only the cases where the low/high wings start on the L and R layers.)

We can use the same inclusion-exclusion trick on, say, the low wings and the midges (instead of low wings and high wings), but that leads to an upper bound of 7 moves, which is worse than the 6 moves we have here.

Let A be the set of colour pairs of the eight wings in the low orbit and the L, R layers, and B be the set of colour pairs of the eight wings in the high orbit and the L, R layers. We have |A| = |B| = 8 and |A∪B| ≤ 12 (there are only 12 possible colour pairs), so by inclusion-exclusion, |A∩B| ≥ 4, i.e. there are at least four colour pairs shared between A and B. We can choose any four such colour pairs, and then move the midges and wings with those colour pairs onto the L and R layers.

This has C(8,4) ⋅ C(8,4) ⋅ C(12,4) cases to consider, where the four low wings are already in the L, R layers, the four high wings likewise, and the four midges can be anywhere. We do not constrain the four low wings or the four high wings to stay in the L and R layers throughout the subphase; we only require that they end up there.

(The actual computation was done with a BFS through the C(12,4)^3 cases with the wings being anywhere, and then filtered to include only the cases where the low/high wings start on the L and R layers.)

We can use the same inclusion-exclusion trick on, say, the low wings and the midges (instead of low wings and high wings), but that leads to an upper bound of 7 moves, which is worse than the 6 moves we have here.

In the second subphase, four tredges are formed out of the pieces chosen in the previous subphase, and these tredges are placed in the E slice positions (FL, BL, BR, FR). The moves used here are almost the same as in phase 5, but off by a z rotation.

Moves allowed: U, D, R, L, F2, B2, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2

Code:

```
0 343000
1 24750
2 194785
3 977228
4 672305
5 204640
6 8792
```

Moves allowed: U2, D2, R, L, F2, B2, Uw2, Dw2, Fw2, Bw2

Code:

```
0 1
1 3
2 17
3 110
4 761
5 4944
6 30453
7 178759
8 995736
9 5144375
10 22521971
11 67281036
12 84004674
13 17258876
14 146284
```

Upper bound: 6 + 14 = 20 moves.

Cumulative upper bound: 66 64 58 moves.

**Phase 5: 3x3x3 reduction (except centres)**In this phase, all the tredges are formed; the centres remain in a "3-colour solved" state.

Moves allowed: U, D, R2, L2, F2, B2, Rw2, Lw2, Fw2, Bw2

Code:

```
0 1
1 4
2 26
3 156
4 999
5 5892
6 36376
7 222480
8 1301886
9 7238228
10 36410756
11 144974952
12 343690470
13 262142742
14 16825016
15 1216
```

Upper bound: 15 moves.

Cumulative upper bound: 81 79 73 moves.

**Phase 6: Centres**Three subphases: one for the U and D centres, one for the R and L centres, and one for the F and B centres. The depth distributions are identical for all three.

Partially obsolete.

Moves allowed (for solving R, L, F and B centres): U2, D2, R, L, F, B, Uw2, Dw2, Rw2, Lw2, Fw2, Bw2

See post #9 for details. Upper bound is 27 moves.

Moves allowed (for solving U and D centres): U, D, R2, L2, F2, B2, Rw2, Lw2, Fw2, Bw2

See post #9 for details. Upper bound is 27 moves.

Moves allowed (for solving U and D centres): U, D, R2, L2, F2, B2, Rw2, Lw2, Fw2, Bw2

Code:

```
0 1
1 -
2 -
3 -
4 2
5 6
6 29
7 146
8 331
9 189
10 592
11 940
12 1560
13 1064
14 40
```

Upper bound: 3⋅14 = 42 27 + 14 = 41 moves.

Cumulative upper bound: 123 121 115 114 moves.

**Phase 7: 3x3x3**Upper bound: 20 moves.

Cumulative upper bound: 143 141 135 134 moves.

Last edited: May 19, 2018