3 Intelligent search
This chapter covers
- Understanding and designing heuristics for guided search
- Identifying problems suited to being solved with guided search approaches
- Understanding and designing a guided search algorithm
- Designing a search algorithm to play a two-player game
3.1 Defining heuristics: Designing educated guesses
Now that we have an idea of how uninformed search algorithms work from chapter 2, we can explore how they can be improved by seeing more information about the problem. For this, we use informed search. Informed search means that the algorithm has some context of the specific problem being solved, instead of blindly searching breadth-first or depth-first. Heuristics are a way to represent this information.
Often called a rule of thumb, a heuristic is a rule or set of rules used to evaluate a state. It can be used to define criteria that a state must satisfy or measure the performance of a specific state. A heuristic is used when a clear method of finding an optimal solution is not possible. A heuristic can be interpreted as an educated guess and should be seen more as a guideline rather than as a scientific truth with respect to the problem that is being solved.