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.

Important note:  The exercises from R&N listed below are for the third edition.  If you are using the second edition, you can access the third-edition Chapter 3 exercises electronically (including all of the ones below), as follows: log on to the COS402 site on blackboard, then click on "E-Reserves", then "Chapter 3 exercises".

1.  [10] There are many "chatterbots" on the web that attempt to carry on human-level conversations, often within a limited domain.  These include:

• "Alice" at alicebot (previous winner of the Loebner Prize, an annual competition of chatterbots).  Click on "chat with Alice".
• "Bildgesmythe" at www.personalityforge.com (previous winner of the Chatterbox Challenge).
• "English tutor".
• Many, many others at www.simonlaven.com and the Chatterbox Challenge.

Have a "conversation" with one or more of these chatterbots.  Try to test what they can or cannot do, what they are good at, and what they are not so good at.  See what you can learn about how they work.  Then briefly (say, in three paragraphs or less) describe and analyze your experience.

2.  [15] Problem 3.15 in R&N (3rd ed.).

3.  [10] Problem 3.18 in R&N (3rd ed.).  Be sure to justify your answer.

4.  [15] Consider the following search problem:

The states are the vertices of this graph.  The start state is S, and the goal state is G.  The actions permit movement along directed edges with costs as indicated.  (For instance, the cost of moving from S to U is 2; the cost from U to V is 9.)  The numbers in blue by each vertex indicate heuristic h values.  (For instance, h(S)=9; h(U)=10.)

a.  Show that this choice of h is consistent.

b.  Draw the search tree that would result from running greedy best-first search.  Also number the nodes of the search tree in the order in which they are expanded.  For instance, place the number 1 by the start node (associated with the start state S).

c.  Do the same thing for A*.  Also indicate the g and f values associated with each search node.

5.  [10] Exercise 3.29 in R&N (3rd ed.).  Also, answer the following:  Does the admissible-but-not-consistent heuristic that you constructed have the monotone property that we discussed?  In other words, is it the case that the f-values are nondecreasing along every path?