ABSTRACT
Efforts using artificial intelligence (AI) to solve problems with computers — which humans routinely handle by employing innate cognitive abilities, pattern recognition, perception, and experience — invariably must turn to considerations of search. This chapter explores search methods in AI, including both blind exhaustive methods and informed heuristic and optimal methods, along with some more recent findings. The search methods covered include (for non-optimal, uninformed approaches) state-space search, generate and test, means-ends analysis, problem reduction, AND/OR trees, depth-first search, and breadth-first search. Under the umbrella of heuristic (informed) methods, we discuss hill climbing, best-first search, bidirectional search, and the A∗ algorithm. Tree searching algorithms for games have proved to be a rich source of study and provide empirical data about heuristic methods. Included here are the SSS∗ algorithm, the use of iterative deepening, and variations on the alpha-beta minimax algorithm, including the recent MTD(f) algorithm.
