jerry writes

I read the articles in the archives about Kociemba's algorithm about
a year ago, without (I confess) fully understanding them. In particular,
I do not fully understand what differentiates Kociemba's algorithm from
Thistlethwaite's algorithm, other than it uses a different arrangement
of nested subgroups.

thistlethwaite's algorithm is a method which guarantees solving any cube
in at most 52 (well, now it's 44) face turns. i don't think it was ever
really used to find short solutions (although at the time it was invented,
52 face turns may have been considered short).

kociemba's algorithm is a method for finding short solutions. it didn't
come with any guarantees, (although i've just shown that the first solution
it finds is at most 43 quarter [30 face] turns, and in these extreme cases,
it will quickly find a shorter solution.) kociemba gave an effective way
to navigate through the sequence of subgroups

G = <U, D, F, R, B, L>,   H = <U, D, F2, R2, B2, L2>,   1 = <>,

without using enormous tables. (this is how it differs from thistlethwaite's
method, and also why there are (well, were) no guarantees.)

kociemba also allows non-optimal sequences in stage 1 in exchange for
shorter sequences in stage 2. we start by finding all length n sequences
in stage 1, and for each, the shortest sequence in stage 2. then we move
on to length n + 1 in stage 1. kociemba's method is so effective, that
searching through length 14 or 15 in stage 1 is usually quite feasible.
also, this technique has been so successful that it's improved many of the
shortest known maneuvers.

But in the meantime, I wonder if you could verify that Kociemba's
algorithm does not guarantee to find a minimal process? In particular,
is it the case that 26q is a minimal superflip, or is it only an
upper bound?

26q is only an upper bound. my program will eventually find the shortest
process, well, if my os doesn't crash first, the universe doesn't end, ...
but i've only given the shortest maneuver it's found so far. at some
point you've gotta give up. (there are plenty of other patterns waiting
to be stuffed into this program. :-) )

The reason I ask is that I have decided to go ahead and calculate God's
Algorithm under quarter turns for depth 11. (Through depth 10 is
already in hand.) Once that is accomplished, it should be a
*fairly* easy task to establish a lower bound on the superflip
at 22 quarter turns via two half depth searches.

you should search with the list you have right now. (i presume you're
talking about a list of all positions within 10q of START.)

you will either find a maneuver of length <= 20q (unlikely, i'd say),
or you will show that its distance from START is >= 22q. this latter
possibility would be very exciting, since it would raise the lower
bound on the diameter of G.

I can already establish a lower bound of 14 quarter turns on the
superflip.

my program can do this in only a few seconds! in fact, it takes 12q
to get from superflip into the subgroup H. since we may also suppose
that the last twist in a shortest maneuver is U , it follows that
superflip requires at least 13q (and thus 14q , by parity).

mike