Homework

This assignment covers Chapter 5 (Adversarial Search), Chapter 7 (Logical Agents), and 12 (Quantifying Uncertainty) from Russell and Norvig.

1. Games

[10 points]

(a) Consider the following zero-sum game tree. The choices for the maximizing player are shown with triangles that point up, and the choices for the minimizing player are shown with triangles that point down. The bottom nodes represent the terminal utilities.

Figure Description 1: A game tree to calculate minimax. As usual max nodes are triangles, min nodes inverted triangles. Costs are illustrated on the leaves.

(a) [6 points] Give the minimax value of each node, assuming both players act optimally. How the game should be played

(b) [4 points] Show the pruning of nodes from the game tree above through alpha-beta pruning? Explain the reason if no nodes can be pruned. Assume the search goes from left to right; when choosing which child to visit first, choose the left-most unvisited child.

1. Consider the below expectimax tree, where circle nodes are chance nodes, the top node is a min node, and the bottom nodes represent the terminal utilities. [10 points]

Figure Description 2: A game tree to calculate expect minimax. As usual max nodes are triangles, min nodes inverted triangles, and probability nodes are circles. Costs are illustrated on the leaves.

(a) [Calculate the expectimax value of each chance node.

(b) What is the value of the min node? Which action should the min player take (e.g., first, second, or third action represented by a chance node)?

(c) Which nodes can be pruned from the game tree above through alpha-beta pruning? Explain the reason if no nodes can be pruned.

1. [10 points] Broadly describe state description, move generators, terminal tests, utility functions, and evaluation functions for one the game of Monopoly. Cite all the sources that you use for your homework.
2. [20 points] Solve the following exercises from Rusell and Norvig, 4th edition on
4. 4 (2,4,6,7,9) [5 points], 6 (2) [2 points]
5. 12 (3,5,7) [3 points]
6. [10 points] In this exercise, we will deal with the game of poker. In particular, consider the set of all possible five-card hands dealt fairly from a standard deck (52 cards).

(a) How many five-card hands are there?. That is, how many atomic events are there in the joint probability distribution? Explain your answer.

(b) What is the probability of each atomic event?

(c) What is the probability of being dealt a Four-of-a-kind? Two Pairs? a Full House? Cite all your sources

1. [10 points] Using the joint probability table for the random variables A,B,C shown below.

Joint Probability TableA

B

C

P(A, B, C)

FalseFalseFalse0.15FalseFalseTrue0.10FalseTrueFalse0.03FalseTrueTrue0.10TrueFalseFalse0.20TrueFalseTrue0.05TrueTrueFalse0.02TrueTrueTrue0.35

(a) Compute the probability P (A = false)?

(b) Compute the probability P (A = true, B = true)

(c) Compute the probability P (A = false | C = true)

(d) Compute the probability P (A = true, B = false | C = true)

(e) Compute the probability that P (A = true | B = true)

instructions with no picture, please see attached photo for illustrations for each question