Fall Semester 2001
- The exam consists of ten questions, one algorithm, and one figure,
on three pages.
Be sure that you have all of these items and that they are all legible.
- Read all questions and their instructions thoroughly before you begin.
It is almost always worth your time to plan ahead!
- You have also been given three blank pages. Use these sheets for your
exam answers. Be sure to write your name on each sheet.
- The exam is worth 100 points. Each problem is worth 10 points.
- Keep the exam questions when you are done, for future reference.
- Points will be awarded based on your explicit answers. Partial credit
will be given where possible, so show all of your work.
- The exam lasts seventy-five (75) minutes. It is due at 3:15 PM.
- Suppose that you have been exchanging letters with a pen pal for a
number of years. You've exchanged letters on a variety of subjects,
some in depth, and you feel like you know this person pretty well--at
least as well as you can not ever having met the person. Suddenly,
you are informed that your pen pal is, in fact, a computer system.
Compare and contrast your experience with Turing's "imitation game".
Would your opinion of your pen pal's intelligence change as a result
of the revelation? Why, or why not?
- Describe some of the advantages that an agent which deliberates
in choosing its next action has over an agent that simply responds to
its environment. What are some of the disadvantages of deliberation?
- The "missionaries and cannibals" problem is as follows:
On one bank of a river are three missionaries, three cannibals, and
a boat. They would all like to cross to the other side of the river.
The boat will hold up to two people. But if the cannibals ever
outnumber the missionaries on one side of the river, the missionaries
will be eaten. The missionaries would like to avoid this fate, and
the cannibals are a kind-hearted bunch (if lacking in self-control),
so they agree to develop a plan to get all six men across the river
Using a simple "iconic" representation of states in this problem, show
how our generic search algorithm would explore this search space. For
this problem, assume that the algorithm favors new states in its
exploration. Be sure to go far enough that the algorithm considers at
least one state three moves away from the initial state.
- Before an agent can formulate a solution through search, it must first
formulate the problem. What are the steps of problem formulation?
What are the components of the resulting problem definition?
- Describe at least three ways in which an agent can use knowledge to
improve how--or how well--it does search.
- Discuss the similarities and differences between uniform cost search and
greedy search. Why do we consider these methods "informed" techniques?
- Consider the game tree below, in which a static evaluation function has
been applied to the leaf nodes.
- What value will the minimax algorithm assign to the initial position?
(Be sure to show your intermediate steps!)
- Why could agent not consider states G, H, K, and L and
still the best move?
- What are the four components of a knowledge representation scheme?
Give examples from the domain of predicate logic.
- Translate the following sentences into predicate logic. You may use
either Horn clause form (with implications) or disjunctive form (with
only ors and nots).
- Bill eats peanuts and is alive.
- Sue eats everything that Bill eats.
- Apples are food.
- Chicken is, too.
- John likes all kinds of food.
- Anything anyone eats and isn't killed by is food.
- Given the database from Problem 6, use modus ponens or resolution
to infer that John likes peanuts.
A generic algorithm for systematic search
- the starting situation (the start state)
- a goal to achieve
- a search strategy
- a sequence of actions (called operators)
that transforms the problem's start state into a goal state
- an announcement that no such sequence can be found
- Initialize the set of states to be considered to include the
- Repeat the following:
- If the set of unconsidered states is empty,
then announce failure.
- Choose a state to consider, based on the search
- If the state chosen is the goal state, then return the
sequence of actions that leads to this state.
- Add to the set of unconsidered states all of the states that
can be reached from the current state by doing one action.
Figure for Problem 7
Eugene Wallingford ====
October 12, 2001