<dik@cwi.nl> writes:
> Because it might interest the readers and to be ahead of Peter Beck:
> Saturday I received CFF (Cubism For Fun) # 28.
> It has an interesting article by Herbert Kociemba from Darmstadt, who
> describes his program to solve Rubik's Cube. He states that he has not
> yet encountered a configuration that required more than 21 moves. A short
> description follows:

it would be nice to know how many patterns he has tested.

Basicly the program consists of two stages, based on the groups:
G0: [U,D,R,L,F,B]
G1: [U,D,R^2,L^2,F^2,B^2]
G2: I
The stages are from G0 to G1 and next from G1 to G2. Note that the first
stage is the combination of the first two stages of Thistlethwaite, and
the last stages combine his last two stages.

His first stage can loosely be described as working in a three dimensional
coordinate system where the coordinates are resp. twist, flip and permutation.
He searches his way until the coordinate [0,0,0] is reached. Most important
here is that he is able to find multiple ways. The second stage is similar,
although he is not very clear here.

He uses lookup tables, but does not tell us how large his lookup tables
are. But his program runs on 1 MByte Atari ST. The heart is coded in
a few lines of 68k assembly, the remainder in GFA Basic. As far as I
know GFA Basic it can be interpreted, but also compiled. He does also
use tree pruning.

does he describe his method of "tree pruning"? this would seem to
be the "intelligent" part of the program, i.e. recognizing when to
abandon a given approach. if anyone has any insight on the tree
pruning, please let me know.

What he does is find successive solutions in stage 1 and fit solutions
from stage 2. Letting the system run longer generally finds shorter
solutions.

His claims are on average less than 14 turns in stage 1, on average less
than 10 turns in stage 2. But according to his article this is not completely
deterministic, so there is no proven upperbound. Perhaps a proof can be
found; I do not know. In practice he finds an upperbound of 21 moves, which
is indeed far better than other algorithms do obtain.

it's not likely that this will lead to a proof of an effective upper
bound. perhaps he can shave a few moves off the 42 obtained by
kloosterman, but i wouldn't expect him to prove an upper bound
anywhere near 21. probably the best bet for this would be to
exhaustively calculate the diameter of the group G_1 (with the
given generators) and the diameter of the coset space G_0 / G_1.
their respective sizes are: 19508428800 and 2217093120, both of
which are out of my league.

i'm not belittling kociemba's program; it's a very impressive feat!

To take this in perspective here Thistlethwaites results from Singmaster's book:
Stage 1 2 3 4
Proven 7 13 15 17
Anticipated 7 12 14? 17
Best Possible 7 10? 13? 15?
(Are there configurations that require the maxima proven for Thistlethwaites
algorithm?)

now look what happens when people use TABs! :-} (the "Proven" line
should be shifted to the left.)

i believe that the diameters of the respective coset spaces are exactly
those numbers listed in the "Best Possible" line. can anyone confirm
this? i've finally written a few programs, and those are the diameters
i get. i'm surprised that thistlethwaite didn't just do an exhaustive
search on these coset spaces. perhaps it's just a matter of not having
the technology when he did his work (~12 years ago).

Kociemba's algorithm appears however to be a big leap forward, although there
are no proofs yet. One example:

In 1981 Christoph Bandelow wrote a book where he offered a prize for the
shortest sequence of moves that would flip every edge cuby and twists
every corner cuby. The deadline was September 1, 1982; at that time the
prize was offered for a 23 move manoeuvre. As Christoph writes:
All solutions presented after the main deadline and shorter than
all solutions submitted before were also proised a prize. Using
his very ingeneous new search program Herbert Kociemba, Darmstadt,
Germany now found:
DF^2U'(B^2R^2)^2LB'D'FD^2FB^2UF'LRU^2F'
for 20 moves.

very nice. now how about "superflip," and also "supertwist?" these
are also reasonable candidates for antipodes of "START." i know the
following manuever for "supertwist" (22 face / 30 quarter turns):
U F' U' (L R2 F2 B')^4 U F U'
(obtained by conjugating a manuever singmaster attributes to thistlethwaite)

Kociemba himself writes about this:
Our first solution had 12 moves in stage 1 and 14 moves in stage 2.
In progress solutions 12+13, 12+12 and 12+11 were found. However,
as soon as we introduced manoeuvres of 13 moves in stage 1, we found
successively 9, 8 and at last 7 moves for stage 2. The program was
stopped after treating about 3000 solutions.
He further states that the first solution in general takes 95 seconds, but
successive solutions take much shorter, and in general he finds one of less
than 22 moves in a few hours on his 8 MHz Atari.

it would also be nice to know how long this first solution usually is.

from the figures i have (111207592 "different" sequences of 7 or fewer
twists and 167024 "different" sequences of 6 or fewer twists WITHIN G_1)
it's clear that exhaustive search is too cumbersome. thus i reiterate
both my statement that the "tree pruning" algorithm is the essential
part of this program, and my desire to know more about it (i.e. for
implementation purposes.)

dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland
dik@cwi.nl

thanks for the info!

mike             reid@math.berkeley.edu