The Dowry Problem (Part 2)

# https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1529778760
import random

NUM_GAMES = 100000
NUM_SLIPS = 200

def main():
  print 'NUM_GAMES = %d, NUM_SLIPS = %d' % (NUM_GAMES, NUM_SLIPS)
  print_win_ratios([
    RandomStrategy(),
    RmsStrategy(),
    RmsStrategyWithWiggle(-.001),
    RmsStrategyWithWiggle(-.002),
    RmsStrategyWithWiggle(-.003),
    RmsStrategyWithWiggle(-.004),
    TowrStrategy(),
  ])

def print_win_ratios(strategies):
  num_wins = [0 for j in range(len(strategies))]
  for i in range(NUM_GAMES):
    slips = [random.random() for i in range(NUM_SLIPS)]
    for j in range(len(strategies)):
      if play_game(strategies[j], slips):
        num_wins[j] += 1
  for j in range(len(strategies)):
    win_ratio = num_wins[j] / (NUM_GAMES + 0.0)
    print '%s: win ratio = %0.4f' % (strategies[j].name(), win_ratio)

def play_game(strategy, slips):
  winning_slip_index = slips.index(max(slips))

  # Play the game.
  strategy.new_game(len(slips))
  for i in range(len(slips)):
    strategy_chose = strategy.should_choose(i, slips[i])
    if strategy_chose:
      # Game ends, return if the strategy won.
      return i == winning_slip_index

  # The strategy didn't choose.
  return False

# Choose a random index and choose it, no matter what its value.
class RandomStrategy:
  def __init__(self):
    self.slip_choice_index = 0

  def name(self):
    return 'RandomStrategy'

  def new_game(self, num_slips):
    self.slip_choice_index = random.randint(0, num_slips - 1)

  def should_choose(self, slip_index, slip):
    return slip_index == self.slip_choice_index

# Choose a slip if it is greater than a given cutoff. The cutoffs are indexed on
# the sample index and are computed from the number of slips.
class CutoffStrategy:
  def __init__(self, my_name, cutoff_lambda):
    self.my_name = my_name
    self.cutoff_lambda = cutoff_lambda
    self.cutoffs = []
    self.num_slips = 0
    self.best_so_far = 0

  def name(self):
    return self.my_name

  def new_game(self, num_slips):
    self.cutoffs = self.cutoff_lambda(num_slips)
    self.num_slips = num_slips
    self.best_so_far = 0

  def should_choose(self, slip_index, slip):
    if self.best_so_far > slip:
      # If we've seen better before, we can't choose this one.
      return False
    self.best_so_far = slip
    if slip >= self.cutoffs[slip_index]:
      return True
    if slip_index == self.num_slips - 1:
      # Last slip, might as well guess.
      return True

# Choose the first slip greater than (num_slips - 1) / (num_slips) + wiggle.
class RmsStrategyWithWiggle(CutoffStrategy):
  def __init__(self, wiggle):
    CutoffStrategy.__init__(
        self,
        'RmsStrategyWithWiggle%.3f' % wiggle,
        lambda num_slips: [
          ((num_slips - 1.0) / num_slips) + wiggle for i in range(num_slips)
        ])

# Choose the first slip greater than (num_slips - 1) / (num_slips).
class RmsStrategy(CutoffStrategy):
  def __init__(self):
    CutoffStrategy.__init__(
        self,
        'RmsStrategy',
        lambda num_slips: [
          (num_slips - 1.0) / num_slips for i in range(num_slips)
        ])

# Choose a slip if there's a >=50% chance of there being a better one later.
class TowrStrategy(CutoffStrategy):
  def __init__(self):
    CutoffStrategy.__init__(
        self,
        'TowrStrategy',
        lambda num_slips: [
          0.5 ** (1.0 / (num_slips - i - 1)) if i < num_slips - 1 else 0
              for i in range(num_slips)
        ])

if __name__ == '__main__':
  main()