Update (none):
Question 1: (Textbook 3E, Question 3.9, copied here
with slight modification):
3.9 The missionaries and cannibals problem is usually stated as follows. Three missionaries and
three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a
way to get everyone to the other side without ever leaving a group of missionaries in one place
outnumbered by the cannibals in that place. This problem is famous in AI because it was the subject
of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).
a. Formulate the problem precisely, making only those distinctions necessary to ensure a valid
solution. Draw a diagram of the complete state space.
b. Design a not-too-trivial admissible heuristic function.
Implement and solve the problem optimally using A* search algorithm.
Is it a good idea to check for repeated states? (Note: implement by hand)
c. Why do you think people have a hard time solving this puzzle,
given that the state space is so simple?
Question 2:
Prove that if h never overestimates by more than c, A* using h returns a solution whose cost
exceeds that of the optimal solution by no more than c.
Question 3: (Textbook 3E, Question 5.9, copied here):
5.9 This problem exercises the basic concepts of game playing, using tic-tac-toe (noughts and
crosses) as an example. We define Xn as the number of rows, columns,
or diagonals with exactly n
X's and no O's. Similarly, On is the number of rows, columns, or diagonals with just n O's. The utility
function assigns +1 to any position with X3 = 1 and -1 to any position with O3 = 1.
All other terminal
positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as
Eval (s) = 3*X2(s) + X1(s) - (3*O2(s)+ O1(s)).
a. Approximately how many possible games of tic-tac-toe are there?
b. Show the whole game tree starting from an empty board down to depth 2
(i.e., one X and
one O on the board), taking symmetry into account.
c. Mark on your tree the evaluations of all the positions at depth 2.
d. Using the minimax algorithm, mark on your tree the backed-up values for the positions at
depths 1 and 0, and use those values to choose the best starting move.
e. Circle the nodes at depth 2 that would not be evaluated if alpha-beta
pruning were applied,
assuming the nodes are generated in the optimal order for alpha-beta pruning.
Question 4:
Solve the cryptarithmetic problem (SEND + MORE = MONEY discussed in the lecture)
by hand, using the strategy of backtracking with
forward checking and the MRV, degree heuristic, and least-constraining-value
heuristics.