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