From cube-lovers-errors@oolong.camellia.org Fri May 30 19:43:03 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 TAA23535; Fri, 30 May 1997 19:43:02 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org Date: Fri, 30 May 97 19:41:15 EDT Message-Id: <9705302341.AA06714@sun34.aic.nrl.navy.mil> From: Dan Hoey To: chrono@ibm.net Cc: cube-lovers@ai.mit.edu Reply-To: hoey@aic.nrl.navy.mil Subject: Re: The rest of us > Prof. Korf's solution to the Cube sounds like it basically maps all > possible iterations within a given number of steps. Once you know all > the possible combinations given the maximum number of turns, you can > then just compare a scrambled cube to the map and see if it falls within > one of the available templates. No, you've misunderstood. Rich doesn't attempt to "map all possible iterations" (by which you seem to imply some sort of preprocessing so as to be able to recognize any position at a given depth). After all, according to his estimate of the median, there should be over 10^18 of them at depth 18f, and finding them all would take his program many thousands of years. Instead, he takes advantage of knowing what the target cube is by using a measure called a "heuristic". A heuristic estimates how far a given process is from solving the cube, such as the "oriented distance from home" (ODH) that appears in the archives. Then if you have tried 7f turns and you know it will take at least 12f more, you know you're on the wrong track, and look elsewhere. But there are lots and lots of wrong tracks, and you need to recognize and discard them quickly. The ODH isn't that good an estimate, so it doesn't discard enough of them--it would still take 250 years to search for one position. Finding better ways of estimating how far you are from the goal is what the research is about. So just because he says it's "brute force" doesn't mean you list all the positions in advance. You definitely need to know what the goal position is for Rich's approach to work. In particular, his method does not seem to be applicable to finding what the furthest position is. Dan Hoey Hoey@AIC.NRL.Navy.Mil