CSC 421: Algorithm Design & Analysis
Spring 2019

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 round in the game (arm wrestling, 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 individual round is fixed, then it should be possible to calculate the probability of that player winning an entire game.

For example, suppose Vicky and Grant are playing a game in which Vicky is acknowledged to be the better player (with a 0.60 probability of winning any given round). If both players are down to a single token, then the probability of Vicky winning is 0.60 (since she has a 0.60 probability of winning the round and a 0.40 probability of losing it). Alternatively, if Vicky has two remaining tokens and Grant has only one, then her probability of winning is even better. There is still a 0.60 probability that she will win the game on the next round. However, there is also a 0.24 chance that she will win it in two rounds (0.40 probability of losing the first round to get to one token each, then a 0.60 probability of winning the second round). Thus, the probability of Vicky 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 round (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 probTopDown(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 round is 0.50. If the players have the same number of tokens, what would you expect probTopDown to return?
  2. How sensitive is the overall outcome to changes in the single round probability? For example, if the probability of winning a single round is 0.75 (and the players start with the same number of tokens), would you expect that player to win the game roughly 0.75 of the time?
  3. Assuming the players are not evenly matched, does increasing or decreasing the initial number of tokens affect the probability of either player winning?
  4. Is there a practical limit to how long of a game that your probTopDown 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 probBottomUp. This method should have the same parameters as probTopDown 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 probBottomUp is significant?
  3. Suppose player 1 is 50% better than player 2 (i.e., has a 0.60 probability of winning a single round as opposed to 0.40). 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 round 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)?
  5. Is there a discernable pattern between how much better a player is and how many extra tokens the opponent should receive in order to yield a fair game?