1 Search-Related Techniques in AI -- Why search -- Objectives -- Problem-solving systems -- State space search and problem reduction -- Blind search and heuristic search -- Graphs and trees -- Organisation of the book -- Searching for a solution path in a state space -- Problem reduction -- A very brief comparison of POP-11 and Prolog -- Further reading -- 2 Simple State Space Search -- Path-finding -- Setting up the database -- Setting up the path-finding function -- The generality of search -- Search spaces and search trees -- Constructing an explicit representation of the search-tree -- Search graphs -- Node terminology -- Backwards v. forwards searching -- OR-tree search in Prolog -- Reading -- Exercises -- 3 State Space Search -- The water jugs problem -- Constructing successor nodes -- The problem space -- Searching for a solution path -- Problem space exploration strategies -- Breadth-first search -- Agendas -- Implementing depth-first search using an agenda -- Iterative deepening -- Water jugs in Prolog -- Agendas in Prolog -- Iterative deepening in Prolog -- Reading -- Exercises -- Notes -- 4 Heuristic State Space Search -- The 8-puzzle -- Constructing 8-puzzle successors -- Heuristic search -- Hill-climbing search -- Heuristic breadth-first search -- Ordered search and the A* Algorithm -- Heuristic Search in Prolog -- Reading -- Exercises -- Notes -- 5 Heuristic Search of Game Trees -- Computing successors in the game of nim -- Minimax evaluation -- Worked example -- Alpha-beta cutoffs -- Implementing a nim-playing program -- Minimaxing in Prolog -- Reading -- Exercises -- Notes -- 6 Problem Reduction (AND/OR-tree search) -- Problem-reduction and the Tower of Hanoi -- Implementing arbitrary AND/OR-trees -- Implementing the AND/OR-tree search function -- Implementing planning as AND/OR-tree search -- Implementing reasoning as AND/OR-tree search -- Loops in the search space -- Solution tree -- The AND/OR search tree -- State space search and problem reduction -- Forward AND/OR-tree search -- Terminology -- Production systems -- AND/OR Search in Prolog -- Reading -- Exercises -- Notes -- 7 Planning (microworld search) -- Operators -- Strategies for microworld search -- Implementing the new search function -- Difference tables -- Goal interactions -- Operators containing variables -- Simple plan finding in Prolog -- Reading -- Exercises -- 8 Parsing (search as analysis) -- Solution trees as analyses -- Parsing -- Data-driven (bottom-up) parsing -- Building trees bottom-up -- Advantages of bottom-up search -- Backwards and forwards parsing in Prolog -- The Prolog grammar rule formalism -- Bottom-up parsing in Prolog -- Why is parsing useful -- Building a top-level interpreter -- Meaning in Prolog -- Reading -- Exercises -- 9 Expert Systems (probabilistic search) -- Probabilistic rules -- Basic probability theory -- Fuzzy set theory -- MYCIN-like search -- Implementing certainty-factors -- Forwards or backwards -- Probabilistic search in Prolog -- Reading -- Exercises -- 10 Concept learning (description search) -- Generalisation hierarchies -- Deriving extensions -- Quantifying generality -- Concept learning -- Implementing the generalisation mechanism -- The focussing algorithm -- Focussing in Prolog -- Generalisation as search -- Reading -- Exercises -- 11 Prolog (search as computation) -- Search rules as predicates -- The use of variables in search rules -- Data structures -- Unification -- Implementing the unification matcher -- Machinery to deliver output -- The search function -- Programming in Toyplog -- A sample interaction with Toyplog -- Reading -- Exercises -- Notes -- References -- Appendix A: Introduction to POP-11 -- Starting POP-11 -- POP-11 as a calculator -- Variables -- Functions -- Defining functions -- Local variables -- Boolean expressions -- Conditionals -- Words and lists -- Hats -- For loops -- Applist -- Syssort -- Matching -- Restriction procedures -- The matcher arrow -- The database -- Readline -- Functions calling functions -- Recursion -- Tracing -- Showtree -- Exiting from a function -- Partial application -- Concluding comment -- Appendix B Where to get the source code.