Princeton University

Computer Science 302
Introduction to Artificial Intelligence
Problem Set 5

Fall 2001
Due Nov 7
  1. The value iteration algorithm from the Games of Chance lecture can be applied to deterministic games with loops. Argue that it produces the same answer as the "Loopy" algorithm from the Game Tree lecture.
  2. Write the matrix form of the game tree.
  3. How many times (on average) do you need to flip a coin before you flip 3 heads in a row? (a) Set this up as a Markov chain, and (b) solve it.