From cube-lovers-errors@mc.lcs.mit.edu  Sat Nov  1 22:17:34 1997
Return-Path: <cube-lovers-errors@mc.lcs.mit.edu>
Received: from sun30.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.1/mc) with SMTP
	id WAA19000; Sat, 1 Nov 1997 22:17:33 -0500 (EST)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Mail-from: From SCHMIDTG@iccgcc.cle.ab.com Sat Nov  1 20:01:52 1997
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sat, 1 Nov 1997 20:01:05 -0500 (EST)
To: cube-lovers@ai.mit.edu
Message-Id: <971101200105.20201302@iccgcc.cle.ab.com>
Subject: Re: Categorization of cube solving programs

"der Mouse" wrote:

>This is a response to a pretty old message:

>> Since I'm interested in such things, I came up with the following
>> categories of cube solving programs in general order of increasing
>> sophistication:

>[...Class 1 through Class 2...]

> Class 3:	A program that when given a specific instance of the
> 		cube, attempts to 'discover' or learn a sequence which
> 		will solve that particular instance.  [eg, Kociemba]
> Class 4:	A program which attempts to discover an ALGORITHM to
> 		solve ALL randomized cubes.  [...]  Korf wrote a
> 		program to do this in the mid 1980s.  [Such programs
> 		generally produce Class-2-ish solutions.]  I believe
> 		Korf's program is the only program ever achieved that
> 		can be placed in this category.

In retrospect, Class 4 programs are not necessarily more sophisticated
than Class 3 programs especially when one considers that the latter
should be be able to produce a macro-table solution by solving for
a sufficient set of specific sequences.  Perhaps, I'm overly fascinated
by a learning program which, in essence, outputs a solving program but
I don't want to discount the fact that there are some very interesting
and sophisticated Class 3 programs out there.

Richard Korf points out a suggestion by Jon Bently that the learning
program can be be interleaved with the solving program, as co-routines,
and only running the learning program when a new macro is needed to
solve a particular problem instance.  Thus, the specific entries
required in the macro-table do not have to be planned out in advance.

>I wish to speak to the last sentence of the Class 4 description.  Back
>in my larval stage (mid-'80s), someone at a lab I worked for build a
>Class 4 program in Franz Lisp.  It wasn't fast, but that was probably
>because it had nothing more than a VAX-11/780 to run on.  (I remember
>it particularly as it was one of the most impressive pieces of hot-spot
>optimization I ever did; replacing about 20 lines of Lisp with about 20
>lines of assembly got a speedup of between two and three orders of
>magnitude overall.)

>I have no idea whether the program still exists in any form.  I do
>believe I can still reach its author, if anyone would like me to
>inquire.

It would be interesting to compare the approach of this program to
Korf's learning program.  If the program is still available I suggest
it would make a quite excellent addition to the cube lovers archive.

Regards,

-- Greg Schmidt