From reid@math.berkeley.edu Mon May 4 23:38:05 1992
Return-Path:
Received: from math.berkeley.edu by life.ai.mit.edu (4.1/AI-4.10) id AA16784; Mon, 4 May 92 23:38:05 EDT
Received: from phnom-penh.berkeley.edu.berkeley.edu by math.berkeley.edu (4.1/1.33(math))
id AA06009; Mon, 4 May 92 20:37:54 PDT
Date: Mon, 4 May 92 20:37:54 PDT
From: reid@math.berkeley.edu (michael reid)
Message-Id: <9205050337.AA06009@math.berkeley.edu>
To: Dik.Winter@cwi.nl, cube-lovers@life.ai.mit.edu
Subject: Re: Are we approaching God's algorithm?
Cc: dseal@armltd.co.uk
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