 # Coinball

a guest
Oct 14th, 2017
384
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/python3
2. from fractions import Fraction
3.
4. # Bit of a hack - using this as a number just counts as 2, so this
5. # is basically saying "choose pass if it doesn't matter either way"
6. # but this lets us tell if a choice is irrelevant for the chart
7. class Irrelevant(int):
8.     pass
9. Irrelevant = Irrelevant(2)
10.
11. def strategy_rush(state, score, player1):
12.     return 1
13.
14. def strategy_pass(state, score, player1):
15.     return 2
16.
17. def strategy_optimal(state, score, player1):
18.     pwin_rush = state.get_probability_turn(score, 1)
19.     pwin_pass = state.get_probability_turn(score, 2)
20.     rush_benefit = pwin_rush - pwin_pass
21.     if not player1:
22.         rush_benefit = -rush_benefit
23.     if rush_benefit > 0:
24.         return 1
25.     elif rush_benefit < 0:
26.         return 2
27.     else:
28.         return Irrelevant
29.
30. class TurnState:
31.     def __init__(self, strategy1, strategy2, nturns, turnix, probabilities, behaviours):
32.         self.strategy1 = strategy1  # strategy for player 1
33.         self.strategy2 = strategy2  # strategy for player 2
34.         self.nturns = nturns  # total number of turns in the game
35.         self.turnix = turnix  # turn index of this state object
36.         self.probabilities = probabilities  # dictionary of scores to probability of player 1 winning
37.         self.behaviours = behaviours  # dictionary of scores to the player's choice under their strategy
38.         self.minreach = None  # the lowest score difference reachable at this point
39.         self.maxreach = None  # the highest score difference reachable at this point
40.
41.     def get_probability(self, score):
42.         """
43.         Return the probability of player 1 winning given the score this turn.
44.         """
45.         if score in self.probabilities:
46.             return self.probabilities[score]
47.         # if score is outside the range in probabilities, then it's a foregone conclusion
48.         # ie score difference is too broad to make up in the remaining turns
49.         elif score < 0:
50.             return Fraction(0)
51.         else:
52.             return Fraction(1)
53.
54.     def get_probability_turn(self, score, behaviour):
55.         """
56.         Return the probability of player 1 winning given the score and player's
57.         behaviour from the previous turn.
58.         """
59.         return (self.get_probability(score - behaviour) +
60.             self.get_probability(score + behaviour)) / 2
61.
62.     def get_behaviour(self, score):
63.         """
64.         Return the player's behaviour at this turn given the score.
65.
66.         Returns None if irrelevant as the game is a foregone conclusion.
67.         """
68.         return self.behaviours.get(score)
69.
70.     def get_predecessor(self):
71.         """
72.         Given this state for turn index turnix, generate the state for turn index turnix-1.
73.         """
74.         player1 = (self.turnix % 2 != 0)
75.         strategy = self.strategy1 if player1 else self.strategy2
76.         # Any score difference beyond this is too large to overcome in the time remaining
77.         maxrange = 2 * (self.nturns - self.turnix + 1)
78.         newprobabilities = {}
79.         newbehaviours = {}
80.         for score in range(-maxrange, maxrange+1):
81.             newbehaviours[score] = strategy(self, score, player1)
82.             newprobabilities[score] = self.get_probability_turn(score, newbehaviours[score])
83.         return TurnState(self.strategy1, self.strategy2, self.nturns,
84.             self.turnix - 1, newprobabilities, newbehaviours)
85.
86. def coinball_table(strategy1, strategy2, nturns=100):
87.     """
88.     Given the strategies for players 1 and 2, gives the resulting table of
89.     probabilities and behaviours.
90.     """
91.     # Generate the state for after the final coin toss
92.     state = TurnState(strategy1, strategy2, nturns, nturns,
93.         {0: Fraction(1,2)}, # call exact ties as worth half a point
94.         {0: True}, # colour the perfect-tie square with the "irrelevant" option
95.     )
96.     # Generate all the previous states back to the start of the game
97.     table = [state]
98.     for i in range(nturns):
99.         state = state.get_predecessor()
100.         table.append(state)
101.     table.reverse()
102.     # Determine what states are reachable from the initial point
103.     minreach = maxreach = 0
104.     for state in table:
105.         state.minreach = minreach
106.         state.maxreach = maxreach
107.         behaviour = state.get_behaviour(minreach)
108.         if behaviour is not None:
109.             minreach -= behaviour
110.         behaviour = state.get_behaviour(maxreach)
111.         if behaviour is not None:
112.             maxreach += behaviour
113.     return table
114.
115. SCALE = 5
116. COL_RUSH = "0 204 0"
117. COL_PUSH = "255 0 0"
118. COL_IRRELEVANT = "153 153 0"
119. COL_UNREACH = "102 102 102"
120. COL_WON = "102 102 102"
121. COL_LOST = "102 102 102"
122. COL_AXIS = ["0 0 0", "0 0 0", "255 255 255", "255 255 255"]
123. def generate_image(fn, table, offset):
124.     """
125.     Given the state table from coinball_table, generate a PNM
126.     """
127.     with open(fn, "w") as fp:
128.         xmin = table[-1].minreach - 5
129.         xmax = table[-1].maxreach + 5
130.         fp.write("P3\n%d %d\n%d\n" % ((xmax - xmin + 1) * SCALE, (len(table) - offset + 1) // 2 * SCALE, 255))
131.         for state in table[offset::2]:
132.             row = []
133.             y = 0
134.             for x in range(xmin, xmax+1):
135.             else:
136.                 if x < state.minreach or x > state.maxreach:
137.                     c = COL_UNREACH
138.                 else:
139.                     b = state.get_behaviour(x)
140.                     if b is None:
141.                         c = COL_WON if x > 0 else COL_LOST
142.                     elif b is Irrelevant:
143.                         c = COL_IRRELEVANT
144.                     elif b == 2:
145.                         c = COL_PUSH
146.                     elif b == 1:
147.                         c = COL_RUSH
148.
149.                 if x == 0:
150.                     row.extend([c] * (SCALE // 2))
151.                     row.append("%s")
152.                     row.extend([c] * ((SCALE - 1) // 2))
153.                 else:
154.                     row.extend([c] * SCALE)
155.             row = ' '.join(row) + "\n"
156.             for i in range(SCALE):
157.                 fp.write(row % COL_AXIS[y])
158.                 y = (y + 1) % len(COL_AXIS)
159.
160. def go(strategy1, strategy2, fn):
161.     table = coinball_table(strategy1, strategy2)
162.     generate_image("/tmp/%s_1.ppm" % fn, table, 0)
163.     generate_image("/tmp/%s_2.ppm" % fn, table, 1)
164.     p = table.get_probability(0)
165.     print(fn)
166.     print("  player 1 - %s (%.10f)" % (p, 100*p))
167.     print("  player 2 - %s (%.10f)" % (1 - p, 100*(1 - p)))
168.
169. def main():
170.     go(strategy_optimal, strategy_rush, "first_vs_rush")
171.     go(strategy_rush, strategy_optimal, "second_vs_rush")
172.     go(strategy_optimal, strategy_pass, "first_vs_pass")
173.     go(strategy_pass, strategy_optimal, "second_vs_pass")
174.     go(strategy_optimal, strategy_optimal, "optimal_mirror")
175.
176. if __name__ == '__main__':
177.     main()