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 Rollorama that is being introduced at the CU Casino for the Probabilistically Challenged. In Rollorama, a player puts down a stack of tokens, and the house matches that with an equal-sized stack. Then the player repeatedly rolls a pair of 6-sided dice. If the dice total is between 3 and 6, then the house loses a token from its stack and places it in the pot. If the dice total is between 8 and 11, then the player loses a token to the pot. If the dice total is 2, 7, or 12, 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 3 tokens, which is matched by the house. If the first roll is a 3, then the house loses a token, leaving it with only 2 (the player still has 3). If the next roll is a 7, both lose a token, leaving the house with 1 and the player with 2. If the next roll is a 10, then the player loses a token, leaving him/her with only 1 (the house still has 1). If a 5 is rolled next, then the house loses its last token. 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 a 2, 7 or 12 is rolled), then the house wins.
Create a class named
Rollorama 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
Rollorama 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: