Advertisement
Guest User

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[0].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()
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement