Consider the following 2-player game played with a 6-sided die. On your turn, you can decide either to roll the die or to pass. If you roll the die and get a 1, your turn immediately ends and you get 1 point. If you instead get some other number, it gets added to a running total and your turn continues (i.e. you can again decide whether to roll or pass). If you pass, then you get either 1 point or the running total number of points, whichever is larger, and it becomes your opponent’s turn. For example, if you roll 3, 4, 1 you get only 1 point, but if you roll 3, 4, 2 and then decide to pass you get 9 points. The first player to get to N points wins, for some positive N.

Alice and Bob are playing the above game. Let W(x, y, z) be the probability that Alice wins given that it is currently Alice’s turn, Alice’s score (in the bank) is x, Bob’s score is y and Alice’s running total is z.

a) Give a recursive formula for the winning probability W(x, y, z).

b) Based on the recursive formula you gave in the previous part, design an O(N3 ) dynamic programming algorithm to compute W(x, y, z). Briefly describe your algorithm, prove its correctness and runtime.