Midterm Examination
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Autumn 2019
Date: Monday, October 28, 2019
Format: Several short-answer questions, with a few longer-answer questions possible.
Topics:
Turing Test

State Space search
  State
  Operator
    Partial function  
    Precondition
  Move
  Goal state
  State space
  Branching factor
  Combinatorial explosion
  Counting distinct states of simple problems
  Towers of Hanoi Problems
  Tic-Tac-Toe
  Missionaries and Cannibals Problem
  The Farmer, Fox, Chicken and Grain Problem
  Problem formulation
  Problem-Space Graph
  Path
  Depth-First Search
  Breadth-First Search
  Uniform-Cost Search
  A* Search
    heuristic function
    admissibility of a heuristic
    consistency of a heuristic
  Iterative Deepening Depth-First Search

Adversarial Search
  Two-Person Zero-Sum Game
  Minimax Search
  Static Evaluation Function
  Alpha-Beta Pruning
  Zobrist Hashing
    Bitwise exclusive-or
    finding a child state's hash value from that of its parent
  
Random variable
  Domain
  Probability distribution
  Expectation

State Spaces with Stochasticity
  Expectimax search
  Markov Decision Process
    Definition
    Matrix representation
    State-transition diagram
    Living reward, cost of living
  Utility using finite horizons
  Utility using discount factors
  Policy