Home »

God's Algorithm out to 17q*

Submitted by tscheunemann on Wed, 07/14/2010 - 15:25.
Well it's done. Here are the results in the Quarter Turn Metric for positions at exactly that distance: 
 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
17 426192982714390 423418744794278 846837132071729 40648181519827392
And since this is probably the last result in the Quarter Turn Metric for some time (say at least a year) for reference the same for positions up to that distance 
 d  (mod M + inv)*   mod M + inv       mod M             positions
-- --------------- --------------- --------------- -----------------
 0               1               1               1                 1
 1               2               2               2                13
 2               7               7               7               127
 3              24              24              32              1195
 4             159             154             251             11206
 5            1224            1185            2229            105046
 6           10874           10578           20624            983926
 7           98910           96761          192153           9205558
 8          916134          899549         1793878          86049153
 9         8492979         8381931        16750144         803838729
10        79044267        78215703       156379338        7505675587
11       736278884       729829304      1459517783       70055290835
12      6864008705      6808918391     13617296850      653625391832
13     63966788843     63500692004    126999819232     6095977016860
14    596195165923    591936888530   1183867516969    56825597219442
15   5551256006313   5513775281036  11027529237603   529321276030446
16  51631742042811  51280174258118 102560251625626  4922891682250569
17 477824724757201 474698919052396 949397383697355 45571073202077961
*The first column is again the number of symmetry reduced positions but only considering the symmetry of the coset which is a fixed edge cube position.

As expected the calculation went without problems with only one hiccup (24 of the biggest cosets wouldn't fit in a single node). To get further than that I would certainly need a bigger computer. Memory is one problem but that could be addressed by using less cores or by using cores in parallel to calculate a single coset. CPU time is the other problem. For a community effort the problem is still to big. PCs with 16 GByte RAM are out there but still not to commonplace.

My 15f* calculation is well underway. I have already done the 210000 biggest cosets, without any memory problems and the rest is only a question of time. But that again in the Full Turn Metric will be it for the time being.

» 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.

Incredible!

Submitted by rokicki on Thu, 07/15/2010 - 23:44.
In less than a year, we've extended Jerry Bryan's results in the QTM by *four levels*---that's absolutely amazing!

How many core-hours did this take? How many do you think 15f* will take? How about 16f*? (Ignore memory issues for now.)

Do you think the program could be made faster?

Let's see. I found 870/1e6 17q*'s; you get 0.000940. Anyone know enough statistics to see if that's within the expected variance for a sample size of 1M entries?
» login or register to post comments

stats

Submitted by Mike G on Mon, 07/19/2010 - 10:07.
I'm no expert, but would reason it as follows:

I assume that you made N=1e6 independent choices of position and that the chance of any one of those being a 17q position was p=9.40e-4. Then the number, k, of trials yielding a 17q position should follow a binomial distribution with mean Np=940 and standard deviation sqrt(Np(1-p))=30.6.

Your result k=870 is about 2.3 standard deviations away from the mean. Since the binomial distribution is very nearly Gaussian for these values of N, p, and k, it's easy to look up the probability of getting a result MORE than 2.3 standard deviations away from the mean in either direction. This probability is about 2%.

Whether to regard that 2% as significant depends on whether you have any doubts about the sampling method: e.g., were your choices of position truly independent? Otherwise, if there are no doubts, it just says you were unlucky to be that far away from the mean.
» login or register to post comments

Random number generators

Submitted by rokicki on Wed, 07/21/2010 - 10:36.
Well, I plugged the Mersenne twister as implemented in the Gnu
Scientific Library into my code, and reran 1M random positions
through ply 17, and got 932 distance-17 positions. So I think
my use of drand48() caused my results to be not-so-random (or
I was just unlucky).

I am tempted to rerun 1M random positions in both HTM and QTM
using the Mersenne twister random number generator, but that
was a *lot* of CPU time, and the impact is reasonably small as
far as I can see.
» login or register to post comments

Choosing Random Cubes

Submitted by Jerry Bryan on Wed, 07/21/2010 - 11:57.
Also, are you scrambling cubes by making a series of randomly chosen moves, or are you directly choosing randomly chosen positions? For the latter, I mean the following. Most people designate a position with four indexes - permutation of corner cubies, twist of corner cubies, permutation of edge cubies, and flip of edge cubies. With this model, the permutation of corner cubies is a number from 1 to 8!, the twist of corner cubies is a number from 1 to 37, etc. Subject to making corners and edges have the same parity, generating a position pseudo-randomly would then reduce to pseudo-randomly choosing a random value for each of the four indexes.
» login or register to post comments

Random cubes

Submitted by rokicki on Wed, 07/21/2010 - 23:25.
The latter. I do a corner permutation selection, corner orientation selection, edge permutation selection, and finally edge orientation selection.

No random moves here.

-tom
» login or register to post comments

Independent

Submitted by rokicki on Mon, 07/19/2010 - 23:20.
Thanks for the analysis. I've actually been chasing this myself and am frustrated that it's so far off but agree it could just be bad luck.

I am using drand48() and it's not the best random number generator in the world. It's *possible* there is some slight pattern there that's affecting me, but I think it's unlikely.

I reran all 1M positions using a completely different solver (limiting it to depth-17 search) and did not find any mis-solves, so I believe my optimal solver is good.

I'm running just odd positions now, and just through a ply-17 search, to see what sampling gives me. I've run 3,371,042 odd positions so far and seen 6,200 distance-17 positions. That's 0.000919596967, which is much closer (you have to multiply the denominator by 2 because I'm only running odd positions). I think this is just about the same in terms of unlikelihood though. I suspect my random number generator (drand48()) may be tripping me up.

I'm going to continue to investigate until I understand what is going on. (Or, I could just plug in a better random number generator and see if things get better.)
» login or register to post comments

Core hours

Submitted by tscheunemann on Fri, 07/16/2010 - 07:37.
For 17q* a single coset took at average about 5 minutes on a 1.9 GHz Opteron Core and there are 2510835 odd cosets. There are faster cores out there but not that much.

For 15f* a single coset takes at average about 8 minutes and I have to calculate all 5022205.

For 16f* a single coset should take at least about ten times as long.

I guess generating positions can't be made much faster, but checking for duplicates and storing positions could of course be made faster by using a bit table. At 40320*2048*2187/2 positions the table needs 11 GBytes of memory but checking and storing are bit operations instead of a binary search and inserting into a table and getting rid of dynamic memory allocation helps too. In a quick test with only the largest 15f* coset time was reduced from 25 minutes down to 15 minutes.

» login or register to post comments