From cube-lovers-errors@mc.lcs.mit.edu Tue Sep 22 18:09:16 1998
Return-Path:
Received: from sun28.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.8/mc) with SMTP
id SAA18211; Tue, 22 Sep 1998 18:09:15 -0400 (EDT)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Date: Thu, 17 Sep 1998 00:03:47 -0400 (EDT)
From: Jerry Bryan
Subject: More on Calculating Weak Local Maxima
To: Cube-Lovers
Message-Id:
In the process of adding the code to my God's Algorithm program to
calculate weak local maxima in the face turn metric, I realized that the
algorithm I posted previously to do so was incomplete in one subtle but
very important respect. This message will provide the missing piece to
the algorithm.
I have posted much of this before, but my program is in general jumping
ahead by more than one move at a time. For example, suppose we can store
all the positions up to five moves from Start. Then, we can determine all
the positions which are eight move s from Start by calculating all the
products xy where x is a position of length five and y is a position of
length three.
Obviously, just because the length of x is five and the length of y is
three does not mean that the length of xy is eight. In fact, the length
of xy could be anywhere from two through eight. To determine the true
length of xy, we compare xy to the stored positions of length two, three,
four, and five. In addition, we compare xy to the calculated positions of
length six and seven, which are calculated in the same manner as is xy.
If xy fails to match all such shorter positions, then its length is indeed
eight.
Next we focus on the quarter turn metric. For some fixed q in Q, the set
of twelve quarter turns, what is the length of xyq if the length of xy is
eight with the length of x equal to five and the length of y equal to
three? First of all, it must be either seven or nine. Second of all, the
length of yq must be either two or four. If the length of yq is two, then
we know that the length of xyq must be seven. But if the length of yq is
four, then we are still not sure. The reason is that there might be some
u not equal to x of length five and some v not equal to y of length three
such that xy=uv, but where the length of vq is two. If so, then the
length of xyq is the same as the length of uvq which is seven.
The basic idea is that if z=xy where the length of x is five and the
length of y is three, then there may be many, many x and y pairs of length
five and three respectively whose product yields z. The length of zq is
nine only if for every such y the length of yq is four. Even if all but
one yq is of length four, it only takes one yq of length two to spoil the
pudding, as it were.
The mechanism which I have posted previously to capture this concept is
the Ends-with function E(z). E(z) is defined to the be set of all moves
with which a minimal maneuver for z can end. So in the case at hand,
since the length of z is eight, the length of zq is nine only if E(z) does
not contain q'. E(z) can be calculated in the case at hand as the union
of E(y) taken over all the y values of length three which can be composed
with an x of length five to create z. Therefore, to say that E(z) does
not contain q' is the same thing as saying that none of the E(y) contain
q'.
So far, so good and there is nothing new here which I haven't posted
before. But let's consider the exact same issue in the face turn metric.
If the length of x is five and the length of y is three, then the length
of xy can be in the range of two through eight as before. And as before,
if we compare xy with all positions of length two through seven without
finding a match, then the length of xy is indeed eight.
But this time we need to consider xyf, where f is some fixed face turn in
the set Q+H of twelve quarter turns and six half turns. What is the
length of xyf? For starters, it is either seven or eight or nine. Also,
the length of yf is two or three or four.
If the length of yf is two, then the length of xyf is guaranteed to be
seven.
If the length of yf is three, then the length of xyf is guaranteed to be
no more than eight. But the length nevertheless might be seven, because
as in the quarter turn case, there may be some u of length five and some v
of length three such that uv=xy, but such that the length of vf is only
two. If so, the length of xyf is the same as the length of uvf which is
guaranteed to be seven.
The definition of Ends-with is the same in the face turn case as in the
quarter turn case, namely E(z) is the set of all face turns with which a
minimal maneuver for z can end. If z=xy then E(z) can be calculated as
the union of E(y) over all the y value s of length three which can be
combined with an x value of length five to form z. To say that the length
of zf is at least eight is the same thing is saying that E(z) does not
contain f' which is the same thing as saying that none of the E(y) contain
f'.
Next, let's suppose that indeed E(z) does not contain f'. We are still
left with the issue of whether the length of z is eight or nine, having
eliminated seven as a possibility. The test is still the length of all
the yf, with a length of two having been eliminated as a possibility. If
all of the yf are of length 4, then xyf is of length nine. But if even so
many as one of the yf are of length three, then xyf is of length 8.
The mechanism I have posted before to capture this concept is the
Ends-with2 function. E2(z) is a little tricky to describe. Informally,
we might say that E2(z) is the set of all f in Q+H with which z can end
without changing it's length. It is probably better to say that E2(z) is
the set of all f in Q+H such that the length of zf' is the same as the
length of z. The technique which I have posted before (and which I must
now correct) to calculate E2(z) is to form the union of E2(y) over all y
values of length three which can be combined with an x value of length
five to form z.
If the length of zf is eight or nine, then this mechanism is fine. But if
the length of zf turns out to be seven, there is a problem. That is,
there may be one y where the length of yf is two and where E(y) contains
f, and there may be another y where the length of yf is is three and where
E2(y) contains f. In such a case, both E(z) and E2(z) would contain f.
Hence, we must always calculate E(z) prior to calculating E2(z), and we
must omit from E2(z) any f values which are already contained in E(z).
With this correction, everything works. A local maximum is a position z
for which |E(z)|+|E2(z)|=18, a strong local maximum is a local maximum z
for which |E(z)|=18 and |E2(z)|=0, and a weak local maximum is a local
maximum z for which |E(z)| < 18 and |E 2(z)| > 0. All my examples have
been specific to y values of length 3 for clarity of exposition, but the
calculation of E(z) and E2(z) is totally general, and is the union of E(y)
and E2(y), respectively, over all y values which can be used to form a z
of the form z=xy, and with any values which are in E(z) omitted from
E2(z).
Finally, my programs also calculate a Starts-with and a Starts-with2
function, which are defined analogously. The same correction must be made
to the Starts-with2 function as was made for the Ends-with2 function.
Equivalently, we can define S(z)=E'(z') and S2(z)=E2'(z'), where E' and
E2' are the set of all inverses of the elements of E and E2, respectively.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990