## Description

Problem 1 (10 points) : Consider the two-player game described in Figure 1.

1. Draw the complete game tree, using the following conventions:

2. Write each state as (sA, sB) where sA and sB denote the token locations.

3. Put each terminal state in a square box and write its game value in a circle.

4. Put loop states (states that already appear on the path to the root) in double square boxes. Since it is not clear how to

assign values to loop states, annotate each with a “?” in a circle.

5. Now mark each node with its backed-up minimax value (also in circle). Explain how you handled the “?” values and

why.

(b) Explain briefly how A

∗

ε

can use the second heuristic function hN to reduce the time of the

search. What tradeoff is being made in choosing ε? [5 points]

(15 points for graduates – 20 points for undergraduates)

Problem 4: Consider the two-player game described in Figure 1.

a. Draw the complete game tree, using the following conventions: [3/4 points]

• Write each state as (sA, sB) where sA and sB denote the token locations.

• Put each terminal state in a square box and write its game value in a circle.

• Put loop states (states that already appear on the path to the root) in double square

boxes. Since it is not clear how to assign values to loop states, annotate each with a “?”

in a circle.

b. Now mark each node with its backed-up minimax value (also in circle). Explain how you

handled the “?” values and why. [3/4 points]

c. Explain why the standard minimax algorithm would fail on this game tree and briefly sketch

how you might fix it, drawing on your answer to (b). Does your modified algorithm give

optimal decisions for all games with loops? [3/4 points]

d. This 4-square game can be generalized to n squares for any n > 2. Prove that A wins if n is

even and loses if n is odd. [6/8 points]

Figure 1: The start position of a simple game. Player A moves first. The two players take turns

moving, and each player must move his token to an open adjacent space in either direction. If

the opponent occupies an adjacent space, than a player may jump over the opponent to the next

open space if any. (For example, if A is on 3 and B is on 2, then A may move back to 1.) The game

ends when one player reaches the opposite end of the board. If player A reaches space 4 first,

then the value of the game to A is +1; if player B reaches space 1 first, then the value of the game

to A is -1.

(15 points for graduates – 20 points for undergraduates)

Problem 5: Consider the problem of constructing (not solving) crossword puzzles: fitting words

into a rectangular grid. The grid, which is given as part of the problem, specifies which squares

are blank and which are shaded. Assume that a list of words (i.e., a dictionary) is provided and

that the task is to fill in the blank squares using any subset of the list. Formulate the problem in

two ways: [Hint: There might be multiple correct answers here.].

a) As a general search problem. Choose an appropriate algorithm, and specify a heuristic function, if you think is needed. Is it better to fill in blanks one letter or one word at a time?

b) As a constraint satisfaction problem. Should the variables be words or letters?

Which formulation do you think will be better? Why?

(10 points)

Figure 1: The start position of a simple game. Player A moves first. The two players take turns moving, and each player

must move his token to an open adjacent space in either direction. If the opponent occupies an adjacent space, than a player

may jump over the opponent to the next open space if any. (For example, if A is on 3 and B is on 2, then A may move back

to 1.) The game ends when one player reaches the opposite end of the board. If player A reaches space 4 first, then the

value of the game to A is +1; if player B reaches space 1 first, then the value of the game to A is -1.

Problem 2 (5 points): Consider the following Bayesian network, where variables A through E are all Boolean valued.

Note: there is a typo in the image, it should be P(A = true) = 0.2 instead of P(D = true) = 0.2 .

c) What is the probability that A is false given that the four other variables are all known to be

true?

[Hint: Try to use the definition of the conditional probability and the structure of the network.

For probabilities that can not be computed directly from the network, remember the following normalization trick: if P() = α · ƒ () and P(¬) = α · ƒ (¬), then you can compute the

normalization factor as α =

1.0

ƒ ()+ƒ (¬)

, since P() + P(¬) = 1.0.]

(15 points)

Question 3: For this problem, check the Variable Elimination algorithm in your book. Also consider

the Bayesian network from the “burglary” example.

a) Apply variable elimination to the query:

P(Brgry|JohnsCstreMryCstre)a) What is the probability that all five of these Boolean variables are simultaneously true?

[Hint: You have to compute the joint probability distribution. The structure of the Bayesian network suggests how

the joint probability distribution is decomposed to the conditional probabilities available.]

b) What is the probability that all five of these Boolean variables are simultaneously false?

[Hint: Answer similarly to above.]

c) What is the probability that A is false given that the four other variables are all known to be true?

Problem 3 (5 points):

a) Calculate P(Burglary|JohnsCalls = true, M aryCalls = true) and show in detail the calculations that take

place. Use your book to confirm that your answer is correct.

b) Suppose a Bayesian network has the from of a chain: a sequence of Boolean variables X1, . . . Xn where

P arents(Xi) = {Xi−1} for i = 2, . . . , n. What is the complexity of computing P(X1|Xn = true) using enumeration? What is the complexity with variable elimination?

.001

P(B)

Alarm

Earthquake

JohnCalls MaryCalls

Burglary

A P(J)

t

f

.90

.05

B

t

t

f

f

E

t

f

t

f

P(A)

.95

.29

.001

.94

.002

P(E)

A P(M)

t

f

.70

.01

Problem 4 (10 points): Suppose you are working for a financial institution and you are asked to implement a fraud detection

system. You plan to use the following information:

• When the card holder is travelling abroad, fraudulent transactions are more likely since tourists are prime targets for

thieves. More precisely, 1% of transactions are fraudulent when the card holder is travelling, where as only 0.4%

of the transactions are fraudulent when she is not travelling. On average, 5% of all transactions happen while the

card holder is travelling. If a transaction is fraudulent, then the likelihood of a foreign purchase increases, unless the

card holder happens to be travelling. More precisely, when the card holder is not travelling, 10% of the fraudulent

transactions are foreign purchases where as only 1% of the legitimate transactions are foreign purchases. On the

other hand, when the card holder is travelling, then 90% of the transactions are foreign purchases regardless of the

legitimacy of the transactions.

• Purchases made over the internet are more likely to be fraudulent. This is especially true for card holders who don’t

own any computer. Currently, 75% of the population owns a computer or smart phone and for those card holders,

1% of their legitimate transactions are done over the internet, however this percentage increases to 2% for fraudulent

transactions. For those who don’t own any computer or smart phone, a mere 0.1% of their legitimate transactions

is done over the internet, but that number increases to 1.1% for fraudulent transactions. Unfortunately, the credit

card company doesn’t know whether a card holder owns a computer or smart phone, however it can usually guess by

verifying whether any of the recent transactions involve the purchase of computer related accessories. In any given

week, 10% of those who own a computer or smart phone purchase (with their credit card) at least one computer

related item as opposed to just 0.1% of those who don’t own any computer or smart phone.

a) Construct a Bayes Network to identify fraudulent transactions.

What to hand in: Show the graph defining the network and the Conditional Probability Tables associated with each

node in the graph. This network should encode the information stated above. Your network should contain exactly

six nodes, corresponding to the following binary random variables:

OC : card holder owns a computer or smart phone.

Fraud : current transaction is fraudulent.

Trav : card holder is currently travelling.

FP : current transaction is a foreign purchase.

IP : current purchase is an internet purchase.

CRP : a computer related purchase was made in the past week.

The arcs defining your Network should accurately capture the probabilistic dependencies between these variables.

b) What is the prior probability (i.e., before we search for previous computer related purchases and before we verify

whether it is a foreign and/or an internet purchase) that the current transaction is a fraud? What is the probability that

the current transaction is a fraud once we have verified that it is a foreign transaction, but not an internet purchase

and that the card holder purchased computer related accessories in the past week?

What to hand in: Indicate the two queries (i.e., P r(variables|evidence)) you used to compute those two probabilities. Show each step of the calculation