• 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!

Predicting God's Number for Higher Order Cubes

Joined
Jun 17, 2011
Messages
148
Location
Dublin, Ireland
WCA
2012HAMM01
YouTube
Visit Channel
I plotted the natural log of the number of states per moves to solve, and got a nice trend.

Taking data from this site for the 2x2x2
c64489583c22a8a2dc13a5c490a3fdf9.png

Taking data from cube20 and making a similar plot
c3ec3c0123aeb767bdc08bf1d9195815.png

We can see from the graph that the 3x3x3 approximations look like they might underestimate 16 moves and over estimate 18 moves, but they are otherwise fairly accurate.

Plotting using the same function for 2x2x2 htm gives a similar looking curve.

Is there any reason this trend shouldn't continue for higher order cubes? Is there any data for the number of states per optimal moves to solve for 4x4x4 cubes?

Code:
0    1    0
1    6    1.791759469
2    27    3.295836866
3    120    4.787491743
4    534    6.280395839
5    2256    7.721348613
6    8969    9.101529466
7    33058    10.40601887
8    114149    11.64525989
9    360508    12.79526943
10    930588    13.74357192
11    1350852    14.11624606
12    782536    13.57029521
13    90280    11.41067123
14    276    5.620400866
Code:
0    1    0
1    18    2.890371758
2    243    5.493061443
3    3240    8.083328609
4    43239    10.67449814
5    574908    13.26196531
6    7618438    15.84608192
7    100803036    18.42867903
8    1332343288    21.0102051
9    17596479795    23.59096471
10    2.32248E+11    26.17107188
11    3.06329E+12    28.75051023
12    4.03744E+13    31.32921767
13    5.31653E+14    33.90701292
14    6.98932E+15    36.48315975
15    9.13651E+16    39.05364047
16    1.1E+18    41.54184185
17    1.2E+19    43.93143832
18    2.9E+19    44.8138275
19    1.5E+18    41.85199678
20    490000000    20.00991595
 

AlphaSheep

Member
Joined
Nov 11, 2014
Messages
1,083
Location
Gauteng, South Africa
WCA
2014GRAY03
I'm not sure what trend you're talking about but just to explain what you're looking at, there are two things that determine how many states are at a given depth.
  1. The number of possible move combinations at a depth. This grows exponentially, so it will appear as a straight line on a log plot.
  2. The number of states that have not yet been reached. This starts off as the maximum number of states and drops off to zero at God's number.
What your graphs show is a long linear part where 1 dominates (i.e. adding a move is likely to produce a new state) followed by a rapid drop off where 2 dominates (adding a new move is likely to reach a state that another move sequence already reached). All NxNxN cubes have this behaviour, and so do all puzzles without weird move restrictions.

1 is very easy to calculate for higher order cubes, although the numbers get very large very quickly. I don't know if you can calculate 2 without brute force, but you can easily get a lower bound using the total number of states and subtract the number of move sequences calculated in 1. That can give you a lower bound on God's number for any puzzle.

No, there's not much information for the number of states at each move depth on 4x4 and up. In fact, even the 3x3 data you give is incomplete for the last depths.
 
Joined
Jun 17, 2011
Messages
148
Location
Dublin, Ireland
WCA
2012HAMM01
YouTube
Visit Channel
Thanks for the link, that helps a lot. Bruteforcing would take a long long time yes, but an approximation could be gotten by only working on a subset of the total possible states, for instance generating (uniformly?) and solving a large amount of 4x4x4 states and extending the reusults. My aim is only to have a guess that is better than the current lower bounds, not an exact figure.
 

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,876
Optimally solving even one random state on 4x4x4 is expected to require years of CPU time, as mentioned on cube20.org, and the situation only gets worse on larger cubes. However, I think that by solving just a handful of random 4x4x4 states optimally, we should be able to improve the lower bound by a few moves.

(We do have upper bounds of 55 OBTM for 4x4x4 and 143 OBTM for the 5x5x5; I don't know if larger cubes have been analysed in detail.)
 
Last edited:

stoic

Premium Member
Joined
Feb 17, 2011
Messages
1,016
Location
Northern Ireland
WCA
2013DEAR01
But with more modern software does it still take years to produce an answer for a single random cube state?
Improving the software can only do so much; actually processing the required number of calculations is a hardware problem.

I'd be interested if anyone has attempted a guess at how long we should have to wait until Moore's Law kicks in sufficiently.
 

tseitsei

Member
Joined
Jan 12, 2012
Messages
1,374
Location
Tampere, Finland
WCA
2012LEHT01
Improving the software can only do so much; actually processing the required number of calculations is a hardware problem.

I'd be interested if anyone has attempted a guess at how long we should have to wait until Moore's Law kicks in sufficiently.
Moore's law will stop working soon since transistors are getting so small that the size of atoms is actually becoming a limiting factor sometime soon.

IMO our hopes lies more with quantum computers... They should be great for this kind of thing since we should be able to simultaneously test many many move(sequences) instead of just one at the time. But I'm not an expert on that subject so I might be totally wrong here...
 
Top