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 interaction in the game (an arm wrestle, 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 interaction is fixed, then it should be possible to calculate the probability of that player winning an entire game.
For example, suppose Melinda and Cody are playing a game in which Melinda is acknowledged to be the better player (with a 0.60 probability of winning any given interaction). If both players are down to a single token, then the odds of Melinda winning are 0.60 (since she has a 0.60 probability of winning the interaction and a 0.40 probability of losing it). Alternatively, if Melinda has two remaining tokens and Cody has only one, then her odds of winning are even better. There is still a 0.60 probability that she will win the game on the next interaction. However, there is also a 0.24 chance that she will win it in two interactions (0.40 probability of losing the first interaction to get to one token each, then a 0.60 probability of winning the second interaction). Thus, the probability of Melinda 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.
oddsTopDown
method return 0.50 as its answer?
oddsTopDown
can 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 oddsBottomUp
. This method should have the same parameters as oddsTopDown
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:
oddsBottomUp
is significant?