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

[Username]

Is there an app or something that can tell you you're move count or is it that you have to do it manually?

The app wouldn't work if you didn't type your solution, and when typing it you might make a mistake and not get the correct movecount. Counting by hand is the safest (I count in tens, ....Thirty, one, two, three, four, five, six, seven, eight, nine, fourty, one, two....)

I was at about 90 after reduction was finished, that + about 50 moves speedsolve + parity goes to about 150-170

 

[IAssemble]

The app wouldn't work if you didn't type your solution, and when typing it you might make a mistake and not get the correct movecount. Counting by hand is the safest (I count in tens, ....Thirty, one, two, three, four, five, six, seven, eight, nine, fourty, one, two....)

I was at about 90 after reduction was finished, that + about 50 moves speedsolve + parity goes to about 150-170

That sounds pretty reasonable. I think I already mentioned that MultiCuber 3 manages to solve middles, pair edges and avoid parity in about 30 turns and then solves the 3x3x3 in about a further 20

Last time I counted, about the time I started working on the efficient software algorithm, I recall it took me well over 200!

 

[LNZ]

Out of interest I did a 4x4 solve and counted the moves. I used a black Eastsheen cube.

I got 159 moves and that included both OLL and PLL parities.

I used keyhole F3L, which is my preffered method and reduction with 2-look OLL and 2-look PLL with some full PLL.

 

[IAssemble]

126 while trying to use fewer moves than in a speedsolve
no parity

That's very good! Far better than me

 

[Ninja Storm]

125 with no parity whatsoever.

 

[qq280833822]

30 moves' reduction is cool. Would you mind telling us how the algorithm works?

 

[IAssemble]

30 moves' reduction is cool. Would you mind telling us how the algorithm works?

Thanks. Sorry, I am not sharing the precise details at the moment but I will summarize it:

The algorithm is lookup table driven (as you would expect). There is about 600MB of data in total in the lookup tables. There is a significant amount of searching done to find a good solution. For example, in 2s x 4 CPUs, MultiCuber 3 attempts about 100,000 solutions and picks the shortest.

The order in which it solves the cube is fairly standard:

1) simultaneously solve two opposite middles
2) simultaneously solve remaining four middles
3) pair all edges (in arbitrary positions) checking parity. This may require several passes but typically only 2 and often just 1
4+5) solve 3x3x3 using my own 2-phase algorithm that I used on CubeStormer II etc.

So overall it is really a 5-phase solver I guess.

Phases 1) and 4) can find an arbitrary numbers of solutions, shortest first. Phase 3) can usually solve in a number of different ways

The solver keeps trying different solutions in phases 1), 3) (ignoring cases with incorrect 3x3x3 parity) and 4) until it finds a complete solution that is "good enough" based on a move count or time-out etc.

 

[tx789]

50 moves is so few on 4x4

 

[Username]

Tried a solve with a bit of FMC in it, but it was linear and basically pure reduction

122 moves no parity

 

[IAssemble]

50 moves is so few on 4x4

Tried a solve with a bit of FMC in it, but it was linear and basically pure reduction

122 moves no parity

Thanks for the information. I think that is pretty good.

 

[Mike Hughey]

For a little while we had 4x4x4 fewest moves as an event in our speedsolving.com weekly competition. It became evident quite quickly that 100 moves on 4x4x4 was equivalent to 35-40 moves on 3x3x3, and 80 moves on 4x4x4 was more like the 30-move target that people often shoot for with 3x3x3 fewest moves. I did it most weeks, and averaged around 95 moves. So I guess the typical proportion of human to computer moves is roughly similar on 4x4x4 and 3x3x3, with humans being about half as efficient as computers, on a move count basis.

 

[ben1996123]

find gods number pls !!!

 

[kcl]

I got a 104 move solution with easy centers, an edge done, and a PLL skip

 

[IAssemble]

find gods number pls !!!

Is that a serious question?

I have not researched this extensively so please forgive me if anything below is incorrect...

There is a huge difference between developing an algorithm that discovers efficient solutions and one which has finds provably optimal solutions or has a provable upper bound.

Either or both those properties might be useful, but not sufficient by themselves to help find "God's number" for the 4x4x4.

If a similar style of proof was used as for the 3x3x3, it would have to include some reasoning about the solution space to break it down into a small enough subset of problems to "brute force" using an efficient algorithm. It would also be need a provable lower bound (that happened to also be the upper bound).

My understanding from what I've seen, is that the current lower bound for the 4x4x4 is probably very weak (probably lower than the actual upper bound) and there has not yet been a breakthrough in being able to reason about sub-dividing the solution space to make a proof anywhere near practical.

 

[Kirjava]

What *are* the current lower and upper bounds for 4x4x4?

 

[windhero]

I averaged around 130 moves with regular Yau-duction and just a tad better lookahead (which I dont count as FMC since I could still do a solve like that in way under 2 minutes easy). Basically intuitive Yau-solves with 130ish moves on average, a solve like the ones I do when I speedsolve.

None of the cases had any parity at all, so thats like +10-27 moves on average give or take (10 for only PLL, 17 for only OLL, 27 for both)

EDIT: Now I know whats stopping me from a sub 1 solve. Even at only 3TPS average I'd be a 50 second solver ,_,

 

[whauk]

@IAssemble:
could you look up the longest solution for every phase of your algorithm? that should give us a reasonable upper bound.

 

[IAssemble]

@IAssemble:
could you look up the longest solution for every phase of your algorithm? that should give us a reasonable upper bound.

You make an assumption that each phase of my algorithm is an exhaustive lookup table for all possible positions with a sequence of moves associated with it... it doesn't! ;-)

I cannot easily bound phases 1) or 4) this way and it would need some work for 3) to determine the worst case number of passes... (and there is a trick I use between 1) and 2) that would need to be considered)

Although actually I would use 20 for a combination of 4) and 5) as they could be replaced by an optimal 3x3x3 solver and we know God's number of 3x3x3 is 20

Maybe I will think about doing this but I suspect it would be *much* higher than the average 51 that it achieves in practice...

 

[antoineccantin]

Linear 4x4 FMC:

23 centers
35 edges
59 3x3 (PLL parity)
= 117 moves

 

[uberCuber]

Solving as if a speedsolve: 132 moves, Yau method, PLL parity

I started to try a linear FMC, but CN Yau confuses the living hell out of me, so I gave up >_>