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
• Monte Carlo tree search

Sequential neural nets

• Historical names
  • Vaswani et al
  • BERT
  • GPT and Llama families of LLMs
• Input and output
  • tokenization
  • convert tokens to vectors (e.g. word2vec)
  • positional encoding
• Recurrent neural networks
  • High-level view of how they work
  • When would we compute loss from last unit vs. summed over all units?
  • Bidirectional RNN
  • How does a "Gated RNN" differ from a standard one?
• Encoder-Decoder architecture
• Attention
  • Weighted sum of vectors in context window
  • Assessing similarity (learned weights plus dot product)
  • "Attention head" (and you can have more than one)
• Transformer blocks
  • what's in them (high-level)
  • residual connections
• LLMs
  • Masked vs. autoregressive
  • BERT, Llama, GPT
  • Pre-training, fine-tuning, task head
  • Training BERT
  • What is BERT good for?
  • Self-training autoregressive model
  • Using autoregressive model
  • Prompt engineering
  • Some very approximate sense of the number of parameters, amount of training data, etc