Problem 4 [20 points. Consider the two-player game descnbed m igure . For the givei game, provide answers to the following questions. a. [5 points) Draw the complete game tree, using the following conventions . Write each state as (sA,sB) where sa and sB denote the token locations. . Put each terminal state in a square box and write its game value in a circle Page 1 Jingun Yu Rutgers University CS 440 Fall 2018 Homework Assignment 3 Due date: 10/21/2018 11:55pm 1 2 3 4 Figure 1: The start position of a simple game. 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, than a player may jump over the opponent to the next open space if any. (For example, if A is on 3 and B is on 2, then A may move back to 1.) The game ends when one player reaches the opposite end. 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 A is -1. . Put loop states (states that already appear on the path to the root) in double square boxes. Since it is not clear how to assign values to loop states, annotate each with a "?" in a circle. b. [5 points] Now mark each node with its backed-up MinMax value (also in circle). Explain how you handled the "? values and why c. 5 pointsl Explain why the standard MinMax algorithm would fail on this game tree and briefly sketch how you might fix it, drawing on your answer to (b). Does your modified algorithm give optimal decisions for all games with loops? d. 15 points) This 4-square game can be generalized to n squares for any n > 2. Prove that A wins if n is even and loses if n is odd