This skills list is still being revised due to changes in the lectures for the last few weeks.

MP practicalities

Questions related to what you built in MP 11 and 12.

Planning (Part 2)

• Historical figures and algorithms
  • STRIPS planner
  • Roger Schank
• 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
• Algorithms and planning languages
  • Truth maintenance systems
  • Towers of Hanoi takes time exponential in input size (number of rings)
  • SATplan
  • GraphPlan

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?
• Interesting recent algorithms
  • Libratus
  • AlphaZero
• 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

Sequential neural nets

Details still TBD