#!/usr/bin/env python # -*- coding: utf-8 -*- __author__ = 'Zachary Voase ' __version__ = '0.1' """ faceoff.py - A fun (non-serious) module for playing games. Example: >>> player1 = ExponentialBayesianTFTPlayer() >>> player2 = RandomPlayer() >>> game = PrisonersDilemma(player1, player2) >>> decisions = game.playoff(n=1000, generator=False) >>> results = (player1.score, player2.score) >>> isinstance(results[0], int), isinstance(results[1], int) (True, True) >>> tft_player1 = TitForTatPlayer() >>> tft_player2 = TitForTatPlayer() >>> tft_game = PrisonersDilemma(tft_player1, tft_player2) >>> tft_decisions = tft_game.playoff(n=1000, generator=False) >>> print (tft_player1.score == tft_player2.score) True """ from collections import deque from decimal import Decimal import random class Game(object): """An abstract base class representing a game-theoretical game.""" PAYOFF = {} def __init__(self, player1, player2): self.player1 = player1 self.player2 = player2 self.history = [] def play(self): # If there is no history, get the initial decisions. if not self.history: d1 = self.player1() d2 = self.player2() # Otherwise, tell each player what the other did in the previous round. else: d1 = self.player1(self.history[-1][1]) d2 = self.player2(self.history[-1][0]) # Add these decisions to the history. self.history.append((d1, d2)) payoff = self.PAYOFF[(d1, d2)] self.player1.score += payoff[0] self.player2.score += payoff[1] return (d1, d2) def playoff(self, n=1, generator=True): if generator: return (self.play() for i in xrange(n)) return [self.play() for i in xrange(n)] class PrisonersDilemma(Game): """ The prisoner's dilemma game. See . """ # True means co-operate, False means defect. COOP = True DEFECT = False PAYOFF = { (COOP, COOP): (3, 3), (COOP, DEFECT): (0, 5), (DEFECT, COOP): (5, 0), (DEFECT, DEFECT): (1, 1) } class Player(object): """An abstract base class for players of game-theoretical games.""" def __init__(self): self.score = 0 def __call__(self, op_last=None): raise NotImplementedError class CoroutinePlayer(Player): """ A Player which wraps around a coroutine; when called, an instance passes the opponent’s last move into the coroutine via `send()`, and the value yielded by the coroutine should be the player's decision. At the beginning of the game, `next()` will be called (so the coroutine can make an initial decision). """ generator = None @classmethod def wrapper(cls, generator): # Subclasses `CoroutinePlayer` to get a new class with the specified generator. return type( generator.__name__, (cls,), { '__module__': generator.__module__, '__doc__': generator.__doc__, # `staticmethod` is required to prevent the generator function # from being turned into an instance method. 'generator': staticmethod(generator) }) def __init__(self, coroutine=None, *args, **kwargs): super(CoroutinePlayer, self).__init__() if coroutine is None: coroutine = self.generator(*args, **kwargs) self.coroutine = coroutine def __call__(self, op_last=None): if op_last is None: return self.coroutine.next() return self.coroutine.send(op_last) @CoroutinePlayer.wrapper def AlwaysDefectPlayer(): """A player which always defects.""" while True: yield False @CoroutinePlayer.wrapper def AlwaysCoopPlayer(): """A player which always co-operates.""" while True: yield True @CoroutinePlayer.wrapper def GrimPlayer(nice=True): """ A Grim player, also known as Friedman. A player which will co-operate until the opponent defects, after which this player will always defect. """ grim = False op_last = yield nice while True: if not (op_last or (op_last is None)): grim = True op_last = yield (not grim) @CoroutinePlayer.wrapper def TitForTatPlayer(nice=True): """A player which will always copy its opponent's last move.""" op_last = yield nice while True: op_last = yield op_last @CoroutinePlayer.wrapper def BayesianTFTPlayer(nice=True): """ A player whose chances of co-operation depend on its opponent's history. The Bayesian Tit-for-Tat player (BTFT) decides whether or not to co-operate based on its opponent's history of co-operation. If the opponent has always co-operated, then the BTFT player is certain to co-operate. If the opponent has co-operated 5 times and defected 10 times, the BTFT player has a 1 in 3 chance of co-operation, and so on and so forth. """ opponent_history = [] op_last = yield nice while True: opponent_history.append(op_last) op_last = yield random.choice(opponent_history) class ExponentialBayesianTFTPlayer(Player): """ A Bayesian TFT player with an exponentially-weighted forgiveness. The Exponential Bayesian Tit-for-Tat player (EBTFT) works in a similar way to the Bayesian Tit-for-Tat player (BTFT), only recent behaviour is given more 'weight' than behaviour long in the past. The opponent's history is weighted with an exponential decay function, so that if an opponent more recently decided to start co-operating, that recent behaviour could cause the EBTFT player to become more co-operative. In this way, the EBTFT is more forgiving than the simple BTFT (where all previous decisions have equal weight no matter how long ago they were), but still less forgiving than the simple TFT. The ``ExponentialBayesianTFTPlayer`` class takes four optional arguments as initial parameters. These affect the behaviour of the player. ``nice`` If a player is 'nice', it will co-operate on the first move (i.e. when it has no reason to defect). ``a`` and ``b`` These affect the exponential decay function which is used to weigh the opponent's history. The function is essentially: a ** (-b * n) Where n is the number of rounds which have elapsed between now and the opponent's decision in question. For example, the most recent decision will have ``n = 0``, the one before that will have ``n = 1``, and so on and so forth. In this case, ``a`` defaults to the mathematical constant *e*, also known as the base of natural logarithms, which is around 2.71828182845904523536, and ``b`` defaults to 1. You can make the EBTFT act like the simple TFT by setting ``b`` to infinity (this value can be found as ``ExponentialBayesianTFTPlayer.INFINITY``), and you can make it act like the BTFT by setting ``b`` to zero. In essence, this means that both the BTFT and TFT players are just special cases of an EBTFT player. ``threshold`` The EBTFT player will only consider decisions in the past where the weight is at least this value. This exists for performance reasons (because iterating over the entire history at every step might take a while), and it might also be useful to some people. By default, the EBTFT will iterate over the entire history of the opponent's previous decisions, calculating weights, et cetera. However, when the weight goes below a certain value (which it may do very quickly with certain parameters), a disproportionate amount of time is spent iterating over past decisions which have a very small effect on the overall result. The threshold tells the EBTFT to stop iterating over the history when the weight goes below a certain value. By default the threshold is ``0.0001``; you can also turn this behaviour off entirely by setting it to zero (or indeed any negative number). """ E = Decimal('2.71828182845904523536') INFINITY = Decimal('Infinity') ONE = Decimal(1) ZERO = Decimal(0) def __init__(self, a=E, b=ONE, threshold=Decimal('0.0001'), nice=True): super(ExponentialBayesianTFTPlayer, self).__init__() # Ensure that `a` and `b` are `Decimal` instances. if isinstance(a, float): a = Decimal(str(a)) if isinstance(b, float): b = Decimal(str(b)) if isinstance(threshold, float): threshold = Decimal(str(threshold)) self.a = a self.b = b self.threshold = threshold self.nice = nice # The opponent's history. self.op_history = deque() def weight(self, n): if self.b == self.INFINITY: # If this is not caught, it results in an error when `n` is zero. # When `b` is infinity, the most recent decision has a weight of # one and all others have a weight of zero; thus, it acts like the # simple TFT player. return int(n == 0) elif self.b == self.ZERO: # This is just a shortcut. When `b` is zero, each decision in the # past has equal weight, so the EBTFT acts like a normal BTFT. return 1 weight = self.a ** (-1 * self.b * n) # Ensure that we return a `Decimal` instance. if isinstance(weight, float): return Decimal(str(weight)) return Decimal(weight) def calculate_coop_probability(self): # The sum of weights where the opponent co-operated. coop_weight = Decimal('0.0') # The sum of all weights. total_weight = Decimal('0.0') for (i, decision) in enumerate(self.op_history): weight = self.weight(i) # Observe the threshold value. if weight < self.threshold: break total_weight += weight # If, in that round, the opponent decided to co-operate: if decision: coop_weight += weight # Because these are `Decimal` instances they should return a precise # value. return coop_weight / total_weight def __call__(self, op_last=None): # `op_last` will be `None` in the first round. if op_last is None: return self.nice self.op_history.appendleft(op_last) coop_probability = self.calculate_coop_probability() # The following is a way of 'throwing a dice', essentially, where # there are two outcomes with different probabilities of occurring. # Since `coop_probability` will lie in the closed interval [0, 1], as # will the result of `random.random()`, the probability that a random # number is less than or equal to the probability of co-operation will # be equal to that probability of co-operation (it's difficult to # explain in words). return (Decimal(str(random.random())) <= coop_probability) @CoroutinePlayer.wrapper def RandomPlayer(): """A player which randomly decides what to do each iteration.""" while True: yield random.choice((True, False)) if __name__ == '__main__': import doctest doctest.testmod()