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.  A scanned copy of the exercises in R&N are available on e-reserves (log on to the COS402 site on blackboard, then click on "e-reserves").

1.  [15]  Exercise 5.9 in R&N.  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 please 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  5.7 in R&N.

3.  [10]  Exercise 7.5a,c in R&N.  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.

Some clarifying notes:  In general, you should not bring additional information to this problem, beyond the facts that are given.  For instance, you should not use your own knowledge that all mammals are mortal, or that unicorns have horns, or any notions you might have about the relationship between creatures that are immortal, magical or mythical.  You should view all of these as separate, independent attributes which are only related as specifically described in the problem.  Also, a "mortal mammal" is just a creature that is both a mammal and a mortal, and "immortal" just means "not mortal".

5.  [10HP]  This optional exercise asks you to prove the correctness of alpha-beta search.  See this pdf for details.