CMSC 471/671 -- Artificial Intelligence
Midterm Exam
October 20, 1998
"MIND, n. A mysterious form of matter secreted by the brain. Its chief activity consists in the endeavor to ascertain its own nature, the futility of the attempt being due to the fact that it has nothing but itself to know itself with. From the Latin mens, a fact unknown to that honest shoe-seller, who, observing that his learned competitor over the way had displayed the motto "Mens conscia recti," emblazoned his own front with the words "Men's, women's and children's conscia recti."
-- Ambrose Bierce (1842-1914), "The Devil's Dictionary", 1911.
This exam is closed book. The points sum to 100. Good luck.
1. Unification in Prolog [10]
For each of the following pairs of Prolog terms, say whether or not the unification would succeed and, if it does, what the most general common instance would be. Assume that the same variable name in two different terms in a given pair represents the same variable.
TERM1 TERM2 Unify? MGI if any
X loves(john,mary).
p(X, q(Y), r(Z)) p(r(a), q(X), r(b))
loves(john, X) loves(Y,Y)
and(father(P1, P2), and(father(X, john),
brother(P1, P3)) brother(john, john))
foo(X) X
[X, Y | Z] [a, b, c, d, e, f, g]
[ ] X
[X, Y] [a, b | Z]
A + B - C '+'(1, '-'(2, 3))
2+3 3+2
2. Prolog mystery predicate [15]
Consider the following mystery predicate:
p([ ],[ ]).
p([A|B], C) :- p(B, D), append(D, [A], C).
where append has the usual definition.
3. Cut in Prolog [15]
Let the predicate
min(N1,N2,Min) be true if Min is the smaller of N1 and N2. Assume all three arguments are integers.Consider the following definition of min/3:
min(N1, N2, N1) :- N1 =< N2, !.
min(N1, N2, N2).
(a) [6] Describe what will happened for each of the following goals:
(b) [9] Write the min/3 predicate without using the cut symbol. Make sure your predicate works whenever the first two arguments are instantiated to integers. The third argument can be either an integer or an uninstantiated variable. That is, the mode would be described as min(+N1,+N2,?N3).
4. Hill-Climbing Search [10]
True. Some problem domains have no local maxima. In such a domain hill-climbing will eventually reach the solution.
(b) [4] What is a main advantage of A* search over hill-climbing search?
A* search is not susceptible to local minima and is, unlike hill-climbing, complete and admissible.
(c) [4] What is a main advantage of hill-climbing search over A* search?
Space efficiency. Hill-climbing stores only the current node on the OPEN list, whereas A* stores all nodes on the current frontier.
5. Game Playing [20]
Consider the following tree for a game
3 7 8 10 8 4 2 7 5
(a) [4] In the figure above, fill in the backed-up values that are computed by the minimax algorithm for the four nodes at depths 0 and 1. The leaf nodes show the values of the evaluation function applied at those nodes.3, 4, and 2 are the values, left-to-right, at the MIN level, and 4 is
the backed-up value at the root.
(b) [8] Now circle the nodes that would not be generated (i.e., would be pruned) by the alpha-beta algorithm assuming children are visited left-to-right.
The rightmost two leaf nodes with values 7 and 5 are pruned.
(c) [8] Reorder the children of the root node and the children of the three nodes at depth 1 so that alpha beta prunes the maximum number of possible nodes. Assume children are visited left-to-right. Do not change any node's parent when you reorder..Again, circle the nodes that would not need to be generated
After reordering the leaf nodes will have values, left-to-right, 10, 4, 8, 3, 7, 8, 2, 7, 5. In this case the 5th, 6th, 8th, and 9th leaf nodes will be pruned.
6. Comparing Search Strategies [10]
Four criteria were defined for comparing search strategies: completeness, optimality (or admissibility) , time complexity, and space complexity. For each of the following statements, specify which of these four criteria best explains why it is true. Note -- each statement should get only one of the four criteria and they can be different.
(a) Iterative-Deepening search is usually preferred over Breadth-First search.
Space complexity
(b) Iterative-Deepening search is usually preferred over Depth-First search.
Completeness (also space complexity, time complexity, optimality)
(c) Alpha-Beta search is usually preferred over Minimax search.
Time complexity
(d) A* search is usually preferred over Greedy search.
Optimality (also completeness)
(e) Algorithm A might be preferred over A* search.
Time complexity (also space complexity)
(f) Bidirectional search is usually preferred over Breadth-First search.
Time complexity (also space complexity)
7. Game Trees [20]
The game of Nim2 is played as follows: Initially, there are two piles, each containing two sticks. Two players alternate turns, and at each turn the current player removes any positive number of sticks from any one pile. At least one stick must be removed during a turn. The player who's turn it is when there are no more sticks to remove wins. Say we represent a state in this game as a triple:
StickInPile1 / SticksInPile2 / Player
where Player is either A or B and indicates which player's move is next. Player A goes first, so the initial state is
2/2/A.(a) [12] Draw the complete game tree for Nim2. Show this as a tree, so states may be repeated.
(b) [6] Assume you are Player A, and a winning state for A is assigned a utility value of +1, and a winning state for B is assigned a utility value of -1. Compute the minimax values for each of the states in the tree shown in your answer in (a). Write the values next to the nodes in your answer in (a).
(c) [2] Note that the complete game tree was used in to compute the minimax values at all nodes based on true utility values at final game positions. What can we therefore conclude about the game of Nim2?