Error with optimality in Iterative Deepening Depth First Search algorithm

Question

I have implemented a version of Rush Hour (the puzzle board game) in Python as a demonstration of some AI algorithms. The game isn't important, because the AI is relatively independent of its details: I've attempted to implement a version of iterative deepening depth first search in Python as follows (note that this code is almost directly copied from Russell and Norvig's AI text, 3rd edition, for those of you who know it):

def depth_limited_search(game, limit):
    node = GameNode(game)
    frontier = []
    #frontier = Queue.Queue()
    frontier.append(node)
    #frontier.put(node)
    frontier_hash_set = set()
    frontier_hash_set.add(str(node.state))
    explored = set()
    cutoff = False
    while True:
        if len(frontier) == 0:
        #if frontier.empty():
           break
        node = frontier.pop()
        #node = frontier.get()
        frontier_hash_set.remove(str(node.state))
        explored.add(str(node.state))
        if node.cost > limit:
            cutoff = True
        else:
            for action in node.state.get_actions():
                child = node.result(action)
                if str(child.state) not in frontier_hash_set and str(child.state) not in explored:
                    if child.goal_test():
                        show_solution(child)
                        return child.cost
                    frontier.append(child)
                    #frontier.put(child)
                    frontier_hash_set.add(str(child.state))
    if cutoff:
        return 'Cutoff'
    else:
        return None

def iterative_deepening_search(game):
    depth = 0
    while True:
        result = depth_limited_search(game, depth)
        if result != 'Cutoff':
            return result
        depth += 1

The search algorithm, as implemented, does return an answer in a reasonable amount of time. The problem is that the answer is non-optimal. My test board of choice has an optimal answer in 8 moves, however this algorithm returns one using 10 moves. If i replace the lines above commented out lines with the commented lines, effectively turning the iterative deepening depth-first search into an iterative deepening breadth-first search, the algorithm DOES return optimal answers!

I've been staring at this for a long time now trying to figure out how a simple change in traversal order could result in nonoptimality, and I'm unable to figure it out. Any help pointing out my stupid error would be greatly appreciated

Answer 1

I can't test this but I think the problem is this predicate:

if str(child.state) not in frontier_hash_set and \
   str(child.state) not in explored:

The problem is that earlier in this DFS iteration, child.state may have been inserted into the frontier or set of visited states, but with a greater cost.

S -> A -> B -> C -> G
 \            /
  \-----> D -/ 

Obviously you will not reach the goal with limit < 3. But when limit = 3, your DFS may first visit A, B, and C. Then when it backtracks to S, visits D, and tries to visit C, it will not push C onto the stack because you visited it earlier.

To fix this, I believe you need to "un-visit" states as you backtrack. Implementation-wise it is probably easiest to write your algorithm recursively and pass copies of your explored-state set in a functional style.