Help with AI search script

[Dennis Watson]

Hi CLPy,

I have been working on creating (well a lot of it is translating from
LISP) some AI scripts for Python.  My hope is to eventually offer
these as Zope Products, so people can add AI functionality to their
web sites.  The goal is to have searches (depth_first, breadth_first,
best_first, beam_search, a_star_search), neural networks (perceptrons,
self organizing maps, etc) and expert systems (forward and reverse
chaining.

So I started by translating the searches found in "Paradigms of
Artificial Intelligence Programming" by Peter Norvig. I am having
trouble with some of the code.  Here is the code:

#!/bin/python

def binary_tree (n): 
    """Creates nodes of a binary tree.  N is the parent node"""
    return [n*2, n*2+1]

def tree_search (states, goal_p, successors, combiner):
    if states == None: return None
    elif goal_p(states[0]): return states[0]
    else: return tree_search( combiner(successors(states[0]),
states[1:]), goal_p, successors, combiner)

def depth_first (start, goal_p, successors):
    """Search new states first until goal is reached"""
    return tree_search ( [start], goal_p, successors, lambda (new,
old): (new.extend(old)) )

def breadth_first (start, goal_p, successors):
    """Search old states first until goal is reached."""
    return tree_search ( [start], goal_p, successors, lambda (new,
old): (old.extend(new)) )

def breadth_first1 (states):
    """Search old states first until goal is reached."""
    print states
    print type(states)
    print binary_tree(states[0])
    if states == None: return None
    elif states[0] == 27: return states[0]
    else: return breadth_first1( states.extend(binary_tree(states[0]))
)


if __name__=='__main__':
    #breadth_first (1, lambda (x): (x == 27), binary_tree)
    #depth_first (1, lambda (x): (x == 27), binary_tree)
    #x = breadth_first1 ([1])
    #print "answer is: ", x

When I test breadth_first or depth_first I get the error message:

Traceback (innermost last):
  File "search.py", line 31, in ?
    breadth_first (1, lambda (x): (x == 27), binary_tree)
  File "search.py", line 18, in breadth_first
    return tree_search ( [start], goal_p, successors, lambda (new,
old): (old.extend(new)) )
  File "search.py", line 10, in tree_search
    else: return tree_search( combiner(successors(states[0]),
states[1:]), goal_p, successors, combiner)
TypeError: too many arguments; expected 1, got 2

The only function that should get one argument is the successors
fuunction binary_tree which is called like "successors(states[0])". 
What am I missing here?  Is it something to do with the way Python
passes parameters (copy vs refference)?

So I simplified the problem with breadth_first1.  Here there are no
functions passed in.  It is hard wired to do a best first search with
binary_tree, etc.  This time I get errors because after the first
iteration the call "states.extend(binary_tree(states[0]))" returns
None!  It should be [2, 3].

Caveats:

    a) I know I should recode it to be iterative rather than recursive
to perform better under Python's sub calling mechanism.  I don't think
there is tail call elimination, and I will blow the stack as well as
waste time copying stack frames, etc.

    b) I might be better off using a different Python data type other
than lists, but I am learning more as I go so...

Any help here (specially if sent to me via email) would be appreciated
greatly.  I can post the working LISP code if that helps.  If you
would like to become involved with coding the other parts (and/or this
one), please send me a shout.

Thanks in advance,


Dennis

[ comp.ai is moderated.  To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai at moderators.isc.org>, and ]
[ ask your news administrator to fix the problems with your system. ]