Error with optimality in Iterative Deepening Depth First Search algorithm

I have implemented a version of Rush Hour (the puzzle board game) in Python as a demonstration of some AI algorithms. The game i开发者_运维知识库sn'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

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.

The reason your code finds a sub-optimal solution is simply because of the way depth-first-search and bread-first-search work.

A breadth-first-search will try all possible 8-move solutions before trying any 9-move solutions, so a breadth-first-search must find a solution with the fewest possible moves.

In contrast, a depth-first-search will try some 9, 10, 11, ... move solutions before it has exhausted all possible 8-move solutions and so may come up with a sub-optimal result.

For example, given a game tree that looks like this:

          1
     /         \
    2           3
  /   \       /   \
 4     5     6     7
 /\    /\    /\    /\
8  9  A  B  C  D  E  F

The code as given will call goal_test on the nodes in this order: 2, 3, 6, 7, E, F, C, D, 4, 5, A, B, 8, 9. Note that nodes E and F are tested before the children of node 6, and also before the children of node 2. This is a depth-first-search.

The alternate version of your code will call goal_test in this order: 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. This is a bread-first-search.

Edit: My bad, my order of calls to goal_test above is only correct for the final iteration in iterative_deepening_search. The actual order of calls to goal_test is 2, 3, 2, 3, 6, 7, 4, 5, 2, 3, 6, 7, E, F, C, D, 4, 5, A, B, 8, 9. I verified this by actually running the code, so I'm 100% sure it is now correct.

Are you sure the child.state value is unique for each game node? If they are not, then the algorithm will fail. For example, consider what happens if node 4 has the same state as node 6. In that case your code will call goal_test on nodes in this order: 2, 3, 2, 3, 6, 7, 5, 2, 3, 6, 7, E, F, C, D, 5, A, B. Note that goal_test is never called on nodes 4, 8 and 9.

But if we switch to the alternate version of your code then goal_test is called in this order: 2, 3, 2, 3, 4, 5, 7, 2, 3, 4, 5, 7, 8, 9, A, B, E, F. Now goal_test is not called on nodes 6, C and D! I believe this may be the cause of your problem.