CS 440编程代写、Java，Python程序代写

日期：2021-12-02 09:39

CS 440: INTRODUCTION TO ARTIFICIAL INTELLIGENCE FALL 2021

Assignment 3

Adversarial Search - Bayesian Networks

Deadline: December 7th, 11:55pm.

Perfect score: 30.

Assignment Instructions:

Teams: Assignments should be completed by teams of up to three students. You can work on this assignment individually

if you prefer. No additional credit will be given for students that complete an assignment individually. Make sure to write

the name and RUID of every member of your group on your submitted report.

Submission Rules: Submit your reports electronically as a PDF document through Canvas (canvas.rutgers.edu).

Each team of students should submit only a single copy of their solutions and indicate all team members on their

submission. Failure to follow these rules will result in lower grade for this assignment.

Late Submissions: No late submission is allowed. 0 points for late assignments.

Extra Credit for LATEX: You will receive 10% extra credit points if you submit your answers as a typeset PDF (using

LATEX, in which case you should also submit electronically your source code). There will be a 5% bonus for electronically

prepared answers (e.g., on MS Word, etc.) that are not typeset. If you want to submit a handwritten report, scan it and

submit a PDF via Canvas. We will not accept hardcopies. If you choose to submit handwritten answers and we are not able

to read them, you will not be awarded any points for the part of the solution that is unreadable.

Precision: Try to be precise. Have in mind that you are trying to convince a very skeptical reader (and computer scientists

are the worst kind...) that your answers are correct.

Collusion, Plagiarism, etc.: Each team must prepare its solutions independently from other teams, i.e., without using

common notes, code or worksheets with other students or trying to solve problems in collaboration with other teams. You

must indicate any external sources you have used in the preparation of your solution. Do not plagiarize online sources and

in general make sure you do not violate any of the academic standards of the department or the university. Failure to follow

these rules may result in failure in the course.

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 st te in a square box and write its g me 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 func-

tion, 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 ga e. 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 pace 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 ( = 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 follow-

ing 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(B?rg??ry|JohnsC???s = tr?e,M?ryC???s = tr?e)

and show in detail the calculations that take place. Use your book to confirm that your answer

is correct.

b) Count the number of arithmetic operations performed (additions, multiplications, divisions),

and compare it against the number of operations performed by the tree enumeration algo-

rithm.

a) What is the probability that all five of these Boolean variables are simultaneously true?

[Hint: You have to compute the joint pr bability 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,MaryCalls = 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

Parents(Xi) = {Xi?1} for i = 2, . . . , n. What is the complexity of computing P (X1|Xn = true) using enu-

meration? What is the complexity with variable elimination?