 # 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()