6.824 Artificial Intelligence, Fall 1993 Problem Set 9

Due: Beginning of class Wednesday, November 24

Problem 1. Consider a game with branching factor 2 and depth d and where the max player moves first. Note that there are 2^{d} leaf nodes. Let δ be \frac{1}{2^{d}}. Suppose that the leaf nodes are assigned the value δ, 2δ, 3δ, … 2^{d}δ = 1. In the limit as d → ∞ the min max value of trees of this form approaches a certain value. What is that value? Explain your answer. What would the limit be if the min player moved first?

Problem 2. Consider a minmax game tree in which each max node has a branching factor of b_{max} and each min node has a branching factor of b_{min}. Now consider an α-β search in which the best move is tried first at each ply and so that an optimal α-β search tree is generated. In a d-ply tree starting at a max node how many leaf nodes will be examined? Your answer should be given in terms of the parameters d, b_{max}, and b_{min}.

Problem 3. Consider a game tree with uniform branching factor b and depth d. Suppose that each leaf is independendtly assigned the value 1 or 0 where the probability of assigning a given leaf the value 1 is P. Assume that the max player moves last. Let P (1| d, b, P) be the probability that the root value is 1 given that the max player moves last, the tree has depth d, the branching factor is b, and the probability that a leaf has value 1 is P. For any value of P and b one of the three following conditions hold.

lim_{d→∞} P (1| d, b, P) = 1

lim_{d→∞} P (1| d, b, P) = 0

0 < lim_{d→∞} P (1| 2d + 1, b, P) < 1

Give conditions on P and b under which each of the above conditions hold. Note that in the third condition only odd values of d are considered. Hint: Think about whether the probability of a min-max value of 1 at a max node gets larger or smaller as one gets farther from the leaves.

Problem 4. Consider a game tree in which each node is associated with a static value. For any node n we let s(n) denote the static value of n. We consider a game where at any max position n with child m we have that s(m) is either s(n) or s(n)+1. If s(m) is s(n) + 1 then we say that the child node m is generated by a capture move from the max position n. The dual conditions apply at min nodes — if n is a min node and m is a child of n then s(m) is either s(n) or s(n) − 1 and in the latter case we say that the child m is generated by a capture move from the min node n. Children other than those generated by capture moves will be said to be generated by noncapture moves.

Construct a four ply game tree with branching factor 2 such that the root node is a max node and every node has one child generated by a capture move and one child generated by a noncapture move. The root value of the four ply tree has minmax value 0. For each of the 16 leaf nodes indicate whether it is in the max defense for avoiding -1, whether it is in the min defense for avoiding +1, and for those leaves which are in one of these two defenses indicate its conspiracy depth in each of the defenses that it belongs to.