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