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

CSC384: Introduction to Artificial Intelligence

Search: Adversarial Search

Practice Problems

1. Consider the game tree shown below:

A

C 

D

 H

1              4           5              9            0                   9              3    2              0           4              6

Assume • and ◦ represent the maximizer’s and minimizer’s nodes, respectively.

(a) Let U(n) denote the utility the maximizer obtains at node, n, assuming both

players use the min-max strategy.  For each non-terminal node, n, indicate u(n) on the figure above.

(b) Circle each node that would be visited during a min-max search with α/β-

pruning.

(c) What utility will the maximizer get if

i. the minimizer plays perfectly

ii. the minimizer always moves from B to E

iii. the minimizer always moves from B to F .

(d) Suppose the adversary is no longer a minimizer, but instead plays non-deterministically, according to the probability distribution,

 0.7, (x,y) = (B,E)

p(x,y) =  0.4, (x,y) = (C,G)

 0.9, (x,y) = (D,J)

i. What is the maximizer’s expected utility?

ii. What is the probability that the maximizer obtains a better utility using the min-max in comparison to to the expectation-maximization approach?