artificial intelligence

Consider the two-player, turn-taking, zero-sum game for the game tree:

Apply the - (alpha - beta) algorithm (with left-to-right expansion order) to compute the value of the root node! Mark which of the branches can be pruned and why.

1. What is the best move of the max player in the initial state?

2. What is the value of the root node?

3. Which branches of the tree can be pruned and why? Name the branches to be cut and which bounds allow you to cut them (e.g., the branch to x can be cut because y=43 (alpha(y) =43) is greater than z=17 (beta(z) = 17)).

4. Suppose you were using a heuristics to decide on the expansion order of the states. What would be the perfect heuristics? That is, for each node, in which order should child nodes be expanded such that the - (alpha - beta) algorithm expands the smallest number of nodes? Write down the names of the all nodes in the order in which they should be expanded. For example, adjkelmbfnogpqchrsitu would be the normal left-to-right expansion.

5. The perfect heuristic as discussed in the previous question is not achievable in practice. Why? Despite that fact, what could be done to increase the amount of pruning that - (alpha - beta) search does?