CSC 550: Introduction to Artificial Intelligence
Fall 2008

Midterm Review

Overview history of AI, Turing test philosophical extremes: neats vs. scruffies, GOFAI vs. emergents, weak vs. strong Scheme and AI programming S-expressions (atoms & lists), functional expressions primitive functions + - * / quotient remainder max min abs expt floor round = < <= > >= exact->inexact inexact->exact car cdr cons list list-ref length member reverse append equal? set! let display begin read programming tools function definitions, if, cond full recursion vs. tail-recursion first-class functions, map, apply AI programming example Eliza: knowledge representation, pattern-matching AI as search state spaces search control strategies uninformed+bold: STUPID uninformed+tentative: depth first search (DFS), DFS with cycle checking no guarantee to find shortest (or any) solution; low memory requirements breadth first search (BFS), BFS with cycle checking guaranteed to find shortest solution; high memory requirements iterative deepening guaranteed to find shortest but repeats search; low memory requirements informed+bold: hill-climbing uses heuristics, potential pitfalls (e.g., foothills, plateaus) low memory requirements informed+tentative: best first search uses heuristics, does not guarantee shortest high memory requirements, better than BFS if heuristic is good optimization problems find minimal cost path (based on some measure) algorithm A basically, best first using hybrid cost function (f = g + h) g: actual cost so far along path; h: expected cost remaining admissibility, algorithm A* game playing game characteristics: two-player, perfect information, zero-sum minimax theorem game trees minimax search, alpha-beta pruning case studies: chess, checkers, connect-4 Knowledge Representation and AI foundational knowledge representation schemes semantic nets graphical representation, info retrieval as graph search, inheritance conceptual dependency representation defined richer set of links for networks, stores underlying concepts frames slot-filler model, inheritance, defaults, constraints, procedures scripts frame structure for representing events, utilized conceptual dependencies expert systems rule-based reasoning common characteristics expert-level performance, focused on a particular (usually narrow) domain, must deal with uncertainty, must provide facilities for explanation, ... layout: user interface, inference engine, knowledge base, case-specific data rule application: depth vs. breadth, best vs. all, forward vs. backward, ... uncertainty: probabilities, certainty factors, fuzzy logic, ...