Advertisement
Guest User

Untitled

a guest
Oct 15th, 2017
244
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/python3
  2. __author__ = 'dnkywin'
  3.  
  4. RUN = 1
  5. PASS = 2
  6.  
  7. """ EVALUATION FUNCTION """
  8.  
  9. def p_win(p1_bot, p2_bot, n_rounds):
  10.     # Determine the probability of winning when one bot goes against another.
  11.     #
  12.     # Each bot is a function that takes in the
  13.     # current point differential and the number of rounds left
  14.     # and returns either RUN or PASS
  15.     #
  16.     # If either p1_bot or p2_bot is None, then
  17.     # we replace it by cheater_bot, which cheats by looking at the future
  18.     # evaluation function.
  19.    
  20.     # We memoize to speed up computation
  21.     cache = {}
  22.     def evaluate(diff, rounds_left):
  23.         if rounds_left == 0:
  24.             if diff < 0:
  25.                 return 0
  26.             elif diff > 0:
  27.                 return 2
  28.             else:
  29.                 return 1
  30.         try:
  31.             return cache[(diff, rounds_left)]
  32.         except KeyError:
  33.             pass
  34.  
  35.         bot = bots[(n_rounds - rounds_left) % 2]
  36.         sz = bot(diff, rounds_left)
  37.         val = -evaluate(sz - diff, rounds_left - 1) - evaluate(-sz - diff, rounds_left - 1)
  38.         cache[(diff, rounds_left)] = val
  39.         return val
  40.  
  41.     if p1_bot is None:
  42.         p1_bot = cheater_bot(evaluate)
  43.  
  44.     if p2_bot is None:
  45.         p2_bot = cheater_bot(evaluate)
  46.  
  47.     bots = [p1_bot, p2_bot]
  48.  
  49.     return evaluate(0, n_rounds) / (2 ** (n_rounds + 1))
  50.  
  51. """ BOTS """
  52.  
  53. def run_bot(diff, rounds_left):
  54.     # always runs
  55.     return RUN
  56.  
  57. def pass_bot(diff, rounds_left):
  58.     # always passes
  59.     return PASS
  60.  
  61. def pass_exploit_bot(diff, rounds_left):
  62.     # best bot against the pass
  63.     if diff < 0:
  64.         if (diff + 2 * rounds_left) % 4 <= 1:
  65.             return PASS
  66.         else:
  67.             return RUN
  68.     elif diff == 1 and (rounds_left % 4 == 0 or
  69.                           (rounds_left % 2 == 0 and rounds_left <= 16)):
  70.         return PASS
  71.     else:
  72.         return RUN
  73.  
  74. def run_exploit_bot(diff, rounds_left):
  75.     # best bot against the run
  76.     if diff > 0 or (diff == -1 and rounds_left % 4 == 0):
  77.         return RUN
  78.     elif diff < 0:
  79.         return PASS
  80.     else:
  81.         if rounds_left % 2 == 0:
  82.             return PASS
  83.         else:
  84.             return RUN
  85.  
  86. def optimal_bot(diff, rounds_left):
  87.     # The optimal strategy where both players are maximizing their score.
  88.     if diff > 0:
  89.         return RUN
  90.     elif diff < 0:
  91.         return PASS
  92.     else:
  93.         return PASS if rounds_left % 4 == 0 else RUN
  94.  
  95. def cheater_bot(ev):
  96.     # cheats by looking at the future evaluation function
  97.     def get_action(diff, rounds_left):
  98.         payoff1 = -ev(1 - diff, rounds_left - 1) - ev(-1 - diff, rounds_left - 1)
  99.         payoff2 = -ev(2 - diff, rounds_left - 1) - ev(-2 - diff, rounds_left - 1)
  100.         return RUN if payoff1 > payoff2 else PASS
  101.     return get_action
  102.  
  103. """ MAIN PROGRAM """
  104.  
  105. def main():
  106.     n_rounds = 100
  107.  
  108.     # show that optimal_bot is optimal
  109.     p_opt = p_win(None, None, n_rounds)
  110.     print("OPTIMAL PLAY: %.16f" % p_opt)
  111.     assert p_win(optimal_bot, None, n_rounds) == p_opt
  112.     assert p_win(None, optimal_bot, n_rounds) == p_opt
  113.     assert p_win(optimal_bot, optimal_bot, n_rounds) == p_opt
  114.  
  115.     # show that run_exploit_bot is the best possible against run_bot
  116.     p1_run_opt = p_win(None, run_bot, n_rounds)
  117.     print("P1 VS RUN: %.16f" % p1_run_opt)
  118.     assert p_win(run_exploit_bot, run_bot, n_rounds) == p1_run_opt
  119.  
  120.     p2_run_opt = 1.0 - p_win(run_bot, None, n_rounds)
  121.     print("P2 VS RUN: %.16f" % p2_run_opt)
  122.     assert 1.0 - p_win(run_bot, run_exploit_bot, n_rounds) == p2_run_opt
  123.  
  124.     # show that pass_exploit_bot is the best possible against pass_bot
  125.     p1_pass_opt = p_win(None, pass_bot, n_rounds)
  126.     print("P1 VS PASS: %.16f" % p1_pass_opt)
  127.     assert p_win(pass_exploit_bot, pass_bot, n_rounds) == p1_pass_opt
  128.  
  129.     p2_pass_opt = 1.0 - p_win(pass_bot, None, n_rounds)
  130.     print("P2 VS PASS: %.16f" % p2_pass_opt)
  131.     assert 1.0 - p_win(pass_bot, pass_exploit_bot, n_rounds) == p2_pass_opt
  132.  
  133. if __name__ == '__main__':
  134.     main()
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement