Home »

Some thoughts about a proof, that 24 moves suffice

Submitted by Herbert Kociemba on Thu, 04/03/2008 - 11:28.

I thought about the number of cosets of H=<U,D,R2,L2,F2,B2> we need to compute to show, that 24 moves suffice.
It is not difficult to show that the number of cosets needes for 24 moves is at most 64430, provided that we get a maximum of 20 moves in each coset (which is quite realistic).

In my way to enumerate the cosets, the flip of the edges and the positions of the four UD-slice corner give a symmetrized coordinate x with 0<=x<64430. The orientation of the corners give a coordinate y with 0<=y<2187 . Multiplying these numbers gives 140908410, which is slightly more than the actual number of symmetrized cosets, which is 138639780, so some pairs (x,y) describe the same coset, but this doesnt matter.

Now we take a look at the distribution at the distances of the corner-orientations, starting with the identity orientation y=0:

distance   positions
  0           1
  1           4
  2          34 
  3         186         
  4         816
  5        1018 
  6         128

So if we show that for all 64430 cosets (x,0) we need at maximum 20 moves, this guaranties at most 26 moves, max. 6 moves to go to the identitiy orientation and max 20 moves to solve this position - nothing new at all.

I computed this distance tables with all possible start values for the orientation. The maximum distance is 6 in 147 cases, 5 in 1968 cases and 4 in 72 cases. Starting with an example position y0 with maximum distance 4 we have

distance   positions
  0           1
  1          16
  2         181 
  3        1087         
  4         902

So if we compute all 64430 cosets (x,y0), x<64430 and show for them <=20 moves indeed have shown that 24 moves suffice.

It is clear hat another choice of cosets might significantly reduce the number of cosets to compute, but computing coset-classes with 64430 cosets based on the corner-orientation has the advantage that the enumeration is quite easy.

I tried what is the best combination when generataing a distance table starting with two values for the orientation, and found some y1 and y2 with

distance   positions
  0           2
  1          36
  2         420 
  3        1575         
  4         154

So computing all the cosets (x,y1), x<64430 and (x,y2), x<64430 significantly increase the number of positions, for which 23 moves suffice.

Because I do not have a machine with enough RAM, I cannot tell how long it takes on average to show <= 20 moves for a single coset. Tom will tell us. But I think it is less than 1 hour and with 40 PC's it would take les that two months to make the 24 move proof in this way.

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

I think a made a mistake above

Submitted by Herbert Kociemba on Thu, 04/03/2008 - 18:00.
The problem is the symmetrized coset definition. Because the x<64430 is the symmetrized coordinate and not the y<2187, a symmetrized coset class represents up to 16 cosets with usually 16 different corner orientations.

So if you take the cube for example with four moves to the corner orientation y0, the other coordinate is actual a pair (x,s) where s is one of 16 symmetries. It depends on the the symmetry part s of (x,s), to which symmetrized coset this cube actually transforms. It is not (x,y0) but some (x,y') where y' is the conjugation of y0 by the symmetry s.

But because we do not know in advance, what y' is, we must compute all possible outcomes, that is usually 16*64430 cosets which is of course too much with the current hardware.
On the other hand, with this new approach we may initialize the distance table for the corner orientation in distance 0 not only with one position but also with all conjugate positions. I have found two corner orientations y1 and y2, so that the maximum distance to one of these two or to their conjugates is 3 at maximum: 

distance   positions
  0          32
  1         416
  2        1394 
  3         345
So 32*64430 is an upper limit for the number of cosets to compute for a 23 move proof. Again, a more clever choice of the cosets of course will reduce this number considerably.
» login or register to post comments

For a proof of 23

Submitted by rokicki on Thu, 04/03/2008 - 18:45.
A quick greedy run (that did only 32 trials for each selection) finds that 253,605 cosets is sufficient to prove 23. If we use 8-core machines, 25 minutes a solution, that works out to 551 machine days, so that's about 20 machines for 28 days. I think a proof of 23 is within reach. (I am sure that count of cosets can be easily reduced just with more trials in the greedy approach.)
» login or register to post comments

If you take these 253605 cose

Submitted by Herbert Kociemba on Fri, 04/04/2008 - 03:56.
If you take these 253605 cosets it also would be interesting how much time it takes on average for one coset to show that it has at most 22 moves and if that would be an alternative to your about 4000 cosets to show that these have at most 20 moves in your 25 move proof.
» login or register to post comments

Runtime: 20 vs 22

Submitted by rokicki on Fri, 04/04/2008 - 11:03.
Right now, running the search phase to depth 16 and the prepass all the way, for the typical coset, splits the time pretty evenly between search and prepass. Reducing the search phase gives at best a 2X speedup. For many respects, doing the search phase to 16 is a sweet spot. If the search phase goes to 17, you'll spend almost all your time there and seldom prove a set to be 19 or better with just that, but if you only run the search phase to 15 you maybe run 2X faster but now you typically only prove 21, with a *lot* of positions remaining at 21.

There is the occasional set for which search at 16 still leaves a ton of 21s on the floor (tens of thousands in one case). Luckily, the six-axis Kociemba algorithm will crank through these amazingly quickly, finding distance-20 positions for each.
» login or register to post comments

Great topic!

Submitted by rokicki on Thu, 04/03/2008 - 12:27.
This is a *very* pertinent topic, and one that I am extremely interested in. I will need to spend some time reviewing your ideas, because I think they can lead to even greater reductions in the count of cosets.

Right now, my (full) list of cosets to solve to prove 24, assuming each comes in at a distance of 20, has 26,380 cosets in it. (This list is self-contained; it does not depend on any cosets I have solved to date, nor on any cosets having a distance of less than 20.) I am sure this can be reduced significantly, perhaps even as much as 2X. I generated this list using a program that is greedy; tries to find the coset that reduces the count of remaining cosets >= 25, for some number of trials, picks that coset, and then repeats.

This list also does not use any of my "eliminating unnecessary cosets" ideas; I've found this does not appear to significantly reduce the count of cosets required, so I've eliminated it to also eliminate a potential source of bugs. Perhaps other people will find different results.

If anyone has any additional ideas on how to reduce the number of cosets, I'd be delighted to hear them. This problem seems related to the vertex cover problem, which is notoriously difficult. Any sort of reasonable heuristic or other solution technique would be great.

Using only a single core, my program (which has been improved) currently runs in about 20-25 minutes on a particular coset to prove it can be done in 20 moves, and takes 3.3GB of RAM. (With multiple cores, as the Q6600 has, it runs faster, but I have not yet achieved linear speedup.)

A proof of 24 may not be far off, indeed.
» login or register to post comments