The final will be open for our official final exam period (Thursday the 16th, 1:30-4:30). I will probably extend this time window somewhat and also set up a conflict time. Details will appear.

The quiz will be 30 minutes long and will cover material through the last lecture.

Historical trivia

Know what the following are/were and briefly place them in context:

• STRIPS planner
• Roger Schank
• a truth maintenance system
• Libratus
• AlphaZero

Planning

• Representing a planning problem
  • State and action representation
  • Preconditions and effects (postconditions)
  • In what ways does this fail to capture our knowledge of objects and actions?
  • The Frame Problem
• Approaches to planning
  • Hierarchical planning
  • Sussman anomaly, interleaved planning
  • Forward and backward planning
  • Situation space planning vs. plan space planning
  • Towers of Hanoi takes time exponential in input size (number of rings)
• Partial order (plan space) planning:
  • the idea
  • plan modification operations
  • plan defects (open preconditions, threats) and how to fix them

Game Search

• Game tree
• What is ..
  • a "ply"? a "move"?
  • a Zero-sum game
  • a stochastic game?
  • a fully observable game?
• Basic method
  • Minimax strategy
  • Minimax search (using depth-first search)
  • Depth cutoff
  • Heuristic state evaluation
• Alpha-beta pruning
  • How it works
  • How well it works
  • Impact of move ordering
  • You will not have to write out detailed code for alpha-beta search. Concentrate on understanding what branches it prunes and why.
• Optimizations around depth cutoff
  • Horizon effect
  • Quiescence search
  • Singular extension
  • Early pruning
• Other optimizations
  • Memoization (transposition table)
  • Opening moves, endgames
  • Where might we use a neural net to help out?
• Stochastic games, games with imperfect information
  • How to model randomized moves using a game tree
  • How much does randomization enlarge game trees?
  • Monte Carlo tree search