Question 1: Game Tree Search [60 points] Consider the game tree below. Let and nodes represent nodes belonging to the maximizing and minimizing player respectively 0 6 1. (20 points) Suppose we wish to run the Minimax algorithm on this game tree. Provide the game theoretic values of nodes AG through optimal play 2. (10 points) Use alpha-beta pruning to compute the Minimax value at each node for the original game tree (i.e., deterministic environm) Assume that nodes are visited from left to right. In addition to the Minimax values, show your alpha and beta values at each node after the final time it is visited 3. (5 points) Which branches, if any, in the game tree are pruned? Show this on the graph above. 4. (5 points) Explain, in English, why we would want to use alpha-beta pruning. 5. (5 points) Now suppose we are in a non-deterministic environment with rules as follows. When a player begins their turn they first flip a fair coin (heads probability .5) and if it turns up heads they choose the optimal action. However, if the coin turns up tails they then flip another fair coin to randomly select their action. In this game, what is the probability of a player choosing an optimal action at each node? 6. (5 points) Given the game described in part 5, redraw the game tree as follows. For each non-terminal node X, introduce a new chance node X' Let X, be the only successor of X, while the original successors of X are now given to X". Label the probability on each edge from X to its successors. These probabilities should sum to 1 for each X 7. (10 points) Using the new game tree in part 6, solve the non-deterministic game. Specifically, provide your answers to the nearest the expected game theoretic value of nodes A G for the new tree. Round 2 decimal places (i.e. X.XX). Hint: this is explained on slide p.58