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