From dik@cwi.nl Sat Aug 28 20:17:32 1993 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA00850; Sat, 28 Aug 93 20:17:32 EDT Received: from boring.cwi.nl by charon.cwi.nl with SMTP id AA17602 (5.65b/3.10/CWI-Amsterdam); Sun, 29 Aug 1993 02:17:26 +0200 Received: by boring.cwi.nl id AA01278 (4.1/2.10/CWI-Amsterdam); Sun, 29 Aug 93 02:17:23 +0200 Date: Sun, 29 Aug 93 02:17:23 +0200 From: Dik.Winter@cwi.nl Message-Id: <9308290017.AA01278.dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu, reid@math.berkeley.edu Subject: Re: Diameter of cube group? > ok, you caught me; i'd already tried this one myself. :-) > but apparently i wasn't as patient as you. i just remember that it ran > for a long time without doing better than 22 face turns. So did it here. 22 in a few minutes, 20 in a lot of hours. > the point to be made here is the following: the length of time the > program takes for a given position depends significantly on how far it > must search in stage 1. This is right, and it appears (though I have not yet thoroughly verified) that configurations that take a long time in stage 1 are a large distance from start. > this seems to make any claim about how long the > program takes to crunch an average position meaningless. Depends on how you interpret that claim. If the claim is that it turns up with a sequence that is 20 turns or shorter you are right. The claim might even be incorrect! The actual claim is that it takes a fairly short time to give a fairly short sequence (where fairly short is deliberately left unquantified). And this is true. For my set of >10000 random positions the program came up with a sequence of 27 turns or less in a short time indeed. (Actually the first solution found was 26 turns or less for all but three configurations.) Bringing that down to 20 took in a number of cases extremely long (in the order of one day). But that is still far less than when we had done a normal single phase backtracking process I think. > i think it would > be more informative to stratify this information. i.e., how long it > takes to search 12 moves in stage 1, and how short a solution is produced. > and then the same info for 13 turns, then 14, etc. Some quantification is not so very difficult I think. Without tree-pruning the time would be proportional to 18^n + 10^m for a n-turn phase1 and a m-turn phase2 solution. The tree-pruning performed is (I think) proportional to the number of turns in each phase; it will chop branches that are to large according to predefined tables. Also there are some short-cuts that make 18 not really 18 and 10 not really 10, but the reasoning remains the same. > what i've been amazed by (and continue to be) is that searching only 13 > or so moves in stage 1 is sufficient to produce very short solutions for > many positions. I do not think this is so very amazing. Each configuration can be brought in 12 turns or less to a configuration for phase 2. The proven diameter of the group of phase 2 is 25, my estimate is 19-21. So, based on my estimate a worst case would be 12 turns required in phase 1 and 21 in phase 2 giving 33 turns in an estimated time of 18^12 + 10^21, this is less than 18^17, and hence is found faster than if we had gone to 17 turns in phase 1. Actually both 12 and 21 are rare; most cases do phase 1 in 10 turns or less and phase 2 in 15 turns or less. > something i'd thought about trying, but never got around to is trying > random positions created by twist sequences such as: > F1 R1 B1 L1 F1 R1 B1 L1 F1 R1 B1 L1 F1 R1 B1 L1 F1 R1 B1 L1 > or some random string of about 20 quarter turns of the faces F,L,B,R. > a string of length 12 or 13 will be solved quickly (by the inverse of > the original string). however, for length 17 or so, the program won't > find the inverse of the original string until it is searching 17 moves > deep in stage 1. this suggests that perhaps these positions may be > harder for the program to handle. but are they harder than random > positions? i don't know. I do not know, but I think not. Yes, asking the program to find the reverse of the string takes a long time. Asking the program to find an inverse of the sequence takes much less time (although the inverse found may both be shorter or longer than the original). I just tried, and after initialization it found a 10+14 turn solution in 20 seconds, going down to 11+10 after less than a minute. Getting this down to 20 might of course take considerable time (if the original sequence is minimal etc.). But I have not the time right now to check. I am busy trying to prove that 20 is minimal for superfliptwist. I have already found that there is no 19 turn solution with 16 turns in phase 1. That took about 48 hours (distributed over 6 machines). Now I am doing the same for 17 turns in phase 1; which wil obviously take much longer. (And yes, I took the precaution of allowing as the first turn only F, F2, R, R2, U, U2 in phase 1. When I go to 19 turns in phase 1, I can skip 18, I need only F, F2, R and R2, I think.) dik -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: dik@cwi.nl