3. Adversarial Search We assume a zero-sum two-player game with perfect information (zero-sum means that one player's gain or loss is exactly balanced by the loss or gain of the other player). The game tree below illustrates an example of such a game. Player 1 has the choice between two moves. Then, Player 2 has the choice between three moves, and finally Player 1 can choose between another three moves to reach one of the terminal game states. The evaluation scores for the terminal states from the first player's view are listed at the leaf nodes of the tree: a positive number indicates the amount of money the first player wins from the second player, while a negative number indicates the amount of money the second player wins from the first player. Player 1 Player 2 Player 1 S A Y B T DOOG F DOO000 K L -18 -7 6-13 18 -19 -8 205-3 11 -22 -23 U V H OP R -7 -3 10 16 21 a) Describe the differences between the minimax algorithm and the a- pruning algorithm. Explain why, despite these differences, both algorithms return the same result for such zero- sum two-player games. b) Assuming that in the above game tree the nodes are visited from left to right, which nodes (interior and leaf nodes labeled A-R) would not be examined by the a- pruning algorithm? Which nodes would not be examined if the a- pruning algorithm would visit the nodes from right to left? Z W X N