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

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 purpose, we use 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 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 in social terms and should be seen more as a guideline than as a scientific truth with respect to the problem that is being solved.

Informed search: Looking for solutions with guidance

A* search

Use cases for informed search algorithms

Adversarial search: Looking for solutions in a changing environment

A simple adversarial problem

Min-max search: Simulate actions and choose the best future

Alpha-beta pruning: Optimize by exploring the sensible paths only

Use cases for adversarial search algorithms

Summary of Intelligent search