From cube-lovers-errors@oolong.camellia.org  Sun Jun  1 21:40:09 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 VAA01521; Sun, 1 Jun 1997 21:40:08 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Sun, 1 Jun 1997 21:22:20 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970601212220.2140c63e@iccgcc.cle.ab.com>
Subject: Re: Generalisation of Korf's method?

Herbert Kociemba wrote:

>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.

I think the two phase approach is relevant to a larger class of problems
than just the cube, or for that matter, combinatorial puzzles in general.
In fact, I think the two phase aspect is what is commonly referred to
as "bidirectional search".  When it can be applied, it has the potential
for reducing search complexity from O(b^d) to O(b^(d/2)).  That is to
say that it can cut the exponent of an exponential search in half.

My earlier comment was more in regards to leveraging specific knowledge
of cube groups.  I'm not sure that specific knowledge of cube groups is
highly applicable to Korf's work as this seems in conflict with the
desire to develop general search methods that are domain independent.
I suspect that he might consider this "cheating" with respect to the
thrust of his work having greater applicability outside combinatorial
puzzle problems.  But if the goal is to develop a highly optimized
Rubik's cube solver, then inputting specific knowledge of the cube
problem is reasonable.

Although I don't yet fully understand the pruning tables used in Kociemba's
algorithm, I suspect they are different than Korf's tables (which I do
understand), especially with respect to how they are applied to pruning
the search.

I have a hunch that combining Korf's heuristic methods with a Kociemba
style two phase approach (a.ka. "bidirectional search) could result in 
a more effective cube solver.

-- Greg