## CS4341 Introduction to Artificial Intelligence. B-2003 SOLUTIONS Exam 1 - November 24, 2003

### By Prof. Carolina Ruiz, Matt Jarvis, and Peter Mardziel Department of Computer ScienceWorcester Polytechnic Institute

#### Instructions

• Ask in case of doubt

#### Problem I. Search (20 points)

Suppose that you need to find a path between S and G in the following graph. The number attached to each edge in the graph represents the COST of traversing the edge. The number inside each node represents a heuristic under-estimate of the distance of the node to the goal G.

For EACH of the following search methods list the nodes in the order in which they are EXPANDED by the search method while looking for a solution. Also, show the search tree (or show the sequence of queue states instead if you prefer) as it is constructed by the search method. When everything else is equal, order the nodes in alphabetical order.

1. (9 points) A*

• List of expanded nodes: __S_B_H_A_B_G________________

• Search Tree: (or show the sequence of queue states instead if you prefer)
```A*
Expanded  Queue
S      [13<S>]
B      [10<B,S> 12<A,S>]
H      [11<H,B,S> 12<A,S> 16<E,B,S>]
A      [12<A,S> 12<G,H,B,S> 16<E,B,S> 19<C,H,B,S>]
B      [11<B,A,S> 12<G,H,B,S> 13<C,A,S> 16<E,B,S>]
G      [12<G,H,B,S> 12<H,B,A,S> 13<C,A,S> 16<E,B,S>]
goal reached!

```

2. (8 points) Greedy Search (= Best 1st Search)

• List of expanded nodes: __S_B_E_H_G__________________

• Search Tree: (or show the sequence of queue states instead if you prefer)
```Greedy
Expanded  Queue
S      [13<S>]
B      [6<B,S> 9<A,S>]
E      [2<E,B,S> 4<H,B,S> 9<A,S> 9<A,B,S>]
H      [4<H,B,S> 9<A,S> 9<A,B,S> 10<F,E,B,S>]
G      [0<G,H,B,S> 8<C,H,B,S> 9<A,S> 9<A,B,S> 10<F,E,B,S>]
goal reached!
```

3. (8 points) Hill-climbing

• List of expanded nodes: __S_B_E_F_G___________________

• Search Tree: (or show the sequence of queue states instead if you prefer)
```Hill Climbing
Expanded  Queue
S      [13<S>]
B      [6<B,S> 9<A,S>]
E      [2<E,B,S> 4<H,B,S> 9<A,B,S> 9<A,S>]
F      [10<F,E,B,S> 4<H,B,S> 9<A,B,S> 9<A,S>]
G      [0<G,F,E,B,S> 4<H,B,S> 9<A,B,S> 9<A,S>]
goal reached!

```

#### Problem II. Search (15 points)

In this problem, you are asked to state an exhaustive list of conditions under which one would prefer a search strategy over another. An illustration is provided below.
1. (0 points) Prefer breadth-first search over depth-1st search
```
A shallow solution (path from initial state to goal state) is preferred.
or the search tree may contain large or possibly infinite branches
or if abundant  memory space to store  the search tree (or the queue)
is  available.

```
2. (5 points) Prefer A* over branch-and-bound
```
A good heuristic that underestimates the distance to the goal is available.
Runtime matters.
Space is a concern.

```
3. (5 points) Prefer hill-climbing over greedy search
```
Very little memory is available to store the search tree.
Backtracking isn't necessary to find the solution.

```
4. (5 points) Prefer iterative deepening over depth-first search
```
A shallow solution is preferred.
The search tree may contain large or infinite branches.
There is a time limit on the search.

```

#### Problem III. Game Playing (20 points)

Assume that your are playing 2 dimensional tic-tac-toe on a 3x3 board. You are the "X" player, it is your turn to move, and the current board configuration is depicted below:
```              |   |
------------
X | O |
------------
X | O  | O

```
Assume also that the utility function is given by:
```                                              /
|  10,  if "X" wins
utility of a terminal board configuration = |   0,  if it is a draw
| -10,  if "O" wins
\
```

Use the minimax procedure TOGETHER WITH ALPHA-BETA PRUNING to select your next move. Mark with the word "PRUNE" the nodes/branches that don't need to be evaluated (and don't expand those unnecessary branches) . Show your work on an adversarial search tree and explain your answer.

Solutions by Peter Mardziel

• red boards are maximizers
• blue boards are minimizers

 10 x o x o o
 10 x x o x o o
 -10 x x o x o o
 -10 o x x o x o o
 PRUNE x o x o x o o
 PRUNE x x o o x o o
 -10 x x o x o o
 -10 o x x o x o o
 PRUNE o x x o x o o
 PRUNE x x o o x o o
 -10 x o x x o o
 -10 o x o x x o o
 PRUNE o x o x x o o
 PRUNE o x o x x o o

#### Problem IV. Rule-Based Systems (20 points)

Consider the following set of rules for identifying animals.

• R1: IF ?x gives milk THEN ?x is a mammal

• R2: IF ?x has feathers AND ?x flies AND ?x lays eggs THEN ?x is a bird

• R3: IF ?x eats meat AND ?x is a mammal THEN ?x is a carnivore

• R4: IF ?x has black stripes AND ?x is a carnivore THEN ?x is a tiger
The working memory contains the following assertions:
• A1: hobbes has black stripes
• A2: hobbes eats meat
• A3: tweety has feathers
• A4: hobbes gives milk
• A5: tweety flies
Solve the following problems. Show your work.

1. (10 points) Use backward chaining to determine whether or not hobbes is a tiger. Construct a tree showing the steps followed by backward chaining and show when and how the working memory is updated during the depth 1st search.
```
BACKWARD CHAINING:

hobbes is a tiger                ?x is a tiger
|
|  R4
|
hobbes has black stripes         ?x has black stripes
|
|  succeeds due to A1
|
hobbes is a carnivore            ?x is a carnivore
|
|  R3
|
hobbes eats meat                 ?x eats meat
|
|  succeeds due to A2
|
hobbes is a mammal               ?x is a mammal
|
|  R1
|
hobbes gives milk                ?x gives milk

succeeds due to A4

hence the working memory is updated with:
A6: hobbes is a mammal
A7: hobbes is a carnivore
A8: hobbes is a tiger

```

2. (10 points) Use forward chaining to derive ALL assertions that are derivable from this knowledge base (that is, from the set of rules together with the assertions in the working memory). Construct all trees showing the steps followed by forward chaining and show when and how the working memory is updated during the process.
```
FORWARD CHAINING:

R1:  hobbes gives milk                      ?x gives milk

succeeds due to A4

WM := WM + {A6: hobbes is a mammal}    ?x is a mammal

R2:  tweety has feathers                    ?x has feathers
|
|  succeeds due to A3
|
tweety flies                           ?x flies
|
|  succeeds due to A5
|
tweety lays eggs                       ?x lays eggs

fails

hence rule R2 is not triggered.

R3:   hobbes eats meat                      ?x eats meat
|
|  succeeds due to A2
|
hobbes is a mammal                    ?x is a mammal

succeeds due to A6

WM:= WM + {A7: hobbes is a carnivore} ?x is a carnivore

R4:   hobbes has black stripes              ?x has black stripes
|
|  succeeds due to A1
|
hobbes is a carnivore                 ?x is a carnivore

succeeds due to A7

WM:= WM + {A8: hobbes is a tiger}     ?x is a tiger

Applying again R1, R2, R3, R4 does not yield any new assertions
and so the forward chaining process stops.
```

#### Problem V. Logic-Based Systems (20 points)

Consider the following set of axioms:
• Everyone who loves someone who loves them back is happy
• A1: for-all x, for-all y, [loves(x,y) & loves(y,x) = > happy(x)]

• Mary loves everyone.
• A2: for-all z, [loves(mary,z)]

• There is someone who loves Mary.
• A3: there-is w, [loves(w,mary)]

• Conclusion: Mary is happy.
• C: happy(mary)

here:

• constants symbols: mary.
• relation symbols: loves, happy.
• variable symbols: w, x, y, z.

Prove the conclusion from the axioms by refutation using resolution:

• (10 points) Translate the axioms and the negation of the conclusion into clausal form. Show each step of the translation (remember that the order in which you apply the steps is crucial).

1. A1: !loves(x,y) || !loves(y,x) || happy(x)
note that p = > q is equivalent to !p || q and that !(r & s) is equivalent to !r || !s

2. A2: loves(mary,z)

3. A3: loves(a,mary), where a is a new constant symbol

4. !C: ! happy(mary)

```

```

• (10 points) Apply resolution (state explicitly what clauses are resolved and which substitutions are made) until the empty clause is found.
```   !C: ! happy(mary)
A1:  !loves(x,y) || !loves(y,x) || happy(x)
__________________________________________________  with x=mary
A4:  !loves(mary,y) || !loves(y,mary)
A2: loves(mary,z)
__________________________________________________  with z=y
A5:  !loves(y,mary)
A3: loves(a,mary)
__________________________________________________  with y=a
empty clause

Since assuming that "mary is not happy" yields a contradiction in the presence of A1, A2, A3,
then the statement "mary is happy" is a logical consequence of A1, A2, and A3.
```