How Close Are We to God's Algorithm?

I have generally assumed the diameter would be found before a complete distance distribution was determined. I think some people might say that a true "God's algorithm calculation" would give you for each position, at least one move that gets you closer to "solved" (or some specified "start" postion). If the distance of each position is calculated and stored, that might also be called a God's algorithm calculation. In fact, storing the distance mod 3 for every position would let one determine the distance of each position with a quick and simple procedure, as has been previously mentioned on this forum. A short series of depth one searches provides an optimal sequence for a position. I would consider merely tabulating the distances for all positions another step further from a true God's algorithm calculation. With the size of the cube group, any distance lookup table would probably require many internet-connected computers to hold all the data. A mere tabulation of the distances is a much more feasible task and allows you to calculate the average distance as well as giving you the maximum.

Merely finding the diameter (sometimes called God's number), I would not really consider to be a God's algorithm calculation. However, that would probably be of much more interest to the general public than a complete tabulation of distances of all positions.

On the topic of carrying out a Rubiks's cube analysis via distributed computing, I thought I would mention that a speedcuber named Lars Vandenbergh recently did a couple of Rubik's cube analyses using distributed computing. The analyses were to compute the number of moves needed to solve the 4 edges of a face, with the face chosen to give the result that minimizes the number for each position. He did one analysis for FTM and one for QTM. Corners, of course, could be ignored so there was slightly under a trillion total positions to consider. He did not use symmetry to reduce the amount of calculations, but he broke the problem down into 2048 orientation cases.

The client program only needed to build a relatively small lookup table, and only needed to be told which orientation case to calculate. The results it needed to pass back to the host was just a small set of numbers giving the number of positions of each distance (and a number identifying the orientation case, of course). So the problem was well suited to distributed computing.

See this link for more infomation about it:
http://www.speedsolving.com/showthread.php?t=3040
(There was also a thread about this on the Yahoo speedsolvingrubikscube forum.)

Given that a distributed computing strategy could be developed for solving God's Algorithm, I would picture it working in broad general terms exactly like the software described in the link in Bruce's message. There would be a script that people could download and run. The script would communicate with a server to fetch a piece of work to do. Upon completing it's piece of work, it would report the results back to the server. And repeat until done. Here are the three possible strategies I mentioned. I'm sure there must be more.

1. The program that would be run on numerous machines in a distributed fashion would be an optimal solver that would solve individual positions rather than cosets. A central server would upon request serve out a range of positions to be worked on, and when those positions were completed the results would be reported back to the central server. The search space would of course be reduced by symmetry and antisymmetry.

The chief problem with this strategy right now is simply speed. If I understand correctly, the best optimal solvers for individual positions currently can solve a few hundred positions per second. The speed needs to be increased to about 14,000 positions per second to get the time to solve the problem down to 1,000,000 computer years.

The chief advantages of this strategy are that most existing desktop machines are capable of running existing optimal solvers, and that this strategy decomposes the overall problem beautifully. That is, none of the numerous machines working on the problem would need to communicate with each other at all. The machines would simply need to communicate with a central server to pick up a bunch of work to do, and much later (possibly months later) they would need to report their results back to the central server.

2. The program that would be run on numerous machines in a distributed fashion would be a variation on my current depth first solver that produces positions in lexicographic order. A central server would upon request serve out a range of positions to be worked on, and when those positions were completed the results would be reported back to the central server. The search space would of course be reduced by symmetry and antisymmetry.

"Never" is a long time, but I do not think my algorithm could ever enumerate the entire cube space. However, my algorithm does have some advantages. It already produces about 20,000 optimal and individual positions per second. And I think this could be increased considerably because the program was originally developed in 1995 to optimize memory usage rather than speed. I think a rewrite to optimize speed might possibly result an as much as a 10 times speed up while still using the same algorithm. Also, the algorithm decomposes beautifully because the positions are produced in lexicographic order. It's very much like a program running in distributed fashion to process a dictionary. One machine could process the A's, one machine could process the B's, one machine could process the C's, etc., and none of the machines would have to communicate with each other at all.

My algorithm does not require storing any of the positions that are being calculated. However, in order to calculate out to a distance of 2N, my algorithm must store all positions out to a distance of N. For example, to calculate the entire cube space in the face turn metric out to a distance of 20f, all positions out to a distance of 10f must be stored. That's about 2.5E11 positions, and the actual positions themselves have to be stored not just the distances from Start. The positions must be stored in memory, not on disk. No existing desktop machine can store all the positions out to 10f. The positions stored out to 10f cannot be reduced by symmetry and antisymmetry (or at least, I've not figured out a way to do so). However, the positions being calculated out to 20f could be reduced be symmetry and antisymmetry.

But my algorithm has an even worse problem, which is why I say "never". The number of positions my algorithm has to calculate for any level in the face turn metric is about 13^N. That's fine as long as the actual branching factor is about 13. But for example when going from 18f to 19f or in going from 19f to 20f, the actual branching factor is much less than 13. Indeed, it is less than 1. So my algorithm is very efficient for example at 12f from Start or 13f from Start or 14f from Start. My algorithm starts becoming less efficient about 17f or 18f from Start, although I think it would be acceptable at those distances if all the other problems associated with calculating those distances could be solved. But my algorithm becomes totally and horribly inefficient at 19f and 20f from Start because the actual branching factor is so small that virtually none of the positions being calculated are useful.

Indeed, if I can make a confession, I worked on solving the edges of the cube with my lexicographic solver for several years before Tom Rokicki succeeded. My program worked great for enumerating God's algorithm for the edges until it got out into the tail of the distribution. And at that point, the run time became totally unreasonable and I never succeeded.

3. The program that would be run on numerous machines in a distributed fashion would be a standard depth first solver that stores all the positions. I've worked out a way to do this that would require a little less than 1,000,000 machines. Each of the machines would represent a unique configuration of the corner cubies, reduced by symmetry and antisymmetry. Each of the machines would have to store a number of positions equal to half the number of edge positions, not reduced by symmetry and antisymmetry. All that would have to be stored would be the distances. The required disk space would be about 500GB. The distances could be stored on disk. The storage requirement could be reduced to about 125GB by storing distances mod 3. However, storing distances mod 3 would require that the problem be run from beginning to end with no interruptions whatsoever. I don't think that's a practical approach, so I think actual distances would need to be stored.

Current desktop machines typically don't have 500GB of disk space, but I think they will in a very few years. The bigger problem with the approach I have worked out is that all the machines solving the problem would have to be running at the same time and they would have to communicate with each other all during the solution. Each machine would only have to communicate with 12 other machines in the quarter turn metric, and with 18 other machines in the face turn metric. But the fact that all the machines would all have to be running at the same time in a cooperative fashion means I think that this approach is not really practical.

> If I understand correctly, the best optimal solvers for individual
> positions currently can solve a few hundred positions per second.

Hmm, what solvers are these? If you really do arbitrary individual positions, the best I know of average on the order of 15 minutes *per* solution, maybe a bit less. This is based on results from a few years ago, so maybe things have sped up, but not that much.

Can you describe these solvers? Maybe there's some hidden assumption I'm unaware of. Certainly if such solvers do exist I could assuredly use them.

Right now the "hard but solvable" problems that I know of for Rubik's cube include proving a position is a depth 19 or depth 20 position. Proving a single suspected depth-20 position takes, for me, something like 8-10 CPU hours.

I think it is possible to solve a few hundred cubes/second within 20 moves with the two-phase-algorithm. But not optimal. My huge optimal solver needs about 2 minutes on average.
Solving cosets is in my opinion the most promising way to gods algorithm. Within a few years a standard PC will solve a H-coset within a day and a million pc need a few months to solve all 138,639,780 symmetry-reduced cosets. The only question is if a million people are interested in solving this problem.

I think I mixed up the performance of near-optimal solvers as compared with the performance of optimal solvers. Sorry.

I have to confess to having more interest in general in solutions for individual positions than in solutions for cosets -- except that coset solvers are almost certainly the way to go do determine the group's diameter.