# Unit 5: Probability in the game of Darts """ In the game of darts, players throw darts at a board to score points. The circular board has a 'bulls-eye' in the center and 20 slices called sections, numbered 1 to 20, radiating out from the bulls-eye. The board is also divided into concentric rings. The bulls-eye has two rings: an outer 'single' ring and an inner 'double' ring. Each section is divided into 4 rings: starting at the center we have a thick single ring, a thin triple ring, another thick single ring, and a thin double ring. A ring/section combination is called a 'target'; they have names like 'S20', 'D20' and 'T20' for single, double, and triple 20, respectively; these score 20, 40, and 60 points. The bulls-eyes are named 'SB' and 'DB', worth 25 and 50 points respectively. Illustration (png image): http://goo.gl/i7XJ9 There are several variants of darts play; in the game called '501', each player throws three darts per turn, adding up points until they total exactly 501. However, the final dart must be in a double ring. Your first task is to write the function double_out(total), which will output a list of 1 to 3 darts that add up to total, with the restriction that the final dart is a double. See test_darts() for examples. Return None if there is no list that achieves the total. Often there are several ways to achieve a total. You must return a shortest possible list, but you have your choice of which one. For example, for total=100, you can choose ['T20', 'D20'] or ['DB', 'DB'] but you cannot choose ['T20', 'D10', 'D10']. """ def test_darts(): "Test the double_out function." assert double_out(170) == ['T20', 'T20', 'DB'] assert double_out(171) == None assert double_out(100) in (['T20', 'D20'], ['DB', 'DB']) """ My strategy: I decided to choose the result that has the highest valued target(s) first, e.g. always take T20 on the first dart if we can achieve a solution that way. If not, try T19 first, and so on. At first I thought I would need three passes: first try to solve with one dart, then with two, then with three. But I realized that if we include 0 as a possible dart value, and always try the 0 first, then we get the effect of having three passes, but we only have to code one pass. So I creted ordered_points as a list of all possible scores that a single dart can achieve, with 0 first, and then descending: [0, 60, 57, ..., 1]. I iterate dart1 and dart2 over that; then dart3 must be whatever is left over to add up to total. If dart3 is a valid element of points, then we have a solution. But the solution, is a list of numbers, like [0, 60, 40]; we need to transform that into a list of target names, like ['T20', 'D20'], we do that by defining name(d) to get the name of a target that scores d. When there are several choices, we must choose a double for the last dart, but for the others I prefer the easiest targets first: 'S' is easiest, then 'T', then 'D'. """ def double_out(total): """Return a shortest possible list of targets that add to total, where the length <= 3 and the final element is a double. If there is no solution, return None.""" # your code here """ It is easy enough to say "170 points? Easy! Just hit T20, T20, DB." But, at least for me, it is much harder to actually execute the plan and hit each target. In this second half of the question, we investigate what happens if the dart-thrower is not 100% accurate. We will use a wrong (but still useful) model of inaccuracy. A player has a single number from 0 to 1 that characterizes his/her miss rate. If miss=0.0, that means the player hits the target every time. But if miss is, say, 0.1, then the player misses the section s/he is aiming at 10% of the time, and also (independently) misses the thin double or triple ring 10% of the time. Where do the misses go? Here's the model: First, for ring accuracy. If you aim for the triple ring, all the misses go to a single ring (some to the inner one, some to the outer one, but the model doesn't distinguish between these). If you aim for the double ring (at the edge of the board), half the misses (e.g. 0.05 if miss=0.1) go to the single ring, and half off the board. (We will agree to call the off-the-board 'target' by the name 'OFF'.) If you aim for a thick single ring, it is about 5 times thicker than the thin rings, so your miss ratio is reduced to 1/5th, and of these, half go to the double ring and half to the triple. So with miss=0.1, 0.01 will go to each of the double and triple ring. Finally, for the bulls-eyes. If you aim for the single bull, 1/4 of your misses go to the double bull and 3/4 to the single ring. If you aim for the double bull, it is tiny, so your miss rate is tripled; of that, 2/3 goes to the single ring and 1/3 to the single bull ring. Now, for section accuracy. Half your miss rate goes one section clockwise and half one section counter-clockwise from your target. The clockwise order of sections is: 20 1 18 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5 If you aim for the bull (single or double) and miss on rings, then the section you end up on is equally possible among all 20 sections. But independent of that you can also miss on sections; again such a miss is equally likely to go to any section and should be recorded as being in the single ring. You will need to build a model for these probabilities, and define the function outcome(target, miss), which takes a target (like 'T20') and a miss ration (like 0.1) and returns a dict of {target: probability} pairs indicating the possible outcomes. You will also define best_target(miss) which, for a given miss ratio, returns the target with the highest expected score. If you are very ambitious, you can try to find the optimal strategy for accuracy-limited darts: given a state defined by your total score needed and the number of darts remaining in your 3-dart turn, return the target that minimizes the expected number of total 3-dart turns (not the number of darts) required to reach the total. This is harder than Pig for several reasons: there are many outcomes, so the search space is large; also, it is always possible to miss a double, and thus there is no guarantee that the game will end in a finite number of moves. """ def outcome(target, miss): "Return a probability distribution of [(target, probability)] pairs." #your code here def best_target(miss): "Return the target that maximizes the expected score." #your code here def same_outcome(dict1, dict2): "Two states are the same if all corresponding sets of locs are the same." return all(abs(dict1.get(key, 0) - dict2.get(key, 0)) <= 0.0001 for key in set(dict1) | set(dict2)) def test_darts2(): assert best_target(0.0) == 'T20' assert best_target(0.1) == 'T20' assert best_target(0.4) == 'T19' assert same_outcome(outcome('T20', 0.0), {'T20': 1.0}) assert same_outcome(outcome('T20', 0.1), {'T20': 0.81, 'S1': 0.005, 'T5': 0.045, 'S5': 0.005, 'T1': 0.045, 'S20': 0.09}) assert same_outcome( outcome('SB', 0.2), {'S9': 0.01, 'S8': 0.01, 'S3': 0.01, 'S2': 0.01, 'S1': 0.01, 'DB': 0.04, 'S6': 0.01, 'S5': 0.01, 'S4': 0.01, 'S19': 0.01, 'S18': 0.01, 'S13': 0.01, 'S12': 0.01, 'S11': 0.01, 'S10': 0.01, 'S17': 0.01, 'S16': 0.01, 'S15': 0.01, 'S14': 0.01, 'S7': 0.01, 'S20': 0.01, 'SB': 0.76})

My solution:

# Unit 5: Probability in the game of Darts """ In the game of darts, players throw darts at a board to score points. The circular board has a 'bulls-eye' in the center and 20 slices called sections, numbered 1 to 20, radiating out from the bulls-eye. The board is also divided into concentric rings. The bulls-eye has two rings: an outer 'single' ring and an inner 'double' ring. Each section is divided into 4 rings: starting at the center we have a thick single ring, a thin triple ring, another thick single ring, and a thin double ring. A ring/section combination is called a 'target'; they have names like 'S20', 'D20' and 'T20' for single, double, and triple 20, respectively; these score 20, 40, and 60 points. The bulls-eyes are named 'SB' and 'DB', worth 25 and 50 points respectively. Illustration (png image): http://goo.gl/i7XJ9 There are several variants of darts play; in the game called '501', each player throws three darts per turn, adding up points until they total exactly 501. However, the final dart must be in a double ring. Your first task is to write the function double_out(total), which will output a list of 1 to 3 darts that add up to total, with the restriction that the final dart is a double. See test_darts() for examples. Return None if there is no list that achieves the total. Often there are several ways to achieve a total. You must return a shortest possible list, but you have your choice of which one. For example, for total=100, you can choose ['T20', 'D20'] or ['DB', 'DB'] but you cannot choose ['T20', 'D10', 'D10']. """ def test_darts(): "Test the double_out function." assert double_out(170) == ['T20', 'T20', 'DB'] assert double_out(171) == None assert double_out(100) in (['T20', 'D20'], ['DB', 'DB']) """ My strategy: I decided to choose the result that has the highest valued target(s) first, e.g. always take T20 on the first dart if we can achieve a solution that way. If not, try T19 first, and so on. At first I thought I would need three passes: first try to solve with one dart, then with two, then with three. But I realized that if we include 0 as a possible dart value, and always try the 0 first, then we get the effect of having three passes, but we only have to code one pass. So I creted ordered_points as a list of all possible scores that a single dart can achieve, with 0 first, and then descending: [0, 60, 57, ..., 1]. I iterate dart1 and dart2 over that; then dart3 must be whatever is left over to add up to total. If dart3 is a valid element of points, then we have a solution. But the solution, is a list of numbers, like [0, 60, 40]; we need to transform that into a list of target names, like ['T20', 'D20'], we do that by defining name(d) to get the name of a target that scores d. When there are several choices, we must choose a double for the last dart, but for the others I prefer the easiest targets first: 'S' is easiest, then 'T', then 'D'. """ def double_out(total): """Return a shortest possible list of targets that add to total, where the length <= 3 and the final element is a double. If there is no solution, return None.""" from itertools import ifilter targets = getTargets() #first we try to finish with a single shot (double out) for target in targets: if target[0] == total and target[2] == 'D': return [target[1]] #now we try to finish with two shots of which the last must be a double out for target1 in targets: for target2 in ifilter(lambda target: target[2] == 'D', targets): if target1[0] + target2[0] == total: return [target1[1], target2[1]] #so it seems we are bad at darts and are going to need 3 throws for target1 in targets: if target1[0] < total: for target2 in targets: if target1[0] + target2[0] < total: for target3 in ifilter(lambda target: target[2] == 'D', targets): if target1[0] + target2[0] + target3[0] == total: return [target1[1], target2[1], target3[1]] return None def getTargets(): #returns a sorted (high to low) array of tuples of all possible targets in form #[(60, 'T20', 'T'), (57, 'T19', 'T'), ...,(50, 'DB', 'D'), ...,(19, 'S19', 'S'),...] targets = [(3*i, 'T' + str(i), 'T') for i in range(1,21)] + [(2*i, 'D' + str(i), 'D') for i in range(1,21)] + [(i, 'S' + str(i), 'S') for i in range(1,21)] + [(25, 'SB', 'S'), (50, 'DB', 'D')] targets.sort() targets.reverse() return targets """ def getTarget(targets, restvalue): #return best target for remaining points to throw or None if we can't double out for target in targets: if target[0] < restvalue: return target if target[0] == restvalue and target[2] == 'D': return target return None """ """ It is easy enough to say "170 points? Easy! Just hit T20, T20, DB." But, at least for me, it is much harder to actually execute the plan and hit each target. In this second half of the question, we investigate what happens if the dart-thrower is not 100% accurate. We will use a wrong (but still useful) model of inaccuracy. A player has a single number from 0 to 1 that characterizes his/her miss rate. If miss=0.0, that means the player hits the target every time. But if miss is, say, 0.1, then the player misses the section s/he is aiming at 10% of the time, and also (independently) misses the thin double or triple ring 10% of the time. Where do the misses go? Here's the model: First, for ring accuracy. If you aim for the triple ring, all the misses go to a single ring (some to the inner one, some to the outer one, but the model doesn't distinguish between these). If you aim for the double ring (at the edge of the board), half the misses (e.g. 0.05 if miss=0.1) go to the single ring, and half off the board. (We will agree to call the off-the-board 'target' by the name 'OFF'.) If you aim for a thick single ring, it is about 5 times thicker than the thin rings, so your miss ratio is reduced to 1/5th, and of these, half go to the double ring and half to the triple. So with miss=0.1, 0.01 will go to each of the double and triple ring. Finally, for the bulls-eyes. If you aim for the single bull, 1/4 of your misses go to the double bull and 3/4 to the single ring. If you aim for the double bull, it is tiny, so your miss rate is tripled; of that, 2/3 goes to the single ring and 1/3 to the single bull ring. Now, for section accuracy. Half your miss rate goes one section clockwise and half one section counter-clockwise from your target. The clockwise order of sections is: 20 1 18 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5 If you aim for the bull (single or double) and miss on rings, then the section you end up on is equally possible among all 20 sections. But independent of that you can also miss on sections; again such a miss is equally likely to go to any section and should be recorded as being in the single ring. You will need to build a model for these probabilities, and define the function outcome(target, miss), which takes a target (like 'T20') and a miss ration (like 0.1) and returns a dict of {target: probability} pairs indicating the possible outcomes. You will also define best_target(miss) which, for a given miss ratio, returns the target with the highest expected score. If you are very ambitious, you can try to find the optimal strategy for accuracy-limited darts: given a state defined by your total score needed and the number of darts remaining in your 3-dart turn, return the target that minimizes the expected number of total 3-dart turns (not the number of darts) required to reach the total. This is harder than Pig for several reasons: there are many outcomes, so the search space is large; also, it is always possible to miss a double, and thus there is no guarantee that the game will end in a finite number of moves. """ def outcome(target, miss): "Return a probability distribution of [(target, probability)] pairs." from itertools import product ring = ring_outcome(target,miss) section = section_outcome(target, miss) if target in ['SB', 'DB']: result = {'SB': ring['SB'] * section['B'] + ring['S'] * section['B'], 'DB': ring['DB'] * section['B']} for i in range(1,21): result['S' + str(i)] = section[str(i)] return result else: return dict((combi[0][0] + combi[1][0], combi[0][1] * combi[1][1]) for combi in product(ring.items(), section.items())) def ring_outcome(target, miss): #target = 'T20' | 'SB' | 'D5' | ... #returns dictionary of ring outcomes if target[0:2] == 'SB': #single bull return {'SB': 1 - miss, 'DB': miss * 0.25, 'S': miss * 0.75} elif target[0:2] == 'DB': #double bull return {'DB': 1 - miss * 3, 'SB': miss * 3 * 1./3, 'S': miss * 3 * 2./3} elif target[0] == 'T': #triple ring return {'T': 1 - miss, 'S': miss} elif target[0] == 'D': #double ring return {'D': 1- miss, 'S': miss * 0.5} #OFF = miss * 0.5 elif target[0] == 'S': #single ring return {'S': 1 - (miss / 5), 'D': (miss / 5) * 0.5, 'T': (miss / 5) * 0.5} else: #should not occur return {} def section_outcome(target, miss): #target = 'T20' | 'SB' | 'D5' | ... #returns dictionary of section outcomes clockwise = [20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12, 5] misstargets = dict((str(clockwise[i]), (str(5),str(1))) if i == 1 else (str(clockwise[i]), (str(12),str(20))) if i == 19 else (str(clockwise[i]), (str(clockwise[i - 1]),str(clockwise[i + 1]))) for i in range(20)) if target[0:2] in ['SB', 'DB']: d = dict((str(i), miss / 20) for i in range(1,21)) d['B'] = 1 - miss return d else: section = target[1:] leftmiss = misstargets[section][0] rightmiss = misstargets[section][1] return {section: 1 - miss, leftmiss: miss * 0.5, rightmiss: miss * 0.5} def best_target(miss): "Return the target that maximizes the expected score." #[(60, 'T20', 'T'), (57, 'T19', 'T'), ...,(50, 'DB', 'D'), ...,(19, 'S19', 'S'),...] targets = getTargets() #first we create a dictionary (target: value) e.g. ('T20': 60) valueDict = dict((target[1], target[0]) for target in targets) return max(getAverageScore(target[1], miss, valueDict) for target in targets)[1] def getAverageScore(target, miss, valueDict): #returns a tuple of format (score, target) e.g. (17.5,'T20') so we can use max function easily target_outcome = outcome(target, miss) score = 0 for entry in target_outcome.items(): miss_target = entry[0] probability = entry[1] score += probability * valueDict[miss_target] return (score, target) def same_outcome(dict1, dict2): "Two states are the same if all corresponding sets of locs are the same." return all(abs(dict1.get(key, 0) - dict2.get(key, 0)) <= 0.0001 for key in set(dict1) | set(dict2)) def test_darts2(): assert best_target(0.0) == 'T20' assert best_target(0.1) == 'T20' assert best_target(0.4) == 'T19' assert same_outcome(outcome('T20', 0.0), {'T20': 1.0}) assert same_outcome(outcome('T20', 0.1), {'T20': 0.81, 'S1': 0.005, 'T5': 0.045, 'S5': 0.005, 'T1': 0.045, 'S20': 0.09})

## No comments:

## Post a Comment