New XKCD Forums

Code: Select all

__doc__ = '''
Submission for round 2 of the "Programming challenges" forum game,
organized by phillip1882 at ramenchef.net/nxf.

Author: Jplus

Usage: at the start of each match, create a new instance of the final
strategy:

    playAsJplus = JplusStrategy()

This instance can be called at every turn, as specified in the task
description:

    next_move = playAsJplus(i, mymoves, myopp)
'''

from operator import itemgetter, methodcaller

ROCK, PAPER, SCISSORS = 0, 1, 2
LOSS, TIE, WIN = 2, 0, 1
INTERPRETATION = {
    'r': ROCK,
    'p': PAPER,
    's': SCISSORS,
    '0': ROCK,
    '1': PAPER,
    '2': SCISSORS,
}
REPRESENTATION = ['rock', 'paper', 'scissors']
ROUND_MISMATCH_MESSAGE = '''
The round number is less than the expected round number. Did you
create a new instance of the strategy before starting the match?
'''


def outcome(ours, theirs):
    """ Given our and their moves, what is the outcome for us? """
    return (ours - theirs) % 3


def beat(theirs):
    """ Given their move, what should be played to beat it? """
    return (theirs + 1) % 3


def beaten(ours):
    """ Given our move, what opponent move would have been beaten? """
    return (ours - 1) % 3


def same(value):
    """ An identity function. """
    return value


def blank_tally():
    """ Empty frequency table for initializing a tally. """
    return {ROCK: 0, PAPER: 0, SCISSORS: 0}


def most_frequent(tally):
    """ Given a frequency table, return the most prevalent move. """
    return max(tally.items(), key=itemgetter(1))[0]


class Strategy(object):
    """
    Base class for playing strategies.

    A strategy is initialized once for each match and can then be called as a
    function for each turn. The call signature is (round_number,
    opponent_moves, own_moves), as specified in the challenge description of
    round 2. The use of a callable class instance instead of a bare function
    makes it possible to build the opponent model incrementally, so that moves
    can be decided efficiently even after many turns.

    A child class must at least define a predict method, which attempts to
    guess what the opponent will play. This method takes no arguments and
    should base its answer purely on an internal model, however simple. The
    move that ends up being played is always beat(self.predict()).

    Optionally, child classes may also override the observe method in order to
    build their internal model. This method takes two arguments: the opponent's
    move in the previous turn, and the own move in the previous turn. Any
    return vaue is ignored.

    All playing strategies keep track of how many turns they have seen and how
    accurate their prediction of the opponent's moves has been so far. This is
    taking care of automatically in the __call__ method.
    """

    def __init__(self):
        self.turn = 0
        self.score = 0

    def __call__(self, round, their_history, our_history):
        assert round == self.turn, ROUND_MISMATCH_MESSAGE
        if round > 0:
            theirs, ours = their_history[-1], our_history[-1]
            self.observe(theirs, ours)
            previous_result = outcome(ours, theirs)
            if previous_result == LOSS:
                self.score -= 1
            elif previous_result == WIN:
                self.score += 1
        guess = self.predict()
        self.turn += 1
        return beat(guess)

    def weighted_call(self, round, their_history, our_history):
        move = self(round, their_history, our_history)
        return self.accuracy(), move

    def observe(self, theirs, ours):
        pass

    def accuracy(self):
        if self.turn < 1:
            return 0
        return self.score / self.turn

    def arbitrary(self):
        return self.turn % 3


def reflect(base):
    """ Given a statistical strategy, return a strategy that counters it. """
    class Reflective(base):
        def observe(self, theirs, ours):
            super().observe(ours, theirs)

        def predict(self):
            their_prediction = super().predict()
            return beat(their_prediction)

    Reflective.__name__ += base.__name__
    return Reflective


class Constant(Strategy):
    """ A strategy that always repeats the same arbitrary move. """

    def __init__(self, move=ROCK):
        super().__init__()
        self.prediction = beaten(move)

    def predict(self):
        return self.prediction


class AntiConstant(Strategy):
    """ Assume that the opponent is biased towards a particular move. """

    def __init__(self):
        super().__init__()
        self.tally = blank_tally()

    def observe(self, theirs, ours):
        self.tally[theirs] += 1

    def predict(self):
        return most_frequent(self.tally)


ReflectiveAntiConstant = reflect(AntiConstant)


class Rotate(Strategy):
    """ A strategy that rotates through the possible moves. """

    def __init__(self, first=ROCK, retrograde=False):
        super().__init__()
        self.first = first
        self.retrograde = retrograde

    def predict(self):
        current = self.turn % 3
        if current > 0 and self.retrograde:
            current = 3 - current
        shifted = (current + self.first) % 3
        return beaten(shifted)


class AntiRotate(Strategy):
    """ Assume that the opponent cycles through the possible moves. """

    def __init__(self):
        super().__init__()
        self.tally = blank_tally()
        self.previous = None

    def observe(self, theirs, ours):
        if self.previous is not None:
            offset = outcome(theirs, self.previous)
            self.tally[offset] += 1
        self.previous = theirs

    def predict(self):
        previous = self.previous
        if previous is None:
            return self.arbitrary()
        offset = most_frequent(self.tally)
        return (previous + offset) % 3


ReflectiveAntiRotate = reflect(AntiRotate)


class Reactive(Strategy):
    """ Respond to the opponent's previous move by a fixed offset. """

    def __init__(self, initial=ROCK, offset=same):
        super().__init__()
        self.previous = offset(offset(initial))
        self.offset = offset

    def observe(self, theirs, ours):
        self.previous = theirs

    def predict(self):
        intended_move = self.offset(self.previous)
        return beaten(intended_move)


class AntiReactive(AntiRotate):
    """ Assume that the opponent responds to our moves by a fixed offset. """

    def observe(self, theirs, ours):
        if self.previous:
            offset = outcome(theirs, self.previous)
            self.tally[offset] += 1
        # A subtle but crucial difference with AntiRotate
        self.previous = ours


ReflectiveAntiReactive = reflect(AntiReactive)


class Human(Strategy):
    """ Represent a human player by asking for input. """

    def observe(self, theirs, ours):
        self.previous = theirs

    def predict(self):
        if hasattr(self, 'previous'):
            print('Opponent\'s move:', REPRESENTATION[self.previous])
        move = INTERPRETATION[input('Your move: ').strip().lower()[0]]
        return beaten(move)


class MarkovChain(Strategy):
    """
    Base the move on a pattern frequency analysis of the opponent.

    Defeats all of the above strategies.
    """

    def __init__(self, stride=4):
        super().__init__()
        self.stride = stride
        self.window = ()
        self.tally = {}

    def observe(self, theirs, ours):
        if self.turn >= self.stride:
            tally = self.tally.get(self.window, blank_tally())
            tally[theirs] += 1
            self.tally[self.window] = tally
            self.window = (*self.window[1:], theirs)
        else:
            self.window = (*self.window, theirs)

    def predict(self):
        tally = self.tally.get(self.window)
        if tally is None:
            return self.arbitrary()
        return most_frequent(tally)


ReflectiveMarkovChain = reflect(MarkovChain)


class JplusStrategy(Strategy):
    """ Counter all of the above strategies. """

    def __init__(self):
        super().__init__()
        self.candidates = [
            MarkovChain(),
            ReflectiveMarkovChain(),
        ]

    def __call__(self, round, their, our):
        # Update this strategy's accuracy, ignoring the prediction.
        super().__call__(round, their, our)
        # Defer the actual move to the best performing candidate.
        forward = methodcaller('weighted_call', round, their, our)
        return max(map(forward, self.candidates), key=itemgetter(0))[1]

    def predict(self):
        # This method needs to be defined, but we never actually use the value.
        return ROCK


def play_match(player1, player2):
    """ Run a match between two strategy instances. """
    moves1, moves2 = [], []
    for round in range(5000):
        try:
            move1 = player1(round, moves2, moves1)
            move2 = player2(round, moves1, moves2)
            moves1.append(move1)
            moves2.append(move2)
        except KeyboardInterrupt:
            break
    return moves1, moves2


def print_match(player1, player2, moves1, moves2):
    """ Show the results of a match to stdout. """
    print('Player 1 accuracy:', player1.accuracy())
    print('Player 2 accuracy:', player2.accuracy())
    print()
    for round, (move1, move2) in enumerate(zip(moves1, moves2)):
        if round == 60:
            break
        show1 = REPRESENTATION[move1]
        show2 = REPRESENTATION[move2]
        print('{}: {}, {}'.format(round, show1, show2))


# Run the module to try the strategy against yourself!
if __name__ == '__main__':
    opponent = Human()
    self = JplusStrategy()
    moves = play_match(opponent, self)
    print_match(opponent, self, *moves)