Reading

Doing

1. Consider the 8-puzzle, with the following start and goal states:
   Start:

   2	8	3
   1	6	4
   7		5

   Goal:

   1	2	3
   8		4
   7	6	5

   Solve this problem with depth-first uninformed search, following the Tree-Search function on page 77 (or you can use Depth-Limited-Search on p. 88). For this problem, we will modify the meaning of "the resulting nodes" in Tree-Search (or, the functioning of problem.Actions in Fig. 3.17) so that a state is never generated that is the same as its "grandparent;" that is, we never move the space back to where it was the previous move. (Thus we are turning Tree-Search into a very limited version of Graph-Search, without using an explored set.) Use a depth bound of 5: if a state is 5 moves from the Start then it has no successors. As suggested on page 71, there are at most four moves (of the blank): Left, Up, Right, and Down and they are always, for this homework, put on to frontier so that they are removed in that order. (For instance, the start state has three successors and the one with blank in the lower left corner should be removed from frontier first.)
   • Show the search tree resulting from solving this problem. Next to each node in the search tree, write a number indicating the order in which it was removed from frontier.
   • Show the value of frontier right after the goal is recognized and before the algorithm returns.
   Note that this problem has been set up to bring home the point that with depth-first search the frontier never grows very large.

2. Consider again problem #4 from homework 2. You now also have a heuristic function h, defined as follows: h(H) = 10, h(L) = 30, h(M) = 2, h(P) = 30, h(S) = 14, h(T) = 28, h(V) = 23, h(W) = 4, h(Z) = 0. Show the search tree resulting from solving the problem using A* search. Next to each node in A*'s search tree, to its upper right, write a number indicating the order in which it was removed from frontier. Also write to the lower right of each node its f value.

3. Do Exercise 3.23 on page 118. "Trace" and "show the sequence" mean draw the same sort of tree that you did for problem 2 of this homework.

4. Consider the problem of scheduling five tasks T1, T2, T3, T4, and T5, each of which takes one hour to complete. The tasks may start at 1:00, 2:00 or 3:00. Any number of tasks may be executed simultaneously, subject to the following constraints:
   1. T1 must start after T3;
   2. T3 must start before T4;
   3. T3 must start after T5;
   4. T2 cannot execute at the same time as T1;
   5. T2 cannot execute at the same time as T4;
   6. T4 cannot start at 2:00.
   Try to solve this problem using the hill climbing algorithm in Figure 4.2 on page 122. In the initial state, each task is scheduled to start at 2:00. The objective function is the number of constraints that are satisfied. (In the initial state, the objective function evaluates to 0, since none of the six constraints are satisfied.) The successors of a state are those states created by moving one task forward or backward by an hour (only 1:00, 2:00, and 3:00 are possible starting times). The initial state has 10 successors (all other states have fewer than 10 successors). Draw a search tree whose root is the initial state. The child of each node in the tree is the node's state's possible successors. Next to each node write its objective function value. When the algorithm stops, has it reached a global maximum?

5. Consider a game in which each player always has two possible moves. We will look ahead four plies, so that mid-game the game tree has 16 (= 2⁴) leaves. Game positions at the bottom level are assigned an integer value by an evaluation function. Draw the game tree, assigning values of your choice to the leaves, so as to maximize the number of nodes that would be pruned when using alpha beta. Show the backed up values for each interior node, and circle (or otherwise indicate) the nodes pruned by alpha beta.

6. Draw a decision tree for the problem of deciding whether to move forward at a road intersection, given that the light has just turned green and you are driving a car. (This is problem 18.3 on p. 676 of the book's second edition.)

7. What is the information content of finding out whether the bottom card in a well-shuffled, regular 52 card deck of cards is an Ace, a Face card (King, Queen, or Jack), or a number card (2 through 10)?

Details

• upload a Word (.doc or .docx) or a PDF file to the EEE dropbox "CS 171 - hw 4" before 11:55pm (based on the EEE server's clock) on Friday, Feb. 1; or
• hand in a printed or neatly hand-written printed copy of your assignment at the start of lecture, 12:00 noon sharp, on Friday, Feb. 1 -- make sure your name is clearly written at the top of the first page, and multiple pages are stapled together.

Late homeworks will be accepted through midnight at the end of Sunday, Feb. 2, with a 50% penalty. (No later submission will be accepted.)