Exercise $2$: Expectimax $[60$ points

$[20$ points$]$ Execute the Expectimax algorithm on the above tree. What are the final values of the nodes? Which branch will the top node choose?

$[20$ points$]$ Assume that the values of the rewards on the leaves are bounded in $1,9.$ Execute the Expectimax algorithm with alpha$-$beta pruning. What are the final values of the nodes? Which nodes are not visited?

$[20$ points$]$ Assume that the values of the rewards on the leaves are bounded in $1,9$ and that alpha$-$beta pruning is used. How can the nodes be shuffled to maximize the number of nodes that are pruned? Draw the tree you found and calculate the final values using Expectimax with alpha$-$beta pruning. NOTE: when you shuffle the nodes, you cannot change their connectivity nor the probabilities; you can only change the order in which they appear. For example, the three leftmost leaves could be reordered as $"3-2-1"$; however, none of those leaves can be moved under a different node, and the probabilities on the edges cannot change.