• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

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

Username

Member
Joined
Dec 15, 2012
Messages
3,418
Location
Finland
WCA
2013JOKI01
YouTube
Visit Channel
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

Member
Joined
May 5, 2010
Messages
248
YouTube
Visit Channel
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

Premium Member
Joined
Jul 13, 2009
Messages
595
Location
Adelaide, SA
YouTube
Visit Channel
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

Member
Joined
May 5, 2010
Messages
248
YouTube
Visit Channel
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.
 

Mike Hughey

Administrator
Staff member
Joined
Jun 7, 2007
Messages
11,305
Location
Indianapolis
WCA
2007HUGH01
SS Competition Results
YouTube
Visit Channel
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.
 

IAssemble

Member
Joined
May 5, 2010
Messages
248
YouTube
Visit Channel
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.
 

windhero

Member
Joined
May 10, 2013
Messages
777
Location
Finland
WCA
2013COCO01
YouTube
Visit Channel
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 ,_,
 
Last edited:

IAssemble

Member
Joined
May 5, 2010
Messages
248
YouTube
Visit Channel
@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...
 
Top