Home

Results of two more cosets of the H group, this time face turn metric.

Submitted by rokicki on Fri, 03/24/2006 - 23:35.
After seeing Silviu have such success with H group (U, D, F2, B2, R2, L2) cosets, I decided to give it a shot in the face turn metric. So far I've completed the identity coset and the flip8 (upper and lower edges) cosets; the superflip coset and flip4 (middle edges) are still running. The identity, flip4, flip8, and superflip are the four centers of the H group. I've also shown that of the approximately 234,101,145,600 positions represented by these four cosets, none have a depth greater than 21. This exploration covers more than 5/1,000,000,000 of the total cube space. The identity coset has the following depths. For comparison on the right I've also listed the depths using only the ten moves that are in H because the two lists are so very close (the second column is also my confirmation of the numbers originally posted by Michael Reid back in January of 1995): 
 d     all moves     moves in H
 0             1              1
 1            10             10
 2            67             67
 3           456            456
 4         3,079          3,079
 5        20,076         19,948
 6       125,218        123,074
 7       756,092        736,850
 8     4,331,124      4,185,118
 9    23,639,531     22,630,733
10   122,749,840    116,767,872
11   582,017,108    552,538,680
12 2,278,215,506  2,176,344,160
13 5,790,841,966  5,627,785,188
14 7,240,785,011  7,172,925,794
15 3,319,565,322  3,608,731,814
16   145,107,245    224,058,996
17       271,112      1,575,608
18            36          1,352
  -------------- --------------
  19,508,428,800 19,508,428,800
The average depth using all moves is 13.5323; using only the ten moves in H is 13.5803, so restricting the second phase of the Kociemba algorithm to moves in H probably doesn't have a large impact on the final solution length. For the flip8 position, the depths are: 
6            128
7          2,480
8         29,616
9        275,072
10     2,025,588
11    12,857,588
12    77,246,640
13   420,070,470
14 1,878,234,188
15 5,160,105,314
16 7,283,921,362
17 4,500,551,722
18   173,096,184
19        12,448
  --------------
  19,508,428,800
I anticipate the other two cosets will complete shortly; they both have fewer than 1000 positions remaining. Thank you to Silviu for both proving it could be done and discussing his approach with me. This is a much more effective coset to search (in terms of optimal solutions per second) than the edge cosets I had been using.
» login or register to post comments

Comment viewing options

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

Still no 21s

Submitted by rokicki on Thu, 04/06/2006 - 15:15.
Okay, I've completed 303 cosets of this group (using a Kociemba two-phase approach), without coming close to finding a 21. These cosets represent about 1.7e14 positions out of the 4e19 positions, so I've found a solution of length 20 or better for more than 4 millionths of the cube space. Except for the four cosets I ran in the normal way, not a single coset has required more than 18 moves in phase 2.

I will probably terminate this investigation soon as the likelihood of finding a depth 21 position appears to be very small.
» login or register to post comments

Did not you mean ....not a si

Submitted by Herbert Kociemba on Fri, 04/07/2006 - 06:47.
Did not you mean ....not a single coset has required more than 18 moves in phase 1?

I still am impressed of the speed of the computation. You said that you generate about 15 million nodes per second. I also experimented with your approach, and with a 3 GHz machine I only get 5 million nodes per second. I localized the problem in the single instruction which reads the value from the pruning table. Without this line I get 20 million nodes per second. I have no idea how to change this behaviour.
» login or register to post comments

Not a single coset has requir

Submitted by rokicki on Fri, 04/07/2006 - 12:42.
Not a single coset has required more than 18 moves in phase 1 (except *possibly* for the first four I ran with the numbers listed exhaustively above, because I ran those in full-optimal mode, not in Kociemba mode).

The 15 million nodes per second I think is a bit bogus for two reasons. First, for a coset investigation, there is a lot of work done for low depths in the pruning table, where things are likely to be in cache, as opposed to a more normal search where you spend almost all your time in the outer reaches of the pruning table where things are not in cache. Secondly, with the version I'm running now, the node count is actually reduced (I don't explore as many nodes) because I'm using a direction table as well, that tells me information on what moves might reduce the depth, so I don't explore all possible moves from each position.

Finally, I'm using a not-fully-symm-reduced pruning table (only 8 times instead of the possible 16 times) because this lets me use smaller transition tables (I use separate corner permutation, edge permutation, and edge orientation symmcoords, and don't combine them at all for transitions). I'm not sure if that makes any difference.

So I wouldn't worry about the node rate; I think my reported 15M number is only valid for this particular type of investigation, and that a 5M node per second rate is actually amazingly fast for a more general search.
» login or register to post comments

The flip4 coset finally compl

Submitted by rokicki on Mon, 03/27/2006 - 23:20.
The flip4 coset finally completed; here is its distribution. I'm surprised at the low average depth. I hope I haven't made a mistake. 
10         2,944
11        78,656
12     1,228,768
13    14,644,176
14   143,702,755
15 1,106,407,845
16 5,318,444,378
17 9,940,797,145
18 2,978,032,610
19     5,089,463
20            60
» login or register to post comments

The four cosets you computed

Submitted by Herbert Kociemba on Tue, 03/28/2006 - 11:38.
The four cosets you computed really do not seem to be representative for the distribution of a random coset. Because the fractional part of all 10-move maneuvers is 5.37*10^-9, there should be only about 105 10-move maneuvers on average in one coset. It is far more in all four cosets.

I am quite sceptical if the computation for random coset will finish within a reasonable time.
If it takes a few days for each of the 4 cosets done, I estimate more than a month with a random coset where the average maneuver length is about 1 higher.
» login or register to post comments

I've been running some additi

Submitted by rokicki on Fri, 03/31/2006 - 16:34.
I've been running some additional cosets in "Kociemba mode"---that is, do the non-H search to a certain depth, and try to complete it with only H moves. With this approach I've been able to complete an additional 63 (and still running) cosets, primarily those at distance 12, 11, and 10, and primarily those with some degree of symmetry. By complete, I mean I only verified that for these cosets there are no depth-21 positions. All told this represents more than 2E13 cube positions of the 4E19, so I've explored approximately one two-millionth of cubespace (and by and large a deeper-than-representative portion because I start so deep in H) and not found a 21. If there is a 21, it's pretty elusive.
» login or register to post comments

Up to which depth you ran the

Submitted by Herbert Kociemba on Sat, 04/01/2006 - 07:15.
Up to which depth you ran the first phase?
And what size has the bitvector you use?
» login or register to post comments

I ran the first phase at incr

Submitted by rokicki on Sat, 04/01/2006 - 12:57.
I ran the first phase at increasing depths. I start most runs at depth 16 (but some I start at depth 15). If that doesn't find solutions for all positions in less than 20 moves, I try depth 17, and so on.

So far no coset has required me to explore a phase one beyond a depth 18. Most seem to succeed with a depth 17 search.

I've finished over 100 cosets now.
» login or register to post comments

Yeah, a random coset will def

Submitted by rokicki on Tue, 03/28/2006 - 12:35.
Yeah, a random coset will definitely take quite some time to compute. It's still the fastest coset I've seen, in terms of optimal solutions per second. And I still have a few ideas for making it yet faster. So all hope is not lost.
» login or register to post comments

I will try to compute another

Submitted by Herbert Kociemba on Tue, 03/28/2006 - 14:19.
I will try to compute another sort of cosets. With my very huge optimal solver I use a table which is 70 times larger than the usual pruning table with 64430*2187 entries to go to phase 2. The target group is 70 times smaller now, with "only" about 278 Mio elements.
Because the average pruning depth is about one more compared with the standard pruning table it should be significantly faster and I hope that the computation for 70 cosets of this kind is faster than the computation of one coset of the 70 times larger group H.
» login or register to post comments

It's definitely worth a try!

Submitted by rokicki on Tue, 03/28/2006 - 19:53.
It's definitely worth a try!

My thoughts however are this. For a given coset, I believe you will end up exploring every possible solution up to the maximum length for every given position in that coset. That is, if position g is in your coset, and g has 15,391 solutions of length 20 or less, then no matter what pruning table you use, you will explore all 15,391 solutions when you explore that coset. (This is with a straightforward coset explorer that simply "solves" and then indexes into a bitvector.)

If this is true, then the only way to speed things up is to speed up your nodes per second, speed up your bitvector/indexing, or use some tricks to work around this duplication. Or try to explore cosets such that all deep positions are grouped together separately from the shallow positions, if that's possible.

So I don't think a deeper pruning depth actually helps here. I think the deeper pruning depth simply reflects the fact that you're solving fewer positions, nothing more than that.

On the other hand, there is this concept of reasonable computation time. For me, it's about 24 hours, and depending on how interested I am, perhaps up to a week (168 hours). Beyond that, I get distracted by other problems. So for this situation, certainly a smaller coset is preferable.
» login or register to post comments

superflip coset finished

Submitted by rokicki on Sun, 03/26/2006 - 11:45.
The superflip coset has finished; here is the distribution. The interesting thing is, despite my expectations, this coset has a lower average distance than the cube as a whole. 
10         2,560
11        70,272
12     1,120,128
13    13,538,360
14   133,692,540
15 1,025,239,348
16 4,847,352,684
17 9,437,764,905
18 4,030,528,357
19    19,118,966
20           680
» login or register to post comments

Very nice result. How many 20

Submitted by Herbert Kociemba on Sun, 03/26/2006 - 15:16.
Very nice result. How many 20f there are M+Inv-reduced? Did you store the maneuvers for the 20f during your run? I would be interested in them.
It also would be interesting to compute a random coset to see how close this distribution will be to the whole cube distribution.
» login or register to post comments

Unfortunately, because of my

Submitted by rokicki on Sun, 03/26/2006 - 15:50.
Unfortunately, because of my optimizations in the search phase, this search did not include the solutions (although I do know the positions). I am currently trying to figure out how to recover the move sequences.

Since I don't have any good notation for positions, the way I'm dumping the positions is raw symmcoords, so there's no easy way to figure out the symmetry of the positions without writing more code. I'm also working on this.

And you're quite right; a random coset (or several!) would definitely be interesting. I suspect I'll start with the high-depth, high-symmetry cosets first, however; they run faster.
» login or register to post comments

I would like to do this too..

Submitted by Herbert Kociemba on Sat, 03/25/2006 - 03:26.
I would like to do this too....;-)
How many time did you need to compute the two tables? Did you solve some of the remaining positions individually?
Would it be possible to compute cosets of one of the G/H 12-moves antipodes?
» login or register to post comments

The identity coset took 14 ho

Submitted by rokicki on Sat, 03/25/2006 - 10:27.
The identity coset took 14 hours to complete. The flip8 coset took 32 hours to complete. In both cases, they ran to completion without any manual work (running of remaining positions or anything like that).

It would indeed be possible to compute the cosets of the antipodes. Right now the program has some simplifications that pertain only to the center positions, so I ran those first, but I plan to generalize the program to run any coset of H; this should be straightforward but I want to be cautious to make sure I don't goof up. For the center cosets, I had assistance from Silviu with his completely independent implementation so we could compare numbers and make sure they matched; I'm hoping he'll help me for the non-center cosets too.

This coset is particularly nice for at least three reasons:

1. The H group splits down into symmcoords beautifully and those symmcoords can be computed very fast; I'm getting about 14M nodes a second on a P4. That's far faster than any other coset/pruning table I've tried.

2. Moves within H at the end of sequences can be computed separately from the main search since they stay within the group; that is, the main search need only consider sequences that end in a non-H move. This gives tremendous speedup.

3. Moves that leave the symmcoords unchanged at the beginning of sequences can likewise be done separately from the main search; in the case of the center position, these are all moves in H.

So for the center position, the main search only considers sequences that both begin and end with moves not in H. This makes things a lot faster.

Further, to prove there are no 21s, you typically don't need to run a deep search; you can use what I call the prepass (a linear scan over the found positions, extending them by moves in H for (2) above, and by premoves for (3) above) repeatedly to find non-optimal solutions; I was able to prove the absence of any length-21 positions in less than an hour each for each of the four center cosets this way. Consider it nothing more than the Kociemba algorithm run in parallel; it's really little more than that.

Your cube explorer program already contains almost all the code you need for this, just add code to index the cube by the permutations of the corners and edges, add a big bitvector, maybe some symmetry reductions of that bitvector, and you've got essentially what I am running. Most of the implementation time for my program was spent reimplementing the H symmcoords (and your website was a great help with that); this is my first actual programming experience with this particular group.
» login or register to post comments