PSet 9: Expectimax

(videos: up to Expectimax)

1. Fill out the values in every node of the tree.

2-5. Using the game tree with chance nodes below (evaluating from left to right):

2. Mark the value of all the internal nodes, and indicate the best moove at the root with an arrow.

3. Justify why you can’t prune the last two leaf nodes on the right. That is, are there possible values of those leaf nodes that would change the outcome - change Max’s mind.

4. Suppose we know that all leaf nodes are only in the range [-2;2]. After you evaluate the first two leaf nodes, what is the range of possible values for the left chance node?

5. Given your answer to (3), what other leaves can be pruned?

Challenge Problems¶

Assume below that “max” trees contain all max nodes, “expectimax” trees contain a max at the root, and alternating layers of max and chance nodes. At chance nodes, all probabilities are non-zero.

1. Assuming leaf nodes that are finite but unbounded (it’s never infinity, but we don’t know how large or how small it could be), is pruning ever possible in a max tree? Why?

2. Is pruning ever available in an expectimax tree under the same conditions? Why?

3. If leaf values are all non-negative, is pruning ever possible in an expectimax tree? Give an example or explain why not.

4. If leaf values are all in the range [0,1], is pruning ever possible in a max tree? Give an example or explain why not.

5. If leaf values are all in the range [0,1], is pruning ever possible in a expectimax tree? Give an example or explain why not.