HW#4: Alpha-Beta Pruning with Chance Nodes
1) Exercise 5.2 in your Book:
i. Consider Alpha-Beta Pruning.
ii. Implement and test your algorithm of choice in (c).
iii. Test your program with TEN different initial states.
iv. For each Test Initial State, report the following:
➢ The initial state
➢ The number of times the program was able to prune of each type (Alpha vs Beta).
v. Repeat (iv) again 4 times with different order of actions tried.
vi. Comment on your observations.
Exercise 5.2 Consider the problem of solving two 8-puzzles.
a. Give a complete problem formulation in the style of Chapter 3.
b. How large is the reachable state space? Give an exact numerical expression.
c. Suppose we make the problem adversarial as follows: the two players take turns moving; a coin is flipped to determine the puzzle on which to make a move in that turn; and the winner is the first to solve one puzzle. Which algorithm can be used to choose a move in this setting?
d. Give an informal proof that someone will eventually win if both play perfectl
—————————————————————————————————————————————————————————————————————————————
2) Exercise 5.16 in your Book.
Note: This is an individual-type assignment, no group work is accepted.
Report the results and include appendix of code, Source Code should also be submitted in a separate file(s);
———————————————————————-
Exercise 5.16 This question considers pruning in games with chance nodes. Figure 5.19 shows the complete game tree for a trivial game. Assume that the leaf nodes are to be evaluated in leftto-right order, and that before a leaf node is evaluated, we know nothing about its value—the range of possible values is −∞ to ∞.
a. Copy the figure, mark the value of all the internal nodes, and indicate the best move at the root with an arrow.
b. Given the values of the first six leaves, do we need to evaluate the seventh and eighth leaves? Given the values of the first seven leaves, do we need to evaluate the eighth leaf? Explain your answers.
c. Suppose the leaf node values are known to lie between –2 and
2 inclusive. After the first two leaves are evaluated, what is the value range for the left-hand chance node?
d. Circle all the leaves that need not be evaluated under the assumption in (c).
