From:

Subject:

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