simple artificial intelligence utilities

Fixes #66 and other small syntax issues that prevented this from running on Python 3.x. Of course, Python 2.x should still work.

Tests seem to still pass, but I have only used a subset of this package myself, so I can't guarantee that everything that the tests don't cover work as expected on 3.x.

fringe may not contain a node with a state that is in the memory. If a new candidate node has that state, it can not be added to the fringe.

See python-astar project for a correct implementation: https://github.com/jrialland/python-astar.

I have a proposal of the implementation of a Genetic Algorithm - AG. Actually I already started to implement one, but I didn't finish it yet.

For mre information about what is that see this link: https://en.wikipedia.org/wiki/Genetic_algorithm

An AG has a lot of functionalities and I'm planning develop that using TDD in order to make a safe development

This algorithm willbe so helpfull for this library.

Dear,

I am learning AI and I am at the beginning.

I would like to limit the use of actions to one time for each. Indeed, I have to find a subset of actions to achieve the goal, but each action can be done only once.

How should I add that constraint to the actions ?

from simpleai.search import SearchProblem, breadth_first, depth_first, greedy, astar

class MyPuzzle(SearchProblem):
    def __init__(self, initial_state = 0):
        self.goal = 51
        super(MyPuzzle, self).__init__(initial_state)

    def actions(self, state):
        if(state > self.goal):
            return []
        else :
            return (1,20,30,25,21,32,65,96,30,16,25,18,75,21,1)

    def result(self, state, action):
        return state + action

    def cost(self, state, action, state2):
        return 1

    def is_goal(self, state):
        return state == self.goal

    def heuristic(self, state):
        return self.goal - state

# Eight Puzzle Solver using A*
# This code is working for few cases and for the rest it is getting into infinite loop
# Please see main() 

from simpleai.search import astar, SearchProblem

class PuzzleSolver(SearchProblem):
    def __init__(self, initial):
        self.goal = '1-2-3\n4-5-6\n7-8-_'

        #lets create a cache for goal positions of all the values
        matrix = self.string_to_list(self.goal)
        self.goal_position = {}
        for x in '12345678_':
            self.goal_position[x] = self.get_coordinates(matrix, x)

        SearchProblem.__init__(self, initial_state= initial)


    #A method that gets current state of the puzzle solver
    #and returns a list of the numbers that can be moved into the empty space
    def actions(self, curr_state):
        matrix = self.string_to_list(curr_state)
        row_empty, col_empty = self.get_coordinates(matrix, '_')
        moves = []
        if row_empty > 0:
            moves.append(matrix[row_empty-1][col_empty])
        if row_empty < 2:
            moves.append(matrix[row_empty+1][col_empty])
        if col_empty > 0:
            moves.append(matrix[row_empty][col_empty-1])
        if col_empty < 2:
            moves.append(matrix[row_empty][col_empty+1])
        return moves

    #A method that accepts current state and action. It returns the new state
    #that results by application of the action.
    def result(self, curr_state, action):
        matrix = self.string_to_list(curr_state)
        row_empty, col_empty = self.get_coordinates(matrix, '_')
        row_action, col_action = self.get_coordinates(matrix, action)
        #swap
        matrix[row_empty][col_empty], matrix[row_action][col_action] = matrix[row_action][col_action], matrix[row_empty][col_empty]

        new_state = self.list_to_string(matrix)
        return new_state

    #Termination criteria for A*
    def is_goal(self, curr_state):
        return curr_state == self.goal

    #Heuristic Search: A method that returns an estimate of distance from the current state to the goal
    #using the Manhattan Distance
    def heuristic(self, curr_state):
        matrix = self.string_to_list(curr_state)
        distance = 0
        for number in '12345678_':
            row_number, col_number = self.get_coordinates(matrix, number)
            goal_row_number, goal_col_number = self.goal_position[number]

            distance += abs(row_number - goal_row_number) + abs(col_number - goal_col_number)
        return distance

    #helper methods
    def string_to_list(self, input_string):
        data = [item.split('-') for item in input_string.split('\n')]
        return data

    def list_to_string(self, matrix):
        w = '\n'.join(['-'.join(x) for x in matrix])
        return w

    def get_coordinates(self, matrix, element):
        for i, row in enumerate(matrix):
            for j, col in enumerate(row):
                if col == element:
                    return i,j

        return None

    def solve(self):
        #invoking A*
        result = astar(self)
        path = result.path()
        action, state = path.pop(0)
        print('Initial State')
        print(state)

        for action, state in path:
            print('After moving ', action, 'into empty space')
            print(state)

        print('Goal Achieved')

    def cost(self, state, action, state2):
        return 1

def main():
    #test cases
    initial = '1-_-2\n6-3-4\n7-5-8' #working
    #initial = '1-2-3\n6-_-4\n7-5-8'  #not working
    initial = '1-2-_\n6-3-4\n7-5-8'  # working
    initial = '_-1-2\n6-3-4\n7-5-8'  # working
    #initial = '1-6-2\n_-3-4\n7-5-8'  #not working
    initial = '1-4-5\n6-3-8\n7-2-_'  # working
    #initial = '1-4-2\n6-3-_\n7-5-8'  # not working
    initial = '1-4-5\n6-8-3\n_-2-7'  # working
    #initial = '1-4-_\n6-8-3\n5-2-7'  # not working
    initial = '1-4-5\n6-8-3\n2-7-_'  # working
    #initial = '1-4-6\n5-8-3\n2-7-_'  # not working
    initial = '7-3-4\n2-_-8\n5-1-6' #not working

    ps = PuzzleSolver(initial)
    ps.solve()

main()

Installing from PIP fails giving the following (using Python 2.7.3)

$ sudo pip install simpleai
Downloading/unpacking simpleai
  Running setup.py egg_info for package simpleai
    Traceback (most recent call last):
      File "<string>", line 16, in <module>
      File "/tmp/pip-build-root/simpleai/setup.py", line 9
        description=u'An implementation of AI algorithms based on aima-python',
                                                                             ^
    SyntaxError: invalid syntax
    Complete output from command python setup.py egg_info:
    Traceback (most recent call last):

  File "<string>", line 16, in <module>

  File "/tmp/pip-build-root/simpleai/setup.py", line 9

    description=u'An implementation of AI algorithms based on aima-python',

                                                                         ^

SyntaxError: invalid syntax

When _search is called with graph_replace_when_better=True, and the node expanded () is better that the one in the fringe it tries to remove it but fails.

Just a pep8 fix. If the code is an initial example that a lot of people will copy & paste for reviewing, could be nice to training them on the benefits of pep8 (better to catch'em early :P ).

on line 271 (add_branch), I propose a encrypted return branch, by adding a randomized value before and after the "branch" or, if the returned value is a number, I recommend using a lock and key. `

It is inconvenient that states have to be hashable. Why not remove the restriction? OR define apis converting state to its hashable version (e.g. self.state_representation(state)) automatically, the users could focus on the raw states.

When Flask 1.0 was released deprecated static_path parameter was removed, and, because dependencies in requirements.txt are not pinned, the web_viewer_server stop working.

This PR solve this situation using static_url_path instead. This was the workaround used in Flask to support the deprecated parameter. See commit where parameter is removed.

I didn't notice that the stochastic HC algorithm chooses randomly from all the improving states. So for those who want the choice to be in respect to the value of each state I've added this pull request.

When using local search the choosen_node event is never raised, so visited_nodes is allways 0. How should we count "visited nodes" on algorithms like beam or genetic?

Once we have viewers for CSP algorithms, and constraint propagation, it would be really nice to have viewers for the constraints propagation.

Depends on #12 and #42

The original Problem.cost() on aima-python receives the state, the actions, and the total cost, and expects to a new total cost to be returned. On simpleai we have changed that, to accept only the states and the action, and expect just the cost of that action to be returned. But this doesn't works for problem with actions that alter the costs of the previously taken actions.