CS 440/ECE 448
Fall 2021
Margaret Fleck
Quiz 7 (= Final exam) skills list
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