From:

~~~ Subject:

On 11/11/94 at 15:36:00 mark.longridge@canrem.com said:

With the computer hardware I'm using (486-DX40 with 4 megs) and

my current algorithm I created a file "ur.dat" which is a flat

ascii file. It contains all the processes which generate distinct

positions up to 12 q turns. I also have the file "ursum.is" which

contains all the `cubesums' for each element of <U, R>.

I have considered keeping a file of processes, either in parallel

with my file of positions, or together in the same file. However,

I have always rejected the idea because it would take too much

storage for the very large searches I want to accomplish.

Also, since I only store representative elements of equivalent

classes in my data base, it is hard to know what a "process"

means (see below).

Using this method I have found a process for all <U, R> positions

with the longest being 22 q turns (so far). The hardest positions

can take as long as a couple of hours. I have no idea what the

antipodes look like at this time, but I'll probably try the

random approach soon.

Interesting approach, and very different than what I do. I simply

do a "game theory" type tree search of positions (*not* processes)

with Start at the root of the tree. I have to search the whole

depth of the tree rather than half the depth of the tree, as you do.

(I could obviously verify the depth of one particular position with

two half-depth searches, but I confess I have never been very

interested in "particular positions". I want to search the whole

tree.)

I tend to think of the processing required for whole tree searches

as "global" because you cannot determine anything about

one particular position except in the context of the other

positions down to the same level of the tree. By contrast, there

is some interesting processing that you can do that is "local";

e.g., conjugate class sizes, symmetry group determination, etc.

can be determined on a position by position basis without

regard to any other position. Such "local" processing is generally

much easier than the "global" processing. "Local" processing

is O( N ) and requires essentially no memory. "Global" processing

is O( N log(N) ) if you are efficient, maybe O(N^2) if you are not,

and is very consumptive of memory. As I have said before, I solve

the memory problem by externalizing the data to files and sorting

the files.

Saying that I have a hard time converting positions into processes

doesn't mean that I cannot do so. The process for a given position

can be extracted from a data base of positions by backtracking

from the position back to Start. However, I have two difficulties.

One is that I store only representative elements of equivalence

classes (of the form {m'Xmc} for centerless cubes, or M-conjugate

classes of the form {m'Xm} for cubes with centers)}. That means

that as you backtrack, the process you are determining (backwards)

will rotate and reflect out from under you. For example, suppose we

have Repr{m'Xm}=f'Xf for some fixed f in M. If Xq for some q in Q

is a neighbor of X which is one move closer to Start than X,

then we might have Repr{m'(Xq)m}=g'(Xq)g for some fixed g in M.

But f and g need not be, and usually aren't, the same.

It might be noted in passing that there is duality between the

symmetry of a position X and a process P=p1 p2 ... pn which produces

X. That is, if f is a fixed element of M, then we have

f'Xf = f'Pf = f'(p1)f f'(p2)f ... f'(pn)f.

The second problem is that my files are so large that I have to

keep them on magnetic tape. If I need to find a process, I first

find a sequence of positions (really, a sequence of representative

elements) on the tapes (hard to search tapes!), and copy the

positions to a small disk file. From that point, it is not

especially hard to run a program to display the positions in

sequence and determine the process.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU

If you don't have time to do it right today, what makes you think you are

going to have time to do it over again tomorrow?