CSCI 324 AI Exam #1

Fall 2009

 

Instructions: The usual…this exam is closed book, closed notes, closed neighbor, open mind.  Read through the entire exam before starting on any one question in order to plan the most efficient use of your time to maximize your score.  Be sure to show all your work in an orderly and legible fashion—if I can’t decipher it, then it is wrong.  There are 100 points on the test not counting the bonus questions.  Good luck, and have fun!

 

I.              AI History (20 points)

What…is your name?

 

 

 

 

 

 

 

 

 

 

What…is your quest?

 

 

 

 

 

 

 

 

 

 

What…is your favorite color?
Search (40 points)

 

(10 points) Consider the following game tree.  The evaluation function is from the viewpoint of white, with higher values indicating better moves for white.  It’s black’s turn to move next, at the root of the game tree.

  1. What is the value at the root node of the evaluation function?

 

 

 

  1. Which move should black choose to make and why?

 

 

 

 

 

  1. Which nodes of the game tree don’t need to be evaluated when doing alpha beta pruning?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


(10 points) If you want to find the shortest path from the root to the solution, which search strategy should you use, and why?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(10 points) Describe three problems with the hill climbing search strategy

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(10 points) How does simulated annealing handle the problem of local minima?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

II.            Knowledge Representation (40 points)

(10 points) One way of representing knowledge for an AI program is to use logic.  Fill in the truth table for the following logical operators:

 

False

False

 

 

 

 

 

False

True

 

 

 

 

 

True

False

 

 

 

 

 

True

True

 

 

 

 

 

 

(10 points) What sentences to the following conceptual dependencies represent?

 

 

 

 

 

 

 

 

 

 

 

 

(10 points) Give an example verb for each of the following conceptual dependency primitive acts.

  1. INGEST

 

 

  1. PTRANS

 

 

  1. ATTEND

 

 

  1. ATRANS

 

 

  1. MBUILD

 

 

(5 points) Rewrite the following logical statement to say the same thing using the existential quantifier instead of the universal quantifier.

 

 

 

(5 points) What knowledge does the first order logic expression above encode?

 

 

 

 

III.            Bonus (10 points)  You all are sudoku experts now, so here is one to have fun with after you finish the test.  Do NOT waste time on this until you finish the rest of the test!  (You just KNEW I was going to give you this, didn’t you? J)

 

9

 

6

 

 

7

8

1

 

1

 

 

 

5

 

 

4

 

 

 

 

1

9

 

3

 

7

 

 

 

 

 

4

 

8

1

 

 

3

6

 

8

5

 

 

5

4

 

9

 

 

 

 

 

6

 

5

 

4

1

 

 

 

 

9

 

 

8

 

 

 

6

 

8

7

3

 

 

1

 

2