CSC 550: Introduction to Artificial Intelligence
Spring 2004

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 AI programming examples Eliza: knowledge representation, pattern-matching automated deduction: predicate calculus, logic programming AI as search state spaces must define (1) state representation (including start and goal states), (2) transitions/moves between states, (3) control strategy to search for a path from start to goal search control strategies tentative vs. bold, informed vs. uninformed strategies depth first search (DFS) efficient, but cycles are a problem can add cycle checking, but still no guarantee of best solution breadth first search (BFS) memory intensive, but finds shortest solution if one exists cycle checking easy DFS with iterative deepening finds shortest solution without memory requirements of BFS some duplication of effort, but not very costly hill-climbing guided by heuristics, bold unless heuristic is perfect, can get stuck (e.g., foothills) best first search guided by heuristics, but tentative similar to BFS, except paths are ordered by the heuristic search applications optimization problems Algorithm A: best first search utilizing heuristic f, where f = g (cost of path so far) + h (estimate of remaining cost to goal) if h is admissible (never overestimates), will find optimal solution game playing minimax principle: applies to 2-person, perfect info, zero-sum games game tree, minimax search, alpha-beta pruning