God's number is...

[rokicki]

FMC vs God's Number

Anyone have an estimate for the total number of FMC competitions that have been held, worldwide, ever?

I would be surprised if, assuming random choice of positions, *any* of the positions in any of the FMC competitions have been at distance 20. Those positions are quite rare.

Indeed, almost certainly most have been at distance 18.

Nonetheless, it's absolutely amazing to me how well FMC competitors manage to do.

 

[Cubenovice]

1 you should be able to extract the official FMC events from the WCA database which can be downloaded from the WCA site.
2 we are currently at round 371 at fmc.mustcube.net
3 the weekly comp on the forum has several years of FMC

there are propbably some more online comps (speedcubers.de, ..., ...)

 

[Stefan]

In the WCA database it looks like 304 scrambles. Though in the recent parallel Chinese fewest moves competitions, maybe they used the same scrambles?

Indeed, almost certainly most have been at distance 18.

If we assume 1000 scrambles, what's the probability for that?

 

[rokicki]

Probabilities

We only have an approximate distance distribution above 16,
but it uses a million sample points so it's probably not too
far off.

Probability of none being distance 20 (assuming all are random
and 1000 samples): probably somewhere around 1-1e-8
(that is, 0.99999999, or eight nines).

Probability of most being distance 18: quite a bit higher than
eight nines; about 67% of all positions are 18, and 1000 is a
high number of samples. I get about 1-1e-28, or 28 nines.

 

[Julian]

God's Number is 20...but the FMC WR is 22, proving that humans aren't perfect.

Yes, I am a Christian.

I am baffled by this post.

 

[rk960925]

I think it's whatever the length of the scramble is because God can't solve it shorter than the scramble.
Or maybe he can. lol

 

[Jaycee]

I think it's whatever the length of the scramble is because God can't solve it shorter than the scramble.
Or maybe he can. lol

50 move scramble?

All positions can be solved in 20 moves or less.

 

[Ranzha]

I think it's whatever the length of the scramble is because God can't solve it shorter than the scramble.
Or maybe he can. lol

Try this:
F R U' R' U' R U R' F' R U R' U' R' F R F' (17)
R2 U' R2 U' R2 U y' R U R' B2' R U' R' (13)
You were saying?

 

[Christopher Mowla]

This might be pointless, but as a consequence of me currently solving mrCage's commutator problem (I'm making progress, but it's slow and I'm not working on it very often), I can solve the nxnxn cube in 2-3 phases. (Assuming that the middle edges and corners can be solved with one commutator) (2 phases if there are no slices with an odd permutation or 3 if some or all of them are). But if all even permutations (and orientations) of the nxnxn cube can be solved with one commutator, then....

Since all even permutation cycle classes for:
8 objects (corners) can be solved with two iterations of 3 2-cycles,
12 objects (middle edges) can be solved with two iterations of 5 2-cycles,
24 objects (wing edges and all non-fixed center orbits) can be solved with two iterations of 11 2-cycles

We can establish an upperbound for the nxnxn cube to be twice the length of the case(s) which require the longest optimal maneuver which does some 3 2-cycle sequence, some 5 2-cycle sequence, and some 11 2-cycle sequence (in all orbits of pieces besides the corner and middle edge orbits) + at most floor(n/2) slice quarter turns (we first do a quarter turn to every slice which has an odd permutation to get the cube into the commutator subgroup).

In other words, if we wanted to calculate the upperbound for the 3x3x3 using this approach (we already know God's number for the 3x3x3, of course), we would need to solve all {3 2-cycle of corners, 5 2-cycle of middle edges} positions (including all orientations of corners and middle edges) and then the upperbound would be twice the length of the case(s) which require the longest optimal maneuver + 1. One such position is generated by the maneuver L2 F' L2 U2 F2 U2 F' L2 F2 U2 F D2 R2 B2. I don't know if this alg is move optimal (cube explorer is too slow), but assuming that it is and assuming that this is one of the worst {3 2-cycle of corners, 5 2-cycle of middle edges} as far as required moves go, then the upperbound for the 3x3x3 would be 2(14)+1 = 29, for example.

It would be a lot of computing, but, taking the 11 2-cycles for 24 objects, for example, we would "only" need to solve (3794809718700/24!)100 = 6.116*10^-10% of the permutations for each set of 24 objects...(well this percentage might be off due to the symmetries of the cube, but it might be in the ballpark). So instead of having 24!^2 positions to test for the 4x4x4 (ignoring the corners at the moment) (which has one wing edge orbit and one X-center orbit), we would need to test (3794809718700)^2 positions.

Of course for non-fixed center pieces on the regular nxnxn cube, we can treat them to be a variety of cycle classes since there are 4 of each color in every orbit, and this complicates things.

I'm not sure if this approach would generate smaller upperbounds than "trivial" approaches which have already been known, but I just thought I should mention it, especially for cube sizes larger than those which we have non-trivial upperbounds for. I have no idea if a product of disjoint 2-cycles are easy cycle classes to solve optimally, but if they are, this approach could be worth while.

 

[cuBerBruce]

(see spoiler)

Spoiler

This might be pointless, but as a consequence of me currently solving mrCage's commutator problem (I'm making progress, but it's slow and I'm not working on it very often), I can solve the nxnxn cube in 2-3 phases. (Assuming that the middle edges and corners can be solved with one commutator) (2 phases if there are no slices with an odd permutation or 3 if some or all of them are). But if all even permutations (and orientations) of the nxnxn cube can be solved with one commutator, then....

Since all even permutation cycle classes for:
8 objects (corners) can be solved with two iterations of 3 2-cycles,
12 objects (middle edges) can be solved with two iterations of 5 2-cycles,
24 objects (wing edges and all non-fixed center orbits) can be solved with two iterations of 11 2-cycles

We can establish an upperbound for the nxnxn cube to be twice the length of the case(s) which require the longest optimal maneuver which does some 3 2-cycle sequence, some 5 2-cycle sequence, and some 11 2-cycle sequence (in all orbits of pieces besides the corner and middle edge orbits) + at most floor(n/2) slice quarter turns (we first do a quarter turn to every slice which has an odd permutation to get the cube into the commutator subgroup).

In other words, if we wanted to calculate the upperbound for the 3x3x3 using this approach (we already know God's number for the 3x3x3, of course), we would need to solve all {3 2-cycle of corners, 5 2-cycle of middle edges} positions (including all orientations of corners and middle edges) and then the upperbound would be twice the length of the case(s) which require the longest optimal maneuver + 1. One such position is generated by the maneuver L2 F' L2 U2 F2 U2 F' L2 F2 U2 F D2 R2 B2. I don't know if this alg is move optimal (cube explorer is too slow), but assuming that it is and assuming that this is one of the worst {3 2-cycle of corners, 5 2-cycle of middle edges} as far as required moves go, then the upperbound for the 3x3x3 would be 2(14)+1 = 29, for example.

It would be a lot of computing, but, taking the 11 2-cycles for 24 objects, for example, we would "only" need to solve (3794809718700/24!)100 = 6.116*10^-10% of the permutations for each set of 24 objects...(well this percentage might be off due to the symmetries of the cube, but it might be in the ballpark). So instead of having 24!^2 positions to test for the 4x4x4 (ignoring the corners at the moment) (which has one wing edge orbit and one X-center orbit), we would need to test (3794809718700)^2 positions.

Of course for non-fixed center pieces on the regular nxnxn cube, we can treat them to be a variety of cycle classes since there are 4 of each color in every orbit, and this complicates things.

I'm not sure if this approach would generate smaller upperbounds than "trivial" approaches which have already been known, but I just thought I should mention it, especially for cube sizes larger than those which we have non-trivial upperbounds for. I have no idea if a product of disjoint 2-cycles are easy cycle classes to solve optimally, but if they are, this approach could be worth while.

I note that the position L2 F' L2 U2 F2 U2 F' L2 F2 U2 F D2 R2 B2 is just two moves away from a position that is only a 2-cycle of corners and a 2-cycle of edges. Thus, I would guess it's more like a near-best case for its cycle structure than a near worst-case.

Around 2/3 of all 3x3x3 cube positions require 18 moves to solve optimally. I would tend to guess some of the positions with the cycle structures cmowla mentioned will require that many moves. Thus, it wouldn't surprise me if the upper bound result would be something more like 36. (I just tried conjugating the above with a rather arbitrary 5-move maneuver, F R' D L F), and this resulted in an 18f* position. This suggests that 18f* positions are probably very common for this particular cycle structure.)

In general, we expect God's number for an nxnxn cube to be only "slightly more" than the peak distance. Thus, I think this will generally produce a bound nearly twice the actual value of God's number, not to mention that for even relatively small n, the number of configurations to solve gets extraordinarily large. So you might have to consider solving only two or even one orbit at a time, and this would result in bounds an increasingly larger factor off from God's number as n increases. While this may be an interesting approach at producing an upper bound on God's number, I think it is not going to get as good a result as other more conventional approaches.

I find that the position cmowla gave is actually 14f*: U2 F D' L2 U B' U' B D2 B' D2 L2 F' D'

I note that applying U2 D2 gives a 13f* position, a 2-cycle of corners and a 2-cycle of edges. I also note that applying D2 (R2 U2)3 results in N-perm. I noticed when I solved all of the PLL configurations (including all AUF cases) optimally, that the N-perms took notoriously long to solve, despite a relative low move count. Since cmowla's position is somewhat related to N-perm, this would seem to have something to do with why Cube Explorer takes so long to solve that position optimally.

 

[Christopher Mowla]

A Simple Algorithm for Approximating God's Number

Hey guys,

The following is just another one of my crazy approximations of god's number (I think it works best with h-b move metric, which I think is OBTM), but it is based off of such a simple idea, and the results seem to be very reasonable, that I thought I should just post it before I forget it.

---

Algorithm
​

Let's let a formula which gives the number of positions of the nxnxn cube be called \( f\left( n \right) \), then I "claim" that god's number is within a small proximity of the result from using the following algorithm.

[1] Choose a cube size for which you want to approximate god's number for in OBTM and call it N.
[2] Evaluate \( \left\lfloor \text{Log}_{10}\left[ f\left( N \right) \right]+0.5 \right\rfloor \) to get the number of digits of \( f\left( N \right) \).
[3] Now, by experimentation, substitute values for k in \( \left\lfloor \text{Log}_{10}\left[ k! \right]+0.5 \right\rfloor \) to try to match the value calculated in step [2]. Choose k + 1 if k is smaller than the result from [2] and k + 1 is larger than the result from [2].

The God's number approximation will be the value of k which is obtained in step [3].

---

Formula
​

Using this approximation of the number of digits of k! and using Mathematica, I get the following formula which "calculates the lower and upperbound" for a cube of size N.

\( \text{God }\!\!'\!\!\text{ sNo.}\left( n \right)=\left\lfloor \frac{\left\lfloor \text{Log}_{10}\left[ f\left( n \right) \right]+0.5 \right\rfloor \left( \ln \left( 2 \right)+\ln \left( 5 \right) \right)}{\text{ProductLog}\left[ \frac{1}{b}\left\lfloor \text{Log}_{10}\left[ f\left( n \right) \right]+0.5 \right\rfloor \left( \ln \left( 2 \right)+\ln \left( 5 \right) \right) \right]} \right\rfloor \)​

, where: ProductLog[x] is the inverse function of \( xe^{x} \),
choose \( b=2 \) to get the "lowerbound" and choose \( b=3 \) to get the "upperbound".
, and again, \( f\left( n \right) \) is any number of positions formula for cube size n.

This formula is only necessary for very large n, and its purpose is to give you an interval where to start testing k values when finding the number of digits k! has (which is step [3] of the algorithm).

---

Results from the Algorithm and the Formula
​

Below, "GN" is the "actual" God's number approximation using the algorithm, and the bracketed pair is the lowerbound and upperbound achieved from the formula.

n=2, {10,11}, GN = 10
n=3, {20,22}, GN = 21
n=4, {36,40}, GN = 39
n=5, {52,57}, GN = 56
n=6, {73,81}, GN = 79
n=7, {95,103}, GN = 101
n=8, {122,132}, GN = 129
n=9, {148,160}, GN = 157
n=10, {179,193}, GN = 189
n=11, {210,226}, GN = 222
n=12, {245,263}, GN = 259
n=13, {281,301}, GN = 296
n=14, {321,343}, GN = 338
n=15, {360,385}, GN = 379
n=16, {404,432}, GN = 425
n=17, {448,478}, GN = 471
n=18, {496,529}, GN = 521
n=19, {544,580}, GN = 571
n=20, {596,635}, GN = 625
n=100, {10344,10801}, GN = 10687
n=1000, {698895,720084}, GN = 714818
n=1001, {700192,721417}, GN = 716142
​

---

Comment
​

I can see that my approximation for n = 1001 is smaller than qqwref's lowerbound of 981766, but I'm not sure exactly if his was correct.

 

[qqwref]

You call that simple?!?

Also, iirc it's known that God's Number is Θ(n^2/log n) - how does this formula compare? It's really hard to tell with all the floors and the ProductLog and stuff. And it sounds like you're pretty much just finding the value of k for which the k! has about the same number of digits as the number of positions of the cube. For instance the 7x7x7 has ~10^160 positions and 101! is ~10^160. But surely factorials have nothing to do with the number of moves it takes to get to a given state, right?

What worries me is that there is really no theoretical basis for your formula (and that the "upper bound" and "lower bound" you give are not upper and lower bounds of God's Number at all, they're just values from slightly different versions of your formula). You sort of just pulled an idea out of thin air based on some numerical coincedences. And remember that you actually only have two data points here (two known God's Numbers), so if you're just trying to fit a function to the data, it'd be extremely easy to find one that looks like it works. Unless you have some reason, based on the properties of cube moves and cube pieces, I don't see any reason not to disregard this formula and the numbers it produces.

 

[Christopher Mowla]

And it sounds like you're pretty much just finding the value of k for which the k! has about the same number of digits as the number of positions of the cube.

That's exactly right.

But surely factorials have nothing to do with the number of moves it takes to get to a given state, right?

Probably not.

What worries me is that there is really no theoretical basis for your formula (and that the "upper bound" and "lower bound" you give are not upper and lower bounds of God's Number at all, they're just values from slightly different versions of your formula). You sort of just pulled an idea out of thin air based on some numerical coincidences.

That's exactly right. However, the results from the formula are not the lower and upperbounds talked about when referring to God's number, but the lower or upperbounds which we choose for k in k! without having to "guess" too much to get the approximation for God's number. The formula is mainly used to aid us to quickly find the value of k in k! such that the number of digits it contains matches the number of digits of f(N).

And remember that you actually only have two data points here (two known God's Numbers), so if you're just trying to fit a function to the data, it'd be extremely easy to find one that looks like it works.

I know. This is the third or fourth formula I've found so far like this.

Unless you have some reason, based on the properties of cube moves and cube pieces, I don't see any reason not to disregard this formula and the numbers it produces.

I wasn't asking you or anyone to take this seriously. I was mainly posting it for entertainment purposes.

Lastly, yes, I call this algorithm simple. The formula isn't exactly, but the algorithm (idea) is very simple. I thought this was a fun way to directly use the number of positions to create an approximation.

 

[qqwref]

It's not a working approximation though, it's just a function that matches the two known values (if you fudge it a bit) and roughly increases as n increases. If someone really wants to get a good sense of what God's Number might be for larger cubes, this is not a good starting point.

 

[IRNjuggle28]

Do we have ideas of what positions are likely to be hardest to solve on NxNxN? On 3x3, for example, people had theorized that superflip was an extremely bad position before brute force solvers proved that. Are there positions on 4x4, or 5x5, or NxN for that matter, that are likely to be hard to solve for theory based reasons? It seems like finding a dozen or so 4x4 positions that are each going to require lengthy solutions for their own individual reasons, and brute forcing them, could at least give an reasonable estimate for God's number.

Another idea that might be worth considering is brute forcing a bunch of random 4x4 permutations, and using that approximate average solution length to generate a guess at 4x4 God's number by examining the standard deviation of solution length as well as the God's numbers of 2x2 and 3x3 and extrapolating.

The reason I'm mostly thinking of this for 4x4 is that I know that things get harder and harder to brute force the bigger they get, and that these estimates will get inaccurate fast if they're extrapolated far enough. So, with those things in mind, are either of these ideas useful? The idea is that conclusions based on vague or approximated data is more likely to be accurate than conclusions based on vague or approximated theory.

 

[qqwref]

I don't think we have any educated guesses about what positions are the hardest to solve, and we are nowhere near being able to brute force optimally solve random 4x4x4 positions anyway. (It's about 10^26 times as hard as brute force optimally solving random 3x3x3 positions.) I'm sure if it was practical to find optimal solutions to 4x4x4 states people would already have done a bunch of random scrambles and difficult-looking pretty patterns, and posted the results.

 

[rokicki]

I estimate that optimally solving a *single* randomly chosen 4x4x4 position would take
roughly as much time as computing God's number for the 3x3x3, based on current
knowledge and technology.

I am also pretty sure we will come up with ideas and techniques to reduce this.

Indeed, pushing this envelope is a big reason I'm sponsoring the Computer/Human
4x4x4 FMC challenge (which ends tomorrow at noon Pacific time.)