#!/usr/bin/python3
__author__ = 'dnkywin'

RUN = 1
PASS = 2

""" EVALUATION FUNCTION """

def p_win(p1_bot, p2_bot, n_rounds):
    # Determine the probability of winning when one bot goes against another.
    #
    # Each bot is a function that takes in the
    # current point differential and the number of rounds left
    # and returns either RUN or PASS
    #
    # If either p1_bot or p2_bot is None, then
    # we replace it by cheater_bot, which cheats by looking at the future
    # evaluation function.

    # We memoize to speed up computation
    cache = {}
    def evaluate(diff, rounds_left):
        if rounds_left == 0:
            if diff < 0:
                return 0
            elif diff > 0:
                return 2
            else:
                return 1
        try:
            return cache[(diff, rounds_left)]
        except KeyError:
            pass

        bot = bots[(n_rounds - rounds_left) % 2]
        sz = bot(diff, rounds_left)
        val = -evaluate(sz - diff, rounds_left - 1) - evaluate(-sz - diff, rounds_left - 1)
        cache[(diff, rounds_left)] = val
        return val

    if p1_bot is None:
        p1_bot = cheater_bot(evaluate)

    if p2_bot is None:
        p2_bot = cheater_bot(evaluate)

    bots = [p1_bot, p2_bot]

    return evaluate(0, n_rounds) / (2 ** (n_rounds + 1))

""" BOTS """

def run_bot(diff, rounds_left):
    # always runs
    return RUN

def pass_bot(diff, rounds_left):
    # always passes
    return PASS

def pass_exploit_bot(diff, rounds_left):
    # best bot against the pass
    if diff < 0:
        if (diff + 2 * rounds_left) % 4 <= 1:
            return PASS
        else:
            return RUN
    elif diff == 1 and (rounds_left % 4 == 0 or
                          (rounds_left % 2 == 0 and rounds_left <= 16)):
        return PASS
    else:
        return RUN

def run_exploit_bot(diff, rounds_left):
    # best bot against the run
    if diff > 0 or (diff == -1 and rounds_left % 4 == 0):
        return RUN
    elif diff < 0:
        return PASS
    else:
        if rounds_left % 2 == 0:
            return PASS
        else:
            return RUN

def optimal_bot(diff, rounds_left):
    # The optimal strategy where both players are maximizing their score.
    if diff > 0:
        return RUN
    elif diff < 0:
        return PASS
    else:
        return PASS if rounds_left % 4 == 0 else RUN

def cheater_bot(ev):
    # cheats by looking at the future evaluation function
    def get_action(diff, rounds_left):
        payoff1 = -ev(1 - diff, rounds_left - 1) - ev(-1 - diff, rounds_left - 1)
        payoff2 = -ev(2 - diff, rounds_left - 1) - ev(-2 - diff, rounds_left - 1)
        return RUN if payoff1 > payoff2 else PASS
    return get_action

""" MAIN PROGRAM """

def main():
    n_rounds = 100

    # show that optimal_bot is optimal
    p_opt = p_win(None, None, n_rounds)
    print("OPTIMAL PLAY: %.16f" % p_opt)
    assert p_win(optimal_bot, None, n_rounds) == p_opt
    assert p_win(None, optimal_bot, n_rounds) == p_opt
    assert p_win(optimal_bot, optimal_bot, n_rounds) == p_opt

    # show that run_exploit_bot is the best possible against run_bot
    p1_run_opt = p_win(None, run_bot, n_rounds)
    print("P1 VS RUN: %.16f" % p1_run_opt)
    assert p_win(run_exploit_bot, run_bot, n_rounds) == p1_run_opt

    p2_run_opt = 1.0 - p_win(run_bot, None, n_rounds)
    print("P2 VS RUN: %.16f" % p2_run_opt)
    assert 1.0 - p_win(run_bot, run_exploit_bot, n_rounds) == p2_run_opt

    # show that pass_exploit_bot is the best possible against pass_bot
    p1_pass_opt = p_win(None, pass_bot, n_rounds)
    print("P1 VS PASS: %.16f" % p1_pass_opt)
    assert p_win(pass_exploit_bot, pass_bot, n_rounds) == p1_pass_opt

    p2_pass_opt = 1.0 - p_win(pass_bot, None, n_rounds)
    print("P2 VS PASS: %.16f" % p2_pass_opt)
    assert 1.0 - p_win(pass_bot, pass_exploit_bot, n_rounds) == p2_pass_opt

if __name__ == '__main__':
    main()