From: shibe@leland.Stanford.EDU (Eric Schaible)
Subject: Re: Defining other intelligence out of existence
Organization: DSG, Stanford University, CA 94305, USA
Distribution: na,local
Date: Tue, 21 Jul 92 08:27:10 GMT

In article <BILL.92Jul14102805@ca3.nsma.arizona.edu>, Bill Skaggs writes:

|> 
|> Intelligence, abstractly viewed, always involves search and pruning.
|> The power of a searching mechanism can be quantified, but no
|> interesting problem can be solved by pure search (because of
|> combinatorial explosion), so any interesting intelligence requires
|> pruning, and there is no general way of quantifying the power of a
|> pruning mechanism.
|> 
|>      -- Bill


How strictly are you using the terms 'search' and 'pruning'?  I confess that
I feel a little uneasy sliding into ai jargon, but here goes....
 
        It would seem to me that the more important part of the 
problem-solving procedure would be the constitution of the search space by
the agent.  While one can talk about the "search space"
as the sum total of all possible solutions, one should limit oneself to
talking about the sum total of all solutions which the agent can/will 
recognize as being possible solutions.

In other words, my guess is that an agent can only perform the equivalent of
'search' and 'pruning' upon those portions of the search space which the
agent can recognize as being portions of the search space.  It makes little
sense to describe the agent as 'pruning out' solutions that it will never
recognize as such.

The 'pruning' process involves throwing away
possibilities--which presumes that the agent recognized them as possibilities,
which in turn presumes a process resulting in recognition.  Pruning could
never generate such a result.  In short, one has to recognize a solution
as being a solution before one can prune it out as a poor solution.  
Possible solutions are not objective things to which the agent
has search access--rather, they are subjective things through which the
agent can search only after they have been created.

Moreover, say that I am an agent with a problem.  What would be the most 
efficient course of action?  To think up only the "best" solutions, or to sit 
and generate an enormity of solutions through which to search and prune?

In short, my guess is that humans do not prune out huge portions of the
space of possibilities--because they do not recognize them as such.  Rather,
they generate a very small number of possibilities--often through pattern
matching to familiar problems--which can then be scrutinized intensively.
This is not pruning through a huge space of objectively existing
possibilities; rather, this is generating a very small space of subjectively
existing possibilities.

If this is so, then it seems to me that a key aspect of human problem
solving is the ability to generate only a very small search space of very
appropriate solutions.  Perhaps humans perform something like search and 
pruning on the generated space, but I doubt that 'search' and 'pruning' 
appropriately describe the process of generating the space of possibilities.
(A space which does not exist in and of itself, but which must be 
created by the agent.)

Later on, you write:

>  Meaningful problems can almost never be solved by
>brute-force search.  It is necessary to use techniques to reduce the
>size of the search space; much of the classical research in AI was
>devoted to finding such techniques -- for example, dividing the
>problem in subproblems, finding subgoals, finding a way to measure
>progress toward the goal, pruning, etc.  It is still quite an active
>research area.

Same problem as before:  the search and pruning seems almost an
afterthought--the real issue here is how to appropriately divide the
larger problem into manageable pieces, and how to generate possibilities
for each piece.  Again--the possibilities need to be generated, and
if you want to be efficient, generate only the good ones.  Maybe then
search and prune, but not before.

Eric

     -------- 
   -------- -
   -      - -
   -      - -    "Sure it's manly--but I like it too!"
   -      - -    
   -      - - 
   -------- 8     
             8  
  ---------- 8 
 ----------