God's Algorithm out to 14f*

First of all I used of course fixed corner cube positions as cosets (a bad case of me translating Eck-Würfel as edge cubes).

About the technique, I tabulated all symmetry reduced positions up to eight moves. I can quite easily tabulate them up to ten moves, but the resulting tables are to large to fit into memory. I then used a combination technique starting at all position at depth one "combining" them with a position at depth eight to reach the desired corner cube position, and then going on to depth two and so on until reaching the desired depth, discarding on the way all duplicate positions. I experimented with pruning tables, after my first version was about a factor 100 to slow compared to your calculation up to 13 moves. During that I found the flaw in my Program (doing a full symmetry analysis of every position, though most of the time the corner cube position is already completely unsymmetric). After correcting that it turned out that the combination method was slower up to depth twelve, but starting at depth 13 it was faster, so I used that method for the calculation out to 14 moves.

As for storing the positions, I simply used an ordered list, which allows quite easily to check if a position is already in the list. Entering a new positon then means of course to move all later positions in memory. For performance reasons I didn't use a single list but actually 131072 by using the edge cube flip and six bits from the edge cube position as index into which list to use. Since the edge cube flip is already in the index all I had to store was the edge cube position. The neccessary 29 bits fit quite easily into 4 bytes.

So even for the largest cosets all positions fit in about 5 GBytes of memory. The Cray has 32 GByte of memory for every 24 cores. Over 99% of all cosets have less then 250 million positions, resulting in less than 1 GByte of memory usage, so I could use all 24 cores in a node. For the largest cosets I used only 4 cores of a node, which means I had 8 GBytes of available memory per coset, taking into account a bit of overhead because of dynamic memory allocation. As estimate for the required memory I used the number of positions the coset had a depth 13 (times ten), which worked out quite nicely.

This as comment since it might be of interest to other people. I will contact you via mail if you do have more questions.

You stated the following: During that I found the flaw in my Program (doing a full symmetry analysis of every position, though most of the time the corner cube position is already completely unsymmetric).

Here is how I think about this issue. For a position x, we let Symm(x) be the set of symmetries that preserve x. Symm(x) will be a subgroup of M, where M is the group of 48 symmetries of the cube. For most positions, it will be the case that Symm(x) contains a single element, namely the identity symmetry.

Also, we may write x as (x_c,x_e), where x_c is the position of the corners and x_e is the position of the edges. It is the case that Symm(x) = Symm(x_c) ∩ Symm(x_e). Because Symm(x_c) is the identity most of the time, it is the case that most of the time there is nothing to calculate to calculate Symm(x) because if Symm(x_c) is the identity then so too is Symm(x).  This can save a tremendous amount of time in calculating symmetry reduction.

The same thing is true in the other direction, of course.  It is usually the case that the edges have the identity as their only symmetry, so it's usually not necessary to calculate the symmetry of the corners if we know the symmetry of the edges. But it's much easier to store all the corner positions than all the edge positions, so it's much easier to pre-calculate the symmetry of all the corner positions than to pre-calculate the symmetry of all the edge positions.

Jerry Bryan

I hadn't thought about that, so initially I did the most easiest thing.

I needed to know how many "real" positions a symmetry reduced position would represent. So I used all 96 operations (including inversion) and counted how many different positions I would get.

Later I started using cosets but still for every position generated I tried out all 96 operations. Since my cosets are fixed corner cube positions and twists, I can do the analysis once and most of the time I don't have to look at the edge cubes to know that this one position represents 96 real positions. And even if the corner position has a symmetry it reduces the number of symmetry operations I have to look at.

There is only one coset where the corner cubes have the full symmetry and this is the one coset which takes the most time to calculate.

The flaw was only that I did not realise that this took over 90% of CPU time and could be avoided at least most of the time.

I add my congratulations. This is an outstanding achievement. Let me request that follow-up questions and comments be kept on the this forum rather than on E-mail, because I think a number of us are interested.

Even though the terminology is quite a bit different, it seems to me that there is a certain amount of kinship between your technique and the algorithm I used several years ago to calculate out to 11f from Start. (Tom Rokicki has long since improved on this result, of course!).

My algorithm produces permutations in lexicographic order. On its face, lexicographic order doesn't sound like it has anything to do with processing cosets. But processing permutations in lexicographic order is in fact producing the permutations in order by coset. I can elaborate further if anybody is interested, but I think it's pretty clear why this is the case. So let me start with just one question.

You state the following: About the technique, I tabulated all symmetry reduced positions up to eight moves. For the set of permutations S and the set of permutations T, my algorithm produces the product ST in lexicographic order. In order to produce positions out to a distance of m+n from Start, my program tabulates all positions out to a distance of m moves from Start in the set S and out to n moves from Start in the set T. More typically, the set S and T are the same set containing all the positions out to n moves from Start, and my program produces the positions out to 2n from Start in lexicographic order.

The difference is that I had to tabulate all positions out to a distance n from Start, not just the symmetry reduced positions. The product ST was symmetry reduced, but not the sets S and T themselves. How did you manage to produce all the longer positions if you only tabulated the symmetry reduced positions out to length 8?

Jerry Bryan

To reach all positions you are of course correct I have to consider all not symmetry reduced positions. But there is a shortcut.

For position S I started with depth one than two up to six. For that I needed all positions so I used the symmetry reduced positions and used all possible symmetry operations to generate the rest. For speed and to avoid duplicate work I stored which symmetry operations would generate different positions along with the position, actually I only stored an index since I found only 76 different sets of symmetry operations.

For position T I only used positions at depth eight. And to reach all positions T too has to be all possible positions at that depth.

But here comes the shortcut. I only need to produce positions which are in a specific coset. It means I know which exact symmetry reduced corner cube position and twist I want to reach. I look at a specific position S and can therefore tell exactly what corner cube position and twist the position T need to have. By use of a lookup table I could then find the corresponding symmetry reduced corner cube position. And by trying out all symmetry operations I could create a list of symmetry operations which would generate the desired corner cube position for T. And again most of the time this is only one.

I had all positions indexed by the symmetry reduced corner cube position and twist. So I could than just by looking at the index tell if there are any fitting positions at depth eight. And if there were any I could than just combine these, after applying all of the list of symmetry operations which would generate distinct positions, with the position S. Since I already know that this will reach exactly the wanted corner cube position and twist, all I had to do was look at the edge cubes.

The rest was to look if I generated a duplicate and if not to increase the counters.

I think I understand about 90% of your algorithm.  Let me ask a further question about what I think is the key element of the algorithm.  To that end, I'm going to describe a simpler algorithm which I believe faithfully replicates the spirit of your algorithm while omitting a certain amount of the necessary but messy bookkeeping.

Let's suppose we have stored two sets S and T, with S being the set of all positions that are 2 moves from Start and T being the set of all positions that are 8 moves from Start.  And let's suppose that we want to calculate the set of all positions that are 10 moves from Start.  Because we are not going all the way out to 14 moves from Start, I will omit the "combining" process of letting S have the positions 2 moves from Start, then letting S have the positions 3 moves from Start, etc.

Let's further assume that the sets S and T are not reduced by symmetry.  It seems to me that reduction by symmetry is essential to the efficiency of your algorithm, but that reduction by symmetry is not essential to the basic correctness of your algorithm.  So I will choose to assume there is no reduction by symmetry in S and T.

So your algorithm is going to form products of the form st.  Some such products will be 10 moves from Start and some such products will be less than 10 moves from Start.  Eliminating those products that are less than 10 moves from Start is a detail that is pretty simple to take care of it, so I will omit that detail.

We are left with the quintessential problem that some of the products that are 10 moves from Start will be duplicate.  s_it_j may or may not be equal s_kt_m, where i ≠ k and j ≠ m.  We only want to count the cases where s_it_j and s_kt_m are not equal.

Your algorithm does not produce the products st in a totally random order, nor does it produce the products in lexicographic order.  Rather, it produces the products in sort of a targeted order.  We let z=st, and we write z as z=(z_c,z_e), where z_c is the position of the corners and z_e is the position of the edges.  For the purposes of your algorithm, a coset is the set of all positions with a fixed z_c.  So it seems to me that you need to find the set of all solutions to the equation z_c=s_ct_c for a fixed z_c.  Some s_c and t_c pairs will solve the equation, and most of them won't.  How do you quickly find all the s_c and t_c pairs that will work?

The following occurs to me, but you are probably doing something a little more clever than this.  For the case where S contains those positions 2 moves from Start, S only contains 114 elements and there are only 114 possible values for s_c.  When S contains positions more than 2 moves from Start, there will be more than 114 elements, of course.  Also, further from Start than 2 moves, there will be fewer distinct corner positions in S than there are elements in S.  But let's just stick with simple case.  Anyway, for each specific s_c in S and for each fixed z_c as described above, we solve z_c=s_ct_c for t_c.  Namely, t_c=s_c^-1z_c.  It's then pretty straightforward to determine if s_c^-1z_c is in T.  But as I said, you may be doing something more clever than this.

Symmetry reduction is not essential for my algorithm. It is merely a way to reduce memory consumption and calculation time. I need 12 Bytes to store a position, so my depth eight table is 166 MBytes in size. Without symmetry reduction it would be nearly 16 GBytes. I have to add a lookup table to easily convert between non symmetry reduced and symmetry reduced, which is 350 MBytes in size (4 Bytes for 88179840 possible corner cube positions) but it still saves over 15 GBytes.

About avoiding duplicates. It is just not that big a deal, that trying to avoid duplicates is worth the trouble. Even at depth 14 I use all non symmetry reduced positions at depth six (there are 7618438) and combine each with essentially every symmetry reduced position at depth eight once (there are 13890036), which is not entirely correct if the depth eight position is symmetric, but this is almost never the case. All in all my algorithm produces 7618438*13890036 which is about 105.8 trillion positions. Out of these 72.8 trillion were not duplicates of depth 14 or shorter moves. This means at best I could avoid generating about one out of three positions. At depth ten is only one out of four positions.

About the last part t_c=s_c^-1z_c is exactly what I am using in my program. It is so straight forward I couldn't think of something more clever than that. And I have a table which indexes the positions at depth eight by their corner cube position, so I just have to look if my index says there are some or there are none.

At depth two for S I simply use all 243 non symmetry reduced positions even though there are only 114 different corner cube positions. Since calculating t_c is so easy I am not sure if I could save much but doing it only once instead of twice. At depth six it would be about once instead of five times, which still is not that much since it is an outer loop. If I had stored the non symmetry reduced positions, this would be quite easy to do. But I have a list of symmetry reduced positions and two positions with the same corner cube position might need to be treated differently because of different edge cube positions.