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

[2180161]

Ok, so Im not good at this whole group theory, but maybe this will spark some Ideas. What is the most efficient 4x4 method out there? What is gods number for the individual steps for that? We dont know, however, we do know that there are 36 single layer turns on the 4x4 this include and are limited to (assuming we are using HTM):R, R' R2, F, F', F2 and so forth for the outer layer turns. However, we then have the inner layer turns:r, r', r2, f, f', f2 and so forth once more. Then judging by the number of those turns, we then have 1 possible permutation that has 0 moves to solve, 36 that take one, and so forth. So wouldnt we just do the same thing we did for 3x3? I mean we know the lower bound, but not the higher. Now if we count double layer turns, so Rr as one turn, then there are even more. So if we are allowing Rr as a single turn, we then have more possible turns. this adds another 18. so it is now 36+18=54. So to find the number of permutations for 2 turns, (not counting double layer turns) we would do 36^2, which would get us 1296, which is wrong because this is allowing turns to be doubled up, so R2, R'. So instead we have to subtract 3 from 36 to get 33 so it would end up being 36*33 or 1188. We still have the wrong number. this is because we have something where we think that we could do L' R', and it would be the same as L' R', so being 18 permutations per axis and 6 axis so we do 36*33-18*6=1080 possible permutations that can be solved using 2 moves. Just the start of something, and I could go on more, but I dont feel like it right now. CORRECT ME IF I AM WRONG.

I dont know how to explain how I got it, as I havent gotten it yet, but know exactly how to find it. So let x represent the number of turns using HTM as I described in my previous post. where Rr equals two turns.
36^x-18*3x and then add those up until we get the # of permutations of the 4x4.
So a = 1 possible set of permutations, b equals another, and we would keep doing a+b+c etc. until a+b+c etc. equals 7.40*10^45
So in conclusion, there are 1117 positions that can be solved with a maximum of two moves (counting the solved one). So is this gods algorithm for a 4x4? Or am I just an idiot who thinks he knows what he is talking about?

etc is just so I wouldnt have to type out many sets.

 

[Ollie]

God's number = every single position on nxnxn can be solved in this number or less.
God's algorithm = the optimal solution for any position.

All you've done is attempt to calculate the number of positions that require 2 move or less.

tl;dr - no, you haven't.

 

[ryanj92]

etc is just so I wouldnt have to type out many sets.

You might want to read from here onwards, because i think this is what you are detailing

 

[unsolved]

I dont know how to explain how I got it, as I havent gotten it yet, but know exactly how to find it. So let x represent the number of turns using HTM as I described in my previous post. where Rr equals two turns.
36^x-18*3x and then add those up until we get the # of permutations of the 4x4.
So a = 1 possible set of permutations, b equals another, and we would keep doing a+b+c etc. until a+b+c etc. equals 7.40*10^45
So in conclusion, there are 1117 positions that can be solved with a maximum of two moves (counting the solved one). So is this gods algorithm for a 4x4? Or am I just an idiot who thinks he knows what he is talking about?

There are only 999 unique positions that are 2 turns from the solved state.

There are 36 @ depth 1.

For each of these, there are 24 times as many at depth 2.
Add to this total the 135 possible turns involving 2 parallel planes, and you have (36 x 24) + 135 = 999.

I already carried out this calculation through to depth 32, which is where the count exceeds the number of permutations. So God's Number for the 4x4x4 cannot possibly be less than 32. It is a definitive lower bound. It is probably 35 or 36 though.

 

[Chrizz]

How did you check up to depth 32 if that takes 307087377247055771290 times the age of the universe?

EDIT: I guess you haven't, you've just calculated how long it would take to check them all. Is 100 million/sec fast for modern computers?

 

[unsolved]

How did you check up to depth 32 if that takes 307087377247055771290 times the age of the universe?

The calculation is just a recursive formula. The 4x4x4 cube can be considered to have 3 separate types of move generators: Legal moves involving 1 rotating face, 2 parallel rotating faces, and 3 parallel rotating faces. A move such as U R is always permissible, but U D' is redundant because it is the same as u' d if you follow that up with a rotation y. So you have to avoid "double counting" positions that create the same cube that differ merely by a physical rotation. There are similar examples for 3 parallel face rotations.

So you have 3 formulas that give you the sum of "unique" permissible rotations, and if you add these up, you get the total move for a given depth.

if d(n) = the total moves at a given depth n, you have

d(1) = R1(1) + R2(1) + R3(1)

There is no way to make 2- or 3-turns @ depth 1 since you only have 1 move.

R1(1) = 36; R2(1) = 0; R3(1) = 0;

So d(1) = R1(1) = 36.

The next level you have to add 1-rotating face totals + 2-rotating face totals.

d(2) = R1(2) + R2(2) + R3(2)

Again, R3(2) = 0 since you can't rotate 3 parallel faces with only 2 moves.

R1(2) = 24 * d(1) = 24 * 36 = 864
R2(2) = 135

d(2) = 864 + 135 = 999

Now at depth 3, you have R3(3) = 72 for the count of legal 3-parallel rotations.

So:

R1(3) = 24 * d(2) = 24 * 999 = 23976
R2(3) = 90 * d(1) = 90 * 36 = 3240
R3(3) = 72

d(3) = 23976 + 3240 + 72 = 27288

For each depth from now on:

R1(n) = 24 * d(n-1)
R2(n) = 90 * d(n-2)
R3(n) = 48 * d(n-3)
d(n) = R1(n) + R2(n) + R3(n)

R1(4) = 24 * d(3) = 24 * 27288 = 654912
R2(4) = 90 * d(2) = 90 * 999 = 89910
R3(4) = 48 * d(1) = 48 * 36 = 1728

d(4) = 654912 + 89910 + 1728 = 746550

So you just keep feeding the numbers into this recursive formula and you get what I have shown.

There is a possible way to "improve" on these counts, and make the total slightly lower, but I don't have these coefficients yet.

Is 100 million/sec fast for modern computers?

The 4x4x4 solving program I wrote averages 20,000,000 turns/second on a slow 3.1 GHz machine.
I think, but I am not sure, that this is the fastest move generator out there. We never really did an official test.

 

[Chrizz]

The 4x4x4 solving program I wrote averages 20,000,000 turns/second on a slow 3.1 GHz machine.
I think, but I am not sure, that this is the fastest move generator out there. We never really did an official test.

So depth 9 or 10 is about as far as we can get now? So… will we ever find Gods number by brute forcing?

 

[unsolved]

So depth 9 or 10 is about as far as we can get now? So… will we ever find Gods number by brute forcing?

I can now reach depth 17 in 4 days worth of searching with my program.

I pre-load certain positions into RAM and can prune 6 turns from the end of the search (back-end pruning) and this allows the program to use forward pruning to parse through 11 plies worth of positions. So 11 + 6 = 17.

It's technical, but I am working on trying to get the program up to 20 plies. With enough RAM, it can be done.

 

[Chrizz]

I can now reach depth 17 in 4 days worth of searching with my program.

I pre-load certain positions into RAM and can prune 6 turns from the end of the search (back-end pruning) and this allows the program to use forward pruning to parse through 11 plies worth of positions. So 11 + 6 = 17.

It's technical, but I am working on trying to get the program up to 20 plies. With enough RAM, it can be done.

That's impressive! What kind of computer would be needed to find God's number?

 

[unsolved]

That's impressive! What kind of computer would be needed to find God's number?

When I first started writing my 4x4x4 program, it was slow. Not only that, it explored more nodes than it had to. It took a great deal of input from some talented minds to guide me along the way to make it better. At first, I reduced node counts by pruning from the back end. This has the best benefit of any technique since it effectively reduces the branching factor by an exponential amount. The results are also constant. By that I mean I prune the same amount from the search no matter what is being searched. This can only be true when you prune the trunk of the tree.

The tree also has branches, and leaves, much like its analog counterpart. The next undertaking I designed only the leaves to be pruned. If specific types of positions were encountered, I did not have to search any further. The search halted for that particular set of moves, which were already at a terminus, so not much was gained in the grand scheme of things. It was not a constant pruning technique, it was a variable pruning technique.

The most recent thing I implemented prunes the branches. Oddly enough, every other programmer who has a 4x4x4 program has already implemented something like this. The most common form of branch pruning is the Corners database. Since corners can only be disturbed by moves involving face turn moves, if the corners are known to be a certain distance from a solved state, then it is impossible to solve a cube with fewer moves. So, if you are in the middle of an 8-move search, and your program is building the line of play: A, B, C, D, E, F, G, H, if before generating move A the corner configuration of your cube is 9 moves from being solved, you don't have to generate ANY moves! You'll never solve it in 8 turns. Likewise, after generating Move A, if your corners can't be solved in 7 turns, no matter what moves follow, you don't have to generate them. After move B, the same is true if the corners database says the new candidate position is more than 6 turns from a solved state.

So the corners database is helpful in two ways. No unnecessary moves need to be made, and it also verifies that the necessary ones are getting you closer to the solution. You can imagine some moves you make just contribute further to the scramble.

We can use information like this to see what it would take to create a "Super Program" capable of making a solver that always finds a solution in God's Number (or better) number of moves. An insufficient scramble, and indeed, every known "alg" is an example of a cube position that can be solved in fewer than God's Number of moves.

Let's start with a speculation that God's number is 36 for the 4x4x4.

The forward end of the search must meet the back end of the search.

Right now, I have back-end data through 7 turns on my supercomputer. That means I would still have to solve the cube through a distance of 29 moves from the scramble.

But... the good news is, the deepest corners database entry is 11 turns. In the event a scramble has an 11-turn corner orientation, we can effectively chop off 11 turns from the distance.

29 - 11 = 18 turns.

The program would race through the first 10 turns because there is no 10-turn solution to the corners configuration, and now it effectively starts searching at depth 11.

But I also have a database of edge cube entries. The deepest one is 7 turns also. But, the beauty of this is, it is not entirely dependent on face turns. A combination of face turns + slices turns is required to solve most edge positions optimally. So, technically speaking, even a 7-turn edge position can be pruned. Imagine an 18-move scramble that first moves only the faces 11 times to a unique 11-turn corner database entry, then move only the slice edges 7 more times in such a way that a redundant position with fewer moves is not encountered. Hypothetically, an 18-move prune can take place. I say hypothetically because it is extremely rare but it is not impossible.

So now the program might be capable of carving 7 more turns off the search.

29 - 11 - 7 = 11 turns.

A very deep search could be achieved that would solve this position, but those 11 turns would be much slower than a depth-11 search natively. It's because you're really parsing the search space at the greater depth, you're just spending 99% of your time pruning.

If we toss contemporary technology aside and dream of a future machine, say one with a back-end pruning capability of 12 turns and an edge pruning capable as deep as edges can go, then along with the 11-turn corner database, we could probably solve every scramble of a 4x4x4 in God's Number of turns or fewer.

 

[rokicki]

When I first started writing my 4x4x4 program . . .

You've made a ton of progress; great job.

I do want to mention here that "finding God's number" and "solving a single random position" are very
different problems; so far your program focuses on the latter, but solving the former is many, many
orders of magnitude more difficult.

At the moment, we cannot expect to solve a single "random" position of the 4x4x4 optimally, even if
we were given access to the top supercomputer in the world for a year. (3,000,000 cores, assume
a depth-14 pruning table, 100M evaluations per core per second). At some point this may change, and
we may have optimal 4x4x4 solvers, probably due to a combination of better techniques and better
technology.

Finding an optimal solution for a random position takes time roughly proportional to the total number
of positions in the puzzle divided by the memory size of the computer we are using.

But proving God's number requires two things. We need to find a position at the purported distance
(and prove that position takes this number of moves), and then we need to *somehow* show that
all other positions can be solved in this number of moves or fewer.

So far our best technique for doing this takes time proportional to the number of positions---there is
no division by the memory size of the computer. And that's assuming everything goes our way
(for instance, on the 3x3x3, we had to wait for machines with 4GB of memory to become commonplace;
the basic idea was ready for years before that happened. For the 4x4x4, we probably need a *lot*
more memory than this to become commonplace.)

But who knows. Someone might make a tremendous leap and figure out some technique to avoid
exploring much of the space. Maybe that person is unsolved. We shall see.

 

[unsolved]

You've made a ton of progress; great job.

The three biggest improvements I can't take too much credit for. The original move generation idea by Jakube and the minimization of the tree generated by the move generator was quite a few people, the corner database (finally!) was your originally suggested by you and Bruce, and the fixed-corner move generator that Herbert pointed out to me. I don't think I would have been able to do any of that in a vacuum.

I do want to mention here that "finding God's number" and "solving a single random position" are very
different problems;

Understood and I agree. When I mentioned "Imagine an 18-move scramble that first moves only the faces 11 times to a unique 11-turn corner database entry, then move only the slice edges 7 more times in such a way that a redundant position with fewer moves is not encountered. Hypothetically, an 18-move prune can take place. I say hypothetically because it is extremely rare but it is not impossible." I was hoping it was clear this was a discussion about a single hypothetical position.

At the moment, we cannot expect to solve a single "random" position of the 4x4x4 optimally, even if
we were given access to the top supercomputer in the world for a year. (3,000,000 cores, assume
a depth-14 pruning table, 100M evaluations per core per second).

I have completely changed my stance about optimizing the speed of move generation after seeing what the two forward pruning mechanisms do that I employ now. Pruning is everything, move generation is nothing. A new pruning paradigm is needed to get us to the next level of performance.

...For the 4x4x4, we probably need a *lot*more memory than this to become commonplace.)

Definitely. Either that or some "magic bitboard" still waiting to be discovered that drops the memory requirement by something that outpaces the growth of base-2 explosion.

But who knows. Someone might make a tremendous leap and figure out some technique to avoid
exploring much of the space. Maybe that person is unsolved. We shall see.

I have one more idea I am trying to code for the upcoming FMC contest. A completely new pruning idea. I am trying to make sure it is, as you say, "permissible." It's a shame that my other one that solves the snake position in 22 moves turns out not be a Karnaugh Map Tautology. Using Godel's work as a primer made me realize such an undertaking was futile to try. But I found out experimentally through computer science.

 

[qqwref]

Right now, I have back-end data through 7 turns on my supercomputer. That means I would still have to solve the cube through a distance of 29 moves from the scramble.

But... the good news is, the deepest corners database entry is 11 turns. In the event a scramble has an 11-turn corner orientation, we can effectively chop off 11 turns from the distance.

Sadly, I am pretty sure it doesn't work that way. The position is at least 11 turns from solved, not at least 11 turns from being in the 7-turns-from-solved database; in fact, it might be only 4 moves from being in the 7-turns-from-solved database.

Imagine an 18-move scramble that first moves only the faces 11 times to a unique 11-turn corner database entry, then move only the slice edges 7 more times in such a way that a redundant position with fewer moves is not encountered. Hypothetically, an 18-move prune can take place.

This may be the case if the two pruning tables truly are additive. If you really do have edge positions that require at least 7 slice moves, no matter how many face turns you have done, then yeah, you should be able to prove some positions are at least 18 moves from solved.

we could probably solve every scramble of a 4x4x4 in God's Number of turns or fewer.

If we could do this (or at least solve random 4x4x4 positions optimally), it would certainly be a great first step. However, it is still very far from being able to find out God's Number. There are 7.4 * 10^45 positions (perhaps decreased by a factor of 48 or so due to symmetry, if you are being clever) so it is certainly not doable to just loop through them and optimally solve them all. Even a coset solver, like what was done for 3x3x3, would require either a gigantic amount of space or a gigantic amount of processing time (or both). A 1 PB table holding one bit per position is still only 9 * 10^15 positions. I certainly agree with rokicki that a huge leap will be required to solve this puzzle anytime soon - 4x4x4 has about 2^87 times as many states as the 3x3x3, so even if Moore's Law holds, with current techniques I'd expect to have to wait until 2140 or so.

 

[rokicki]

. . . if Moore's Law holds, with current techniques I'd expect to have to wait until 2140 or so . . .

The good news here is that for optimally solving a random position, the speed is roughly proportional to
the instruction execution rate times the amount of memory used. Since Moore's law is increasing
both (number of cores for one, and aggregate memory size for the other), optimal solvers end up
getting a double-barrel boost from Moore's law.

Of course, now that machines that can easily handle HD video fit in your pocket, there's less incentive
for performance improvements on commodity hardware and more focus on making the computer as
thin as possible.

 

[unsolved]

Since Moore's law is increasing
both (number of cores for one, and aggregate memory size for the other)

Yeah most people mistakenly believe Moore's Law refers to time required to double the processor performance. It doesn't. It refers to the duration required to cost-effectively double the number of transistors on a die. It would be interesting to see if this relationship still holds now that Intel made a 3D transistor that takes up less surface area on the 2D planar portion of the die. They are down to 22 nm technology. That's almost 20 times smaller than the smallest wavelength of light we can see! How do you debug that?

It's funny how after all of my explaining, some people still don't understand how my TFS databases work. Of course they are trunk pruners and only queried after the move generator has produced an entire move sub-sequence to depth D - n, where n is the greatest distance available in the database. The branch pruning databases are forward pruners, and may be engaged at any time during the sub-sequence generation process. If a corner database's cube position can't be solved in fewer than C moves, and I am at distance D - x < C, I am guaranteed that there is no solution available in the remaining number of moves not-yet-generated, so I can prune.

Concrete example:

Trying to search to depth D = 12
TFS database n = 7
Program generates moves A, B (x = 2) of the 5 moves it has to generate before it queries the TFS.
Position after moves A,B,C,D,E is guaranteed to be in the TFS-7 database if they lead to a 7-turn solution.
Shorter solutions are also found with 1 database query (TFS-0 through -7 is combined into one buffer).
Say the corner database says scramble + A + B yields a distance C = 11.

The cube can't be solved in fewer than 11 moves from here, guaranteed.

I made moves A, B already. There are D - x = 12 - 2 = 10 moves remaining in the program's horizon.
If there was a solution of depth D - 1 = 11, it would have been found on the prior iteration.

Therefore, with 10 moves remaining to the terminus, and no solution possible < 11 moves according to the corners database, I can prune and stop searching.

It does not matter that the program is 3 moves away from the TFS database. The solution is demonstrably not present.

EDIT: To Cmowla, can't access my email right now. I am running your 22-move scramble on the 5x5x5 on this 4.7 GHz server:

Spoiler

And here is what it looks like:

Spoiler

A concrete example for the 5x5x5 cube, where pruning has even more radical results:

Spoiler

The program is searching remarkably fast even on a non-supercomputer workstation. It hit a peak of 117 trillion positions/second when it finished depth 10 on the 5x5x5 in one second. It is holding at about 81 trillion/second for the deeper searches, mostly a function of its deep pruning.



Edit 01: I am running into the problem now where the node count exceeds the maximum value of a 64-bit integer!

 

[qqwref]

The good news here is that for optimally solving a random position, the speed is roughly proportional to
the instruction execution rate times the amount of memory used. Since Moore's law is increasing
both (number of cores for one, and aggregate memory size for the other), optimal solvers end up
getting a double-barrel boost from Moore's law.

Indeed, but I'm more talking about a full computation, which I don't think can be sped up much by throwing additional memory into pruning tables. I could be wrong, though. My starting point for that date estimate was 2010, when God's Number was proven - I assume that single cubes could be solved optimally many years before that.

Of course, now that machines that can easily handle HD video fit in your pocket, there's less incentive
for performance improvements on commodity hardware[...]

I heard somewhere that chip manufacturers were having trouble increasing the performance any further, which is why they have started moving towards more and more cores... I may be mistaken, though.

 

[unsolved]

YouTube video of the 5x5x5 "desktop computer" version (< 12 GB RAM) still solves it in a decent amount of time.

The first clump of text is the program reading the wing edge forward-pruning databases through 5 turns. The second clump of text is reading the corner forward-pruning database through 8 turns. The last group of colored text is building the 5-turns-from-solved back-end-pruning database on the fly. Then it loads a 10-turn scramble for a last layer 3-cycle position. This shows that combining forward- and backward-pruning can be powerful. Note the corners are already solved in this scramble, so it was mostly the (very small) wing-edge-05 database + TFS-05 that was responsible for this performance.

EDIT: 186,175,388,666,006,296,695 nodes in 14 minutes + 14 seconds!

Translating these 5x5x5 pruning mechanisms to the 4x4x4 cube now. There is no middle edge on the 4x4x4 so pruning by that cube subset will not translate, but I'm hopeful that the others will be seamlessly ported.

At depth 12, the node count exceeds a 64-bit integer. I did not convert my nodes/second to such a large data type because I thought there would never be a need for such a thing! (That's why there is ???? after depth 11).