CS 6601:  Midterm study guide

Note:  R&N = AI, A Modern Approach, by Russell & Norvig

• Adversarial search (R&N Chapter 5)

• Observable games (e.g. isolation)
• Minimax
• Alpha-beta pruning

• Performance improvement

• Utility and evaluation functions

• Sensitivity

• Optimization tricks

• Move-ordering
• Symmetry

• Iterative deepening
• Multiplayer games
• Probabilistic games
• Partially observable games (e.g. poker)

• Search (R&N Chapter 3, uninformed and informed)

• Uninformed

• Breadth-first search
• Depth-first search
• Depth-limited search
• Iterative deepening depth-first search
• Uniform-cost search

• Informed

• Greedy search
• A* search
• Heuristics

• Consistency/admissibility
• Dominance
• Derivation by relaxation

• Bidirectional
• Tridirectional
• Tree vs. graph search
• Completeness, space/time complexity, path optimality

• Agent design (R&N Chapter 2)

• Rationality
• PEAS

• Performance
• Environment

• Observability
• Deterministic/stochastic
• Episodic/sequential
• Static/dynamic
• Discrete/continuous
• Single/multi-agent

• Actuators
• Sensors

• Uncertainty

• Agent types

• Reflex
• Reflex with state
• Goal-based
• Utility-based
• Learning

• Random algorithms (part of R&N Chapter 4)

• Hill-climbing
• Beam search
• Iterative improvement
• Simulated annealing
• Genetic algorithms
• Local vs. global maximum
• Local stochastic search

• Constraint satisfaction problems (R&N Chapter 6)

• Variables, domains, constraints
• Standard search
• Backtracking
• Heuristics

• Minimum remaining values
• Least constraining value

• Forward-checking
• Arc consistency
• Path consistency
• Problem re-structuring

• Probability (R&N Chapters 13 and 14a, 14b)

• Independence/dependence
• Discrete/continuous variables
• Joint distribution
• Central Limit Theorem
• Conditional probabilities

• Bayes’ Rule
• Chain Rule
• Conditional independence

• Bayesian networks

• How to construct
• Local independence
• Inference

• Exact (calculation)

• Enumeration
• Variable elimination

• Inexact (sampling)

• Rejection sampling
• Stochastic simulation
• MCMC simulation

• Decision/utility theory

• Expected value