###
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