Heuristic Knowledge

Breadth and Depth first searches are uninformed. No knowledge is used to guide the search. Often some knowledge about the problem is available and can be used to make searching more efficient by rating the nodes and expanding the most promising ones first.
Consider the 8-puzzle again. On each move there are 2, 3, or 4 choices. The uninformed searchers just choose which to look at first in a purely arbitrary (although systematic) way.
But all choices are not necessarily equal. The knowledge applied to help choose which is best is called heuristic knowledge. Best first search is sometimes called heuristic search.
Heuristic knowledge is not complete knowledge. It is not guaranteed to make the right choice. If you always knew enough to make the right choice, you would not really be engaged in search.
There is a tradeoff between knowledge and search. The more knowledge you have, the more easily ou can keep the search on the right path.
Heuristic knowlege is sometimes referred to as “rules of thumb” to emphasize that this knowledge is ‘weak’ knowledge, knowledge that usually helps, but not always.

Some heuristics for the 8-puzzle
• Count the number of squares out of place in each position with respect to the goal position, and choose the position which minimizes this number.
• Sum the the so-called “Manhattan Distances” of all the squares in a position with respect to the goal position. Choose the position with the smallest Manhattan distance.
• Count the number of pairs of tiles in the reverse order, compared to the goal position, around the edge of the board. Choose the position with the smallest number of out of order pairs.

Some chess heuristics
• Don’t move your queen early in the game.
• Place rooks on open files.
• Castle as soon as possible.
• Always try to control the 4 centre squares
• A bishop pair are more valuable than a pair of knights or a bishop and knight.

Using Evaluation Functions
For a machine to use heuristic knowledge, it must be quantified. The quality of a state can then be represented as a function of the various heuristics. For instance, in the 8-puzzle, you could combine all three of the above heuristics:
f^(n) = a * (# tiles out of place) + b * (total Manhattan) + c * (bad pair count) for node n.
a, b and c, are adjustable coefficients reflecting how important each factor is thought to be.
f^(n) is an estimate of the cost of getting from node n to the goal node.
The position with minimum f^ (n) would be the best choice. (For the goal, f ^ (n)= f (n)= 0.)
(Here, f(n) is the actual, real, cost of getting from node n to the goal node.)

8-Puzzle with one simple heuristic
Here is the same 8 puzzle as before. This examples uses the very simple heuristic,
f ^(n) = (# tiles out of place in node n).
Image_ nHeuristic.gif
You can see from this picture that the heuristic by itself has not helped much. The heuristic function h^(n) allows us to choose among nodes at the same level (siblings), but does not allow comparisons between levels.
With h^(n) alone we get a cross between a depth first and a breadth first search. Maybe we are getting the worst of both worlds! Lots of nodes expanded, wasting memory, and the possibility of getting lost deep in the search space.
To take advantage of heuristic knowledge we need to add one more factor to prevent these futile plunges too deep into the space.