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 outlines 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.