From cube-lovers-errors@oolong.camellia.org Sun Jun 1 05:20:49 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 FAA29296; Sun, 1 Jun 1997 05:20:49 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <33913E47.F3C@hrz1.hrz.th-darmstadt.de>
Date: Sun, 01 Jun 1997 11:17:59 +0200
From: Herbert Kociemba
X-Mailer: Mozilla 3.0 (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
Subject: Generalisation of Korf's method?
References: <9705312220.AA22245=dik@hera.cwi.nl>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Greg wrote:
> 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).
Maybe. But I'm not sure about that. I am no specialist concerning IDA*
search, but I think it is worth while to examine, for which general
class of problems a two phase algorithm is profitable, that means doing
IDA* search to some subgoal which consists of an appropriate subset
(including the end goal) of the problem space (phase1) and appropriate
heuristic functions, then doing IDA* search from here to the end goal
(phase2). Then continuing with IDA* search in phase1, creating more
solutions and then doing IDA* search in phase2 with a maximal length of
L=N-n1-1, where N is the length of the already found (usually not
optimal) last solution and n1 is the lenght in phase1.
L decreases for two reasons when the alogrithm is running: Every new
solution found will have an length N at least one smaller then the
previous solution and nl will increase also.
If you have enough time, you wait until nl=N, then you have the
guaranteed optimal overall solution.
This approach could be valuable, if the problem space is very large, and
in this case you get a sequence of solutions with decreasing length
which might be better than waiting for the optimal solution for 100
years with single IDA* search.
In the case of Rubik's cube the sequences of solutions seem to converge
very quick to a solution with minimal overall length in many cases,
though it might be difficult to prove this rigorously.
I would be interesting to see, how the two phase algorithm handles the
10 cubes, Rich Korf solved.
Dik.Winter@cwi.nl wrote:
> 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.
This is not quite true. I don't think that the algorithm would have
worked then satisfactory. I did not add the details in the description
of the algorithm in CFF28, because I did not want to hide the
principles.
Because of the limited memory (1MB!! at this time) I worked in four
dimensional space and also used heuristic functions based on
two-dimensional coordinate-planes. To get 4 dimensions, I did not use
the turns of the 6 faces, but I fixed the DLB-corner. Instead of the L,
B, and D turns I did R, F and U turns together with a slice move then,
which is of course identical with L, B and D turns and then turning the
whole cube. The additional coordinate is the position of the
center-cubies(24 states). In this way you have only 7! corner
permutations (instead of 8!) and 3^6 possible corner orientations
(instead of 3^7). Only this fact made it possible for me use two
dimensional coordinate planes for the heuristic functions.
Herbert