# 5x5x5 OBTM upper bound

Discussion in 'Puzzle Theory' started by xyzzy, Jun 11, 2016.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

1. ### xyzzyMember

227
84
Dec 24, 2015
(Has anyone else attempted such computations before? I didn't find anything.)

tl;dr: 143 OBTM.

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

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.

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

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

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 moves.
Cumulative upper bound: 46 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.) More precisely, we can exploit the inclusion-exclusion principle thus. There are eight wings in one orbit in the L, R layers, and eight wings in the other orbit; since there are only twelve possible pairs of colours the wings can have, this means that the intersection of the sets of pairs of colours among these sixteen wing pieces has at least four pairs of colours. We can then choose any four such pairs of colours, and then solve the midges and wings with those colours onto the L and R layers.

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).

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

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 moves.
Cumulative upper bound: 123 moves.

Phase 7: 3x3x3

Upper bound: 20 moves.
Cumulative upper bound: 143 moves.

Last edited: Jun 12, 2016
2. ### Herbert KociembaMember

153
26
Nov 29, 2008
It is not so hopeless as you think. You can reduce the problem by 16 symmetries, then you have two symmetry-reduced coordinates with size each of about C(24,8)/16 = 50000. These can be combined to a coordinate of size about 50000^2*16= 40GB. You can construct a pruning table with 2 bits for each entry, so the pruning table will not have more than 10 GB. Just for a breadth first search you only need 1 bit per entry, so even 5 GB will be enough.

StachuK1992 likes this.
3. ### xyzzyMember

227
84
Dec 24, 2015
We don't need two symmetry-reduced coordinates, but only one symmetry-reduced coordinate and one non-reduced coordinate, right? 5 GB would fit in my free RAM pretty snugly, so I'm going to give this a shot. I'm somewhat afraid that the computation will take many hours and I'll stay up all night staring at a progress bar slowly fill up, though.

4. ### Herbert KociembaMember

153
26
Nov 29, 2008
Yes this ist true and surely a simpler approach. Additionally you then need a table which transforms the non-reduced coordinates to new non-reduced coordinates by conjugation with each of the 16 symmetries.

5. ### xyzzyMember

227
84
Dec 24, 2015
For phase 3, we don't actually have to look at all 2^11 C(24,12) / 2 ~ 2.8 billion states, since we're free to assign the starting midge position to be whatever we want. For instance, if we consider the midges to always start as being oriented, the distribution changes to:

Code:
 0          1
1          -
2          -
3          -
4          8
5        128
6        863
7       3990
8      23788
9     151274
10     611614
11    1110867
12     661700
13     132522
14       7364
15         37
This doesn't improve on the upper bound, but we can look at other starting midge orientations (since we don't care if the reduction leaves the cube with flipped tredges at the end).

Of the 288 antipodal positions, 37 of them have midges solved at the start, 21 have midges in the S slice flipped, 75 have midges in the E slice flipped, and 75 have midges in the M slice flipped, so 208 of the 288 antipodes have D8 symmetry on the midges along some axis. One of the antipodes is given by having all wings solved and all midges flipped, which is about as symmetric as you can get.

Anyway, if we start with the six midges at UF, UL, UB, FL, BL and DR flipped, this is the distribution.

Code:
 0         -
1         -
2         -
3         -
4         -
5         9
6       194
7      2888
8     30212
9    216169
10    857006
11   1246820
12    346302
13      4556


This reduces the upper bound for phase 3 to 13 moves, and the overall upper bound to 141 moves. This is the "best" we can do with a fixed starting midge orientation (every starting orientation has some case that needs at least 13 moves), but a potential improvement in this direction is to use set cover techniques to try different starting orientations.

Last edited: Mar 18, 2017