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/