From cube-lovers-errors@oolong.camellia.org Sun Jun 1 00:58:07 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 AAA28890; Sun, 1 Jun 1997 00:58:06 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org From: SCHMIDTG@iccgcc.cle.ab.com Date: Sun, 1 Jun 1997 0:19:28 -0400 (EDT) To: cube-lovers@ai.mit.edu Message-Id: <970601001928.2140f226@iccgcc.cle.ab.com> Subject: Re: Searching and Metrics in (Korf 1997) Dan Hoey wrote: >I've read through Rich Korf's paper now, and I have a few ideas on the >paper and how the method might be improved... I feel that there is a fundamental point regarding cube solving approaches that is worth making. First there is what I shall call the "Kociemba approach". I would loosely paraphrase this approach as follows: "If one examines the behavior of the cube in great detail and applies group theoretic concepts to the spaces generated by the cube, one can apply this analysis to great effect towards producing an algorithm capable of solving the cube." Then there is what I shall refer to as the "Korf approach". Loosely paraphrased as: "The cube is a difficult combinatorial puzzle that provides a fertile ground for advancing the state of the art of search methods." It should be apparent that the goal of these two approaches is quite different. The "Kociemba approach" is focused only on solving the cube. All domain specific knowledge about the cube problem, such as specific group theoretic properties of the cube, can and should be applied. Whereas the "Korf approach" attempts to be a general approach, applicable to other problems, not just the cube (i.e. the cube problem is merely incidental). This approach should not rely on methods that are specific to a single (or at least very narrow) class of problems. This is close to the definition of so called "weak" methods in AI. Weak methods are those that do not rely heavily on human provided domain specific knowledge. For example, an expert system does not classify as a weak method, whereas a search method that is given little more than a description of the problem space and a desired goal does. Stepping back a bit, I would say that Korf's method applies to a broad class of problems, much larger than the cube alone. In effect, his method says: "If one can partition the desired end goal of a problem into subgoals, and for each subgoal provide a cost to achieve that subgoal, then one can use this information to produce a higher quality (i.e. "more informed" in search parlance) heuristic. An effective way to achieve this is by firt precomputing the cost information associated with each subgoal and storing it in a table. This table can be reused across multiple problem instances and represents an effective way to utilize available memory to improve the effectiveness of the search." And so I feel it is necessary to say that any suggestion for improving Korf's method, should take this distinction into account since solving the cube is only incidental to the emphasis of the research work that professor Korf is involved in. In no way am I intending to imply that methods which are not consistent with the "Korf approach" should not be considered. In fact, I find this a fascinating topic. I'm just pointing out it is both a virtue and a goal of his approach that he hasn't leveraged extended knowledge of "cube principles" in order to devise an effective algorithm. I hope I haven't misrepresented Mr. Kociemba or Mr. Korf in this discussion. If so, please speak up. -- Greg