Here are some quotes of my findings from one of my Assignments from the course with the open university 'Natural and Artificial Intelligence'.

context : search in Sokoban ( a puzzle game)

"One method of developing heuristics is to identify constraints in the problem and relax them to form an easier problem. The cost of solving the easier problem can be quickly calculated; which gives an approximate cost for solving the real problem...."

How many constraints you relax to develop a heuristic depends on the complexity of the task and the time it takes to evaluate. Relaxing one might be enough to create the most efficient heuristic or you might need two or more, but there is a balance that needs to be met so that the best heuristic is found within the allotted development time. Bringing in too much complexity can lead to confusing and unmanageable code. However exploring a number of constraints can lead to a better solution.

The best heuristic is the one which more accurately estimates the cost and so more accurately guides the search towards the goal state, resulting in fewer nodes expanded which means a faster and optimal search. The heuristic should also be admissible.

A heuristic is admissible if it always underestimates the cost of the path to the solution. It is important for finding optimal solutions at it means the partially constructed optimal paths will always be chosen over the sub optimal paths to the goal state.

The things that affect the relative performance of the algorithms using different heuristics appear to be the size of the state space, if it is small then a less complex algorithm can find it fast. If the state space is large then the similar algorithm that is slightly less complex can be faster but expands more nodes. So I if you had to choose only one algorithm/ heuristic it would be best to use A* (displaced heuristic) as it is complete optimal and efficient.....

Obviously my results are only valid for the Sokoban puzzle that i was experimenting with but there are some general principles to draw from.

We used a program called 'search lab' which let you try out many different combinations of algorithms.