Historical trivia

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

• STRIPS planner
• Roger Schank
• a truth maintenance system
• Libratus
• AlphaZero
• SATplan
• GraphPlan
• PDDL

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
• Representations of objects and actions
  • object types and instances
  • count vs. mass nouns
  • fluents
  • activities, state changes, accomplishments
  • decaying properties and maintenance actions
• Upgrades to the environment
  • Incompletely known
  • Other actors, moving obstacles
  • Actions might not execute as planned
  • Time limitations on planning
  • Contingent planning

Game Search

• Game tree
• What is ..
  • a "ply"? a "move"?
  • a Zero-sum game
  • a stochastic game?
  • a fully observable game?
• What other game features could make planning hard? (E.g. dynamic world, more than two players, limits on thinking time.)
• 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