From cube-lovers-errors@oolong.camellia.org  Tue Jun  3 01:54:34 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id BAA05361; Tue, 3 Jun 1997 01:54:33 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Mon, 2 Jun 97 22:20:26 EDT
Message-Id: <9706030220.AA22877@sun34.aic.nrl.navy.mil>
From: Dan Hoey <Hoey@aic.nrl.navy.mil>
To: cube-lovers@ai.mit.edu
Subject: Re: Searching and Metrics in (Korf 1997)

My earlier remarks on searching, outside of saying "underestimate" for
"overestimate", are pretty much redundant given the availability of
Rich's survey article.  Here are some remarks on what I said about the
quarter-turn metric.

I said "No one who is familiar with the cube-lovers archives (e.g. my
message of 9 January 1981) would generate both [ FF and F'F' ] any
more than they would generate [ both FB and BF]".  This is both too
strong and too weak a statement.

First, there are search techniques that are unable to determine what
the last move was, so they must go ahead and generate such moves
(hopefully discarding them later).  I should have replaced "any more
than they would" with "if they could avoid" or something.

But second, I seem to have given the impression this is "a cube thing"
rather than "a search thing".  But counting unit turns instead of
multiple turns is easily generalized, moreso than the problem of
commutativity.

Suppose you have generators g1, g2, g3, ..., gk of a group, so that
their inverses g1', ..., gk' are also generators.  The order of a
generator g, o(g), is the minimum positive integer for which g^o(g) is
the identity.  (I try to avoid using the asymptotic little-o when I'm
talking about this.)

What is the appropriate rule for the set of possible next generators?

The generalization of the face-turn metric is the "power-turn" metric.
We count gi, gi^2, gi^3, ..., gi^(o(gi)-1) as generators.  Then after
each gi^k we refuse to allow the next move to involve gi.  We deal
with commutativity by also refusing to allow the next move to involve
gj if j<i and gi commutes with gj.  We need only keep a k-valued state
variable around to know what moves are available next (though this
doesn't solve the commutativity problem in general, see below).

For the "unit-turn" metric, we wish to count gi^2 as twice as
expensive as gi if o(gi)>3.  We still assume gi' is the same cost as
gi, so if o(gi)=3 we have gi^2=gi'.  For each gi, let the half-order
h(gi)=Floor((o(gi)-1)/2).  The state variable assumes 2 h(gi) values
1,2,...,h(gi) and -1,-2,...,-h(gi).  If the previous state did not
involve gi, then gi enters state 1 and gi' enters state -1.
Thereafter, positive states can accept gi and increment, and negative
states can accept gi' and decrement, to the maximum of their range.
There is one more case: if o(gi) is even, then state h(gi) can accept
one more gi and go to state -h(gi).  Otherwise gi and gi' are
prohibited.  This prevents backtracking (gi gi' or gi' gi),
overturning (gi^x or gi'^x where 2x>o(gi)) and halfway-duplication
(gi'^(o(gi)/2)).  So the total number of states is
2(h(g1)+h(g2)+...+h(gK)).  Commutative duplication is prevented by the
same prohibition as for the power-turn metric.

So for the unit-turn cube metric, we need 12 states (two per face).
The megaminx requires 48 states (12 per face) because the generators
have order 5.

This completely solves the problem about there being more duplication
in the unit-turn metric than the power-turn metric.  But the problem
of commuting generators is more complicated, as I remarked with
respect to the Megaminx on 23 September 1982.  We can find commuting
pairs {A,B} and {B,C} such that {A,C} do not commute.  Remember that
when we are ordering generators, we require that commuting generators
appear in order.  But suppose A<B<C.  This rule would allow duplicate
processes BCA and CAB.  I did some work on trying to avoid this, but
I'm not sure I got a satisfactory solution.

Dan
Hoey@AIC.NRL.Navy.Mil