From cube-lovers-errors@mc.lcs.mit.edu Thu Dec 17 19:18:53 1998
Return-Path:
Received: from sun28.aic.nrl.navy.mil (sun28.aic.nrl.navy.mil [132.250.84.38])
by mc.lcs.mit.edu (8.9.1a/8.9.1-mod) with SMTP id TAA22644
for ; Thu, 17 Dec 1998 19:18:53 -0500 (EST)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Message-Id: <36796BF2.5B57@hrz1.hrz.tu-darmstadt.de>
Date: Thu, 17 Dec 1998 21:39:14 +0100
From: Herbert Kociemba
Reply-To: kociemba@hrz1.hrz.tu-darmstadt.de
To: Jerry Bryan
Cc: Cube Lovers
Subject: Re: Optimal Cube Solver
References:
Jerry Bryan wrote:
>
> On Mon, 07 Dec 1998 19:30:49 +0100 Herbert Kociemba
> wrote:
>
> >
> > The third coordinate describes the edge permutation. Because there are
> > 12! coordinate values, even reduction by 48 symmetries still gives too
> > many coordinate values. So for use in a turntable we define two edge
> > permutations a and b equivalent, if a=m1*b*m2, were m1 and m2 are in M.
> > In this way we get 208816 equivalence classes c. If now m1*c*m2 is a
> > (not necessarily unique) representation of an edge permutation applying
> > a faceturn T is done like that:
> >
> > (m1*c*m2)*T = m1*c*[m2*T*m2^-1]*m2 = m1*[c*T']*m2=
> > [m1*m1']*c'*[m2'*m2]=m1''*c'*m2''
> >
> I used to talk about 1152-fold symmetry for the 2x2x2
> (1152=24*48). Herbert's approach for the third coordinate
> yields a 2304-fold reduction in the search space
> (2304=48*48). However, the reductions in the search space
> in the two cases are not really dealing with quite the same
> issue. In the case of 1152-fold symmetry for the 2x2x2,
> there are (up to) 1152 equivalent positions which are the
> same distance from Start. If I am understanding Herbert's
> technique correctly, when positions are equivalent in the
> third coordinate, there are (up to) 2304 positions of
> the edges for which the distance from Start has the same
> lower bound. (Maybe I should say "the same non-trivial
> lower bound", because (for example) zero would be a lower
> bound for all positions.)
I do not use the equivalence in the third coordinate as an index in a
pruning table. On the contrary, I have to "expand" the coordinate again
by a factor of 48 to get equivalence classes, which have the same
distance from start and from which I built the pruning table. But due to
the large size (12!) of edge permutations, it seems a good way (and I
see no other way) to keep track of the edge-permutation-coordinate with
only a few table-lookups.
I now have enough RAM (128MB) to implement a pruning table for all
possible coordinates of the first phase of my Two-Phase-Algorithm, which
brings the cube into the subgroup H=__. This is what Mike
Reid already did about one year ago and which seems powerful enough even
to be used as an Optimal Solver (omitting phase 2, in which the edge-
and cornerpermutations are restored). Due to this power I think of
implementing a "static" phase 2 only with a table which stores the edge-
and corner permutations of all positions up to maybe 5 face-turns in H
from start.
Using the approach for the edge permutation from above,the computation
of the starting position of phase 2 should be very fast. In the
implementation currently used, I have to switch back from the
coordinate-representation of the cube in phase 1 to a more "physical"
representation using edges and corners, apply the maneuver generated in
phase 1 and then compute the starting coordinates of phase 2. In the new
approach only coordinates could be uses.
Herbert
__