Home »

In search of: 21f*s and 20f*s; a four month odyssey.

Submitted by rokicki on Sun, 05/07/2006 - 12:21.
In January of this year I set out to find a 21f* position---or, at the very least, extend the set of known 20f* positions. At that time I knew of only three 20f* positions, despite having exhaustively solved several collections of pretty patterns and performed months of optimal cube solutions.

At this point, I have found no 21f* positions, but with Herbert Kociemba and Silviu Radu, have found 11,313 (mod M+inv) 20f* positions. This set represents 16,510 mod M positions, and 428,982 overall cube positions. The majority of the positions were found by Silviu using a spectacular coset solver that he will write about soon.

In addition to running my coset solver in a mode to find 20f*'s, I also have been running it in a faster, two-phase mode to prove that there are no 21f*'s in that coset. So far I have finished running over 1,000 cosets in this two-phase manner. These cosets are of size 19 billion positions, and depending on the symmetry of the generating position can represent up to 1.9 trillion total positions each. In total, the cosets I have run represent 7.6e14 positions out of 4e19, or about one cube in 53,000---and there are no 21f*'s in all these positions.

All the technology I have been using has been previously presented on this list. Silviu has some new technology he will be sharing with us soon. In addition, Kociemba has implemented (and perhaps improved) some of the technology himself.

The total set of found 20f*'s are available at http://tomas.rokicki.com/all20.txt.

I plan to continue running both efforts (the 20f* search and the 21f* search) for a little while until something else comes up to occupy the machines. At some point I may turn my attention to the quarter-turn metric to see if there are any other 26q*'s, or perhaps a 27q*.

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

Making pictures of the 20q+h positions

Submitted by cubex on Thu, 06/15/2006 - 13:31.
I was just thinking it might be interesting to see some pictures of the 20 q+h positions. With your permission I'll like to post some of them at some future time. Do we still only have one known position at 26q?

Mark
» login or register to post comments

Pictures

Submitted by rokicki on Thu, 06/15/2006 - 17:43.
Sounds great! I still only have one 26q position. I haven't searched too hard in this space, though.

I've looked at so many of these tens of thousands of 20f* positions and to me, so far, they all pretty much look random.
» login or register to post comments

Due to some impossibly excell

Submitted by rokicki on Tue, 05/09/2006 - 21:46.
Due to some impossibly excellent work by Silviu, the count of 20f*'s is now up to 30,401. Still no 21f* in sight.
» login or register to post comments

That's a lot of 20f* position

Submitted by Mike G on Wed, 05/10/2006 - 11:01.
That's a lot of 20f* positions. :)

Do any of them lack symmetry? And how much of the searching has been done on positions (cosets?) without symmetry?
» login or register to post comments

As you can see from Tom's fil

Submitted by Herbert Kociemba on Wed, 05/10/2006 - 16:00.
As you can see from Tom's file all20.txt, in the moment there are "only" 1279 20f* positions without symmetry. But this does not mean that there are less 20f* without symmetry than with some symmetry.
The percentage of positions with 20f* in the symmetric subgroups is much higher than in the cube group itself, so this was the main reason to take a closer look at the symmetric subgroups.

While I was only able to find the 20f* in the smaller symmetric subgroups (the biggest was D2 (face) with about 300000 elements) Silviu Radu managed to completely analyze the really big symmetric subgroups like Ci etc. with billions of elements in a really beautiful way and I hope he is telling us more about his method here soon. Only two subgroups are left and I am sure we soon know that all symmetric positions of the cube can be solved within 20 moves.

Doing this classification is the reason that we know much more symmetric 20f* positions in the moment than unsymmetric 20f* positions.

But it is not difficult to get many unsymmetric 20f* positions: Just take a symmetric 20f* position as the representant of a coset and do a coset search (the cosets I use have about 280 million elements and take about 4 hours to 2 days to compute depending on the symmetries). Typically a get in the order 10 to 100 new 20f* positions, though it also happens that the representant is the only 20f* position in the coset. Most of them have no symmetries. So I am sure that there are much more 20f* without symmetries than there are 20f* with symmetry.
» login or register to post comments

Yep, out of the (still-increa

Submitted by rokicki on Wed, 05/10/2006 - 15:25.
Yep, out of the (still-increasing) 30,403 (mod M+inv), there are currently 1,279 positions that are not symmetric mod M. Of these, 10 are self-inverses and 384 are antisymmetric but not self-inverse; the rest are not antisymmetric.

Most of the cosets explored have exhibited symmetry, but a few have not. I have not run any positions totally lacking in symmetry with the big 19B solver yet because I still need to make one more modification in order to do that (I need to make it do the prepass to and from disk).

I believe most 20f*'s lack symmetry; the reason symmetrical positions are so common in our current list is because the majority of those positions were found by Silviu using a profound and amazing discovery I hope he will share soon.
» login or register to post comments

It's Silviu Radu; sorry I got

Submitted by rokicki on Mon, 05/08/2006 - 10:27.
It's Silviu Radu; sorry I got the name backwards in the story. If anyone can fix the story, that would be excellent! Thanks!
» login or register to post comments