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