undefined

Consider a simple game described below. A B 1 2 3 4 The starting position of a simple game is shown in the above picture. It is a two player game (player A and B). Player A moves first. The two players take turns moving, and each player must move his token to an open adjacent space in either direction. If the opponent occupies an adjacent space, then a player may jump over the opponent to the next open space if any. (For example, if Ais on 3 and Bis on 2, then A may move back to 1.) The game ends when one player reaches the opposite end of the board. If player A reaches space 4 first, then the value of the game to A is +1; if player B reaches space 1 first, then the value of the game to Ais -1. (4-a) Draw the complete game tree, using the following conventions: Write each state as (sa, 53), where s, and se denote the token locations. Put each terminal state in a square box and write its utility value in a circle. Put loop/repeated states (states that already appear on the path to the root) in double square boxes. Since their value is unclear, annotate the utility of each of these states with a "?" in a circle. (4-6) Mark each node with its backed-up minimax value (also in a circle). Explain how you handled the "?" values and why. [ no need to show the traces of the algorithm, you can directly use the minimax recurrence here.] (4-c) Do you see any challenges in applying minimax algorithm to this game tree. Explain. (4-d) What is the time and space complexity of minimax for deciding the best move for MAX player? Consider a simple game described below. A B 1 2 3 4 The starting position of a simple game is shown in the above picture. It is a two player game (player A and B). Player A moves first. The two players take turns moving, and each player must move his token to an open adjacent space in either direction. If the opponent occupies an adjacent space, then a player may jump over the opponent to the next open space if any. (For example, if Ais on 3 and Bis on 2, then A may move back to 1.) The game ends when one player reaches the opposite end of the board. If player A reaches space 4 first, then the value of the game to A is +1; if player B reaches space 1 first, then the value of the game to Ais -1. (4-a) Draw the complete game tree, using the following conventions: Write each state as (sa, 53), where s, and se denote the token locations. Put each terminal state in a square box and write its utility value in a circle. Put loop/repeated states (states that already appear on the path to the root) in double square boxes. Since their value is unclear, annotate the utility of each of these states with a "?" in a circle. (4-6) Mark each node with its backed-up minimax value (also in a circle). Explain how you handled the "?" values and why. [ no need to show the traces of the algorithm, you can directly use the minimax recurrence here.] (4-c) Do you see any challenges in applying minimax algorithm to this game tree. Explain. (4-d) What is the time and space complexity of minimax for deciding the best move for MAX player