CMSC 671

Artificial Intelligence -- Fall 2001

HOMEWORK FOUR
out 10/11/01 due 10/30/01

http://www.cs.umbc.edu/671/fall01/hw/hw4.html



PART I.   Constraint Satisfaction (35 points)

Consider the task of scheduling n final exams in k rooms. For each exam, we are given the list of students that must take the exam. Evry exam has to be assigned to a time slot. More than one exam may be assigned to the same time slot, with two constraints: no student will be required to take two exams at the same time, and at most k exams may be scheduled in a time slot. The task is to produce an assignment of exams to time slots that satisfies these contraints.

(a) Formulate this problem as a constraint-satisfaction problem, to be solved by search through the space of partial exam assignments. Describe the components of the problem, namely:

(b) Suppose that rather than using standard backtracking search to find a solution, we wish to find an optimal solution to this problem, namely, one that minimizes the number of different exam slots. What search technique(s) could you apply?

(c) Describe two different nontrivial admissible heuristic functions for this problem, and explain why they are admissible.

(d) Describe two variable-ordering heuristics that could be applied to select an order in which to instantiate the variables for this problem. This heuristic should be domain-specific, so if you name a "generic" heuristic (such as "minimum width ordering"), give an example of each heuristic for the exam-scheduling domain.

(e) Describe two value-ordering heuristics that could be applied to select the order in which to try the possible instantiations of a particular variable for this problem. Again, if you name a generic heuristic, give an example of each heuristic for this domain.
 

PART II. Game Playing (35 points)

(R&N 5.1) This problem exercises the basic concepts of game-playing using Tic-Tac Toe as an example. Xn is defined to be the number of rows, columns, or diagonals with exactly n Xs and no Os. Similarly, On is the number of rows, columns, and diagnoals with just n Os. 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. We will use a linear evaluation function defined as
Eval(Board) = 3X2 + X - (3O2 + O1)
(a) Show the game tree for Tic-Tac-Toe starting from an empty board down to depth 2 (i.e., one X and one O on the board), taking symmetry into account (i.e., not repeating any positions that are rotations of another position). You should have 3 positions at level 1 and 12 at level 2.

(b) Mark on your tree the evaluations of all the positions at level 2.

(c) Mark on your tree the backed-up values for the positions at levels 1 and 0, using the minimax algorithm, nad use them to choose the best starting move.

(d) CIrcle the nodes at level 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.
 

Part III. Philosophy of AI (30 points)

For questions 2 and 3, you should write 200-500 words in response to each. There are no right or wrong answers, only arguments and opinions that are presented well or poorly. Aim for the former!  Please visit the Writing Center in the library if you think you need help in this area. If you lose points for excessive grammatical errors (or I return your essay ungraded due to lack of readability), I will give you one retry: that is, you may rewrite and resubmit your answer one time.

John Searle's Chinese Room argument essentially boils down to this: a symbol processing system is insufficient to represent "true" intelligence. He uses a "reductio ad absurdum" argument to analogize an AI system to a room containing a non-Chinese-speaking person who is answering questions in Chinese by manipulating symbol tables with no understanding of the content of these tables. (Effectively, the person in the room is running the program, by acting as the CPU, with pieces of paper as the "memory" of the CPU.) Searle claims that it is absurd to believe that the peson -- or the whole system -- "understands" Chinese.

1. Do you agree, disagree, or partially agree with Searle's assertion?

2. If you agree, how would you describe the nature of the difference between the symbol processing system and the brain's mental processes? That is it, what is it about human mental processing that makes it inherently different from physical symbol processing in a computer? If you disagree, how do you think Searle would characterize this essential difference?

3. In general, people are not willing to accept simulations of processes as equivalent to those processes. For example, I could write a simulation of a car's engine, but you wouldn't say that that simulation actually is a car's engine. Supporters of AI seem to be claiming that a simulation of intelligence is intelligent. Do you agree with this position? Why or why not? In particular, why is a simulation of intelligence like (or unlike) a simulation of a car's engine?