Artificial Intelligence Through Search

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 asAND/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.