CS50 AI lecture 0 search. I tried to implement Maze.py by myself

Question

But I don't know how it's stuck in an infinite loop. I added the explored variable. If the node is examined it shouldn't get added to the frontier. But still, it's stuck in an infinite loop. The same node is going back and forth and not exploring the new direction. I don't know what's the problem.

Here's the code:

class Agent():

    def __init__(self, node, parent):

        self.node = node
        self.parent = parent


class Queue():

    def __init__(self):
        self.frontier = []
        self.explored = []

    def contains_state(self, state):
        return any(node.node == state for node in self.frontier)

    def add(self, child):

            self.frontier.append(child)

    def remove(self):

        node = self.frontier[-1]
        self.frontier = self.frontier[::-1]
        return node


class Stack():
    pass

class Maze():

    def __init__(self):

        self.filename = 'maze1'

        with open(self.filename) as f:
            self.maze = f.read().splitlines()

        self.height = len(self.maze)
        self.width = len(max([x for x in self.maze]))

        self.walls = []

        for i in range(self.height):

            for j in range(self.width):

                if self.maze[i][j] == '0':

                    self.walls.append((i, j))

                if self.maze[i][j] == 'A':

                    self.start = (i, j)

                if self.maze[i][j] == 'B':
                    self.goal = (i, j)

    def action(self, position):

        print(position)

        action_dict = {'up': (position[0]-1, position[1]),
                       'down': (position[0]+1, position[1]),
                       'left': (position[0], position[1]-1),
                       'right': (position[0], position[1]+1)}

        possible_actions = []

        for actions in action_dict:

            r = action_dict[actions][0]
            c = action_dict[actions][1]

            if r >= 0 and r < self.height and c >= 0 and c < self.width:

                if self.maze[r][c] != '0':

                    possible_actions.append((r, c))

        return possible_actions

    def solve(self):

        solver = Queue()

        agent = Agent(node=self.start, parent=())

        new_observation = agent

        solver.add(new_observation)

        self.explored = set()

        while (True):

            child = solver.remove()

            if child.node == self.goal:

                path = []
                while child.parent is not None:
                    path.append(child.node)
                    child = child.parent

                for i in path:
                    self.maze[i[0]] = self.maze[i[0]][:i[1]] + '*' + self.maze[i[0]][i[1] + 1:]

                n_names = ["{}\n".format(i) for i in self.maze]
                with open(self.filename + '_solution', 'w') as fp:
                    fp.writelines(n_names)
                break

            neighbours = self.action(child.node)

            for i in neighbours:

                child = Agent(node=i, parent=new_observation.node)

                if not solver.contains_state(i) and i not in self.explored:

                    solver.add(child)
                    self.explored.add(i)

            if len(solver.frontier) == 0:

                print("No solution")
                break

algo = Maze()
algo.solve()

Here's the Maze I am trying to solve:

000B00
00  00
00 000
00  00
A  000

Answer 1

I assume you have found the problem by now. This is for anyone else that is interested in this code.

The major problem is with the Queue remove method. (And, this is a stack/LIFO, not a queue.) I changed the code to use a list pop instead of a slice. The original slice syntax in the code didn't remove anything.

24,25c24,26
<         node = self.frontier[-1]
<         self.frontier = self.frontier[::-1]
---
>         # stack
>         node = self.frontier.pop(-1)
>         #self.frontier = self.frontier[:-1]

I found the Agent names confusing. I changed it to:

def __init__(self, node, parent):

    self.coord = node
    self.parent = parent

Later, the code is looking for None as a terminator. Make sure the start node has None as a parent.

89c89
<         agent = Agent(node=self.start, parent=())
---
>         agent = Agent(self.start, parent=None)

The parent must be an Agent. Why? Because you need both the coord and the parent for that node to walk the path back to the start.

120c122
<                 child = Agent(node=i, parent=new_observation.node)
---
>                 new_node = Agent(i, parent=child)

You need to keep the "child" you removed to use as the parent when you create new Agents. Each neighbour to the child has the same parent.

Here, you don't need to do two checks. The self.explored is set at the same time as solver.add(new_node). Doing two checks doesn't hurt anything, but it is confusing.

122c124,125
<                 if not solver.contains_state(i) and i not in self.explored:
---
>                 #if not solver.contains_state(i) and i not in self.explored:
>                 if i not in self.explored:
124c127
<                     solver.add(child)
---
>                     solver.add(new_node)

So, this code was very close to solving the problem. Just a few problems.