Home »

God's Algorithm out to 16q*

Submitted by tscheunemann on Fri, 07/09/2010 - 05:06.
So switching to edge cube positions as cosets (instead of corner cube positions and twist) made a huge impact on the calculation, but more on that later. So my results for up to 16q* for positions at exactly that distance are: 
 d (mod M + inv)*     positions
-- -------------- ----------------
 0              1                1
 1              1               12
 2              5              114
 3             17             1068
 4            135            10011
 5           1065            93840
 6           9650           878880
 7          88036          8221632
 8         817224         76843595
 9        7576845        717789576
10       70551288       6701836858
11      657234617      62549615248
12     6127729821     583570100997
13    57102780138    5442351625028
14   532228377080   50729620202582
15  4955060840390  472495678811004
16 46080486036498 4393570406220123
* The (mod M + inv) column means symmetry reduced postions but only considering the edge cube positions. I just included it because I had those numbers. It is not comparable to earlier calculations because it may include duplicate positions of the full cube and is dependent on what cosets are used in the calculation.

Compared to my 14f* calculation I have switched to symmetry reduced edge cube positions as cosets. Instead of 934778 cosets I had 5022205 cosets to calculate. For the final results I used my combination method, but got rid of symmetry reduction inside the inner loop, and I tabulated symmetry reduced (but only considering edge cubes) positions up to 10 quarter turn moves. The final calculation took 36 and a half hours on 576 1.9 GHz Opteron cores.

Switching to edge cube positions as cosets made this calculation actually easy. On average you would expect that the positions in each cosets are reduced to one fifth. While this is certainly true on average, as both choices must give the same number of positions, the real problems are the cosets with the largest number of positions because they are the ones you have to fit into memory. I have no real numbers for 16q* only that my smallest coset had 9333371 positions (ignoring the ones with 0 positions) and the largest coset had 95678272 positions. Times 4 Bytes I need to store every position this is less than 400 MBytes for each coset.

I have better numbers for 14f* to show how big the impact really is. In my previous calculation using fixed corner cubes and twist as cosets, the smallest coset had 3394915 and the largest had 1121466975 different positions at 14 moves. If I had skipped on symmetry reduction this would have been 32656704 for the smallest and 1846987309 for the largest coset. After redoing the 14f* calculation (it is about 17% finished) the smallest so far has 11610701 and the largest has 35758291 positions. Chances are (because the largest seems to be the first the fully symmetric coset) this is actually the largest coset. So the largest number of positions in a coset is reduced by a factor of nearly 52 along with the memory consumption to store the positions.

All in all fixed edge cube positions are much better suited for this kind of calculation, because the distribution of positions on cosets is more even. Using these cosets 15f* and 17q* look doable if I find the time (CPU-time that is).

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Symmetry Reduction

Submitted by tscheunemann on Fri, 07/09/2010 - 17:43.
Thinking a bit about it, it occurred to me that there is a much simpler way to generate fully symmetry reduced numbers, at least compared to what I have done before. So I just redid the 63515 symmetric cosets and here are the more traditional results: 
 d (mod M + inv)*  mod M + inv      mod M           positions
-- -------------- -------------- -------------- ----------------
 0              1              1              1                1
 1              1              1              1               12
 2              5              5              5              114
 3             17             17             25             1068
 4            135            130            219            10011
 5           1065           1031           1978            93840
 6           9650           9393          18395           878880
 7          88036          86183         171529          8221632
 8         817224         802788        1601725         76843595
 9        7576845        7482382       14956266        717789576
10       70551288       69833772      139629194       6701836858
11      657234617      651613601     1303138445      62549615248
12     6127729821     6079089087    12157779067     583570100997
13    57102780138    56691773613   113382522382    5442351625028
14   532228377080   528436196526  1056867697737   50729620202582
15  4955060840390  4921838392506  9843661720634  472495678811004
16 46080486036498 45766398977082 91532722388023 4393570406220123
» login or register to post comments

Symmetrical cubes

Submitted by rokicki on Sun, 07/11/2010 - 16:36.
Very nice result!

In regards to the half turn metric:

Herbert, is there some way we can verify the (mod M) numbers
against the (positions) numbers, based on the symmetric
numbers you've compiled on your website?

Indeed, if there's some way to publish the expected relationship
for all of the depths that would be very nice. (For instance,
at depth 15, positions = 48 * (mod M positions) + ccccc for some
constant ccccc).

Mod M + inv is of course harder because the antisymmetric
positions have not been tabulated.

In any case, that's how I do things; I run the cosets with symmetry
in a slower, more careful way than the normal, non-symmetrical
cosets.

Do you think you might get time for 15f*?

The rate of new results appears to really be accelerating.

-tom
» login or register to post comments

Of course we also can do it the other way round too

Submitted by kociemba on Tue, 07/13/2010 - 19:48.
When we have the number 145610854487909 of mod M classes for 14f* we subtract then number 18183156 of all symmetric classes with 14f* and get the number 145610836304753 of C1 classes. Multiplying by 48 gives 6989320142628144 positions for the C1-cubes. Now we add the 436197214 symmetric positions and get the 6989320578825358 total 14f* positions?

So we only need to count the number of the positions mod m to retrieve the number of all positions. Does this help to do the calculations faster?
» login or register to post comments

Symmetry

Submitted by rokicki on Tue, 07/13/2010 - 20:51.
Potentially. Alternatively, we can compute the *total* number of positions by computing symmetry only on a per-coset basis (and do *no* per-position computations whatsoever), then use your symmetry results to recover the number of positions mod M.
» login or register to post comments

Results in HTM

Submitted by kociemba on Tue, 07/13/2010 - 08:52.
Yes, I verified the (mod M) numbers in HTM from 11f* to 14f* and all numbers came out correctly. As an example the computation for 14f*:

From the number 6989320578825358 of 14*f positions we subtract the number 436197214 of symmetric 14f* positions given at http://kociemba.org/math/c1.htm. We get the number 6989320142628144 of unsymmetric positions, symmetry class C1. This number must be divisible by 48 and fortunately it is. We get the number 145610836304753 of positions mod M with symmetry class C1.
Now we add the number of 14f* positions mod M for all other 32 symmetry classes which are all listed on the pages dealing these symmetries.
We get (the numbers are in the same order as the symmetries are listed at http://kociemba.org/symmetric2.htm)

0 + 0 + 0 + 0 + 0 + 1 + 1 + 6 + 12 + 418 + 18 + 8 + 67 + 20 + 958 + 1944 + 103 + 18 + 54 + 378 + 1064 + 2185 + 704 + 4549 + 671 + 2489 + 671 + 12702003 + 540239 + 2501038 + 135189 + 2288348 + 145610836304753=145610854487909.

This is a good verification for the numbers of tscheunemann as well as for my own numbers.
» login or register to post comments

Symmetry

Submitted by tscheunemann on Mon, 07/12/2010 - 07:54.
It was kind of an evolution for me.

In my first program I did symmetry reduction on all positions I would find, by using all 96 (mod M + inv) symmetry operations and see which would give the "lowest" coordinate and then only store this coordinate.

When using cosets this changes, which I didn't realize at first. You only need to look at symmetry operations that won't change the coset. Since most cosets are not symmetric, you can skip the whole symmetry thing and just know that every position you generate is a representative for 96 other positions.

But for the symmetric cosets this means you still have to consider up to 96 symmetry operations. This resulted in a very large difference in calculation time between cosets. The most symmetric coset took as much CPU-Time as 500 other cosets. That is when I decided to skip about symmetry and just store all positions even if they are duplicate.

Then it occurred to me that I could have both. I still store all positions, even if they are duplicate, but now if I find a new position, I use all symmetry operations which won't change the coset, produce all duplicates and, if they are not already in the list, just store them. This is a rather fast operation and by counting how many "real" duplicates I produce I can calculate the "real" symmetry reduced numbers. If I later produce another duplicate, even if it is not the "lowest" coordinate, it is already in the list and I can just skip it.

I have now redone my 14f* calculation. Including symmetry it took 38 and a half hours on 1200 1.9Ghz Opteron cores. As I have noted before the strange thing is the distribution of positions on cosets. The smallest coset has 9789963 and the largest has 35758291 positions at 14f*, which is only a factor of 3.652 between those two cosets. Even though I have changed cosets, from fixed corner position and twist to fixed edge position, results are still the same. Which is to be expected, but at least it gives me some confidence in my results.

I have already calculated the 0 coset for 15f* and 17q* as this is most likely the largest coset for both depths. For 15f* I have 320713432 positions and for 17q* there are 501826957 (including duplicates). Since I now only need to store two Bytes for every position because I am using 1377810 arrays, I don't expect bigger memory troubles for 15f* and 17q* at all.

Looking at the CPU-time I needed for 14f* and 16q* I expect that 15f* will take more than twice as long as 17q*, so I started with 17q*, which is about 30% done.

The computer I am using is now going more and more into "production", so I am not entirely sure how much more CPU-time I can squeeze in and the results may take some time.

» login or register to post comments