Question
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
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 opponents 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 Alices turn, Alices score (in the bank) is x, Bobs score is y and Alices 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.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started