From cube-lovers-errors@oolong.camellia.org Sat May 31 19:10:39 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 TAA28171; Sat, 31 May 1997 19:10:38 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 1 Jun 1997 00:57:00 +0200
From: Dik.Winter@cwi.nl
Message-Id: <9705312257.AA23367=dik@hera.cwi.nl>
To: cube-lovers@ai.mit.edu
Subject: Re: Searching and Metrics in (Korf 1997)
> So two questions remain. First, is there really a difference in the
> duplication of positions in the two metrics? I think Jerry Bryan's
> table shows that only about 1.74% of the 63 billion positions are
> duplicated at 11q. Do we have statistics on duplication for the
> face-turn metric?
I do not think there are really statistics. But I have done a complete
analysis on similar puzzles (domino, 2x2x2) where the number of positions
from start increases roughly by the factor you would expect if you
eliminate elementary duplicates as you listed. This both for face
turns and quarter turns. This increase goes on until shortly before
the maximum of turns when the number of new configurations drops
dramatically. I think the figures are in the archives. I have no
reason to expect the case to be different for the cube, rather all my
experiments lead me to predict that the same is the case with the cube.
> Second, is there any technical justification for
> using the face-turn metric?
None, except that the diameter of the group will be larger. (But not
much larger.) And that makes it in Rich's algorithm only computationally
more expensive.
> I'm aware that most of the published
> literature uses it, and that small numbers of moves sound more
> impressive than large ones, but these aren't very satisfying reasons.
> As far as I know, the problem of finding optimal solutions can be
> fruitfully approached in either of the metrics, or in any of several
> other metrics.
The last is almost certainly not true. In the archives there must be an
article by Michael Reid where he made an attempt to generalize Kociemba's
algorithm. I.e. find a subgroup of the total group, phase 1 is to
find a path to that subgroup and phase 2 is to find a path to the
solution. I disremember the entire contents, but as far as I remember
the optimal partitions all used a subgroup which needed only half turns
for at least one face pair. Looking for quarter turn optimization is
not really feasable with such a partition.
dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/