N-puzzle a-star python solver efficiency

I've written an a-star algorithm designed to solve sliding-block/n puzzles. It works just fine on small puzzles, but struggles heavily with increasing complexity.

I've already implemented several methods to improve efficiency (heapq, etc) but I've reached the end of my ideas. Can you think of anything else I can do to improve it?

My code is here: https://repl.it/@Jaspirian/SimilarWoodenMemoryallocator

Some important parts:

The heuristic:

def heuristic_estimate_manhattan(self, other):
    """
    Finds the heuristic estimation of the cost to reach another state from this one.
    This heuristic is based on "manhattan distance."
    """
    estimate = 0

    for index in range(len(self.blocks)):
        estimate += abs(other.blocks[index][0] - self.blocks[index][0]) + abs(other.blocks[index][1] - self.blocks[index][1])

    return estimate

The neighbor function:

def get_neighbors(self, previous):
    """
    Gets all adjacent neighbors of the state, minus the previous.
    This function gives 7 neighbors: 4 orthogonal, 4 diagonal, with the previous state trimmed.
    """
    neighbors = []

    moves = ((-1,0),(1,0),(0,-1),(0,1))
    zeroLoc = self.blocks[0]

    for move in moves:
        # swap 0 and whatever
        newBlocks = copy.deepcopy(self.blocks)
        newZeroLoc = (zeroLoc[0] + move[0], zeroLoc[1] + move[1])
        # skip this state if we've moved off the board
        if newZeroLoc[0] < 0 or newZeroLoc[1] < 0 or newZeroLoc[0] > self.width-1 or newZeroLoc[1] > self.height-1:
            # print("we've moved off the board.")
            continue
        # skip this state if it's the same as the previous
        if previous and previous.blocks[0] == newZeroLoc:
            # print("this is just the same!")
            continue

        # move the 0
        newBlocks[0] = newZeroLoc

        # move whatever's in that location...
        # to the previous one
        for face, location in newBlocks.items():
            if face != 0 and location == newZeroLoc:
                newBlocks[face] = zeroLoc

        neighbor = Block_Puzzle(newBlocks)
        neighbors.append(neighbor)

    return neighbors

The a-star algorithm:

def aStar(start, goal):
"""
A star search algorithm. Takes a start state and an end state.
While there are available moves, loops through them and exits if the end is found.
Returns the list of states that are the "quickest" way to the end.
"""
...
openHeap = [start]
heapq.heapify(openHeap)
...
# While there are yet nodes to inspect,
while(len(openHeap) > 0):
    # Pop the lowest f-score state off. 
    current = heapq.heappop(openHeap)

    # print(len(openHeap))

    # If we've reached the goal:
    if current == goal:
        # return the list of states it took to get there.
        ...
        return path

    # make sure we won't visit this state again.
    closedDict[current] = True

    # For each possible neighbor of our current state,
    for neighbor in current.get_neighbors(cameFrom.get(current)):
        # Skip it if it's already been evaluated
        if neighbor in closedDict:
            continue

        # Add it to our open heap
        heapq.heappush(openHeap, neighbor)

        tentative_gScore = gScore[current] + 1
        # If it takes more to get here than another path to this state, skip it.
        if tentative_gScore >= gScore[neighbor]:
            continue

        # If we got to this point, add it!
        cameFrom[neighbor] = current
        gScore[neighbor] = tentative_gScore
        fScore[neighbor] = gScore[neighbor] + neighbor.heuristic_estimate_manhattan(goal)

return None

Solution

In get_neighbors, newBlocks is not used during those checks (like bounds checks). If any of those checks fail, the deepcopy() (or regular copy() going by jsmolka's answer) will be a waste of time. You can move that copy to after the checks.

In the algorithm itself, I'd recommend multiplying the heuristic by a number slightly greater than 1. For example:

fScore[neighbor] = gScore[neighbor] + 1.0001 * neighbor.heuristic_estimate_manhattan(goal)

This should automatically implement tie-breaking in such a way that we prefer paths where the cost is mostly g (real cost, reliable information, known to be correct), instead of those where the same total cost f is determined to a larger extent by the heuristic h (heuristic, guess, may not be entirely correct/reliable). This is generally the best tie-breaker for A*. In theory, that multiplication may make your heuristic inadmissible, but if the multiplier is close enough to 1.0 that won't matter.

Suppose current has a score f_current, and just got popped off of the openHeap. Suppose a newly generated neighbor ends up with exactly the same f score (just now a larger g component and a smaller h component). You know for sure that, in the next iteration, a node with this score would just immediately get popped again. This means that it is inefficient to actually push it into the heap and then pop again.

It is more efficient to have a separate (unsorted) stack available as well. Push nodes onto this stack instead of the heap if the f score equals the parents' f score. If this stack is non-empty, always pop nodes off of this instead of popping off of your heap. Only pop off of the heap if this stack is empty.

Note: this idea gets complicated to implement in combination with the multiplication-based tie-breaking described above. If you can manually specify the sorting criterion for your heap, you can also implement the tie-breaking differently (e.g. explicitly treating a node that is equal based on f score as smaller if it has a greater g / smaller h).