Home »

Solving the 4x4x4 in 57 moves(OBTM)

Submitted by CS on Mon, 09/30/2013 - 13:31.
According to my computation, the 4x4x4 cube can be solved no more than 57 moves.
The solving algorithm is based on tsai's 8-step method which can be found here: link

The only modification is that I merged step 3 & step 4 to one step.

For some reasons, the algorithm cannot be defined to the conversions between subsets, but can be defined to the conversions between sets:
S0: <U R F D L B Uw Rw Fw Dw Lw Bw>
step 1 =>
S1: <U R F D L B> * <U R F D L B Uw2 Rw Fw2 Dw2 Lw Bw2>
step 2 =>
S2: <U R F D L B> * <U R2 F D L2 B Uw2 Rw2 Fw2 Dw2 Lw2 Bw2>
step 3 & step4 =>
S3: <U R F D L B>
3x3x3 solver =>
S4: Solved State

In step 1, we should:
Place R&L centers to R&L faces

which can be done in 8 moves:
depth    states
0        1
1        4
2        82
3        1206
4        14116
5        123404
6        422508
7        173254
8        896

In step 2, we should:
Separate low edges and high edges (or the orientation of the edges. I have no idea how to deal with it in a simple way, so I modified it to "let low edges to low places and high edges to high places, or low to high & high to low",totally C(24,12)/2 = 2,704,156 different states or 86048 symmetry classes)
U&D centers to U&D faces, F&Bcenters to F&B faces ( C(16, 8)/2 )
R&L centers to one of 12 states which can be solved in step 3 (12 solved states in 70, or 6 in 35 if we only care about the separation of R L pieces)
The parity of all edges ( 2 )

which can be done in 14 moves:
depth    states mod M
0        6
1        12
2        48
3        381
4        3643
5        45030
6        606937
7        8154706
8        102867620
9        1114713818
10       8194798024
11       21637154427
12       7652855512
13       49121344
14       92

total    38760321600 = 86048 * 6435 *35 * 2
Notice that in depth 14, there're only 92 symmetry classes and no more than 92*16 = 1472 states while the orientation of the edges can be defined in 2048 different ways. After redefining edges, the 14-move states won't occur. And the step 2 can be solved in 13 moves.
In merged step 3 & step 4, we should:

Pairing Edges. (12!/2 different states or 14999140 symmetry classes)
Solving centers. (C(8, 4)/2 * C(8, 4)/2* 12)
Fix the parity of centers, edges and corners. (2)

which can be solved in 16 moves:
depth    states mod M
0        1
1        2
2        11
3        85
4        547
5        3757
6        29154
7        249155
8        2287529
9        21385620
10       197829833
11       1788075646
12       14489430468
13       86675095891
14       242701855493
15       94978862660
16       119610148

total    440974716000 = 14999140 * 35 *35 * 12 * 2

After step 3 & step 4, the reduction is finished and the cube can be solved by <U, R, F, D,L, B>. According to the god's number of 3x3x3, the step 5 to step 8 can be solved in 20 moves.

Thus, the 4x4x4 cube can be solved in 8 + 13 + 16 + 20 = 57 moves.
» 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.

441 *billion*

Submitted by rokicki on Fri, 10/04/2013 - 17:53.
Can you share some of the technical details on how you
did the exploration? A 441B (reduced mod M, so the total
state space there is probably closer to 21T) state space
exploration is a pretty big one. What's your overall
technique? What sort of machines? How much time did it
take?

This is very intriguing to me.
» login or register to post comments

As I noted in another post, t

Submitted by Bruce Norskog on Sat, 10/05/2013 - 21:57.

As I noted in another post, the symmetry reduction is not mod M, but a 16x reduction. So it's a little over 7 trillion states, 7041323520000 to be exact. My corner and edge permutation analysis of the 3x3x3 used 48x reduction from about 9.66 trillion states to about 236 billion states. (I did not use antisymmetry.) So that was roughly half the size in symmetry-reduced terms. It was done on a Pentium 4 with a gigabyte of RAM. Of course, for QTM all states for a particular distance were in one half of the files or the other half. So it was sort of like the state space was only half as big.

The lowering of the upper bound for OBTM from 82 to 57 is a really big jump. I note that the set of subgroups I used was chosen with single-slice turn metric in mind, not OBTM (twists). Since it wasn't a great deal extra programming effort, I did it anyway.

It seems to have not been mentioned yet that these analyses also lowers the bound for BTM, where the blocks of layers that are allowed to be turned need not include a face layer. This bound is lowered from 67 to 57. (Perhaps down to 55 if 18s* were to be proven worst case for the 3x3x3.) Of course, using BTM-specific breadth-first searches should reduce it further.

» login or register to post comments

Your real name?

Submitted by rokicki on Thu, 10/03/2013 - 13:26.
Would you be willing to share your real name with the board?
» login or register to post comments

Shuang Chen (陈霜)

Submitted by CS on Thu, 10/03/2013 - 14:08.
Shuang Chen (陈霜)
Dept. EE
Tsinghua University

My wcaid is 2008CHEN27(https://www.worldcubeassociation.org/results/p.php?i=2008CHEN27).
» login or register to post comments

Fantastic work

Submitted by rokicki on Thu, 10/03/2013 - 13:20.
This is fantastic work! I was hoping to get to this but perhaps I can duplicate/verify your numbers. I think this is great progress on the 4x4x4, and I think this can be the basis of an excellent solver.
» login or register to post comments

Not full mod X reduction

Submitted by Bruce Norskog on Thu, 10/03/2013 - 15:00.

One thing that has occurred to me is that CS has not produced actual mod X reduced numbers. He has reduced a portion of the state space mod X, but not the whole space. The true mod X numbers will generally be slightly less than the numbers he shows. This is because there will be some mod X symmetry classes that will be represented by more than one element of his reduced state space. This means if you want to verify his numbers (not merely the bound), you will have to reduce the search space in exactly the same way. It would be nice if he had computed true mod X values, and/or computed non-symmetry reduced numbers. This would generally make verifying his numbers easier, since you wouldn't necessarily have to implement the symmetry reduction in the same manner. A hash table based breadth-first search could easily produce non-symmetry reduced results to a limited depth. This could provide a partial verification that his results are correct, but it would require (unless this verification code also implemented symmetry reduction) the non-reduced numbers.

I note that when I first tried to do symmetry reduction, I did something similar. I found a problem in that elements that mapped to the same symmetry class were not always being marked with the same distance value. To fix the problem, whenever I found a new element (meaning its distance was now known), I made sure I found all elements in the reduced state space that corresponded to the same symmetry class, and immediately marked all those elements with the same distance before proceeding on with the search. I hope CS has not made this same mistake, although even if he has, I think the upper bound would still be valid as an upper bound.

» login or register to post comments

CS, nice job on doing some im

Submitted by Bruce Norskog on Tue, 10/01/2013 - 23:39.

CS, nice job on doing some impressively large breadth-first searches.

However, to be sure you solve the centers so that the colors are in the correct relative arrangement, it appears to me that you need to track 70*70*12 center states in your step 3 rather than 35*35*12. Basically you have two colors for each axis, and 3 axes. When all the center pieces are grouped, the two colors on each axis can be in either the "correct" position or swapped. What's important is that the parity of these three potential swaps is even. To do this, you need to know which pieces are which color. So 70*70*12 center states are needed for step 3.

This "color scheme parity" needs to be correct independent of PLL parity. As for PLL parity, it appears to me that the extra factor of 2 is for tracking the corner parity and I think you have sufficent edge information so that PLL parity can be determined. Since you are putting centers on the "correct" axes, and you (must) avoid incorrect color scheme parity, the center permutation parity will be even, so it's not a factor in determining the PLL parity.

Your claim of being able to avoid depth 14 in step 2 seemed a little suspicious. Usually such avoidance is done by considering in the previous step alternative choices for the final move of that step so you get to a different state in the new step. Hopefully, this other state will not be an antipode so you can choose to go to that state instead.

In your case, you seem to be doing "extra work" in step 2, so that when reduction is finished, you would have either 0 or 12 dedges oriented. So apparently what you are doing is to have some even number of dedges flipped with respect to the rest of the dedges instead of having all 12 the same. This seems to conveniently place you in a different position in step 2, so it would seem the antipode can be avoided. When reduction is finished, you would have something other than 0 or 12 dedges flipped, but it would still have an even number of dedges oriented, so it would still be in a valid (pseudo) 3x3x3 state which is all you need. I think the explanation needs to be a little more rigorous, but I think it will work.

It appears to me that in step 1 you could "solve" the L/R centers to any of L/R, U/D, or F/B. Then do a whole cube rotation, if necessary, to put the L/R centers on L/R. This would mean you would have 3 solved states, and this could possibly reduce (by 1, with any luck) the number of moves required. Similarly, you could consider solving U/D and F/B centers to F/B and U/D, respectively, in step 2 with corresponding 90-degree cube rotation afterward. Then you would start with 12 solved states instead of 6 in that step.

You should put commas between the generators. <U R F D L B>, since it lacks commas, would normally be interpreted as a single-generator group, with that generator being the move sequence U R F D L B. That group has 60 elements, not 43252003274489856000. That clearly is not what you mean.

Another notational point. You are using a 16-element symmetry group for your symmetry reduction. Hoey's M-symmetry group has 48 elements. So while it appears to me you are using the correct symmetry group for these steps, you are not reducing "mod M". Hoey called the 16-fold symmetry subgroup X-symmetry, but his symmetry group naming (especially for the subgroups of M) is probably becoming less and less used, so you might want to just say "symmetry reduced" instead of something more precise.

» login or register to post comments

In step 3, if we don't care w

Submitted by CS on Wed, 10/02/2013 - 01:41.
In step 3, if we don't care whether the centers are correct or swapped, there will be only 35 * 35 * 6 different states. As we don't need to correct centers on each axis but only the parity of them, the total states needed for step 3 is 35 * 35 * 6 * 2 instead of 70 * 70 * 12.

I did do the search with 3 solved states in step 1. Unluckily, It still requires 8 moves. Also I will check whether it possible that the 8-move state appears on F/B U/D R/L centers simultaneously. --- update: After searching, it does exist several states cannot be solved in 7 moves on any colors and solved axis.

While describing the goal of step 2, I made a mistake. "U&D centers to U&D faces, F&B centers to F&B faces" should be corrected to "Separate U&D centers and F&B centers into different axis". That's why there're only C(16, 8)/2 different states instead of C(16, 8).

Sorry for missing commas between the generators and some other notational errors.
» login or register to post comments

It appears to me then that in

Submitted by Bruce Norskog on Wed, 10/02/2013 - 08:36.

It appears to me then that in step 3 for the centers, you use 35 states for U&D, 35 states for F&B, and 6 states for L&R, and 2 states (1 bit) for the color scheme parity. For the color scheme parity, it seems you could pick one of the 8 center positions on each axis, and the parity state tells you whether an even or odd number of these three reference positions have the "correct" color. Each time you perform a move, you determine how many of the three reference positions change color, and flip the parity state if that number is odd. But it seems to me having such reference positions would have an impact on the symmetry reduction. So I would like to understand how you track the parity state during step 3 so you end up with the centers in the correct color scheme at the end of step 3.

EDIT: OK, I think I see how it works. Given a "35*35*6*2" state, you convert the state value for each axis to a 8-bit bitmask, where it is assumed that a 1 in the bitmask represents, L, D, or B color, and 0 represents R, U, or F. If the parity bit is 1, you swap the colors of the L/R cubies (invert the bits in that bitmask). Then you perform a move. You must now match up the new state for each axis, with one of the 35 or 6 possible bitmasks. To do so, you may have to invert the bits. If you have to invert the bits for an odd number of axes, you flip the parity state. I believe this works. I believe conjugating by a symmetry element doesn't affect the overall parity. Tsai needed 70*70*12*1 states because he solved to a specific cube orientation.

So it seems to me that it may be valid from what I can tell. Have you created a solver that tests that you can use your distance tables to create a solution for random positions (at least verifying that steps 1 to 3 create a valid pseudo-3x3x3 position)?

» login or register to post comments

The wca 4x4x4 scrabler

Submitted by CS on Thu, 10/03/2013 - 14:13.
The 4x4x4 scrambler of WCA is also a 4x4x4 solver with the same algorithm(three-phase reduction algorithm) written by me. Its sources can be found in github (https://github.com/ChenShuang/TPR-4x4x4-Solver).

Of course it does not use the huge distance table, but can be used to check the correctness of reduction.
» login or register to post comments

I have found that even when t

Submitted by Bruce Norskog on Thu, 10/03/2013 - 15:16.

I have found that even when the symmetry reduction is done correctly, if the breadth-first search is not done properly, you can still get erroneous results. Thus, I feel doing a verification on the table is important.

Using random access lookups in the disk files, the solver can still be fairly fast. I have found that disk-based method can actually be faster than IDA*-based RAM approach, since execution for IDA* increases exponentially with depth, while the execution time increases linearly with depth using disk files.

» login or register to post comments

Verificaition

Submitted by CS on Fri, 10/04/2013 - 00:40.
Of course I did do some verification. In step 3, to verify the values in the table is correct, I checked all 8-move elements and randomly 10000 16-move elements using the IDA* solver.
In step 2, the similar verification is done without any error occurs.
» login or register to post comments