## CS4341 Introduction to Artificial Intelligence. C2000 Exam 1 - February 4, 2000

### Prof. Carolina RuizDepartment of Computer ScienceWorcester Polytechnic Institute

#### Instructions

• Show your work
• Justify your answers
• Use the space provided to write your answers
• Write your name on each page
• Ask in case of doubt

### NAME: Weiyang Lin _________________________________________

#### Problem I. Search (40 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. Assume also that the ESTIMATED distances to the goal are given by the following table:

 Node: S B C D E F G Estimated Distance to G: 6 1 3 2 5 4 0

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. As an illustration, the solution for Depth 1st search is provided below.

1. Depth 1st Search

List: [S, B, D, E, C, F, G]

2. (5 points) Breadth 1st Search

List: [S, B, C, D, E, F, G]

3. (5 points) Depth-limited Search (depth-limit = 2)

List: [S, B, C]
An alternative answer would be [S, B, D, E, C, F, G] if you use the convention that depth-limited search expands nodes that are in the "depth-limit level".

4. (5 points) Iterative Deepening Search

List for depth-limit = 0: []

List for depth-limit = 1: [S]

List for depth-limit = 2: [S, B, C]

List for depth-limit = 3: [S, B, D, E, C, F, G]

An alternative answer would be the one below if you use the convention that depth-limited search expands nodes that are in the "depth-limit level".

List for depth-limit = 0: [S]

List for depth-limit = 1: [S, B, C]

List for depth-limit = 2: [S, B, D, E, C, F, G]

List for depth-limit = 3: [S, B, D, E, C, F, G]

5. (5 points) Branch-and-Bound (= Uniform Cost Search)

List: [S, B, C, E, F, D, G]

6. (5 points) Greedy Search (= Best 1st Search)

List: [S, B, D, C, G]

7. (5 points) A*

List: [S, B, C, G]

8. (5 points) Hill-climbing

List:

• [S, B, D] <--- without backtracking
• [S, B, D, E, C, G] <--- with backtracking

9. (5 points) Beam Search (m = 2)

List: [S, B, C, D, G]

### NAME: Kannan Gangadharan __________________________________

#### Problem II. Game Playing (20 points + 10 EXTRA points)

Suppose you and a friend of yours are playing a board game. It is your turn to move, and the tree below represents your situation. The values of the evaluation function at the leaf nodes are shown in the tree. Note that in this tree not all leaf nodes are at the same level.

1. (20 points) Use the minimax procedure to select your next move. Show your work on the tree below. You select the second child of the root node as your next move since that child produces the highest gain.

2. (10 EXTRA points) Use the minimax procedure TOGETHER WITH ALPHA-BETA PRUNING to select your next move. Mark with an "X" the nodes that don't need to be evaluated. Show your work on the tree below and explain your answer. Nodes marked with an "X" are not evaluated when alpha-beta pruning is used. None of the nodes in the subtree rooted at the node marked with an "X" in the third level of the tree are evaluated.

### NAME: Weiyang Lin _________________________________________

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

Consider the following set of rules that describe when a person can vote in a presidential election.

• R1: IF ?x was born in the US THEN ?x is an American

• R2: IF ?x received US citizenship THEN ?x is an American

• R3: IF ?x's age >= 18 THEN ?x is an adult

• R4: IF ?x is American AND ?x is an adult THEN ?x can vote

Assume that the operator ">=" (greater than or equal) is a basic operator implemented in the inference engine.
The working memory contains the following assertions:

• A1: Bill's age is 16.

• A2: Sue received US citizenship.

• A3: Bill was born in the US.

• A4: Sue's age is 20.
Solve the following problems. Show your work.

1. (10 points) Use backward chaining to determine whether or not Bill can vote. 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.
```
Bill can vote
| (Using R4)
|
Bill is an American
/ (Using R1)      \ (Using R2)
/		        \
Bill was born in the US          Bill receives US citizenship
| (succeeds!)
| WM <- {Bill is an American.}		Fails!
Bill is an adult
| (Using R3)
|
Bill's age >= 18

Fails!

So, Bill cannot vote!

```

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 trees showing the steps followed by forward chaining and show when and how the working memory is updated during the process.
```  Using R1
|	?x was born in the US
|
Bill was born in the US

Succeeds!
WM <- { Bill is an American.}

Using R2
|	?x received US citizenship
|
Sue received US citizenship

Succeeds!
WM <- { Sue is an American.}

Using R3
|	?x's age >= 18
|
Sue's age >= 18

Succeeds!
WM <- { Sue is an adult.}

Using R4
/\       ?x is an American
/	   \
/	      \
Bill is an American.           Sue is an American
|  ?x is an adult		     |  ?x is an adult
|				     |
Bill is an adult	            Sue is an Adult

Fails!			Succeeds!
WM <- { Sue can vote.}

```

### NAME: Kannan Gangadharan __________________________________

#### Problem IV. Frame Systems (20 points)

Consider the following hierarchy of frames.
```                   COMPUTER USERS
/           |
/            |
ako/             | ako
/              |
/               |
UNIX USERS             PC USERS           MICROSOFT
CUSTOMERS
\           /        \           /
\         /          \         /
ako\       /ako      ako\       /ako
\     /              \     /
\   /                \   /
LINUX USERS            WINDOWS98
USERS
\           /
\         /
is-a \       /is-a
\     /
\   /
AMY
```

1. (15 points) Give the class-precedence list for Amy that would be obtained by applying the topological-sorting algorithm to the previous graph. (You don't need to show the steps of the topological sorting algorithm.)

 Node Fish-hook pairs Amy Amy-Linux Users, Linux Users-Windows98 Users Linux Users Linux Users-Unix Users, Unix Users-PC Users Windows98 Users Windows98 Users-PC Users, PC Users-Microsoft Customers Unix Users Unix Users-Computer Users PC Users PC Users-Computer Users

Class Precedence list :

Amy
Linux Users
Unix Users                                -  Use C
Windows98 Users
PC Users                                  - Use C++
Computer Users                        - Use Fortran
Microsoft Customers

2. (5 points) Suppose that each of the classes Unix users, PC users and Computer Users contains a favorite programming language slot. The default value for this slot is:
• Fortran, for the Computer Users class.
• C, for the Unix Users class.
• C++, for the PC Users class.

What is the value obtained for Amy's favorite programming language according to the class-precedence list you constructed above? Explain you answer.

Amy's favorite programming language is C