From cube-lovers-errors@mc.lcs.mit.edu Tue Dec 8 13:31:28 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 NAA19371 for ; Tue, 8 Dec 1998 13:31:28 -0500 (EST) Precedence: bulk Errors-To: cube-lovers-errors@mc.lcs.mit.edu Message-Id: <366C1ED9.C11@hrz1.hrz.tu-darmstadt.de> Date: Mon, 07 Dec 1998 19:30:49 +0100 From: Herbert Kociemba Reply-To: kociemba@hrz1.hrz.tu-darmstadt.de To: cube-lovers@ai.mit.edu Subject: Optimal Cube Solver New Optimal Cube Solver I wrote an optimal Cube Solver and experimented with coordinates different of those I use in my Cube Explorer program or of those in Mike Reid's Optimal Cube Solver. Its pruning tables are not very large (about 25MB), so the performance is relatively low (at least in comparison with Mike's program), but I think it is worth to give you some information about it. Some general considerations on the use of "coordinates" in cube solving algorithms first. Instead of representing a state of the cube by the positions of corners or edges, the use of coordinates not only increases the speed of computing a face-turn but also serves as an index for the pruning tables. If we have an arbitrary subgroup H of the Cube Group G, we map the right cosets Ha to natural numbers from 0 to ord(G)/ord(H)-1). A face-turn T (which also is an element from G) now induces a map on these numbers, which can be implemented as a simple lookup-table. For this to work we have to ensure that if x=h1*a and y=h2*a are in the same coset Ha, then x*T and y*T are in the same coset Hb. But this is true because (x*T)*(y*T)^-1 = (h1*a*T)*(h2*a*T)^-1 = h1*h2^-1 is in H. If we take for example H1={all g from G with corner orientations 0, corner permutations and edges arbitrary} the resulting coordinate (0<=x<2187) represents the orientation of the corners. It also should be possible to reduce the size of the coordinates by the 48 symmetries of the cube (or at least by a subgroup of the symmetry group M). This is done by defining equivalence classes on the cosets. Two cosets Ha and Hb are called equivalent, if there is an m from M with Hb = m*Ha*m^-1. But to make this definition work we have to ensure, that the elements of a coset Ha are really all mapped to the same coset Hb by the conjugation with m. This only is true, if (1) mHm^-1=H The subgroup H1 from above for example does have this property only for symmetries which do not change the UD-axis in the way the orientations of the corners are usually defined. So the corner orientation coordinate can only be reduced by 16 symmetries. Is it possible to define the corner orientations in another way, so that (1) holds for all 48 symmetries? I do not believe it, but I do not know how to prove this. For the analogous case of the edge orientations there is a possibility to define the orientations in a way (different to the way usually used) which allows reduction by all 48 symmetries: every quarter turn changes the orientation of any involved edge. In my program I use 3 coordinates. The first (let's call it the X2-coordinate) is defined by the subgroup, where the edges are arbitrary and the corners are generated by . There are 918540 different cosets. Because (1) holds for all m, they can be reduced by all 48 symmetries and we get 19926 equivalence classes. The second coordinate is the edge orientation defined by the subgroup {all g from G with edge orientations 0, edge permutations and corners arbitrary}. There are 2048 cosets. I do not reduce them by symmetries because the number is relative small. 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'' The operations in square brackets are done by table lookups: [m2*T*m2^-1]:=T', [c*T']:=m1'*c'*m2', [m1*m1']:=m1'' and [m2'*m2]:= m2''. A cube, which has all three coordinates zero, is in a subgroup with 96 elements, were the edges are in place and the corner orientations are correct. To find such states, I use two pruning-tables. The first combines the X2-coordinate and the edge-orientation coordinate which takes 19926*2048/2=20404224Bytes of memory (we only need 4 bit per entry). The maximal table entry is 12, with an average of about 9.5. The second is a pruning table for the edge-permutation. It takes 208816*48/2=5011584Bytes, the maximal table entry is 10 (so it takes not more then 10 faceturns to position all edges ignoring the orientations). The program produces about 1 million nodes per second on a P350 and a depth 15 search is done in about 4 minutes (depending on the situation). So a complete depth 18 search will need a few days which of course is not very satisfying. A possible improvement could be to use the subgroup instead of for the first coordinate. The subgroup has only 4 elements, so the coset-space has 24 times the size. The pruning table will need about 480MB instead of 20MB which is above that what is possible for me in the moment. But a complete depth 18 search should be done in about 1/24 of the time which will be a few hours then. Herbert