God's Algorithm out to 18q*: 368,071,526,203,620,348

[rokicki]

Almost exactly four years after 17q* was announced by Thomas
Schuenemann, we have calculated the number of positions at a distance
of exactly 18 in the quarter-turn metric. This is more than one in
twenty positions.

This number matches (mod 48) the count of distance-18 symmetric
positions; this provides a bit of confirmation that it is correct
(or rather, about 5.6 bits of confirmation).

The approach we used does not permit us to calculate the number of
positions mod M or mod M+inv without significantly increasing the
amount of CPU required; these computations will have to wait for
someone with more ambition and more CPU time, or a different approach.

This new result is a part of our ongoing investigation into the
quarter-turn metric to complement the earlier work on the half-turn
metric. The bulk of the code is the same between this work and
that work, but some improvements have been made to search.

This work was supported in part by an allocation of computing time
from the Ohio Supercomputer Center.

This is joint work with Morley Davidson.

 

[qqwref]

Wow, crazy! 368 quadrillion is a huge number. I'm curious what techniques you are using to find info like this, although I understand if you don't want to release it.

 

[rokicki]

Wow, crazy! 368 quadrillion is a huge number. I'm curious what techniques you are using to find info like this, although I understand if you don't want to release it.

Thanks for the response!

We used pretty much the same technique as for the 15f* result---a coset solver. Indeed, we
used pretty much the same code as on cube20.org site, except we adapted it for the quarter-turn
metric, and we improved the search by putting actual full move sequences (encoded) in the
pruning table to cut down on the number of lookups.

But in the end, we burned a lot of cycles.

We'll be releasing the source soon (need to clean up some of the documentation and make it
prettier).

 

[Renslay]

Woah! That is pretty amazing!

The number of positions you examined is simply mindblowing.

Are you going to publish those results in a scientific paper?

 

[AvGalen]

1 in 20? That is twice what Ron did without a computer

Spoiler

http://blog.gmane.org/gmane.games.rubiks.speedsolving/month=20060901/page=11

Is there any reason to do this research or any conclusion you can draw from the results? Without that it just seems like science for the sake of science (which is still a good enough reason in my book)

 

[cuBerBruce]

1 in 20?

Except it seems that Tom meant 1 in 120, not 1 in 20.

 

[AvGalen]

Except it seems that Tom meant 1 in 120, not 1 in 20.

Yeah, I am getting 1 in 115, not 1 in 20. So disappointing that Ron still hasn't been beaten

 

[rokicki]

Yes; it's one in 120, not one in 20. That was a last-minute addition I did not double-check.
Arghh.

We will indeed be writing a paper and releasing source.

We do this because it's there, much like the reason we all solve the cube in the first place.
The new techniques needed to solve these problems are also interesting both from a
technology perspective and also from the perspective of advancing the art of search.

But mostly for me it's just part of my general interest in recreational computing.