From cube-lovers-errors@oolong.camellia.org Mon Jun 2 13:11:40 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 NAA03434; Mon, 2 Jun 1997 13:11:39 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org Date: Mon, 02 Jun 1997 11:23:05 -0400 (Eastern Daylight Time) From: Jerry Bryan Subject: Re: Searching and Metrics in (Korf 1997) In-reply-to: <9705312055.AA16150@sun34.aic.nrl.navy.mil> To: cube-lovers@ai.mit.edu Reply-to: Jerry Bryan Message-id: MIME-version: 1.0 Content-type: TEXT/PLAIN; charset=US-ASCII X-X-Sender: jbryan@pstcc6.pstcc.cc.tn.us On Sat, 31 May 1997, Dan Hoey wrote: > > So two questions remain. First, is there really a difference in the > duplication of positions in the two metrics? I think Jerry Bryan's > table shows that only about 1.74% of the 63 billion positions are > duplicated at 11q. Do we have statistics on duplication for the > face-turn metric? Second, is there any technical justification for > using the face-turn metric? I'm aware that most of the published > literature uses it, and that small numbers of moves sound more > impressive than large ones, but these aren't very satisfying reasons. > As far as I know, the problem of finding optimal solutions can be > fruitfully approached in either of the metrics, or in any of several > other metrics. > I do not think there is really any difference of the sort that Prof. Korf was talking about. I have done extensive breadth-search searches with both the quarter-turn and face-turn metrics (although I have done more work on the quarter-turn). Dan has posted what I will call "syllable analyses" for both metrics. Dan's "syllable analyses" (e.g., FB=BF, etc., where FB and BF are our syllables) provide an upper bound on possible branching factors. The observed branching factors are extremely close to Dan's upper bounds for both metrics out to the levels I have searched. Hence, I see no advantage either way. Dan's syllable analyses are essentially based on short relations. Observed branching factors deviate from Dan's tight bounds only to the extent that there exist longer relations which are not taken into account by Dan's formulas. The fact that the bounds are tight simply reflects that there are not very many longer relations, at least out to the level that has been searched. Far enough from Start, there will be a major break in branching factors, and the break will occur closer to Start for the face-turn metric than for the quarter-turn metric. This break in branching factors will be reflective of longer relations which do not simply contain shorter relations. And again, these longer relations will be shorter in face-turns than in quarter-turns. But that's just the way the metrics work. We seem to be degenerating into one of our periodic face-turn vs. quarter-turn arguments (I am a confirmed quarter-turner because quarter-turns are conjugate). But this reminds me of something I ran across in Singmaster which I found curious. Singmaster is a face-turner, but he nevertheless defined the length of a position as the number of quarter-turns from Start for the position. In other words, he did not identify the number of moves to solve a position with the length of the position. Is his definition of "length" standard in group theory? If so, we would have only one length for each position, although we could have several metrics for "number of moves from Start" (face-turns and quarter-turns are by no means the only possible metrics). In the same vein, is the term "diameter" reserved to mean the maximum length for any position so that the diameter is unique, or do we have one diameter for quarter-turns, another diameter for face-turns, etc.? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 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