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

[Stefan]

Benchmarks dont tell everything but just by the contrast between the setups you can imagine how a setup with 2x 6-core 12k point benchmarked CPUs perform against a single quadcore at 5.8k benchmark points.

About 2*12k/5.8k if it scales well, so maybe factor 4. Don't know why you mention the number of cores.

Also this is what a super computer means in 2012
Thats 72,000 cpus.

No. 72288 cores, not cpus. It's 9036 cpus.

I dont know how many operations one 4x4 case requires but I suppose it would be possible to do it even now.

We're talking about roughly 10^26 as many states and they're more complicated than the 3x3's. If you use a million cpus and if it scales well, you're still a factor of 10^19 away, plus the more complicated states.

Regular desktop CPUs evolve at an equal rate.

No. The super computers owe their performance increase to a large degree to the number of cpus, not just to individual cpu performance increases.

 

[windhero]

About 2*12k/5.8k if it scales well, so maybe factor 4. Don't know why you mention the number of cores.



No. 72288 cores, not cpus. It's 9036 cpus.



We're talking about roughly 10^26 as many states and they're more complicated than the 3x3's. If you use a million cpus and if it scales well, you're still a factor of 10^19 away, plus the more complicated states.



No. The super computers owe their performance increase to a large degree to the number of cpus, not just to individual cpu performance increases.

Yes. Read what I said. I said that regular desktop CPUs evolve at an equal rate. That is because super computers use the same cpus, just in bigger amounts. You can compare desktop computers from a few years back and see a radical change in computing power. I know it's about more cpus in supercomputers, but my first example was exactly about that improvement in computing power of single cpus.

And I believe I aknowledged the difference in magnitude of the two, but I still wouldnt say it's impossible. I'm not saying it should be done or anything of the sort. I dont really believe anyone with the funds would want to invest in such a project. Those interested dont have the excess cash. Typical situation.

The benchmark results do not scale very well, compare points between the cpus at stock voltages and overclocked ones. More cores = more operations so I'd say it should help. Just needs a good script that can take advantage of those multiple cores.

All this is just wild speculation since no one will probably ever do this all the way.

 

[jayefbe]

Windhero - you're missing the entire point. CPU-years are simply meant to give the casual observer an idea of how computationally intensive it would be to reach a solution. It's not literally how long it would take to reach a solution. Your arguments are actually supporting their usage.

 

[Stefan]

Read what I said.

I had. But ok, let's do it again:

The best in 2008 was at 1.7 PFlops. The best of 2013 is at 33.8PFlops. I'd say they evolve very fast.

Regular desktop CPUs evolve at an equal rate.

That's a factor of 19.9 over five years. The X9770 was realeased in 2008 and has 4815 points (and I'm not even sure it was the best). Please show me today's desktop processor with 96000 points. Max I see is 12942. That's a factor of 2.7, not 19.9. And hardly seems "radical", btw.

 

[IAssemble]

Yes. For example, on the 4x4x4 from a given position, there are generally 4^3-1 = 63 new positions reachable from just making moves along one axis. (One layer can be regarded as a fixed reference.) The analysis uses one optimal (for the given metric) representation for reaching each of these 63 new states. So LR would not be considered distinct from RL. (But if the L face is treated as the fixed layer, a 3-layer wide R turn would be used in its place of L.)

Some of the 4^3-1 moves do not reach "new" positions. 3 of them are effectively the same position where the whole cube is re-orientated. I note in the thread to which you refer, it states "Also, the orientation of the puzzle is considered not to matter."

 

[cuBerBruce]

Some of the 4^3-1 moves do not reach "new" positions. 3 of them are effectively the same position where the whole cube is re-orientated.

No, the 4^3-1 moves result in distinct positions because the 4th layer is regarded as a fixed reference which serves to identify the orientation of the cube. If we didn't use 1 layer as a fixed reference, we would have 4^4-1 positions, and then obviously some of those would be equivalent when we regard the orientation of the cube not to matter.

 

[qqwref]

Another way to say what Bruce is saying: since 4x4x4 has no fixed centers one easy way to fix the orientation is to fix the position of one corner. Then a single-layer turn with that corner can be thought of as a 3-layer turn on the opposite face. From that perspective it's easy to see that there are always 4^3-1 possible moves on each axis (in axial turn metric).

 

[windhero]

Alright on another note. We know that super flip is the combination on the 3x3 that requires the most moves to solve, was this discovered by the computer or by someone just figuring it out? If it's the latter can a "superflip" position be figured out for a cube of a bigger order too? Or is there any guarantee that there are no combinations that require more moves than the super flip?

 

[EMI]

Alright on another note. We know that super flip is the combination on the 3x3 that requires the most moves to solve, was this discovered by the computer or by someone just figuring it out? If it's the latter can a "superflip" position be figured out for a cube of a bigger order too? Or is there any guarantee that there are no combinations that require more moves than the super flip?

The superflip was the first position that was proven to require 20 moves to be solved. It didn't prove there were no positions that required more than 20.

 

[windhero]

Alright, thanks for clarifying.

 

[Renslay]

Actually, people who did the proof were hoping for finding a position that requires 21 moves, since that would be "the hardest position ever known so far." Fortunetly or unfortunetly, the computer said that every case can be solved in 20 moves at most.

 

[IAssemble]

No, the 4^3-1 moves result in distinct positions because the 4th layer is regarded as a fixed reference which serves to identify the orientation of the cube. If we didn't use 1 layer as a fixed reference, we would have 4^4-1 positions, and then obviously some of those would be equivalent when we regard the orientation of the cube not to matter.

Ooops. I should read and think more carefully! Yes, that makes perfect sense now.

 

[IAssemble]

Alright on another note. We know that super flip is the combination on the 3x3 that requires the most moves to solve, was this discovered by the computer or by someone just figuring it out? If it's the latter can a "superflip" position be figured out for a cube of a bigger order too? Or is there any guarantee that there are no combinations that require more moves than the super flip?

It would be interesting to find a position that is demonstrably "harder" to solve for a 4x4x4 than general random positions...

Thinking about this from an "intuitive" perspective. In some sense I can "appreciate" why superflip requires a larger number of moves than random positions - each edge has to be moved away from its neighbouring corners and then put back next to them in the opposite orientation. For a random position, many edges will start separated from their neighbouring corners and only need putting next to them in the correct orientation.

As I said, this is not based on any real mathematical principles but rather just on "intuition". However, given this, can anyone think of similar kinds of patterns on a 4x4x4 cube that have this "intuitively hard" property that could be explored at some level to see if they appear to require more moves than randomly scrambled positions? Something like a position where every edge/corner piece is next to its neighbours but in the "wrong" orientation and every middle piece is next to edges in the wrong orientation?

I am aware from a mathematical sense that superflip is unique in that there are some interesting mathematical properties: see about 2:30 onwards in this video:

Does anyone have any ideas about a position on the 4x4x4 cube that has similar mathematical properties?

 

[Stefan]

Superflip is highly symmetric, and symmetric positions apparently have a large probability of being very hard.

About 1 in 260,000,000 of all positions has symmetry.
About 1 in 275 of all hardest positions (needing 20 moves) has symmetry.

About 1 in 143,000,000,000 positions needs 20 moves.
About 1 in 150,000 symmetric positions needs 20 moves.

(Unless they already reduced the numbers by symmetry, not sure right now, but it'd be at most factor 96 or so.)

Thread with more information: http://cubezzz.dyndns.org/drupal/?q=node/view/63

I think there was some reasoning *why* symmetric positions are likelier harder, but I'm too tired to think right now. Anyway, if we could optimally solve 4x4 positions, I'd check out symmetric ones first as well.

 

[Renslay]

Does anyone have any ideas about a position on the 4x4x4 cube that has similar mathematical properties?

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

S could not permute any elements, because if it permutes an element number 1 with 2:
S = (1 2 ... k) in cyclic permutation notation,
then I can find an A such that it permute 2 but not 1 (e.g., (2 k+1 ... k+n), hence SA != AS
Consequently, S cannot effect centers.

S also cannot effect the orientation of the corners (for a similar reason, since a corner has 3 orientations; for further reasoning, look up why the superflip is the only state for SA = AS in a 3x3).

Hence, a superflip in the 4x4x4 could only affect the edges; but on a 4x4x4, edges has only permutation (you cannot flip just one single edge), hence they form a permutation. Therefore, there is no superflip on a 4x4x4.

The "original" superflip does not work here, see this for example:
case1: AS

case2: SA

 

[IAssemble]

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

S could not permute any elements, because if it permutes an element number 1 with 2:
S = (1 2 ... k) in cyclic permutation notation,
then I can find an A such that it permute 2 but not 1 (e.g., (2 k+1 ... k+n), hence SA != AS
Consequently, S cannot effect centers.

S also cannot effect the orientation of the corners (for a similar reason, since a corner has 3 orientations; for further reasoning, look up why the superflip is the only state for SA = AS in a 3x3).

Hence, a superflip in the 4x4x4 could only affect the edges; but on a 4x4x4, edges has only permutation (you cannot flip just one single edge), hence they form a permutation. Therefore, there is no superflip on a 4x4x4.

The "original" superflip does not work here, see this for example:
case1: AS

case2: SA

Thanks for this proof that position with properties similar to "superflip" cannot exist on a 4x4x4. I was coming to that conclusion myself but with less rigorous reasoning.

 

[qqwref]

I think the presence of parity on 4x4x4 may mean that perfectly symmetric patterns are relatively easy to create. I wonder if a near-symmetric pattern such as an 11-flip will have a relatively long solution.

 

[IAssemble]

I think the presence of parity on 4x4x4 may mean that perfectly symmetric patterns are relatively easy to create. I wonder if a near-symmetric pattern such as an 11-flip will have a relatively long solution.

Interesting idea.

I just tried "11-flip" with my latest 4x4x4 solver (using OBTM metrics).

For random positions it averages around 48 turns in 100s of CPU time but for "11-flip" it finds a 33 turn solution in the same time which suggests it is much easier to solve than a random solution.

Of course this result is inconclusive and it could just be that the algorithm is based on reduction so will naturally find solutions more easily for positions where the middles are solved and edges paired since it only has to find a way to fix the parity and then solve the 3x3x3 which is probably no longer in the superflip position...

Any other ideas for "hard" positions?

 

[Christopher Mowla]

Any other ideas for "hard" positions?

I know this question wasn't directed at me, but I'm curious how many moves it takes your solver to solve the following cases:
[1] Rw' U' R' U' Rw F' R' F' Rw'
[2] Lw F2 U2 l' U2 Lw U' R U l U2 l' U R' U Lw' F2 Lw'
[3] And just a "potential bad case" to check: the case generated by this set of algorithms.

 

[ben1996123]

Interesting idea.

I just tried "11-flip" with my latest 4x4x4 solver (using OBTM metrics).

For random positions it averages around 48 turns in 100s of CPU time but for "11-flip" it finds a 33 turn solution in the same time which suggests it is much easier to solve than a random solution.

Of course this result is inconclusive and it could just be that the algorithm is based on reduction so will naturally find solutions more easily for positions where the middles are solved and edges paired since it only has to find a way to fix the parity and then solve the 3x3x3 which is probably no longer in the superflip position...

Any other ideas for "hard" positions?

what was the solution and what does it find for OLL parity?