COS 402: Artificial Intelligence

Numbers in brackets indicate approximate number of points each problem is worth.  See the course home page for information on when and where to submit written exercises, and grading criteria.  As always, please be very careful to do the right problems for your edition of R&N.  A scanned copy of the exercises in R&N (3rd ed.) are available on e-reserves (log on to the COS402 site on blackboard, then click on "e-reserves").

1.  [15]  Exercise 6.1 in R&N (2nd ed.) OR Exercise 5.9 in R&N (3rd ed.).  Assume player X goes first.  In part (a), "game" should be interpreted to refer to a complete path through the search tree from the root to a leaf, in other words, a sequence of plays culminating in either a victory for one of the players or a draw.  Note that part (a) asks for an approximate estimate, so don't spend a lot of time trying to get an exact answer.  In part (e), "optimal order" means that the best successors (in terms of their value) are always examined first.

2.  [10]  Exercise 6.2 in R&N (2nd ed.) OR Exercise  5.7 in R&N (3rd ed.).

3.  [10]  Exercise 7.4a,c in R&N (2nd ed.) OR Exercise 7.5a,c in R&N (3rd ed.).  Be sure to prove these assertions; don't just "wave your hands".

4.  [15]  (Adapted from a similar exercise in R&N.)  Consider the following facts:

"If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal.  If the unicorn is either immortal or a mammal, then it is horned.  The unicorn is magical if it is horned."

1. Translate the facts above directly into sentences of propositional logic using a suitable (and clearly defined) set of proposition symbols.
2. Determine whether or not each of the following are entailed by the facts above, and justify your answers:
   1. "The unicorn is mythical."
   2. "The unicorn is not mythical."
   3. "The unicorn is magical."
3. Simulate the resolution algorithm to show how it would determine whether or not the following statement is entailed by the facts above:  "The unicorn is both magical and horned."  You can resolve clause-pairs in whatever order you wish.  Be sure to state the final outcome of running the algorithm.

5.  [optional -- 5 hops (honors optional points)]  This optional exercise asks you to prove the correctness of alpha-beta search.  See this pdf for details.