God's Algorithm out to 14q*

Howdy, Jerry!

I just built a corners pruning table (80M entries; I didn't reduce
by symmetry). Then I enumerated all possible corners positions and
reduced them by symmetry and antisymmetry. For each of the
reduced corners positions, I found all solutions that took those
corners to solved while permuting the edges arbitrarily.

Essentially, I broke the problem up into approximately 1M smaller
problems, each independent, and solved those sequentially.

By the way, I also verified all of your numbers on the way (the
totals, anyway; I haven't verified all of the symmetry breakdowns
but I did some of them.)

I can push these one more level (13f* and 15q*), I think.

Nice result. I requested the sequence A080601 in the OEIS to be updated with a(11) from Jerry 2006 and a(12) from Tom 2009.

I think I understand the principle, but how did you keep track of the 12!*2^11 edge permutations?

I'm going to ask Prof. Sloane to update a number of the sequences; I'm making a list right now.

For the edge permutations, there weren't that many in each coset, so I just made a simple sequential list of them during exploration, then sorted them and scanned for duplicates. Each list easily fit in memory.

This starts to fall apart at 13f* and 15q*, but I am confident I can solve that, by one of the following:

* Instead of doing cosets in parallel, have threads work cooperatively on the same coset (this way only one coset needs to be in memory at once).

* Use a larger group (edge permutations for instance) so there are more cosets to solve (and thus smaller cosets).

* If all else fails, for the large cosets, write them to disk by radix bin.

Both 12f* and 14q* took less than a day on an i7 920. Jerry, you should really think about getting a new machine; these Nehalems are amazingly fast.

I do need a faster machine, but I don't think a machine 10 times faster or even 100 times faster would really do the trick with my current algorithm. Indeed, a machine 100 times faster would get me down to about a day just to get to 11f and 13q. I would need a machine about 1000 times faster to match your times for 12f and 14q. So I guess I need to understand your algorithm. Unlike Herbert, I don't really understand it yet. I'm going to have to give it a little think.

I've long thought I could speed up my existing algorithm by about 10 times with a rewrite of the existing program. The problem is that the existing program was written about 1994/1995 and was optimized to reduce memory rather than to maximize speed. Modern machines have enough memory that I could reverse the optimization to optimize for speed. But I don't see how I could get much more than about a 10 times speedup and still use the basic underlying algorithm.

The best I can tell, my algorithm is an O( n log(n) ) algorithm, where n is the total number of positions the program has to process to get to k moves from Start. So the algorithm is going to "slow down" as n increases, no matter what. The n part of n log(n) in the performance of my algorithm is straightforward. It's hard to see how any algorithm could do better than O(n). The log(n) part of n log(n) in the performance of my algorithm is due to the fact that the algorithm includes a binary tree that implicitly sorts the positions without actually having to store them all. So the log(n) part of n log(n) in the performance of my algorithm essentially reflects the fact that the depth of the binary tree increases as n increases. My algorithm doesn't use cosets at all, and I guess that's where your algorithm gets its tremendous speed.

My algorithm is (currently) O(n log(n)) in theory, because I do a sort on the entries from each coset, but so far the sort has not contributed an appreciable fraction to the runtime (and when it does I can replace the sort with a radix sort to get back to O(n)).

My program uses the following ideas:

1. Cosets are partitions of the whole group, so we can separate the problem into cosets, and solve each coset separately. This is elementary group theory but is essential to understanding the idea.

2. Enumerating the elements of a given depth that belong to the coset can be done by using a pruning table containing the distance of positions within the group that defines the coset (here distance is defined to be the length of the shortest word [of a given set of generators] that equals that position).

Our "group" is essentially corners+centers; this has 80M possible elements, so the pruning table is small and fits in memory easily. (I use quotes because there are some subtleties about parities which we will ignore for the moment; an "odd" corner permutation must have an "odd" edge permutation, so the cube group is not a simple direct product of corners x edges.)

Each "coset" is all cube positions that have a particular "corner position"; that is, fix the corners (and their orientations) and consider every permutation/orientation of the edges that is possible. That's the coset.

To enumerate the whole positions in each coset of a given distance, I just enumerate all sequences that take the given corner position and solve it; each of these sequences generates a whole-cube position that's a member of the coset we are currently exploring. This is easy to do with iterative deepening depth-first search.

For now, at the leaves of the dfs, I just make a simple list of positions found, since the number of duplicates is usually small.

Once I'm done running dfs on a coset up to a given depth, I take the aggregate list, sort it, uniquify it, and if necessary, evaluate the symmetry of the positions found. (Most cosets have a corner position without symmetry, so for most cosets, I can just count the unique positions.) Some cosets have many more entries than others, so sometimes there is a fair bit of memory involved here, but it has not yet been a problem.

The cosets of corner positions that are related by symmetry are also related by symmetry, and so their position counts and the like are equal, so I only evaluate a representative coset. But to make this work, I need to see if each whole-cube position found for these cosets also have the same symmetry, so I evaluate the symmetry of each of these independently.

That's pretty much it. The whole program is pretty short and pretty easy to write; I did spend some time making my corner-position-to-index and index-to-corner-position reasonably fast, so the pruning table lookup and thus search is pretty quick.

There are some improvements I can make to make it even faster, but it's fast enough for now and I have more computer time than programming time (they work while I sleep). I think I can get another 2X in speed.

I think my machine (a single i7 920) is probably about 15 times faster (in total) than a 2.8GHz P4 (I think that's what you have?) so an appreciable fraction of the speedup is due to the faster machine.

-tom

Thanks for the update and the details.

I had already managed to give it a little think, and I worked out most of the details of what you must be doing in my head while I was walking my dog the other night. If I understand it correctly, it's an incredibly elegant idea.

Many parts of what you are doing are straightforward - reduction by symmetry, reduction by anti-symmetry, matching parities between corners and edges, etc. Here's the part where I don't yet quite understand how I would write the code.

To enumerate the whole positions in each coset of a given distance, I just enumerate all sequences that take the given corner position and solve it; each of these sequences generates a whole-cube position that's a member of the coset we are currently exploring. This is easy to do with iterative deepening depth-first search.

My question is how do you enumerate all sequences that produce the given corner position? For example, suppose your given corner position is the one produced by applying the maneuver URF to a pristine cube. There are other and longer maneuvers that will produce the same corner position and that will produce different edge positions. How does your iterative deepening depth-first search find those other and longer maneuvers?

And to be more specific, I assume your iterative deepening search will be looking (in turn) for maneuvers of length 1q, 3q, 5q, 7q, 9q, etc. that will yield the URF corner position. Well, you would probably start the iteration at 3q rather than at 1q. How does your search look for 5q, 7q, and 9q etc. maneuvers for the URF corner position?

There is a very close connection between three different problems:

1. Solving a cube c with a two-phase-algorithm and an intermediate group H
2. Counting the number of cubes of the coset H*c with an optimal maneuver length D.
3. Solving a whole coset H*c

Problem 1: We use a pruning table to quickly find optimal and suboptimal maneuvers to get the cube into the group H. Then we solve the cube in H, looking for short overall maneuver lengths.

Problem 2: Instead of solving the cube in H we just continue to generate suboptimal maneuvers of a certain depth D and count the number of elements of H to which the cube c is transformed by these maneuvers. This is exactly the number of cubes of the coset H*c which have an optimal maneuver length D (though this might not be obvious on first sight). If we sum up over all cosets we get the total number of cubes with optimal maneuver length exactly D.

Problem 3: We continue to generate subobtimal maneuvers until all elements of H are "hit" by the transformation of c by the subotpimals maneuvers. For the subgroup H = (U,D,R2,F2,L2,B2) with about 20 billion elements you can keep track for example with a bitvector of about 2.3 GB. Counting the number of new "hits" for each maneuver length gives the optimal solution distribution for this coset.

So once you have written a program for one of these problems it is not difficult to modify it to solve the other two problems.

Nice explanation!

Of course, different subgroups may be appropriate for different problems.

For calculating new upper bounds, the standard "Kociemba group" (U,F2,R2,D,B2,L2) works great because the coset can be "completed" with moves in the group---we only need apply dfs up to depth 15 or 16 and those positions used as "seeds" to solve the remaining positions to 20 very quickly.

Similarly, the "Kociemba" group works great for a two-phase solver, because the "second phase" stays within the group.

But for enumerating cube positions out to a depth, you want a subgroup that allows you to reduce the problem using maximum symmetry and antisymmetry. There are only a handful of subgroups that exhibit the full 48-way symmetry.

If you try to use the Kociemba group to enumerate cube positions to a given depth you encounter difficulties because this group only has 16-way symmetry, so every symmetry-reduced position occurs in up to three cosets, and every symmetry-and-antisymmetry-reduced position occurs in up to six cosets. So combining the results from the individual cosets is more complicated.

Presently I am using the "edges fixed" subgroup, but I may switch to the "corners fixed and edge orientation fixed" subgroup.

There are a couple of details that cause confusion, and I hope to write something on that soon.

Thank you for your kind words. I'm going to answer your question with code. The table t[pos] gives us the distance from solved for a given corner position. The variable togo tell us how many moves we have left in the current sequence we are constructing. I will omit some details (like not generating sequences where moves of the same face are adjacent). The code is:

void dfs(const cornerpos pos, int togo, vector &seq) {
   if (togo == 0) {  // no more moves
      if (t[pos] == 0) { // truly a solution
         handle_sequence(seq) ; // do whatever with this sequence
      }
   } else {
      for (m : moves) { // try all moves
         cornerpos pos2 = pos ;  // copy the position
         pos2.move(m) ; // make the move
         if (t[pos2] <= togo-1) { // did not move too far away
            seq.push_back(m) ; // add this move to sequence
            dfs(pos2, togo-1, seq) ; // recurse
            seq.pop_back() ; // pop that move
         }
      }
   }
}

That's it; it's a pretty standard "find a solution" recursion.

The check at the top of the loop (that t[pos]==0) is not really needed because of the way the recursion works (unless you start with a not-solved position and togo=0), and there are some additional optimizations you can make, but this is the basic code.

The pruning table I *really* use has additional information, such as which neighbors take us further from solved and which neighbors bring us closer to solved, so I don't actually consider all moves, only those that the table says I should.

And there are a few more tricks, but they are not essential.

First of all, congratulations on the new 13f results. Spectacular!

I always write messages that are too long. Let's see if I can clarify my additional questions briefly.

1. I assume you doing an iterative deepening depth first search from Start, going further and further away from Start. Is that correct? I just want to understand if you are enumerating from Start to each of the other positions, or from each of the other positions back to Start.

2. I understand how to reduce the problem by symmetry and antisymmetry, but let's suppose for a moment that you weren't reducing the search space in that way. If you just enumerate cube space moving away from Start and store all the positions, the problem you immediately run into is running out of memory pretty quickly. If I understand your search correctly, you are choosing a particular corner position and only storing those overall cube positions that match that particular corner position. But you are still enumerating all positions, not just the ones that have the particular corner position. Is that right?

3. Assuming I have #2 right, and absent reducing the problem by symmetry and antisymmetry, that would mean that you would be storing only about 1 out of every 88179840 positions that you enumerate. (88179840 is of course the well known number of distinct corner positions.) So you can enumerate further from Start with the same amount of memory. On the other hand, you would have to repeat the process for each possible corner position. So absent symmetry and antisymmetry, the program would have to run 88179840 times longer to achieve the same result than if you had a hypothetical machine of the same speed and infinite memory? Is that right?

4. Assuming I have #3 right, if you do reduce by symmetry and antisymmetry then the search space is reduced to 934778 distinct corner positions. But if I'm understanding the process correctly, you would still have to repeat the search for each of the 934778 distinct corner positions, which would require about 934778 as much time to achieve the same results as would be required if you had a hypothetical machine of the same speed and infinite memory. Is that right?

Up until this point, it all makes sense to me except for the performance characteristics. The calculations to 12f and to 14q each took about a day. There are 86400 seconds in a day and there are 934778 corner positions unique to symmetry and antisymmetry. So to enumerate the positions in the way I described, you would have to be able to enumerate all the positions to 12f or to 14q in about 1/10 second and repeat the enumeration 934778 times.

I think the thing I must be missing is that you already know the minimum distance to Start for every position in the coset defined by a particular corner position. Your algorithm apparently is taking advantage of this knowledge, and my really simple minded algorithm is not.

Howdy, Jerry!

Sorry this response is so late. Your messages are clear and explicit, and just as concise as they need to be; please do not change the way you write!

Actually, I'm doing the iterative deepening from the "corner position" that is the inverse of a representative element of the coset. Consider the group K composed of the direct product of the corner group C and the edge group E (this group is 2x larger than the "normal" cube group G because the parity of the edges and corners need no longer match). Every position k in K can be represented by a pair (c, e) where c in C and e in E.

The total size of C is 88,179,840. Each coset I solve corresponds to a single c in C. We use a big table giving the distance from solved for every c in C.

To solve the coset corresponding to a given c in C, we start by making a cube position (this cube position may not be in G but it is in K) with the tuple (c', 1) (that is, the corner is in the inverse of the position c, and the edges are solved).

I then do the iterative deepening to bring the position (c', 1) to (1, e') in all the possible ways. The table giving the distance of all c's in C keeps me from exploring paths that will not get us to a "solved" corner position.

Now, every sequence that took (c', 1) to (1, e') would also take (1, 1) to (c, e'). So in this sense, we do "start" from solved. But we do it by premultiplying by (c', 1) so that we can use our pruning table.

So you're exactly right, except that I go c'->1 rather than 1->c, which enables me to use the pruning table to get excellent computational efficiency.

I have no more questions for now. This message fills in the missing piece for me. Much thanks for such a clear explanation!

In the last paragraph, I said "the minimum distance to Start" which should really say "a lower bound on the distance to Start".