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

[Herbert Kociemba]

Does anyone have any idea about how many unique solutions (where L R == R L, for example) there are for solving all corner positions of the 2x2x2 up to a length of, say, 35 htm?

There are 9*6^34=2,578,606,199,622,633,886,542,987,264 different 35 move htm maneuvers on 2x2x2, so this approach will not work.

 

[qq280833822]

After analyzing step3&4 of tsai's algorithm, the upper bound is reduced to 57 (OBTM) moves (step1: 8 moves, step2: 13 moves, step3&4: 16 moves, step5~8: 20 moves).

The proof is posted to http://cubezzz.dyndns.org/drupal/?q=node/view/525

 

[CubePhysics]

Please pile this thread with sources as to lower bounds with the 4x4. As soon as I have enough I will use a server farm to try and prove or disprove algorithms, eventually finding God's Number!

Don't call this thread naive. Technology proved in 2010 that God's Number is 20. This year, 4 years after, will be the year that we will find it. Many may argue that according to Moore's Law, which is still alive, we are only <compute power of 2010>^2^2 today, but those who say that are naive themselves. They fail to realize that exponential values do not draw a straight line. While we may only be <compute power of 2010>^4 ahead, and the 4x4 is about 10^25 harder, it is possible (and with my own calculations, true) that they do not line up if you were to draw a line at all. The line that would represent technology advancements would be much steeper than the difficulty of the Rubik's cube, resulting in the possibility that God's Number is possible. As soon as I find a good online charting program, I will present this to you.

Please, pile and pile, row after row, reply after reply, fill up an entire hard disk's worth of resources! Thanks!

We seem to have a lot of computing power now. I think it should be calculable.

How much computing power was needed to prove 20 on a 3x3 and how much time has gone by?

They said when they released gods number that a beefy computer would take 1.1 billion years to calculate what they did in a few weeks in one of googles computer farms.

 

[qqwref]

If you don't understand how hard this problem is, you certainly don't know enough cube theory to have a shot at completing this project. At current computing speeds, all the computers in the world couldn't find God's Number for the 4x4x4 in a million years.

For reference, though, there is an upper bound of 57 moves OBTM and a lower bound of 35 moves.

 

[Ollie]

http://www.youtube.com/watch?v=E9jwqibslUk

2:04 onwards begins to explain just how hard the problem was for the 3x3x3 and how 43 quintillion combinations (and much much less, I think) is even beyond Google's leftover CPU time.

 

[Stefan]

They said when they released gods number that a beefy computer would take 1.1 billion years to calculate what they did in a few weeks in one of googles computer farms.

No.

 

[IRNjuggle28]

Slightly off topic. Apologies. What's God's number for 2x2?

 

[Lucas Garron]

Slightly off topic. Apologies. What's God's number for 2x2?

11htm, 14qtm.

Jaap's page usually has great coverage of the theory: http://www.jaapsch.net/puzzles/cube2.htm

 

[Soren333]

What is a God's number?

 

[whauk]

the length of the longest shortest solution. i.e. every state can be solved with god's number or less moves.

 

[unsolved]

Hardest 4x4x4 scramble to solve at present?

For reference, though, there is an upper bound of 57 moves OBTM and a lower bound of 35 moves.

Is there a cube position that is generally regarded as the most difficult to solve?

I would imagine the joining of long best-known solves for positions that seem to have no intersection would be strong candidates.

Maybe...

Created by 22 move corner twister + 15 move single dedge flip + one of the longest adjacent center swaps I solved (14 moves) == 51 moves total if no intervening shortcut. The centers open up that possibility. So take them away...

This is 37 moves if the dedge + corner twister are completely orthogonal

...or maybe...

 

[cuBerBruce]

For twisty puzzles, the number of positions generally grows roughly exponentially with respect to the distance from solved, until you start getting a significant percentage of the positions covered. You then get a peak, and after that the number of positions at each successive depth will start dropping dramatically. Thus, we expect most of the positions to be quite close to the maximum distance. So choosing a position at random will likely get you a position at least close to the maximum. But picking a position at random will also be extremely unlikely to give you an actual maximal position. Positions with a lot of pieces solved can have a tendency to be not quite so deep.

Positions with high symmetry, while generally rare overall, have a tendency to be relatively common among antipodal positions. But symmetrical positions can also be fairly close to solved. The best way to guess at possibliities for the deepest positions might be to look at high symmetry positions that also seem difficult to solve.

We basically haven't yet been able to prove any specific positions to be very deep (in the range of what we estimate God's number to be), so it's pretty much unknown at this point what positions are deepest.

 

[qqwref]

Here's my suggestion, superfliptwist plus symmetrically messed-up centers:

 

[unsolved]

Here's my suggestion, superfliptwist plus symmetrically messed-up centers:
http://www.speedsolving.com/wiki/ex...gbbogbrggbrrgryyorryorwoorwwoyyyybbygbwggwwww

I've been building solutions where only centers need to be solved, and you would be surprised that some of the messed-up cases have solutions that are not so deep. The deepest centers-only position I have solved so far is 14 turns. The latest version of my program has every 7-turn and fewer center position available, so just typing in a 7-turn scramble that has only centers needing solving should hit the hash table and be announced as such. I am working on the website now, I'll post a link when it is up.

P.S. Do you have a scramble sequence for your position?

link to download latest versions: http://lightningcloudcomputing.com/OO_4x4x4/Rubiks_Revenge_4x4x4_Program.shtml

 

[IAssemble]

Is there a cube position that is generally regarded as the most difficult to solve?

I would imagine the joining of long best-known solves for positions that seem to have no intersection would be strong candidates.

...

I like the idea, but if I understood the positions correctly, my (non-optimal) solver quickly finds several shorter solutions for your second and third cases including:

Second: 29 OBTM
Third: 26 OBTM

I'll try the first too in a while out of interest.

Here's my suggestion, superfliptwist plus symmetrically messed-up centers:
http://www.speedsolving.com/wiki/ex...gbbogbrggbrrgryyorryorwoorwwoyyyybbygbwggwwww

My "get feeling" is that this has great potential to be a bad case! Is this the position you mean?

My solver finds this 45 OBTM generator in a few minutes:
B R D R' D' R2 B' F2 R' B' U' F' D' B' F L2 R' U Lw' D' L2 B D L' B' Lw U F Lw F Lw2 D' F Lw U B Uw' B U D' Bw' Lw' D' Fw' R' // View at alg.cubing.net

And has just found this 40 OBTM generator:
L' D L2 B D B' L2 B' R' D' L2 D R2 B D2 L R' Rw B2 F D B2 L D' F' B D Lw F' B' Fw R' L' Lw2 Uw' D2 Rw2 D' B' U' // View at alg.cubing.net

BTW I doubt that this 40 OBTM sequence is optimal since it is (obviously?) using reduction, albeit with an optimal 17 move 3x3x3 section, and my "gut feeling" is that an optimal solution is likely to solve all pieces more "directly"/"randomly" than in three phases of middles, edge-pairing and optimal 3x3x3 that is typical of reduction methods.

Edit: it wasn't optimal as it has now found a 39 OBTM generator:
L' D F' U2 L' F2 D2 F2 B' R U R B L2 U D2 Uw R L2 B L2 D R' B' L B Dw R' L' Rw U' D' Dw2 Fw' B2 Uw2 B' L' F' // View at alg.cubing.net

 

[qqwref]

Wow, great solutions! I'm glad mine turned out somewhat difficult I feel like reduction of centers and edges together (as you seem to be doing) and then an optimal 3x3x3 stage is probably one of the best ways to go for suboptimal 4x4x4 solving. Of course, looking directly for an optimal solution is probably way out of reach.

 

[Christopher Mowla]

I like the idea, but if I understood the positions correctly, my (non-optimal) solver quickly finds several shorter solutions for your second and third cases including:

Second: 29 OBTM
Third: 26 OBTM

Nice solutions, although unsolved's solver is not for OBTM, but for single slice half turn moves, and thus if he claimed to have gotten a 37 move solution to the second scramble, he matched your 29 OBTM in his solver's move metric.

I'll try the first too in a while out of interest.

In his metric, I found a 38 move "direct" solution:
B2 L R f R2 f' R' F2 U2 R2 U2 R' F2 R2 U2 R' f2 R d R' U2 R d' R f' R2 U2 f2 U2 F2 R2 F2 f R2 f' L' R' B2

All I did was combine my 12 move double parity alg: f2 R d R' U2 R d' R f' R2 U2 f2 with an N perm. I then simply conjugated it. I suspect that your solver might use a wide turn last layer double parity algorithm + N-perm + setup moves, as this was the first route I chose.

BTW, nice solutions to qqwref's position!

 

[unsolved]

I like the idea, but if I understood the positions correctly, my (non-optimal) solver quickly finds several shorter solutions for your second and third cases including:

Second: 29 OBTM

That's interesting, from 37 down to 29.

What solver are you using? Do you have a link? I'd like to check it out.

Your 39-mover for the qqwref position seems to have flipped up-down and one other pair of sides. No matter, if a more direct scramble involves a rotation or 2, so be it. I will feed it into OO_4x4x4 when I get a chance. I am having it crank on something for the time being. I'm just curious to see if the 7-turns-from-solved center database has a chance (doubt it, too far away) but I am pretty sure when I complete the 14-turns database, it will be of some help

 

[IAssemble]

That's interesting, from 37 down to 29.

What solver are you using? Do you have a link? I'd like to check it out.

Your 39-mover for the qqwref position seems to have flipped up-down and one other pair of sides. No matter, if a more direct scramble involves a rotation or 2, so be it. I will feed it into OO_4x4x4 when I get a chance. I am having it crank on something for the time being. I'm just curious to see if the 7-turns-from-solved center database has a chance (doubt it, too far away) but I am pretty sure when I complete the 14-turns database, it will be of some help

It is my own solver that I developed in order to achieve this which at the moment I have not shared - sorry:

Thanks for observing the adjacent opposite double layer turns that could be optimized. I was aware that my solver occasionally does this because I've seen it do it with a physical cube on many occasions It is because it assumes a fixed orientation for the colors (since it evolved from my 3x3x3 algorithms that had fixed orientation owing to the centre pieces and does not have the concept of tilting as part of its solution! I keep meaning to get round to making the optimization to combine moves like this and replace them with tilts or, better still, allow it to search directly for solutions with the final color placement in any orientation since there may be more direct solutions to do that than simply combining these moves with my existing algorithm.

Edit:

Wow, great solutions! I'm glad mine turned out somewhat difficult I feel like reduction of centers and edges together (as you seem to be doing) and then an optimal 3x3x3 stage is probably one of the best ways to go for suboptimal 4x4x4 solving. Of course, looking directly for an optimal solution is probably way out of reach.

Thanks My algorithm does not reduce edges and centres together. It does have a separate centers phase followed by an edge-pairing phase but in the same way that my (sub-optimal) 3x3x3 solver makes multiple searches starting with different attempts at each phase, it can find "lucky" solutions for the centres phase that allows it to find a "simple" edge-pairing phase. It is this behavior that probably looks like it is solving both together but I would suggest it is really solving the centers in such a way that "happens" to pair some of the edges

And yes, I agree that a direct search for an optimal solution is currently way out of reach until someone has an insight into the group theory behind it that could help prune the search optimally or we manage to create quantum computers on a large scale?

 

[unsolved]

I keep meaning to get round to making the optimization to combine moves like this and replace them with tilts or, better still, allow it to search directly for solutions with the final color placement in any orientation since there may be more direct solutions to do that than simply combining these moves with my existing algorithm.

I believe the fastest way to do it is using 64-bit bitboards to detect the solved state, like I am doing now. I can "check" all 24 solved states with one instruction. No flipping of the cube, no calling conversion data structures. My 4x4x4 cube is constructed using only 6 variables, 64-bits each, one for each face. Each "sticker" is 4-bits: 0010 for top, 0011 for right, 0101 for front... etc, with 1101 for bottom (all primes in base 10). So I can check if a face is solved by testing if the cube.whatever_face == 0x222222222222222 or 0x3333333333333333 .... 0xDDDDDDDDDDDDDDDD. So my compound instruction tests cube.top = 0x22..., 0x33..., 0x55...,0x77..., 0xBB... or 0xDD..., ditto for right, front, bottom, left, back. It executes very quickly.

And yes, I agree that a direct search for an optimal solution is currently way out of reach until someone has an insight into the group theory behind it that could help prune the search optimally or we manage to create quantum computers on a large scale?

There is hope. Remember, we just need to come up with an approach. It is obvious a great deal of pruning is needed. One of the questions I have been asking is, "Can pruning techniques be combined in a non-hazardous way?" Well, we know I have already come up with a hazardous solution despite the fact that the over-aggressive pruning solved a 22-ply "snake" position in under one minute (and offered a few interesting non-regurgitated version of the scramble).

The answer to the question is: yes! Consider this example:

We see look-ahead search and back-end pruning being combined successfully. Note this is different from Bruce's forward pruning of the 2x2x2 corners data. Once I add this 3rd type of pruning to these two pruning mechanisms, the search depths shown will probably be amazing.

I only need to generate one-ply worth of moves to see up to ply 6 when I have the 5-Turns-From-Solved database probed in RAM. In the diagram, I only have the 3-TFS loaded in RAM. Basically, for the cost of spawning 64-bit hash numbers and probing an O(1) hash table implementation, I get up to 5 plies of search. A very good trade.

Next, look at [Solution 0001]. It is during the 10th ply, and I only had to generate 7 plies' worth of nodes, yet it found a 13-ply solution! How? It probed the 6-Turns-From-Solution database that features positions where only centers are in need of solving, and it found a matching position. So, even from "ply 7" which is really "ply 10" when you are using a 3-TFS database, I can look ahead even further by using a specialized database I can query IF there is a "ring" of corners and edges solved (I don't need to call this database otherwise).

So, with enough tricks like these, we can shave up to 12-plies off searches for now. I am in the process of building larger center databases, and have enough resources to get to 10-TFS on my own. Coupled with an 11-ply max reduction with 2x2x2 corner pruning, and the 5-TFS database, there is a chance for a 26-ply reduction in search.