Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Primary Examination, Semester 1, 2016

Artificial Intelligence

COMPSCI 3007, 7059

Problem solving by searching

Question 1

The following is a map of a country with several cities connected by high- ways. The numbers attached to the lines connecting any two cities denote the length of the connecting highways.

Boston

Portland

 

140

San

Francisco

Los 

Angeles

Figure 1: Map of a country.

(a) We aim to nd a path from Portland to Boston. Draw the search tree

that solves this problem based on Uniform Cost Search (UCS). Indicate clearly the path cost at each node. Remember to avoid repeated states.

(b) In the context of pathnding, dene the start distance of a given state.

(c) Copy the map in Figure 1 to your answer booklet.  Then, using Port- land as the start state, calculate the start distances of all the cities, and annotate the start distances clearly on the map.

(d) Given the start distances of all the states, how would you nd the desired shortest path?

(e) Changes have occurred to the map in Figure 1. The new map is shown

in Figure 2, where changes are highlighted in red. With reference to

the start distances you have calculated in part (c) above, which states are now locally inconsistent? Show your workings clearly.

Highway demolished!

Portland

New York

Distance

updated

110

140

Pheonix

Figure 2: New map with changes highlighted in red.

Game playing I

Question 2

(a) What does it mean by perfect information in the context of two-person

adversarial games?

(b) When applying the minimax algorithm on the game of checkers, what

game rule must be imposed to ensure that the game tree is nite?

(c) The following gure shows a game tree of up to three moves. The rst move belongs to Max.

Max

Min

Max

9  3   1  6  3  9  7  6  4  2  2  5

Figure 3: Game tree.

Copy the game tree in Figure 3 into your answer booklet, then search the tree using alpha-beta pruning. In particular,

i. Write clearly the minimax value at the root node; and

ii. Circle clearly the branches that are pruned (i.e., branches that do not need to be visited).

(d) The utility values in the game tree in Figure 3 are to be updated ac- cording to a function f (u), where u is the old utility value.

i. Under which of the following 5 update functions f, will lead to the same branches being pruned by alpha-beta pruning?

1.  f (u) = 2u2 + 3

2.  f (u) = (u 3)(u 7)

3.  f (u) = 1/u2

4.  f (u) = 3 ln(u) + tan(5π/4)

5.  f (u) = min(u3 , cos(u))

ii. Justify your answer above.

(e) If you are allowed to reorder the leaf nodes in the original game tree

in Figure 3 before alpha-beta pruning is conducted,

i. How would you reorder the leaf nodes so as to increase the num- ber of branches that can be pruned?

ii. Draw the game tree with your suggested ordering in part i above, and clearly circle the branches that are pruned.

Game playing II

Question 3

Three Men’s Morris is a played on a 3x3 board.  Each of the two players is allowed three game pieces. The objective is to place the three pieces on a straight line (horizontally or vertically) on the board.  The game begins with a blank board, and the players take turns to place the pieces one-by- one on the board. If the game has not ended by then, the players take turns to move the pieces until one of them wins. Each piece can be moved hori- zontally or vertically (but not diagonally) to an adjacent empty location.

The left diagram below shows an example board state, where the move belongs to Max.  If Max moves the leftmost X piece up, it will lead to the board state in the right diagram, which corresponds to an end state.

X

X

X

 

O

O

 

 

O

(a) What is the branching factor of Three Mens Morris?

(b)  Starting from the board state below, where the move belongs to Max,

draw the game tree up to two plies (one move for each player).

 

X

O

X

O

X

 

 

O

(c) For each of the leaf nodes in the partial game tree that you have drawn in part (b) above, evaluate its utility value according to the function

Longest X 一 Longest O

where “Longest X” is the longest vertical or horizontal sequence of X in the board state, and similarly for Longest O” . Annotate the calculated utility values in the game tree clearly.

(d) Based on the game tree that you have drawn in part (b) and the eval- uation value calculated in part (c), what is the best move to make at the board state in part (b) according to the minimax principle?

Learning

Question 4

(a) In the context of learning systems, what is the principle of Occams

Razor?

(b) The following shows a perceptron unit with two inputs.

- 1    w0

x1    w1    

 

x2        w2

● Write an expression for the output as a function of the other quan- tities in the unit.

● Explain why the perceptron can only solve linearly separable prob- lems.

(c) Figure 4 in Page 8 shows a set of points on the plane.

i. Construct a kd-tree for this set of points, using the split rule x ≤ splitval or y ≤ splitval.  Draw your kd-tree in the following for- mat, and remember to indicate clearly the split rule at each node.

 

Hint: Each leaf node in your kd-tree should correspond to a point in Figure 4.

ii. We wish to nd the nearest neighbour of query point (5,81) using the kd-tree search algorithm. Which are the points in Figure 4 that need to be compared with the query point?  List the coordinates of those points here.

6

Figure 4: A set of points on the plane.

(d) The following is a set of observations of 10 prominent computer scien- tists: whether they have a Maths degree, whether they have won the Turing Award, whether they drive a BMW, and the number of papers they publish per year (20, 30 or 40).

Scientist

Maths

Turing

BMW

Papers

s1

s2

s3

s4

s5

s6

s7

s8

s9

s10

N

N

N

Y

Y

Y

N

N

Y

Y

N

N

N

N

N

Y

Y

Y

Y

Y

Y

N

N

N

N

Y

Y

N

Y

Y

20

20

20

30

30

40

40

40

30

30

We aim to build a decision tree that can predict whether an early ca- reer computer scientist will win a Turing Award in his/her lifetime, based on the other attributes.   To answer the following questions, these numbers will be useful:  log2 0.1  =  一3.32,  log2 0.2  =  一2.32, log2 0.3 = 一1.73, log2 0.4 = 一1.32, log2 0.6 = 一0.73, log2 0.8 = 一0.32.

i. What is the information content at the root node?

ii. Calculate the information gain of attributes Math and BMW at the root node.

iii. Between Math and BMW, which is the better attribute to use at the root node?

Probabilistic reasoning

Question 5

(a) Why is it necessary to consider approximate inference methods?

(b) In the context of probabilistic reasoning over time, what does it mean

by the rst order Markov assumption?

(c) The following is a Bayesian network of 13 Boolean variables.

 

K

 M

C

H

D

What is the number of independent probability values required to fully define the Bayesian network?

(d) This following description is adapted from Charniak, 1991:

I share a house with my brother.  When I go home, I want to know if anyone is home before I go in.  From past experience, when my brother leaves the house, with probability 0.3 he turns on the outside light. When he is at home, sometimes he still turns the outside light on since he is expecting guests.  When nobody is home, our dog is always left outside.  When my brother is home, the dog is never left outside, unless if it is suffering from bowel-troubles, in which case it is left outside with probability 0.7.  If the dog is outside, I will hear it barking 80% of the time. Sometimes, when our dog is not outside, with probability 0.3 I still hear barking.  My brother is not at home 60% of the time when I go home, and the dog has bowel-troubles with probability 0.3 at any day. My brother expects guests 60% of the time when he is at home.

The variables in the above system are represented by the following symbols:

● H: my brother is at home.

● L: the outside light is on.

● D: the dog is outside.

● B: the dog has bowel-troubles.

● K: I can hear barking.

i. Draw the Bayesian network corresponding to the above descrip- tion. Remember to define the relevant CPTs.

ii. What is the global semantic (i.e., joint distribution of all the vari- ables) encoded by the Bayesian network?

iii. If I can hear barking and can see that the outside light is on when I get home, what is the probability that nobody is at home?

(e) A computer science student eats one of three types of food for dinner: salad, pasta, or burger - in decreasing level of healthiness. What the student will eat today depends on what he had yesterday. Specifically, there is a 10% chance that the student will have the same thing as yesterday.   If the student decides to have something different than yesterday, he will choose the healthier option twice as likely as the less healthy one. At any given night, the trash can of the student will consist of the container for his dinner: either a plastic box or a tin foil wrapper.  It is known that, in 7 out of 10 times, salad and pasta are sold in plastic boxes. 80% of the time, burgers are wrapped in tin foil.

i. The eating habit above can be summarised by a HMM. Define the state transition matrix T if this HMM.

ii. The mother of the student wishes to monitor what he has been eating, without asking him directly. She made a record of the type of container in his trash can for several days.

day

1

2

3

4

5

container

box

foil

foil

box

box

Given the observations above, derive the probability distribution of the type of food F consumed by the student on

● day 1; and

● day 2.

Leave the probability distributions as numerical expressions, and without solving for any normalising constants.  Assume the stu- dent was equally likely to consume the food types on day 0.