In the lectures, we considered two different solutions to the World Series puzzle. The divide & conquer solution utilized recursion to break the problem into simpler instances and combined solutions to those instances to solve the overall problem. The dynamic programming solution utilized a table of subproblem solutions that it filled in a bottom-up manner. Both solutions were based on a simple recurrence relation that defined how a problem solution could be built out of solutions to smaller problems.
In a related problem, consider a game in which two players start with the same number of tokens. Each round in the game (arm wrestling, staring contest, karaoke showdown, whatever) results in the loser forfeiting a token. The game continues until one of the players runs out of tokens, and the other player is declared the winner. If the probability of a particular player winning an individual round is fixed, then it should be possible to calculate the probability of that player winning an entire game.
For example, suppose Vicky and Grant are playing a game in which Vicky is acknowledged to be the better player (with a 0.60 probability of winning any given round). If both players are down to a single token, then the probability of Vicky winning is 0.60 (since she has a 0.60 probability of winning the round and a 0.40 probability of losing it). Alternatively, if Vicky has two remaining tokens and Grant has only one, then her probability of winning is even better. There is still a 0.60 probability that she will win the game on the next round. However, there is also a 0.24 chance that she will win it in two rounds (0.40 probability of losing the first round to get to one token each, then a 0.60 probability of winning the second round). Thus, the probability of Vicky winning the game is 0.60 + 0.24 = 0.84.
Create a class named
GameSim that contains the following static method:
Once you have tested your method thoroughly, answer the following questions and provide experimental results to justify your answers:
probTopDowncan handle? In particular, if you want to know the probability of winning a game in which the players start with N tokens, how big of an N can your method handle before the delay is significant?
Add an additional method to your
GameSim class named
probBottomUp. This method should have the same parameters as
probTopDown and should calculate the same value, only now using a dynamic programming approach. In particular, it should avoid duplicate calculations by building up a table of answers in a bottom-up fashion.
Answer the following questions and provide experimental results to justify your answers: