From cube-lovers-errors@oolong.camellia.org Wed Jun 4 17:30:26 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA04584; Wed, 4 Jun 1997 17:30:25 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <33959796.3784@hrz1.hrz.th-darmstadt.de>
Date: Wed, 04 Jun 1997 18:28:06 +0200
From: Herbert Kociemba
X-Mailer: Mozilla 3.0 (Win95; I)
MIME-Version: 1.0
To: Dan Hoey , cube-lovers@ai.mit.edu
Subject: Re: Detailed explanation of two phase algorithm
References: <9706040106.AA26157@sun34.aic.nrl.navy.mil>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Dan Hoey wrote:
>
> > ...If you analyze the preceeding phase1 algorithm you will see that
> > it is indeed just an IDA* with lowerbound heuristic functions based
> > on tables.
>
> It sure is. Now here's a question. Should it be combined with phase2
> in such a way that the entire search is IDA*?
>
> The way I would see this happening is that whenever you get to phase 2
> (at depth i with a cutoff of L1), instead of allowing the phase2
> search to iteratitively deepen, you run a depth-first A* search with a
> fixed depth cutoff of L1-i. It would take longer to get the first
> answer, but when you got an answer it would be optimal, and you would
> never spend time searching longer processes.
>
I try to understand but I can't grasp the idea. Maybe I did not describe
clearly enough, how phase1 and phase2 work together.Doing the entire
search in one single IDA* will result inevitably in a program, which
applys IDA* to the whole cube group in my opinion. Rich Korf did this
now. I could not do this (though I would have liked to do) due to a lack
of the appropriate hardware. So I had to apply it to the much smaller
groups G2=__ in phase2 and G1=G/G2 in phase1.
Is the "i" you use above the same "i" I used in my explanation? There we
have i=0 every time we enter phase2. Beyond that I can't see how to
guarantee optimal solutions whith a phase2 at all, because we only allow
R2,L2,F2 and B2 moves there.
Why does the algorithm work so surprisingly well? Let us assume, that
every time we enter phase2 while the algorithm is running, the state is
a random sample of G2. From the archives (7 Jan 95), where Michael Reid
computed the distances of the elements of G2 from SOLVED we compute for
example, that the chance to get a state with distance less than 9 in
phase2 is about 2.6*10^-4. But in phase1 even with a very modest
iteration depth we already produce very very many solutions for G2.
Today I applied my algorithm to Rich Korfs Random Cube Nr.10 with
minimum length 18 for example, and within a minute I had a solution with
20 moves, 12 in phase1 and 8 in phase2. The next solution took about 15
minutes and gave a 19 move solution with 14 in phase1 and 5 in phase2. I
did not try for more than an hour, in this time no 18 move solution
appeared.
> One final thing, which I'm not sure ever got asked, much less
> answered, is that Mike Reid did an exhaustive search of the subgroup
> (7 Jan 1995). Did this verify that the optimal
> face-turn process for each element of the subgroup is a word on those
> generators? Or are there shortcuts that use forbidden quarter-turns?
>
There definitely are shortcuts with quarter turns. I just tried the
first of the antipodes of phase2 Mike Reid gave (7 Jan 1995) with 18
moves. They usually are hard to solve with the algorithm, but because of
the asymmetrie of stage2, conjugation with moves, that turn the whole
cube lead to a much easier to solve state. Within less than a minute a
had the generator B R2 U2 L2 R2 B2 F' . U' R2 U F' D2 R2 B' D F' D'
(17).
It would be interesting, if it is possible to reduce all of the
antipodes of phase2 to 17 moves, which would reduce algorithms upper
bound for the maneuver length.
Herbert
__