Artificial Intelligence: Problem Set 2

Assigned: Feb. 9
Due: Feb. 22

Problem 1

A. Suppose that you are doing game tree evaluation, and you know that the evaluation function always lies between some specified maximum and minimum values. For instance, you know that the evaluation function is always an integer between 1 and 5 or, even more simply, that the evaluation function is always 0 or 1 (i.e. that this is in fact an AND/OR tree). Then it is sometimes possible to do more pruning than just the pruning allowed by the alpha-beta rules. State the new pruning rules and give an example.

B. Let T be an AND/OR tree of height 2 and constant branching factor 3. That is, the root of T is an OR node; it has three children, each of them an AND node; these each have three children, all leaves. Suppose that T is evaluated left to right and no pruning whatever can take place. Give an example of such a tree. Is there only one such example, or more than one?

Problem 2

Consider the following two color problem: We have a map with three countries, X, Y, and Z, where Y borders X and Z. We wish to color these countries red and blue in such a way that no two neigboring countries are given the same color.

We can represent this in a propositional language with six atoms XR meaning "X is red", XB, YR, YB, ZR, and ZB.

A. In the above propositional language, express the constraints (a) that every country is either red or blue; (b) that no two neighboring countries have the same color.

B. Express the fact that X and Z have the same color.

C. Using propositional resolution, prove (B) from (A).