Q4 8 Points In the graph shown in (a) comprising nodes 'A' through 'E', we assume that the players red and green take turns to move into one of the adjacent nodes at any single turn. The state of the game can be denoted by an ordered pair of letters. For example, the initial state of the game in (a) can be specified as 'AC', and after green's move to the 'E', the state becomes as 'EC! The game ends only when the players are on the same node. The cost of each turn for player green is one, hence, the utility value of a terminal node S (denotes as v(S)) for the green player is the minus of total turns taken until S. The game is assumed to be zero-sum. From the initial state in (a), the green player starts first and the game follows afterwards resulting in the partial game tree in the panel (b). B ED DD AD 3 (a) Initial state (b) Partial game tree Q4.1 3 Points Follow the game tree in (b) and specify the states denoted by: S1: Enter your answer here S2: Enter your answer here and S3: Enter your answer here Q4.2 2 Points Specify the terminal utility values of: V(DD) Enter your answer here V(BB) Enter your answer here Q4.3 2 Points Without further expanding the game tree, specify the possible range of utility values for v(Si), v(S2), and v(S3), and propagate them to obtain v(AC) (Hint: consider the least cost of the shortest paths on the graph until the game is finished.) v(SI)