## 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).