Early AI research emphasized the optimization of search algorithms. This approach made a lot of sense because many AI tasks can be solved by effectively by defining state spaces and using search algorithms to define and explore search trees in this state space. Search programs were frequently made tractable by using heuristics to limit areas of search in these search trees. This use of heuristics converts intractable problems to solvable problems by compromising the quality of solutions; this trade off of less computational complexity for less than optimal solutions has become a standard design pattern for AI programming. We will see in this chapter that we trade off memory for faster computation time and better results; often, by storing extra data we can make search time faster, and make future searches in the same search space even more efficient.
What are the limitations of search? Early on, search applied to problems like checkers and chess mislead early researchers into underestimating the extreme difficulty of writing software that performs tasks in domains that require general world knowledge or deal with complex and changing environments. These types of problems usually require the understanding and then the implementation of domain specific knowledge.
In this chapter, we will look at two search problem domains for studying search algorithms: searching graphs and alpha-beta game players. Game search is a type of graph search, but I think it is easier to understand the code if we keep the examples separate.
TBD
TBD