[next] [prev] [up] Date: Tue, 19 May 92 01:17:40 +0200
[next] [prev] [up] From: Dik T. Winter <Dik.Winter@cwi.nl >
~~~ [prev] [up] Subject: Re: My program is too fast ;-).

> stop it, you're killing me!
Stop yourself ;-).
> i wouldn't suggest using singmaster's notes for pattern
> maneuvers. have you seen bandelow's book? it has very short
> maneuvers for most patterns, including two different ones for
> "walker's worm" in 14 turns (assuming i've got the right pattern in
> mind). bandelow counts "slice turns" as one move, though, so
> his maneuver for 6X (order 3) is 24 face turns.
Leider haben wir nur die Deutschen Ausgabe. There are apparently
differences between the German and the English edition. The English
edition is later and has probably improved sequences (he has promised
also improved sequences for the second German edition, but I do not
think it ever came out).

> what amazes me about this whole business is that the algorithm
> finds very short moves when they exist. i would have expected
> the program to produce maneuvers of approximately the same
> length for all patterns. i would say that this is a major step
> forward.
The point is that my program deliberately tries short sequences first in
both phases. This is at the expense of more work when longer sequences
are tried (because you will find the shorter sequences again that you
abort). The main advantage is that if you find an overall short sequence
you have much less work to do in the second phase, and can much faster
abort your searches. Here some information about the searching for
superflip (the numbers are for phase 1):
Length Number found Solutions found
8 0 -
9 0 -
10 3072 10+13, 10+12
11 61568 11+10
12 792256 -
13 8695488 13+ 7
As you see when having the large number of solutions for length 13 in phase 1
we have only to look at most 7 moves deep in phase 2, and 6 deep as soon as
we found the solution (which occurs reasonably fast). That is why it is
possible to do all that work in about 45 minutes. (For der Mouse, the machine
is an FPS. A SPARC processor twice as fast as a SPARCStation ELC. But I
think the program is bounded by memory access time. The program requires
about 12 MB memory.) Now I think the longest distance in phase 1 is about 11
or 12 (it is at least 11, that is sure). So in general you will find a
solution already when there is no need yet to do very much.

 > you'll probably be swamped with patterns to test, but here's a
 > couple:
 > stripes: (18) F3 U1 F2 U3 R1 B2 R3 U1 F2 L2 U3 L1 B2 L3 U1 L2 U3 F1.
 > python: (15) R1 U3 F3 B1 L1 F2 L3 F1 B3 U3 R3 L1 F2 U2 L3.
I could not improve the first but what do you think of:
(12+ 2=14): U2 B3 D3 L1 F1 B3 U3 F1 U3 D1 R3 B1 D1 F2

> since i found these by hand, i'm curious to see how close they
> are to optimal. hopefully i'll have my program running soon.
14 for python is probably optimal. But you can try as you have your program

[next] [prev] [up] [top] [help]