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.
For this assignment, you will consider a new game named Roller Derby that is being introduced at the CU Casino for the Probabilistically Challenged. In Roller Derby, a player puts down a stack of tokens, and the house matches that with an equal-sized stack. The player is able to select two numbers in the range 1-6, and the house does the same from the remaining numbers. Then the player repeatedly rolls a 6-sided die. If a roll matches one of the player's selected numbers, then the house loses a token from its stack and places it in the pot. If the roll matches one of the house's numbers, then the player loses a token to the pot. If the roll is matches one of the two unselected numbers, then both the player and the house lose a token to the pot. The game continues until either the player or the house completely runs out of tokens. At that point, all of the tokens in the pot go to the one with tokens remaining.
For example, suppose a player begins a game with a stack of 4 tokens and selects the numbers 1 and 6. The house selects 3 and 4. If the first roll is a 1, then the house loses a token, leaving it with only 3 (the player still has 4). If the next roll is a 2, both lose a token, leaving the house with 2 and the player with 3. If the next roll is a 6, then the house loses a token, leaving it with only 1 (the player still has 3). If a 5 is rolled next, then both lose a token, leaving the house with none and the player with 2. At that point, the player is declared the winner and gets all of the tokens. Note that if both run out of tokens on the same turn (i.e., both have 1 token remaining and an unselected number is rolled), then the house wins.
Create a class named
RollerDerby 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.
oddsTopDownmethod repeatedly with the same inputs, will you always get the same answer? If so, explain why. If not, describe what random events contribute to the differing answers.
oddsTopDowncan handle? In particular, if you want to know the probability of winning a game in which the player and house start with N tokens, how big of an N can your method handle before the delay is significant?
Add an additional method to your
RollerDerby 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: