From cube-lovers-errors@mc.lcs.mit.edu Wed Mar 17 14:36:56 1999 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 OAA07208 for ; Wed, 17 Mar 1999 14:36:55 -0500 (EST) Precedence: bulk Errors-To: cube-lovers-errors@mc.lcs.mit.edu From: Jerry Bryan To: Cube Lovers Subject: Re : Re: Edges only, Ignoring Flips, Face Turn Metric In-Reply-To: <199903120601.BAA15248@euclid.math.brown.edu> Message-Id: Date: Wed, 17 Mar 1999 00:34:12 -0500 (Eastern Standard Time) On Fri, 12 Mar 1999 01:01:52 -0500 michael reid wrote: > i guess i'm not sure what you're doing, jerry. but i don't think > it should be *that* difficult. the number of configurations is > 12! = about 480 million. if you divide out by symmetry, you get > about 10 million configurations. this should be small enough to > store in memory and do a complete breadth-first search of the space. > The way you describe the search is how Herbert Kociemba did it, but it is not how my program does it. I think his program only took an hour or two. I am applying my program to a problem to which it is not well suited because I do not have time to write one more like Herbert's. I tend to think that the most fundamental design decision in a program which does a Start rooted breadth first search for a cube space is to decide whether the search space can fit in memory. If it can, and if there is an easy way to index the search space, then the permutations themselves do not have to be stored. All that has to be stored is the distance from Start for each permutations. These distances are usually stored one per byte, or sometimes one per half-byte. There is even some discussion the Cube-lovers archives about how the storage can be reduced to two bits per permutation. If the search space cannot fit in memory, then it seems to me to be the case that some representation of the permutations themselves must be stored in addition to the distance from Start for each permutation. My program is designed to search as much as possible of the 4.3*10^19 search space for the entire cube group, so it stores permutations. To make it into a program to search edges only without flips, I simply fixed the corners and the flips, plus I made the lexicographic ordering consider edges before corners. But it still stores the permutations. It's sort of a quick and dirty solution which runs very slowly for the problem at hand. When a search space consists of the elements of a cube group, it is easy to index the search space. But when a cube group is reduced by symmetry the result is generally not a group and the resultant search space is (in my experience) not very easy to index. The thing about Herbert's program that I have trouble comprehending is that he is able to reduce the search space by symmetry and still have the indexing be well behaved. He has posted a clear exposition of his method, so the problem is in my understanding rather than in his explanation. The reason reduction by symmetry results in poorly behaved indexing for the search space is because not all positions are equally symmetric. There is much discussion of this phenomenon in the archives under the general heading of "the real size of cube space". Herbert seems to have overcome this problem for the edges problem. But if I understand correctly, he does not believe the same solution can be applied to the corners. If Q[n] is the set of permutations which are n moves from Start, then my program is calculating the product Q[6]Q[6] (all products of the form st for s and t in Q[6]) as a way to determine Q[12]. For the whole cube, most such products are in fact 12q from Start and most such products are distinct. There is very little wasted time or energy. But for edges only without flips, Q[12] is in the tail of the distribution so most such products are either duplicate or are less than 12q from Start. Nearly all the products are a waste of time. My program does reduce by symmetry to certain extent. If R[n] is the set of representatives (patterns) which are n moves from Start, then I only store R[n]. (R[n] is about 48 times smaller than Q[n].) Q[n] is inferred via pointers to R[n], and is represented as Q[n]=R[n]^M, where M is the set of 48 rotations and reflections of the cube. Secondly, I only produce elements of R[2n] rather than elements of Q[2n], which in theory speeds up the program by about 48 times but which in practice only seems to speed it up by about 20 times. But for the edges without flips search, this kind of a speedup is utterly dwarfed by all those wasted products from Q[6]Q[6]. My program always runs into this problem when it gets into the tail of a distribution. ---------------------------------------- Jerry Bryan jbryan@pstcc.cc.tn.us Pellissippi State Technical Community College