From cube-lovers-errors@oolong.camellia.org Sat May 31 18:34:15 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 SAA28044; Sat, 31 May 1997 18:34:14 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Date: Sun, 1 Jun 1997 00:20:40 +0200
From: Dik.Winter@cwi.nl
Message-Id: <9705312220.AA22245=dik@hera.cwi.nl>
To: cube-lovers@ai.mit.edu
Subject: Re: More on Korf's method
Herbert Kociemba:
> From the description it is evident, that the algorithm Richard E Korf
> uses is basically identical to the the sub-algorithm which is used in
> each stage of my two stage algorithm to solve the cube.
This is right.
Dan Hoey:
> From the description, I think Rich's heuristic functions
> are quite a different type from what you use (though I do not
> understand either exactly yet).
Not really. Rich's heuristic functions are (precomputed) distances
along some coordinates of a multidimensional space. His best apparently
are the corner positions and twice one half of the edge positions.
Similarly in both phases of Herbert's algorithm similar heuristic
functions (pruning tables, filters, ...) are used.
Of course the choice of heuristic function plays an essential role.
For instance, Herbert's original algorithm uses in the first phases
three heuristic functions all three based on a single coordinate
in a three dimensional space. I modified it to use three heuristic
functions based on two dimensional coordinate planes in that same
space. Depending on the problem to solve, this may be better or not,
in this case it is (much) better. A similar modification did I do
in the second phase.
> My guess is that your heuristics have a good chance
> of being more effective at finding optimal solutions for random cubes
> than Rich's, though perhaps some ideas from Rich need to be
> incorporated.
As far as the first is concerned, I think so too. When Herbert's
algorithm is run through to the end it will find an optimal solution
indeed, and in the search for that optimal solution it will use a
new heuristic function for the total solution: the result of previous
suboptimal solutions that come in pretty fast, which is used to prune
the second phase rigorously. I have been able to proof (with my
modification of Herbert's algorithm) some pretty large (18-20 turn)
solutions optimal. I do not think Rich's algorithm will be able to do
that in reasonable time.
> First, we know 18f is not optimal, because the 12-flip is proven to
> require 20f moves exactly (unless Mike Reid made a mistake, or I
> misunderstood).
No, this is right indeed.
> But we _can_ say there's at most one chance in 1024 that the first ten
> random cubes you pick will all be closer than the median to solved.
> So this demonstrates Rich's claim that the median optimal solution is
> very likely 18f.
Something I did estimate already a long time ago. I have done a few
hundred random cubes (a few thousand? I do no longer remember) back
so many years ago. As I remember, I let the program look for optimal
solutions upto 18f (longer is a bit time consuming). As I remember,
there were only very few that could *not* be solved in 18f. There must
be a discussion about this in the archives.
dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/