3 Intelligent Search
What you will learn in this chapter:
- Understanding and designing heuristics for guided search.
- Identifying problems suited to be solved using 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, we can explore how they can be improved by providing more information about the problem. For this we used informed search. Informed search means that the algorithm has some context of the specific problem being solved. Heuristics are a way to represent this context. Often described as 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 define 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” in social terms and should be seen more as a guideline rather than a scientific truth with respect to the problem that is being solved.