CS 380/480 - Foundations
of Artificial Intelligence
- Winter 2007
Assignment 4
Due: Friday, March 9
- Consider the following tree corresponding to a two player game (with MAX
starting at the top), where the numbers below the leaf nodes represent the
heuristic evaluations of for those nodes:
- Use the (3-ply) Minimax procedure to determine the best move for MAX at node
A. Also show the (backed-up) value of each node in the tree.
- Determine which nodes will be pruned (cut-off) when using alpha-beta pruning. Assume
depth-first evaluation from left-to-right. Show your work.
-
Three prisoners, A, B, C are
in their cells. They are told that one of them will be executed the next day and
the others will be pardoned. Only the governor knows who will be executed.
Prisoner A asks the guard a favor. “Please ask the governor who will be
executed, and then tell either prisoner B or C that they will be pardoned.” The
guard does as was asked and then comes back and tells prisoner A that he has
told prisoner B that he (B) will be pardoned. What are prisoner A’s chances of
being executed, given this message? Is there more information than before his
request to the guard?
-
Suppose an automobile insurance
company classifies a driver as good, average, or bad. Of all their insured
drivers, 25% are classified good, 50% are average, and 25% are bad. Suppose for
the coming year, a good driver has a 5% chance of having an accident, and
average driver has 15% chance of having an accident, and a bad driver has a 25%
chance. If you had an accident in the past year what is the probability that you
are a good driver? [Hint: Use Bayes' Rule to obtain the probability
p(good | accident). A similar example was discussed in
class.]
-
Consider the meningitis example given in Russell and Norvig, Page 480.
In this problem we explore how to use Bayesian updating. Starting with
a patient about whom we know nothing, show how the probability of having
meningitis, P(m) is updated after we find patient has stiff neck (s). Next
show how P(m) is updated again when we find that the patient also has fever (f).
Assume that the conditional probability P(f|m) is determined based on
historical data to be 0.8. Also, assume that probability of fever P(f) is
0.02.
Hint: Note that it is not usually reasonable to estimate P(f | s)
since this does not denote a casual relationship. Instead, you need to
use normalization. Also, you can assume that the probability of having fever
given that patient does not have meningitis, P(f | m) is about the same
as the probability of having fever, P(f).
Note: A similar example was discussed in
class.
 Back to Assignments
Back to Main Page
|
