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