What is God's number on a 4x4 Rubik's cube?

qqwref · Dec 22, 2014

unsolved said:
So can you annotate the steps undertaken as the Yau solution indicates?
[...]
I am completely unfamiliar with Yau but it sounds interesting.

1) Solve two opposite centers - already done
2) Solve three edges on the left center - already done
3) Solve last 4 centers without messing up the three edges - two centers were already done, so I just finished off the last two
4) Pair and insert last edge on left center
5) Pair remaining edges
6) Solve like a 3x3x3 with a solved cross

Remember that human solving methods are designed for random scrambles, so anything with a large chunk solved will generally save time, if sometimes only a small amount

unsolved · Dec 22, 2014

cuBerBruce said:
In your example, you have a goal depth of 10, and building a search tree out to depth 7 since at that point you can determine if a 10-move solution exists for any of the nodes at depth 7 from the scramble position. But you also check if the position is of the special type. For a certain node, you find this is the case, and know that it has a 6-move solution. So you are basically checking for a possible solution that is deeper than the current goal depth. In this case, you find a solution that is 7 + 6 = 13 moves, while you haven't finished verifying if a 10-move solution exists. The solution you found may be suboptimal. In this case, it is not. My solver found an 11-move solution in about 8 seconds: R B U2 r l U2 B2 D2 R B2 b2.

If you looked more carefully, you would have seen I was testing 3-TFS + the centers database. I am aware there are other solutions possibly <= the deepest find. In such cases, the program just continues searching. I needed to see how the program would behave when it encounters a position whose solution was beyond the range of the current depth. When I turn on the 5-TFS databases, the solution is found before the center databases are encountered.

The behavior I am looking for is the ever-tightening noose:

Here the program finds a 10-ply solution at depth 4 by hitting the 6-turn center database, which is improved within the same depth to 9-ply by finding a 5-turn center solution. Finally a 7-ply result without using the center databases at all trumps all. This demonstrates the program is capable of continuing to search for improvements.

cuBerBruce said:
Let's say you found a position that can be solved either with 6 inner layer turns (no other turns). Let's say there is another ("shortcut") solution having 2 inner layer turns and 2 outer layer turns. The inner layer pruning heuristic would say at least 2 inner layer turns are required. The face turn heuristic will say you need at least zero face turns because a solution exists that doesn't use any face turns. You add the two heuristics and you get that at least 2 + 0 = 2 turns are required. In actuality, you really need 4 turns in this example. But the additive heuristic has not overestimated the distance to solved, so it is a valid heuristic.

I would like to see an example position where a solution depth = the sum of the two depths you mentioned. Take a position with a known optimal solving distance that uses only face turns. Pick another position with a known optimal solving distance comprised entirely of inner slice turns. Apply the scramble of position 2 to position 1 already scrambled. If what you are saying is true, there can be no shorter solution than the sum of these depths.

qq280833822 · Dec 22, 2014

unsolved said:
Since my solver is "brute force" and not a stage-solver, it will need every pruning trick in the book to tackle positions like these.

According to you description, in my viewpoint, your solver is a two-stage solver. The goal of stage 1 is defined as: {all states which can be solved in X moves (the X-TFS database), or all states with solved edge and corner (the center database)}.

And at stage 1, you use brute force search without any pruning, while at stage 2, you use a simple look-up table method to get the full solution.

If it's true, as the length of stage 2 is quite small (e.g. less than 10 moves), the length of stage 1 needed would be relatively high (e.g. more than 15 moves) for a far enough state. In this case, you must do a full 15-move search (more than billions of billions of nodes), which is impractical right now I think.

unsolved · Dec 22, 2014

qq280833822 said:
According to you description, in my viewpoint, your solver is a two-stage solver. The goal of stage 1 is defined as: {all states which can be solved in X moves (the X-TFS database), or all states with solved edge and corner (the center database)}. And at stage 1, you use brute force search without any pruning, while at stage 2, you use a simple look-up table method to get the full solution.

Well my program has no intermediate goals, nor does it do anything "different" as a function of depth. It searches all moves. It generates a 64-bit hash number if "depth minus available databases" is in range. And, if so, it probes the hash table, resolves hash collisions, and returns a result if found. It continues to search while depth_of_solution >= current depth, and depth_of_solution = 99 to start. So if it finds a center database solution beyond the current depth, there is a chance a better solution is waiting.

qq280833822 said:
If it's true, as the length of stage 2 is quite small (e.g. less than 10 moves), the length of stage 1 needed would be relatively high (e.g. more than 15 moves) for a far enough state. In this case, you must do a full 15-move search (more than billions of billions of nodes), which is impractical right now I think.

But this is the exact nature of what I intended to design! My objective was not to make a fast stage solver. My objective was to make a brute force solver.

And 15 moves is "only" 4,790,008,577,248,538,697,216 by my calculation

qq280833822 · Dec 22, 2014

unsolved said:
Well my program has no intermediate goals, nor does it do anything "different" as a function of depth. It searches all movs. It generates a 64-bit hash number if "depth minus available databases" is in range. And, if so, it probes the hash table, resolves hash collisions, and returns a result if found. It continues to search while depth_of_solution >= current depth, and depth_of_solution = 99 to start. So if it finds a center database solution beyond the current depth, there is a chance a better solution is waiting.

Well, I'll try to explain why I think your solver is a degraded two-stage solver. Let's compare your solver to an imaginary two-stage solver.

It searches all movs.

The two-stage solver searches all moves at stage 1, as there's no pruning table at this stage.

It generates a 64-bit hash number if "depth minus available databases" is in range.

The two-stage solver generates a number to represent the state, if "depth minus maximum stage 2 length" is in range.

And, if so, it probes the hash table, resolves hash collisions, and returns a result if found.

If we found that the number represents a state which can be solved in stage 2 (in another word, we finished stage 1), we will return the solution (as all solutions for stage 2 states has been generated before).

It continues to search while depth_of_solution >= current depth, and depth_of_solution = 99 to start.

After finding a solution, the two-stage solver continue trying more stage 1 solutions while depth_of_solution >= current depth, and depth_of_solution = 99 to start.

cuBerBruce · Dec 22, 2014

unsolved said:
I would like to see an example position where a solution depth = the sum of the two depths you mentioned. Take a position with a known optimal solving distance that uses only face turns. Pick another position with a known optimal solving distance comprised entirely of inner slice turns. Apply the scramble of position 2 to position 1 already scrambled. If what you are saying is true, there can be no shorter solution than the sum of these depths.

I am talking about using two admissible pruning heuristics for the same position and deriving a third admmissible heursistic by adding them (something not true in general, but may be true for particular heuristic functions). You are talking about two different positions and some relationship to a third position derived by composing maneuvers for those first two positions. That isn't what I'm talking about. You are trying to say that I'm claiming something that I'm not.

unsolved · Dec 22, 2014

cuBerBruce said:
That isn't what I'm talking about. You are trying to say that I'm claiming something that I'm not.

Bruce, my post was a request for clarification. Dissect your original post, and my interpretation was not out of the realm of possibility.

The way my program works, only 1 pruning mechanism operates on a position in question. I query the TFS database first and foremost, always. If there is no confirmed finding, I test to see if there is a "ring" position with only centers disturbed. No ring position, no query is necessary. If a ring position hits the center database, I check the depth reported. If that depth <= the shallowest (quickest solve) depth, I show the solution.

But now, even my misinterpretation of your post brings up an interesting question. Suppose we have a position from a scramble such as RLFB RLFB RLFB. There is no shorter move sequence to produce this position, and it was achieved using only face turns. There are other ways to create it, such as R L U2 F2 U2 B2 R L F2 D2 B2 D2 but this requires the same number of moves, so it is of no consequence. Now let's look at something simple, like u r u' r'. It features only slice turns, and there is certainly no shorter way to create that position from a solved cube. So, what happens if we combine them? Is there a shorter way to create the position resulting from u r u' r' RLFB RLFB RLFB? I do not think there is. So that would mean we can add depths together if they are created from mutually exclusive cube component rotations. I think.

qqwref · Dec 22, 2014

There may not be a shorter way for that particular position, but you can't prove it just based on (RLFB)4 and uru'r' being optimal in face-turns-only and slice-turns-only. When you are solving the whole cube, moves that help solve the corners and edges may combine with moves you use for solving the centers, or vice versa. There also may be multiple ways of solving the centers, and one could give an easier 3x3x3 solve than the other. If you want to prove that uru'r'(RLFB)4 is optimal, one way would be to prove that it requires at least 4 slice turns, and separately prove that it requires at least 12 face turns - but it is possible that one of these may be false, and that there may be a shorter solution.

Does anyone have a rough guess at God's Number for the 4x4x4 centers, where slice turns count as 1 but face turns count as 0? That is, how many slice turns a position may be demonstrated to require. In unsolved's metric (but not in BTM or OBTM), we should be able to add together the number of slice turns required by the centers and the number of face turns required by the corners.

cuBerBruce · Dec 22, 2014

unsolved said:
But now, even my misinterpretation of your post brings up an interesting question. Suppose we have a position from a scramble such as RLFB RLFB RLFB. There is no shorter move sequence to produce this position, and it was achieved using only face turns. There are other ways to create it, such as R L U2 F2 U2 B2 R L F2 D2 B2 D2 but this requires the same number of moves, so it is of no consequence. Now let's look at something simple, like u r u' r'. It features only slice turns, and there is certainly no shorter way to create that position from a solved cube. So, what happens if we combine them? Is there a shorter way to create the position resulting from u r u' r' RLFB RLFB RLFB? I do not think there is. So that would mean we can add depths together if they are created from mutually exclusive cube component rotations. I think.

No, it doesn't work. Consider:

Maneuver 1: U R F (3 moves)
Maneuver 3: r2 b2 r2 u2 b2 r2 (6 moves)
Combined maneuver: U R F r2 b2 r2 u2 b2 r2 (9 moves)

Optimal solution of combined maneuver: f2 r2 f' b' u2 B' D' R' (8 moves)

An even more trivial case:

Maneuver 1: U D'
Maneuver 2: u d'

unsolved · Dec 23, 2014

qqwref said:
Does anyone have a rough guess at God's Number for the 4x4x4 centers, where slice turns count as 1 but face turns count as 0? That is, how many slice turns a position may be demonstrated to require. In unsolved's metric (but not in BTM or OBTM), we should be able to add together the number of slice turns required by the centers and the number of face turns required by the corners.

I found that if you eliminate face turns, the number of unique center arrangements per depth will be exhausted quicker than you might expect. I have a 550 MB text file with every possible center arrangement through depth 6, plus a few at depth 7, using face moves + slice moves. A vast majority of the moves are slice turns, of course.

Here are my counts of unique center arrangements per depth:

Code:

#define TOTAL_POSITIONS_TFS_CENTERS_DEPTH_04 4896
#define TOTAL_POSITIONS_TFS_CENTERS_DEPTH_05 9216
#define TOTAL_POSITIONS_TFS_CENTERS_DEPTH_06 212472
#define TOTAL_POSITIONS_TFS_CENTERS_DEPTH_07 1202928

While the numbers are small, the number of positions that must be examined to establish this is quite large. I examined all 24 rotated states during a 36^n move generation run to scan for uniquely-occurring positions with disturbed centers.

Edit: But these are only counts with the corners and edges solved. I am thinking maybe this was not what you were asking.

cuBerBruce · Dec 23, 2014

unsolved said:
Edit: But these are only counts with the corners and edges solved. I am thinking maybe this was not what you were asking.

Yes, it is different. I'm rather confident qqwref meant that the corner and edge pieces are to be ignored. Also, I understand that he also wanted face turns not to be counted. That is for each position at depth n, you try all 18 slice turns, and then (on each of these resulting positions) try all 4^6 different ways the 6 face layers can be turned. Count each new state encountered as depth n + 1. (Considering the 4 rotated states of a face as equivalent can be used to reduce the effective number of states, but it's still a pretty large state space for a full breadth-first search.) Note that with the corners and edges ignored, the face layer turns are independent of each other. (They commute.)

I rather doubt anyone has determined God's number for this. One might get an estimate of it through solving thousands of random states or through a partial breadth-first search and using the derived branching factor.

dannah · Jan 3, 2015

before you calculate it for the 4*4 what about the2*2?

Jakube · Jan 3, 2015

dannah said:
before you calculate it for the 4*4 what about the2*2?

11 moves

ryanmcg86 · Jan 20, 2015

Renslay said:
You mean that Superflip * A = A * Superflip for all A sequence of moves? (Which equals to ASA' = S)

is there some comprehensive list somewhere of all, or just all KNOWN move equivalents? like, as an example, LLL (3 moves) is the same thing as L'(1 move, for a total of 2 (3 - 1) move-amount difference), another would be RR' being the same as making no moves, whether you're talking about a 4x4x4 or a 3x3x3. if there isn't a list for all the equal sets where one is less moves than the other, we should start compiling one, because if you had all of them, you can calculate the permutations that can be solved in less moves than the number of moves in the initial randomizing. by being left with the unique cases that take x minimal moves to solve, where x is the number of moves made when initially randomized, you can take a summation of those cases and figure out what gods number is, for potentially any n x n x n cube, once the summation is equal to the total amount of unique states that cube can be in.

qqwref · Jan 20, 2015

You could easily get a list of pretty trivial cases (moves that cancel), but all the decent solving programs already take the trivial stuff into account. Once you get into useful equivalencies, the list would get extremely large very quickly. It's certainly not easier to generate this list than to find God's Number by itself. Think about this: for every position that has two solutions, those two solutions are move equivalents, and solution1 + (solution2)' is the solved state. Now consider that a given position may have many many solutions of 20 moves or less - they are all equivalent with each other. And that's just the situation for 3x3x3, never mind 4x4x4...

ryanmcg86 · Jan 20, 2015

qqwref said:
You could easily get a list of pretty trivial cases (moves that cancel), but all the decent solving programs already take the trivial stuff into account. Once you get into useful equivalencies, the list would get extremely large very quickly. It's certainly not easier to generate this list than to find God's Number by itself. Think about this: for every position that has two solutions, those two solutions are move equivalents, and solution1 + (solution2)' is the solved state. Now consider that a given position may have many many solutions of 20 moves or less - they are all equivalent with each other. And that's just the situation for 3x3x3, never mind 4x4x4...

where would one find such a list? even the trivial cases, if not all the cases, but i don't know where such a list exists and i'm rather curious

jaap · Jan 21, 2015

Way back in 1981 some identities were enumerated. There are essentially only 3 that use 12 quarter turns, but no shorter ones apart from the really trivial stuff, and about a dozen of 14q, and many more longer ones. Here are some historic posts from the cube lovers mailing list where they were first published:
http://www.math.rwth-aachen.de/~Mar...ris_C._Worrell__Re__Identities_(galore)!.html
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Chris_C._Worrell__Identities....html
http://www.math.rwth-aachen.de/~Mar...orce_Report__The_fourteen-qtw_identities.html

ketchuphater999 · Jan 22, 2015

You're all wrong. The 4x4 is the Rubik's Revenge, right? Revenge is supposed to be 'corrupting to your soul'. When god wants revenge?

SATAN'S NUMBER!

But really, has no one derived a general function to get god's number for any cubical cube(wut)?

qqwref · Jan 22, 2015

Gallifrey said:
But really, has no one derived a general function to get god's number for any cubical cube([/SIZE][/SIZE]wut)?

No, of course there is no such formula... we only know the number for 2x2x2 and 3x3x3. Even if we had such a formula how could we possibly prove it was correct? We do know the number grows proportional to n^2/log(n) for an nxnxn cube, but apart from that, pretty much nothing.

Christopher Mowla · Jan 22, 2015

qqwref said:
No, of course there is no such formula...

Hey, you didn't tell him about my latest formula (and my final one)!

Thread starter	Similar threads	Forum	Replies	Date
T	STM solver and god's number?	Puzzle Theory	5	Friday at 8:26 AM
	When do you think will there be a sub god's number fmc mean OFFICALLY	General Speedcubing Discussion	4	May 29, 2023
M	Dodecahedron (and other) God's Numbers	Puzzle Theory	2	Jul 14, 2022
K	God's Number for CFOP and Roux	Puzzle Theory	26	Jun 15, 2022
S	God's Number for 4x4 Found!	General Speedcubing Discussion	93	Sep 30, 2011

What is God's number on a 4x4 Rubik's cube?

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Member

Premium Member