Answer Happy

Consider the two-player Race Game introduced in the course. Initially there is a token on cell 1. The two players take turn to move the token 1, 2 or 3 cells to the right. We call these three moves movel, move2 and move3, respectively. The one who moves the token into cell 15 has won. It is not allowed to move the token beyond cell 15. The initial state, so, can be illustrated like this: 80 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 If player 1 initially decides to perform the move move2 (move the token two cells), the resulting state will be the state si illustrated like this: 81 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Each state of the game can be represented as a pair (x, y) = N² where x is the position of the token and y is the number of the player who has the move. So the initial state is so = (1, 1) and the state resulting after player 1 moves the token two cells to the right is s₁ = (3,2). We assign utility +1 to the player who moves the token into cell 15, and utility -1 to the other player. a. Provide part of the formal description of the game by determining the following function values: ACTIONS ((1, 1)) ACTIONS ((13, 1)) RESULT((1, 1), move3) TERMINAL-TEST((13,1)) TERMINAL-TEST((15,2)) UTILITY ((15,2), 2) b. What is the size of the state space of the game (the number of states reachable from the initial state)? Make sure to explain your calculation. 4 c. Suppose we change the rules of the game, so that each player can move the token 1, 2 or 3 cells either to the right or to the left. Will player 1 still have a winning strategy as in the original game? Can we still use MINIMAX to determine an optimal strategy? Explain your answers.