From:

Subject:

<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