CSC 421: Algorithm Design & Analysis
Spring 2013

HW6: D&C vs. Dynamic

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.

Part 1: Divide & Conquer Solution

Create a class named GameSim that contains the following static method:

/** * Determines the probability that a player will win a game in progress * (using a top-down, divide & conquer approach). * @param winProb the probability of winning a single interaction (0 <= winProb <= 1) * @param tokens the number of tokens currently held by the player * @param oppTokens the number of tokens currently held by the opponent * @return the probability of winning the game */ public static double oddsTopDown(double winProb, int tokens, int oppTokens)

Once you have tested your method thoroughly, answer the following questions and provide experimental results to justify your answers.

  1. Suppose the two players are evenly matched, i.e., the probability of winning a single interaction is 0.50. When should the oddsTopDown method return 0.50 as its answer?
  2. How sensitive is the overall outcome to changes in the single interaction probability? For example, if the probability of winning a single interaction is 0.75, would you expect that player to win the game roughly 0.75 of the time?
  3. Assuming the players are not evenly matched, does the number of tokens the players start with affect the probability of either player winning?
  4. Is there a practical limit to how long of a game that your 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?

Part 2: Dynamic Programming Solution

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:

  1. Does this new method return the same answers as the previous one? How would you go about testing this?
  2. Is this version noticeably faster? If so, how long can the games be before the delay using oddsBottomUp is significant?
  3. Suppose player 1 is twice as good as player 2 (i.e., has a 2/3 probability of winning a single interaction as opposed to 1/3). If player 1 starts with 10 tokens, how many should player 2 start with if we want the game to be as fair as possible (i.e., have close to a 0.50 probability of either player winning)?
  4. Suppose player 1 is twice as good as player 2 (i.e., has a 2/3 probability of winning a single interaction as opposed to 1/3). If player 1 starts with 20 tokens, how many should player 2 start with if we want the game to be as fair as possible (i.e., have close to a 0.50 probability of either player winning)?