Advertisement
Guest User

The Dowry Problem (Part 2)

a guest
Jul 7th, 2018
180
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1529778760
  2. import random
  3.  
  4. NUM_GAMES = 100000
  5. NUM_SLIPS = 200
  6.  
  7. def main():
  8.   print 'NUM_GAMES = %d, NUM_SLIPS = %d' % (NUM_GAMES, NUM_SLIPS)
  9.   print_win_ratios([
  10.     RandomStrategy(),
  11.     RmsStrategy(),
  12.     RmsStrategyWithWiggle(-.001),
  13.     RmsStrategyWithWiggle(-.002),
  14.     RmsStrategyWithWiggle(-.003),
  15.     RmsStrategyWithWiggle(-.004),
  16.     TowrStrategy(),
  17.   ])
  18.  
  19. def print_win_ratios(strategies):
  20.   num_wins = [0 for j in range(len(strategies))]
  21.   for i in range(NUM_GAMES):
  22.     slips = [random.random() for i in range(NUM_SLIPS)]
  23.     for j in range(len(strategies)):
  24.       if play_game(strategies[j], slips):
  25.         num_wins[j] += 1
  26.   for j in range(len(strategies)):
  27.     win_ratio = num_wins[j] / (NUM_GAMES + 0.0)
  28.     print '%s: win ratio = %0.4f' % (strategies[j].name(), win_ratio)
  29.  
  30. def play_game(strategy, slips):
  31.   winning_slip_index = slips.index(max(slips))
  32.  
  33.   # Play the game.
  34.   strategy.new_game(len(slips))
  35.   for i in range(len(slips)):
  36.     strategy_chose = strategy.should_choose(i, slips[i])
  37.     if strategy_chose:
  38.       # Game ends, return if the strategy won.
  39.       return i == winning_slip_index
  40.  
  41.   # The strategy didn't choose.
  42.   return False
  43.  
  44. # Choose a random index and choose it, no matter what its value.
  45. class RandomStrategy:
  46.   def __init__(self):
  47.     self.slip_choice_index = 0
  48.  
  49.   def name(self):
  50.     return 'RandomStrategy'
  51.  
  52.   def new_game(self, num_slips):
  53.     self.slip_choice_index = random.randint(0, num_slips - 1)
  54.  
  55.   def should_choose(self, slip_index, slip):
  56.     return slip_index == self.slip_choice_index
  57.  
  58. # Choose a slip if it is greater than a given cutoff. The cutoffs are indexed on
  59. # the sample index and are computed from the number of slips.
  60. class CutoffStrategy:
  61.   def __init__(self, my_name, cutoff_lambda):
  62.     self.my_name = my_name
  63.     self.cutoff_lambda = cutoff_lambda
  64.     self.cutoffs = []
  65.     self.num_slips = 0
  66.     self.best_so_far = 0
  67.  
  68.   def name(self):
  69.     return self.my_name
  70.  
  71.   def new_game(self, num_slips):
  72.     self.cutoffs = self.cutoff_lambda(num_slips)
  73.     self.num_slips = num_slips
  74.     self.best_so_far = 0
  75.  
  76.   def should_choose(self, slip_index, slip):
  77.     if self.best_so_far > slip:
  78.       # If we've seen better before, we can't choose this one.
  79.       return False
  80.     self.best_so_far = slip
  81.     if slip >= self.cutoffs[slip_index]:
  82.       return True
  83.     if slip_index == self.num_slips - 1:
  84.       # Last slip, might as well guess.
  85.       return True
  86.  
  87. # Choose the first slip greater than (num_slips - 1) / (num_slips) + wiggle.
  88. class RmsStrategyWithWiggle(CutoffStrategy):
  89.   def __init__(self, wiggle):
  90.     CutoffStrategy.__init__(
  91.         self,
  92.         'RmsStrategyWithWiggle%.3f' % wiggle,
  93.         lambda num_slips: [
  94.           ((num_slips - 1.0) / num_slips) + wiggle for i in range(num_slips)
  95.         ])
  96.  
  97. # Choose the first slip greater than (num_slips - 1) / (num_slips).
  98. class RmsStrategy(CutoffStrategy):
  99.   def __init__(self):
  100.     CutoffStrategy.__init__(
  101.         self,
  102.         'RmsStrategy',
  103.         lambda num_slips: [
  104.           (num_slips - 1.0) / num_slips for i in range(num_slips)
  105.         ])
  106.  
  107. # Choose a slip if there's a >=50% chance of there being a better one later.
  108. class TowrStrategy(CutoffStrategy):
  109.   def __init__(self):
  110.     CutoffStrategy.__init__(
  111.         self,
  112.         'TowrStrategy',
  113.         lambda num_slips: [
  114.           0.5 ** (1.0 / (num_slips - i - 1)) if i < num_slips - 1 else 0
  115.               for i in range(num_slips)
  116.         ])
  117.  
  118. if __name__ == '__main__':
  119.   main()
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement