Searching Algorithms

Heuristic Functions

A heuristic function is a way to inform the search about the direction to a goal.

In the context of Adversarial Search: An evaluation function estimates the expected utility of the game from a given state. You can also call this Value Function, borrowed from the RL community.

Grid Search

Suppose you have a goal position $(x_g,y_g)$ and your current position is $(x_n,y_n)$, then you can use some simple heuristics:

Manhattan Distance $H(x_n,y_n)=|(x_n-x_g)|+|(y_n-y_g)|$ Euclidean Distance $H(x_n,y_n)=\sqrt{(x_n-x_g{)}^2+(y_n-y_g{)}^2}$