polygram

This program has been disqualified.

Source code:

class predictor(object):
    def __init__(self,alphabet):
        self.alphabet = alphabet
        self.prediction = None
        self.probs = None
        self._name = 'Generic'

    @property
    def name(self):
        return self._name

    def _random_choice(self):
        from random import choice
        return choice(self.alphabet)

    def _weighted_random_choice(self,weights):
        w_sum = sum(weights.values())
        from random import random
        ch = int(random()*w_sum)
        for m in [ m for m in self.alphabet if m in weights ]:
            ch -= weights[m]
            if ch <= 0:
                return m

    def _predict(self,state):
        probs = self.probabilities(state)
        if probs is None:
            return None
        return max(probs,key=lambda x:probs[x])

    def _update(self,state,move):
        pass

    def _probabilities(self,state):
        pass
    
    def reliable(self,state,treshold):
        return True
    
    def probabilities( self, state ):
        if self.probs is None:
            self.probs = self._probabilities(state)
        return self.probs
        
    def predict(self,state):
        if self.prediction is None:
            self.prediction = self._predict(state)
        return self.prediction

    def update(self,state,move):
        self._update(state,move)
        self.prediction = None
        self.probs = None
        
    def clear(self):
        pass
        

class randomPredictor(predictor):
    def _probabilities(self,state):
        return {self._random_choice():1}

class weightedRandomPredictor(predictor):
    def __init__(self,alphabet,weights):
        predictor.__init__(self,alphabet)
        self.weights = weights
        self._name = 'WeightedRandom'
    
    def _probabilities(self, state):
        return {self._weighted_random_choice(self.weights):1}

class constantPredictor(predictor):
    def __init__(self,alphabet,c):
        predictor.__init__(self,alphabet)
        self.c = c
        self._name = 'Constant'
    
    def _probabilities(self,state):
        return {self.c:1}


class rotPredictor(predictor):

    def __init__(self,alphabet):
        predictor.__init__(self,alphabet)
        self.pos=0
        self._name = 'Rot'

    def _probabilities(self,state):
        return {self.alphabet[self.pos]:1}

    def _update(self,state,move):
        self.pos += 1
        if self.pos >= len(self.alphabet):
            self.pos = 0

    
class ngramPredictor(predictor):

    def __init__(self,alphabet,n):
        predictor.__init__(self,alphabet)
        self.n = n
        self.data = {}
        self._name = str(n)+'-gram'
        
    def clear(self):
        self.data = {}
        
    def _seen(self,state):
        ngram = ''.join(state[-self.n:])
        if len(ngram) < self.n:
            return (None,ngram)
        if ngram not in self.data:
            return (0,ngram)
        return (sum(self.data[ngram].values()),ngram)
            
    def _probabilities(self,state):
        (cnt,ngram) = self._seen(state)
        if not cnt:
            return None
        else:
            probs = {}
            for (l,c) in self.data[ngram].items():
                probs[l] = float(c)/cnt
            return probs

    def _update(self,state,move):
        (cnt,ngram) = self._seen(state)
        if cnt is None:
            return
        if cnt == 0:
            self.data[ngram] = {}
        if not move in self.data[ngram]:
            self.data[ngram][move]=1
        else:
            self.data[ngram][move] += 1
            
    def reliable(self,state,treshold):
        (cnt,ngram) = self._seen(state)
        if cnt is None:
            return False
        else:
            return cnt > treshold


class weightedMultiPredictor(predictor):
    def __init__(self,alphabet,predictors,treshold=2,updateWeights = False ):
        predictor.__init__(self,alphabet)
        self.predictors = predictors
        self.treshold = treshold
        self.updateWeights = updateWeights
        self._name = 'weightedMultiPredictor'
        self.original_weights = map(lambda x:x[1],predictors)
        self.factor = float(1)/len(predictors)
        self.update_weights_after = 50
        self.num_of_updates = 0
        
    def addPredictor(self, pred, weight ):
        for i in range(len(self.predictors)):
            self.predictors[i][1] *= (1-weight)
            self.original_weights[i] *= (1-weight)
        self.original_weights.append(weight)            
        self.predictors.append([pred,weight])
        
    def clear(self):
        for p in self.predictors:
            p[0].clear()
        for i in range(len(self.predictors)):
            self.predictors[i][1] = self.original_weights[i]
    
    def _probabilities(self,state):
        predictions = {}
        for pred in self.predictors:
            if pred[0].reliable(state,self.treshold):
                probs = pred[0].probabilities(state)
                w = pred[1]
                for (l,p) in probs.items():
                    if l in predictions:
                        predictions[l] += w * p
                    else:
                        predictions[l] = w*p
        if len(predictions) == 0:
            return None
        return predictions
        
    def _updateWeights(self,state,move):
        if not self.updateWeights:
            return 
        successful = []
        failed = []
        sum_suc = 0
        sum_fail = 0
        for p in self.predictors:
            pr = p[0].probabilities(state)
            if not (pr is None):
                if move in pr:
                    if p[0].predict(state) == move:
                        successful.append(p)
                        sum_suc += pr[move]
                    else:
                        failed.append(p)
                        sum_fail += 1-pr[move]
                else:
                    failed.append(p)
                    sum_fail += 1
            factor = float(1)/len(self.predictors)
        for p in successful:
            p[1] += float(self.factor * p[0].probabilities(state)[move])/sum_suc
        for p in failed:
            pr = p[0].probabilities(state)
            if move in pr:
                p[1] -= float(self.factor*(1-pr[move]))/sum_fail
            else:
                p[1] -= float(self.factor)/sum_fail
        
    def _update(self,state,move):
        self.num_of_updates += 1
        if self.num_of_updates % self.update_weights_after == 0:
            self._updateWeights(state,move)
        for p in self.predictors:
            p[0].update(state,move)
        
class polygramPredictor(weightedMultiPredictor):
    def __init__(self,alphabet,weights,treshold=2,updateWeights = False):
        w_sum = sum(weights)
        norm_weights = map(lambda x: float(x)/w_sum, weights)
        preds = []
        for i in range(len(weights)):
            preds.append([ngramPredictor(alphabet,i+2),norm_weights[i]])
        weightedMultiPredictor.__init__(self,alphabet,preds,treshold,updateWeights)
        self._name = str(len(weights))+'-polygram'

class rps(object):
    moves = ['R','P','S']
    rules = { 'R':'P',
              'P':'S',
              'S':'R' }

    @classmethod
    def result( self, first, second ):
        if first == second:
            return 0 # Draw
        if self.rules[first] == second:
            return 1 # Second won
        return -1    # First won

    @classmethod
    def counter( self, move ):
        return self.rules[move]


class player(object):
    def __init__(self,name='Computer'):
        self._name=name
        self._human=False

    def name(self):
        return self._name

    def name(self,value):
        self._name=value

    def human(self):
        return self._human

    def move(self,game):
        return None

    def update(self,game,opponent_move):
        pass
    
    def clear(self):
        pass

class human( player ):
    def __init__(self,name = 'Human'):
        player.__init__(name)
        self._human= True
        
    def move(self, game):
        return raw_input('R,P,S,Q,?')
        
class predictorPlayer( player ):

    def __init__(self, predictor, name='Computer'):
        player.__init__(self,name+'-'+predictor.name)
        self.predictor = predictor
        
    def clear(self):
        self.predictor.clear()

    def move( self, game ):
        pred = self.predictor.predict( game )
        if pred is None:
            return 'R'
        return rps.counter( pred )

    def update( self, game, opponent_move ):
        self.predictor.update( game, opponent_move )
        
class multiPredictorPlayer( player ):

    def add_predictor( self, predictor ):
        self.predictors[predictor] = {'score':0,
                                      'prediction':None}

    def __init__(self,predictors, name='Computer-MultiPredictor'):
        player.__init__(self,name)
        self.predictors = {}
        for p in predictors:
            self.add_predictor(p)
            
            
    def clear(self):
        for p in self.predictors.keys():
            p.clear()
            self.predictors[p]['score']=0

    def printInfo(self):
        for (p,data) in self.predictors.items():
            print p.name,':',data['score']

    def move(self,game):
        max_score = 0
        outcome = None
        for (p,data) in self.predictors.items():
            prediction = p.predict(game)
            data['prediction'] = prediction
            if data['score'] >= max_score:
                outcome = prediction
                max_score = data['score']
        if outcome is None:
            return 'R'
        return rps.counter(outcome)

    def update( self, game, move ):
        for (p,data) in self.predictors.items():
            p.update( game, move )
            if move == data['prediction']:
                data['score']+=5
            else:
                data['score']=max(data['score']-5,0)
            data['score'] *=0.9
                

def match( adam, eve, rounds ):
    a_score = 0
    game = []
    human = adam.human or eve.human
    for i in range( rounds ):
        a_move = adam.move(game)
        e_move = eve.move(game)
        if human:
            if a_move == 'Q' or e_move == 'Q':
                return (a_score,game)
            print 'SC:',a_score, ' (',a_move,',',e_move,')'
        a_score += rps.result( e_move, a_move )
        adam.update(game,e_move)
        eve.update(game,a_move)
        game += [a_move,e_move]
    return (a_score,game)
    
if input == "":
    polyPred = polygramPredictor(rps.moves,[3,3,6,6,10,10,13,13,16,16],2,True)
    polyPred.addPredictor( randomPredictor(rps.moves), 0.5 )
#    tri = ngramPredictor(rps.moves,6)
#    bi = ngramPredictor(rps.moves,3)
#    quad = ngramPredictor(rps.moves,8)
    polyPred.factor=0.001
    polyPred.update_weights_after=300
    polyPlayer = predictorPlayer(polyPred)
#    triPlayer = predictorPlayer(tri)
#    biPlayer = predictorPlayer(bi)
#    quadPlayer = predictorPlayer(quad)
    
    bot = polyPlayer
    
    game = []
    output = bot.move(game)
    my_last_move = output
else:
    bot.update(game,input)
    game += [my_last_move,input]
    output = bot.move(game)
    my_last_move = output