COS 402: Artificial Intelligence

This assignment consists of written exercises only (all later assignments will also involve programming).  All problems are worth 10 points, except problem 3 which is worth 15 points.  See the assignments page for information on when and where to submit written exercises.

Remember that if you do not already know Java, you should be learning it at this time.

1.  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.org (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).
• "Alan" at www.a-i.com.  Click where it says "click to launch".
• 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.  Problem 3.7 in R&N (where successor function refers simply to the actions that are possible from each state).  Do any two of the four parts of this problem.

3.  Consider the following search problem:

The states are: A, B, C, D, E and F.  The initial state is A.  The goal state is E.  The actions permit movement along directed edges (for instance, from B, we can move to C, D or E).  Assume unit step cost.

Draw the search tree that would be produced by running each of the search algorithms BFS, DFS and IDS on this problem.  Use the tree-search version of each algorithm.  Show in the tree all of the nodes that would be generated.  Number the nodes in the order in which they are generated (not expanded).  When multiple nodes are added all at once to the fringe (or queue), assume they are added in such a way as to be removed later from the fringe in alphabetical order.  If a goal state is reached, indicate the solution (sequence of states) that was found and whether or not it is optimal.  For IDS, give separate answers for each choice of the depth parameter.

4.  Problem 3.13 in R&N.  Be sure to justify your answer.