CMSC 421

Artificial Intelligence -- Fall 2005

HOMEWORK TWO
due 10/13/05

1.  Constraint Satisfaction (25 pts.)

In this question, you will be solving a map-coloring problem.  In this domain, each of the regions on a map must be colored either black, gray, or red.  The regions
must be colored in such a way that no adjacent regions are the same color.  Two regions are considered to be adjacent if they touch along an edge.  (Two regions that touch only at a corner are not adjacent.)  Here is the map that you'll be using for all of the questions in this section:

<MAP>

a. Backtracking search (10 pts)

Suppose we decide to use simple backtracking search to find a solution to this constraint satisfaction problem.  The variable ordering heuristic we use is simply to instantiate the variables in numbered order.  The value ordering heuristic is to consider the values in the order black, gray, red.  You can use any reasonable shorthand to indicate the instantiations (e.g., "1=B" can mean region 1 is instantiated to the color black).

(i) Show the complete search tree, circling the solution node, if one is found.
(ii) Show the final coloring, if one is found, on the map above or on a copy of the map.
(iii) How many variable instantiations (search steps) are tried by this search method?

b. Forward checking (10 pts)

Now suppose we use forward checking to eliminate illegal values from the domains of uninstantiated variables.  (Recall that in forward checking, only the constraints immediately connected to instantiated variables are checked.)  Furthermore, suppose we use a variable ordering heuristic that chooses the variable with the fewest legal instantiations remaining to instantiate next.  If more than one such variable exists, the one earlier in the numbered order is selected.  The same value ordering heuristic is used as in backtracking search (i.e., consider first black, then gray, then red).

(i) Show the complete search tree for forward checking search.  At each node, show the remaining legal values for the uninstantiated variables.  For example, at the first node below the root, only region 1 will be colored, so you should indicate the legal values for variables 2, 3, 4, and 5.  Continue until your search finds a solution or fails. 
(ii) Show the final coloring, if one is found, on a copy of the map above.
(iii) How many variable instantiations are tried by this search method?

c. Solution spaces (5 pts)

(i) How large is the search space for this problem?  That is, how many different colorings, legal or illegal, are there for the blank map shown above?
(ii) For this map, how many different solutions (legal colorings) are there?

2.  Game Playing (15 pts)

Recall the game of Nim that we played in class. Initially, there are k piles, each containing nk sticks.  Two players alternate turns, and at each turn the current player removes any positive number of sticks from one of the piles.  At least one stick must be removed during a turn. The last player to remove a stick loses.  We will represent a state in this game as a k+1-tuple:
[s1 ... sk p],
where si is in the interval [0,nk], and represents the number of sticks remaining in pile i; and p is either A (MAX) or B (MIN), representing which player's move is next.

For those problem, you will be considering Nim211, a variation of Nim with three piles, one containing two sticks, and the others each containing one stick.  Player A goes first, so the initial state is [211A].

a. Game Tree (10 points)

Draw the complete game tree for Nim211.  The left-to-right order of actions taken should always be:  remove 1 stick from pile 1, remove 2 sticks from pile 1, remove 1 stick from pile 2,  remove 1 stick from pile 3.  (Obviously you should only have branches for actions that are legal in a particular state.)  We will ignore the issue of repeated states for this problem, so it's OK if a state appears in more than one place in your tree.

b. Minimax and Alpha-Beta (5 points)

(i) Mark the terminal nodes in the game tree you drew for Question II.1 with their utility values, using +1 to indicate a win for A (MAX), and -1 to indicate a win for B
(MIN). 
(ii) Annotate each of the nodes in the tree with its backed-up minimax value. 
(iii) Circle the nodes that would be pruned by alpha-beta pruning using depth-first (left-to-right) search. (You should assume that the alpha values are initialized to -1, rather than -infinity, and that the beta values are initialized to +1, rather than +infinity.

 

3. Propositional Logic - Models (9 points)
Russell and Norvig, question 7.5, p. 237

4. Propositional Logic - Validity (16 points)
Russell and Norvig, question 7.8, p. 237

5. Proposition Logic - Resolution (30 points)
Russell and Norvig, question 7.9, p. 238
Write as a propositional knowledgebase, convert to clausal form and use resolution refutation.

5. First Order Logic - Representation (25 points)
Russell and Norvig, question 8.6, p. 269





Web Accessibility