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 competition in which two players repeatedly play a game that can end in a win, loss, or tie (e.g., chess, rock-paper-scissors, karaoke showdown). The players each begin with the same number of tokens. If a game results in a winner, then the loser forfeits one of his/her tokens. If the game results in a tie, then both players forfeit a token. The competition ends when one of the players runs out of tokens, and the other player is declared the winner (or it ends in a draw if both run out simultaneously).
For example, suppose Katherine challenges Michael to a lawn darts competition where each player starts with five tokens. It has been determined that Katherine's odds of winning a game are 0.50 and Michael's odds of winning are 0.30 (with a 0.20 chance of a tie). Thus, there is a 50% chance that she will win the first game (resulting in a token count of 5-4), a 30% chance that she will lose the first game (resulting in a token count of 4-5), and a 20% chance that they will tie (resulting in a token count of 4-4). The competition will continue until one or both players run out of tokens.
Create a class named Competition
whose constructor has two parameters: the probabilities of a player and his/her opponent winning a game, respectively. These probabilities should each be between 0.0 and 1.0, and should add up to a number less than or equal to 1.0. Your class should also have the following method:
Finally, create a driver program that allows the user to specify the winning probabilities and the initial number of tokens, and displays the odds of the first player winning the competition. Using your program, answer the following questions and provide experimental results to justify your answers.
oddsOfWinningTopDown
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 Competition
class named oddsOfWinningBottomUp
. This method should have the same parameters as oddsOfWinningTopDown
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.
oddsOfWinningBottomUp
is significant?