Coinball

#!/usr/bin/python3
from fractions import Fraction

# Bit of a hack - using this as a number just counts as 2, so this
# is basically saying "choose pass if it doesn't matter either way"
# but this lets us tell if a choice is irrelevant for the chart
class Irrelevant(int):
    pass
Irrelevant = Irrelevant(2)

def strategy_rush(state, score, player1):
    return 1

def strategy_pass(state, score, player1):
    return 2

def strategy_optimal(state, score, player1):
    pwin_rush = state.get_probability_turn(score, 1)
    pwin_pass = state.get_probability_turn(score, 2)
    rush_benefit = pwin_rush - pwin_pass
    if not player1:
        rush_benefit = -rush_benefit
    if rush_benefit > 0:
        return 1
    elif rush_benefit < 0:
        return 2
    else:
        return Irrelevant

class TurnState:
    def __init__(self, strategy1, strategy2, nturns, turnix, probabilities, behaviours):
        self.strategy1 = strategy1  # strategy for player 1
        self.strategy2 = strategy2  # strategy for player 2
        self.nturns = nturns  # total number of turns in the game
        self.turnix = turnix  # turn index of this state object
        self.probabilities = probabilities  # dictionary of scores to probability of player 1 winning
        self.behaviours = behaviours  # dictionary of scores to the player's choice under their strategy
        self.minreach = None  # the lowest score difference reachable at this point
        self.maxreach = None  # the highest score difference reachable at this point

    def get_probability(self, score):
        """
        Return the probability of player 1 winning given the score this turn.
        """
        if score in self.probabilities:
            return self.probabilities[score]
        # if score is outside the range in probabilities, then it's a foregone conclusion
        # ie score difference is too broad to make up in the remaining turns
        elif score < 0:
            return Fraction(0)
        else:
            return Fraction(1)

    def get_probability_turn(self, score, behaviour):
        """
        Return the probability of player 1 winning given the score and player's
        behaviour from the previous turn.
        """
        return (self.get_probability(score - behaviour) +
            self.get_probability(score + behaviour)) / 2

    def get_behaviour(self, score):
        """
        Return the player's behaviour at this turn given the score.

        Returns None if irrelevant as the game is a foregone conclusion.
        """
        return self.behaviours.get(score)

    def get_predecessor(self):
        """
        Given this state for turn index turnix, generate the state for turn index turnix-1.
        """
        player1 = (self.turnix % 2 != 0)
        strategy = self.strategy1 if player1 else self.strategy2
        # Any score difference beyond this is too large to overcome in the time remaining
        maxrange = 2 * (self.nturns - self.turnix + 1)
        newprobabilities = {}
        newbehaviours = {}
        for score in range(-maxrange, maxrange+1):
            newbehaviours[score] = strategy(self, score, player1)
            newprobabilities[score] = self.get_probability_turn(score, newbehaviours[score])
        return TurnState(self.strategy1, self.strategy2, self.nturns,
            self.turnix - 1, newprobabilities, newbehaviours)

def coinball_table(strategy1, strategy2, nturns=100):
    """
    Given the strategies for players 1 and 2, gives the resulting table of
    probabilities and behaviours.
    """
    # Generate the state for after the final coin toss
    state = TurnState(strategy1, strategy2, nturns, nturns,
        {0: Fraction(1,2)}, # call exact ties as worth half a point
        {0: True}, # colour the perfect-tie square with the "irrelevant" option
    )
    # Generate all the previous states back to the start of the game
    table = [state]
    for i in range(nturns):
        state = state.get_predecessor()
        table.append(state)
    table.reverse()
    # Determine what states are reachable from the initial point
    minreach = maxreach = 0
    for state in table:
        state.minreach = minreach
        state.maxreach = maxreach
        behaviour = state.get_behaviour(minreach)
        if behaviour is not None:
            minreach -= behaviour
        behaviour = state.get_behaviour(maxreach)
        if behaviour is not None:
            maxreach += behaviour
    return table

SCALE = 5
COL_RUSH = "0 204 0"
COL_PUSH = "255 0 0"
COL_IRRELEVANT = "153 153 0"
COL_UNREACH = "102 102 102"
COL_WON = "102 102 102"
COL_LOST = "102 102 102"
COL_AXIS = ["0 0 0", "0 0 0", "255 255 255", "255 255 255"]
def generate_image(fn, table, offset):
    """
    Given the state table from coinball_table, generate a PNM
    """
    with open(fn, "w") as fp:
        xmin = table[-1].minreach - 5
        xmax = table[-1].maxreach + 5
        fp.write("P3\n%d %d\n%d\n" % ((xmax - xmin + 1) * SCALE, (len(table) - offset + 1) // 2 * SCALE, 255))
        for state in table[offset::2]:
            row = []
            y = 0
            for x in range(xmin, xmax+1):
            else:
                if x < state.minreach or x > state.maxreach:
                    c = COL_UNREACH
                else:
                    b = state.get_behaviour(x)
                    if b is None:
                        c = COL_WON if x > 0 else COL_LOST
                    elif b is Irrelevant:
                        c = COL_IRRELEVANT
                    elif b == 2:
                        c = COL_PUSH
                    elif b == 1:
                        c = COL_RUSH

                if x == 0:
                    row.extend([c] * (SCALE // 2))
                    row.append("%s")
                    row.extend([c] * ((SCALE - 1) // 2))
                else:
                    row.extend([c] * SCALE)
            row = ' '.join(row) + "\n"
            for i in range(SCALE):
                fp.write(row % COL_AXIS[y])
                y = (y + 1) % len(COL_AXIS)

def go(strategy1, strategy2, fn):
    table = coinball_table(strategy1, strategy2)
    generate_image("/tmp/%s_1.ppm" % fn, table, 0)
    generate_image("/tmp/%s_2.ppm" % fn, table, 1)
    p = table[0].get_probability(0)
    print(fn)
    print("  player 1 - %s (%.10f)" % (p, 100*p))
    print("  player 2 - %s (%.10f)" % (1 - p, 100*(1 - p)))

def main():
    go(strategy_optimal, strategy_rush, "first_vs_rush")
    go(strategy_rush, strategy_optimal, "second_vs_rush")
    go(strategy_optimal, strategy_pass, "first_vs_pass")
    go(strategy_pass, strategy_optimal, "second_vs_pass")
    go(strategy_optimal, strategy_optimal, "optimal_mirror")

if __name__ == '__main__':
    main()