Trilema de prisionero iterado

19

ESTADO DEL DESAFÍO: ABIERTO

Comenta, abre un RP o grítame si me falta tu bot.


El dilema del prisionero ... con tres opciones. Loco, ¿eh?

Aquí está nuestra matriz de pagos. Jugador A a la izquierda, B en la parte superior

A,B| C | N | D
---|---|---|---
 C |3,3|4,1|0,5
 N |1,4|2,2|3,2
 D |5,0|2,3|1,1

La matriz de pagos está diseñada para que sea mejor para ambos jugadores cooperar siempre, pero puedes ganar (generalmente) eligiendo Neutral o Defection.

Aquí hay algunos bots de ejemplo (competidores).

# turns out if you don't actually have to implement __init__(). TIL!

class AllC:
    def round(self, _): return "C"
class AllN:
    def round(self, _): return "N"
class AllD:
    def round(self, _): return "D"
class RandomBot:
    def round(self, _): return random.choice(["C", "N", "D"])

# Actually using an identically-behaving "FastGrudger".
class Grudger:
    def __init__(self):
        self.history = []
    def round(self, last):
        if(last):
            self.history.append(last)
            if(self.history.count("D") > 0):
                return "D"
        return "C"

class TitForTat:
    def round(self, last):
        if(last == "D"):
            return "D"
        return "C"

Tu bot es una clase Python3. Se crea una nueva instancia para cada juego, y round()se llama cada ronda, con la elección de su oponente de la última ronda (o Ninguno, si es la primera ronda)

Hay una recompensa de 50 repeticiones para el ganador en como un mes.

Detalles específicos

  • Cada bot juega a cualquier otro bot (1v1), incluido él mismo, en rondas [ELIMINADO].
  • Lagunas estándar no permitidas.
  • No te metas con nada fuera de tu clase u otras travesuras deshonestas.
  • Puedes enviar hasta cinco bots.
  • Sí, puedes implementar un apretón de manos.
  • Cualquier respuesta que no sea C, No se Dtomará en silencio como N.
  • Los puntos de cada bot de cada juego que jueguen se sumarán y compararán.

Controlador

¡Cheque!

Otros idiomas

Prepararé una API si alguien la necesita.

Puntajes: 2018-11-27

27 bots, 729 games.

name            | avg. score/round
----------------|-------------------
PatternFinder   | 3.152
DirichletDice2  | 3.019
EvaluaterBot    | 2.971
Ensemble        | 2.800
DirichletDice   | 2.763
Shifting        | 2.737
FastGrudger     | 2.632
Nash2           | 2.574
HistoricAverage | 2.552
LastOptimalBot  | 2.532
Number6         | 2.531
HandshakeBot    | 2.458
OldTitForTat    | 2.411
WeightedAverage | 2.403
TitForTat       | 2.328
AllD            | 2.272
Tetragram       | 2.256
Nash            | 2.193
Jade            | 2.186
Useless         | 2.140
RandomBot       | 2.018
CopyCat         | 1.902
TatForTit       | 1.891
NeverCOOP       | 1.710
AllC            | 1.565
AllN            | 1.446
Kevin           | 1.322
SIGSTACKFAULT
fuente
1
¿Cómo se ponen los robots unos contra otros? Grudger me dice que siempre hay dos bots uno contra el otro y que la última opción del enemigo se pasa al bot. ¿Cuántas rondas se juegan? Y para un juego: ¿solo cuenta el resultado (es decir, quién ganó) o también los puntos?
Black Owl Kai
1
Obtendría más entradas si hiciera este lenguaje independiente, o al menos más amplio. Podría tener una clase de envoltura python que genera un proceso y le envía comandos de texto para recuperar las respuestas de texto.
Sparr
1
Hecho. ¡Esto estuvo en el cajón de arena como por un mes!
SIGSTACKFAULT
2
Si envuelve la mayor parte de main.py en while len(botlist) > 1:la botlist.remove(lowest_scoring_bot)en la parte inferior del bucle, se obtiene un torneo de eliminación con resultados interesantes.
Sparr
1
Otra versión de esto algún día podría pasar todo el historial de interacción en lugar de solo el último movimiento. No cambia mucho, aunque simplifica ligeramente el código de usuario. Pero permitiría extensiones, como canales de comunicación ruidosos que aclaran con el tiempo: "Realmente, una D, ¿aunque he dicho C cuatro veces seguidas? No, no dije D; ¿qué me llevas? para? Oh, lo siento, ¿podemos olvidar esa ronda? "
Scott Sauyet

Respuestas:

10

EvaluaterBot

class EvaluaterBot:
    def __init__(self):
        self.c2i = {"C":0, "N":1, "D":2}
        self.i2c = {0:"C", 1:"N", 2:"D"}
        self.history = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
        self.last = [None, None]

    def round(self, last):
        if self.last[0] == None:
            ret = 2
        else:
            # Input the latest enemy action (the reaction to my action 2 rounds ago)
            # into the history
            self.history[self.last[0]][self.c2i[last]] += 1
            # The enemy will react to the last action I did
            prediction,_ = max(enumerate(self.history[self.last[1]]), key=lambda l:l[1])
            ret = (prediction - 1) % 3
        self.last = [self.last[1], ret]
        return self.i2c[ret]

Gana contra todos los bots enviados anteriormente, excepto (tal vez) el bot aleatorio (pero podría tener una ventaja, ya que elige D en un sorteo y D debería ser óptimo) y juega un sorteo constante contra ellos mismos.

Black Owl Kai
fuente
Sí, supera todo.
SIGSTACKFAULT
Rasca eso, PatternFinder lo supera un poco.
SIGSTACKFAULT
7

Equilibrio de Nash

Este bot ha tomado una clase de teoría de juegos en la universidad, pero fue flojo y no fue a la clase donde cubrieron juegos iterativos. Por lo tanto, solo juega un solo juego de equilibrio mixto nash. Resulta que 1/5 2/5 2/5 es el NE mixto para los pagos.

class NashEquilibrium:
    def round(self, _):
        a = random.random()
        if a <= 0.2:
            return "C"
        elif a <= 0.6:
            return "N"
        else:
            return "D" 

Equilibrio constante de abuso de Nash

Este robot aprendió una o dos lecciones de su hermano perezoso. El problema de su hermano perezoso era que no aprovechaba las estrategias fijas. Esta versión verifica si el oponente es un jugador constante o titfortat y juega en consecuencia, de lo contrario, juega el equilibrio nash regular.

El único inconveniente es que promedia 2.2 puntos por turno jugando contra sí mismo.

class NashEquilibrium2:

    def __init__(self):
        self.opphistory = [None, None, None]
        self.titfortatcounter = 0
        self.titfortatflag = 0
        self.mylast = "C"
        self.constantflag = 0
        self.myret = "C"

    def round(self, last):
        self.opphistory.pop(0)
        self.opphistory.append(last)

        # check if its a constant bot, if so exploit
        if self.opphistory.count(self.opphistory[0]) == 3:
            self.constantflag = 1
            if last == "C":
                 self.myret = "D"
            elif last == "N":
                 self.myret = "C"
            elif last == "D":
                 self.myret = "N"

        # check if its a titfortat bot, if so exploit
        # give it 2 chances to see if its titfortat as it might happen randomly
        if self.mylast == "D" and last == "D":
            self.titfortatcounter = self.titfortatcounter + 1

        if self.mylast == "D" and last!= "D":
            self.titfortatcounter = 0

        if self.titfortatcounter >= 3:
            self.titfortatflag = 1

        if self.titfortatflag == 1:
            if last == "C":
                 self.myret = "D"
            elif last == "D":
                 self.myret = "N"    
            elif last == "N":
                # tit for tat doesn't return N, we made a mistake somewhere
                 self.titfortatflag = 0
                 self.titfortatcounter = 0

        # else play the single game nash equilibrium
        if self.constantflag == 0 and self.titfortatflag == 0:
            a = random.random()
            if a <= 0.2:
                self.myret = "C"
            elif a <= 0.6:
                self.myret = "N"
            else:
                self.myret = "D"


        self.mylast = self.myret
        return self.myret
Ofya
fuente
1
NashEquilibrium.round necesita tomar argumentos incluso si no los usa, para ajustarse al prototipo de función esperado.
Ray
Gracias lo arregló
Ofya
Poco más corto:class NashEquilibrium: def round(self, _): a = random.random() for k, v in [(0.2, "C"), (0.6, "N"), (1, "D")]: if a <= k: return v
Robert Grant
7

TatForTit

class TatForTit:
    def round(self, last):
        if(last == "C"):
            return "N"
        return "D"

Este bot alternará eligiendo DNDN mientras TitForTat alterna CDCD, para una ganancia neta promedio de 3 puntos por ronda si he leído la matriz de pagos correctamente. Creo que esto podría ser óptimo contra TitForTat. Obviamente, podría mejorarse detectar a un oponente que no sea TFT y adoptar otras estrategias, pero solo apuntaba a la recompensa original.

Sparr
fuente
6

PatternFinder

class PatternFinder:
    def __init__(self):
        import collections
        self.size = 10
        self.moves = [None]
        self.other = []
        self.patterns = collections.defaultdict(list)
        self.counter_moves = {"C":"D", "N":"C", "D":"N"}
        self.initial_move = "D"
        self.pattern_length_exponent = 1
        self.pattern_age_exponent = 1
        self.debug = False
    def round(self, last):
        self.other.append(last)
        best_pattern_match = None
        best_pattern_score = None
        best_pattern_response = None
        self.debug and print("match so far:",tuple(zip(self.moves,self.other)))
        for turn in range(max(0,len(self.moves)-self.size),len(self.moves)):
            # record patterns ending with the move that just happened
            pattern_full = tuple(zip(self.moves[turn:],self.other[turn:]))
            if len(pattern_full) > 1:
                pattern_trunc = pattern_full[:-1]
                pattern_trunc_result = pattern_full[-1][1]
                self.patterns[pattern_trunc].append([pattern_trunc_result,len(self.moves)-1])
            if pattern_full in self.patterns:
                # we've seen this pattern at least once before
                self.debug and print("I've seen",pattern_full,"before:",self.patterns[pattern_full])
                for [response,turn_num] in self.patterns[pattern_full]:
                    score = len(pattern_full) ** self.pattern_length_exponent / (len(self.moves) - turn_num) ** self.pattern_age_exponent
                    if best_pattern_score == None or score > best_pattern_score:
                        best_pattern_match = pattern_full
                        best_pattern_score = score
                        best_pattern_response = response
                    # this could be much smarter about aggregating previous responses
        if best_pattern_response:
            move = self.counter_moves[best_pattern_response]
        else:
            # fall back to playing nice
            move = "C"
        self.moves.append(move)
        self.debug and print("I choose",move)
        return move

Este bot busca ocurrencias previas del estado reciente del juego para ver cómo respondió el oponente a esas ocurrencias, con preferencia por partidos de patrón más largos y partidos más recientes, luego juega el movimiento que "vencerá" el movimiento predicho del oponente. Hay mucho espacio para que sea más inteligente con todos los datos que rastrea, pero se me acabó el tiempo para trabajar en ello.

Sparr
fuente
Cuando tengas tiempo, ¿te importaría darle un pase de optimización? Es fácilmente el mayor sumidero de tiempo.
SIGSTACKFAULT
2
@Blacksilver Acabo de reducir la longitud máxima del patrón de 100 a 10. Debería ejecutarse casi instantáneamente ahora si está ejecutando <200 rondas
Sparr
1
¿Quizás usar un número altamente compuesto (es decir, 12) obtendría mejores resultados?
SIGSTACKFAULT
5

Jade

class Jade:
    def __init__(self):
        self.dRate = 0.001
        self.nRate = 0.003

    def round(self, last):
        if last == 'D':
            self.dRate *= 1.1
            self.nRate *= 1.2
        elif last == 'N':
            self.dRate *= 1.03
            self.nRate *= 1.05
        self.dRate = min(self.dRate, 1)
        self.nRate = min(self.nRate, 1)

        x = random.random()
        if x > (1 - self.dRate):
            return 'D'
        elif x > (1 - self.nRate):
            return 'N'
        else:
            return 'C'

Comienza optimista, pero se vuelve cada vez más amargo a medida que el oponente se niega a cooperar. Muchas constantes mágicas que probablemente podrían modificarse, pero esto probablemente no sea lo suficientemente bueno como para justificar el tiempo.


fuente
5

Conjunto

Esto ejecuta un conjunto de modelos relacionados. Los modelos individuales consideran diferentes cantidades de historial y tienen la opción de elegir siempre el movimiento que optimizará la diferencia de pago esperada o seleccionar aleatoriamente un movimiento en proporción a la diferencia de pago esperada.

Cada miembro del conjunto vota sobre su movimiento preferido. Obtienen una cantidad de votos igual a cuánto más han ganado que el oponente (lo que significa que los modelos terribles obtendrán votos negativos). Cualquier movimiento que gane el voto se selecciona.

(Probablemente deberían dividir sus votos entre los movimientos en proporción a cuánto favorecen cada uno, pero no me importa lo suficiente como para hacerlo ahora).

Es mejor que todo lo publicado hasta ahora, excepto EvaluaterBot y PatternFinder. (Uno a uno, supera a EvaluaterBot y pierde a PatternFinder).

from collections import defaultdict
import random
class Number6:
    class Choices:
        def __init__(self, C = 0, N = 0, D = 0):
            self.C = C
            self.N = N
            self.D = D

    def __init__(self, strategy = "maxExpected", markov_order = 3):
        self.MARKOV_ORDER = markov_order;
        self.my_choices = "" 
        self.opponent = defaultdict(lambda: self.Choices())
        self.choice = None # previous choice
        self.payoff = {
            "C": { "C": 3-3, "N": 4-1, "D": 0-5 },
            "N": { "C": 1-4, "N": 2-2, "D": 3-2 },
            "D": { "C": 5-0, "N": 2-3, "D": 1-1 },
        }
        self.total_payoff = 0

        # if random, will choose in proportion to payoff.
        # otherwise, will always choose argmax
        self.strategy = strategy
        # maxExpected: maximize expected relative payoff
        # random: like maxExpected, but it chooses in proportion to E[payoff]
        # argmax: always choose the option that is optimal for expected opponent choice

    def update_opponent_model(self, last):
        for i in range(0, self.MARKOV_ORDER):
            hist = self.my_choices[i:]
            self.opponent[hist].C += ("C" == last)
            self.opponent[hist].N += ("N" == last)
            self.opponent[hist].D += ("D" == last)

    def normalize(self, counts):
        sum = float(counts.C + counts.N + counts.D)
        if 0 == sum:
            return self.Choices(1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0)
        return self.Choices(
            counts.C / sum, counts.N / sum, counts.D / sum)

    def get_distribution(self):
        for i in range(0, self.MARKOV_ORDER):
            hist = self.my_choices[i:]
            #print "check hist = " + hist
            if hist in self.opponent:
                return self.normalize(self.opponent[hist])

        return self.Choices(1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0)

    def choose(self, dist):
        payoff = self.Choices()
        # We're interested in *beating the opponent*, not
        # maximizing our score, so we optimize the difference
        payoff.C = (3-3) * dist.C + (4-1) * dist.N + (0-5) * dist.D
        payoff.N = (1-4) * dist.C + (2-2) * dist.N + (3-2) * dist.D
        payoff.D = (5-0) * dist.C + (2-3) * dist.N + (1-1) * dist.D

        # D has slightly better payoff on uniform opponent,
        # so we select it on ties
        if self.strategy == "maxExpected":
            if payoff.C > payoff.N:
                return "C" if payoff.C > payoff.D else "D"
            return "N" if payoff.N > payoff.D else "D"
        elif self.strategy == "randomize":
            payoff = self.normalize(payoff)
            r = random.uniform(0.0, 1.0)
            if (r < payoff.C): return "C"
            return "N" if (r < payoff.N) else "D"
        elif self.strategy == "argMax":
            if dist.C > dist.N:
                return "D" if dist.C > dist.D else "N"
            return "C" if dist.N > dist.D else "N"

        assert(0) #, "I am not a number! I am a free man!")

    def update_history(self):
        self.my_choices += self.choice
        if len(self.my_choices) > self.MARKOV_ORDER:
            assert(len(self.my_choices) == self.MARKOV_ORDER + 1)
            self.my_choices = self.my_choices[1:]

    def round(self, last):
        if last: self.update_opponent_model(last)

        dist = self.get_distribution()
        self.choice = self.choose(dist)
        self.update_history()
        return self.choice

class Ensemble:
    def __init__(self):
        self.models = []
        self.votes = []
        self.prev_choice = []
        for order in range(0, 6):
            self.models.append(Number6("maxExpected", order))
            self.models.append(Number6("randomize", order))
            #self.models.append(Number6("argMax", order))
        for i in range(0, len(self.models)):
            self.votes.append(0)
            self.prev_choice.append("D")

        self.payoff = {
            "C": { "C": 3-3, "N": 4-1, "D": 0-5 },
            "N": { "C": 1-4, "N": 2-2, "D": 3-2 },
            "D": { "C": 5-0, "N": 2-3, "D": 1-1 },
        }

    def round(self, last):
        if last:
            for i in range(0, len(self.models)):
                self.votes[i] += self.payoff[self.prev_choice[i]][last]

        # vote. Sufficiently terrible models get negative votes
        C = 0
        N = 0
        D = 0
        for i in range(0, len(self.models)):
            choice = self.models[i].round(last)
            if "C" == choice: C += self.votes[i]
            if "N" == choice: N += self.votes[i]
            if "D" == choice: D += self.votes[i]
            self.prev_choice[i] = choice

        if C > D and C > N: return "C"
        elif N > D: return "N"
        else: return "D"

Marco de prueba

En caso de que alguien más lo encuentre útil, aquí hay un marco de prueba para mirar emparejamientos individuales. Python2. Simplemente coloque a todos los oponentes que le interesan en oponents.py, y cambie las referencias a Ensemble a las suyas.

import sys, inspect
import opponents
from ensemble import Ensemble

def count_payoff(label, them):
    if None == them: return
    me = choices[label]
    payoff = {
        "C": { "C": 3-3, "N": 4-1, "D": 0-5 },
        "N": { "C": 1-4, "N": 2-2, "D": 3-2 },
        "D": { "C": 5-0, "N": 2-3, "D": 1-1 },
    }
    if label not in total_payoff: total_payoff[label] = 0
    total_payoff[label] += payoff[me][them]

def update_hist(label, choice):
    choices[label] = choice

opponents = [ x[1] for x 
    in inspect.getmembers(sys.modules['opponents'], inspect.isclass)]

for k in opponents:
    total_payoff = {}

    for j in range(0, 100):
        A = Ensemble()
        B = k()
        choices = {}

        aChoice = None
        bChoice = None
        for i in range(0, 100):
            count_payoff(A.__class__.__name__, bChoice)
            a = A.round(bChoice)
            update_hist(A.__class__.__name__, a)

            count_payoff(B.__class__.__name__, aChoice)
            b = B.round(aChoice)
            update_hist(B.__class__.__name__, b)

            aChoice = a
            bChoice = b
    print total_payoff
Rayo
fuente
El controlador está listo, no tuvo que hacer todo eso ...
SIGSTACKFAULT
1
@Blacksilver Me di cuenta de eso justo cuando estaba a punto de presentar. Pero este funciona en versiones anteriores a 3.6 y proporciona información sobre enfrentamientos individuales que pueden ayudar a identificar puntos débiles, por lo que no fue una pérdida de tiempo completa.
Ray
Lo suficientemente justo; corriendo ahora Probablemente agregaré opciones a mi controlador para hacer cosas similares.
SIGSTACKFAULT
"Es mejor que todo lo publicado hasta ahora excepto Ensemble y PatternFinder" Me siento honrado :)
Sparr
@Sparr Oops. Se suponía que debía decir EvaluaterBot y PatternFinder. Pero eso es cuando se compara el puntaje total con todo el campo. PatternFinder sigue siendo el único que supera esto en un enfrentamiento directo.
Ray
4

OldTitForTat

El jugador de la vieja escuela es demasiado vago para actualizarse para las nuevas reglas.

class OldTitForTat:
    def round(self, last):
        if(last == None)
            return "C"
        if(last == "C"):
            return "C"
        return "D"
Joshua
fuente
3

NeverCOOP

class NeverCOOP:
    def round(self, last):
        try:
            if last in "ND":
                return "D"
            else:
                return "N"
        except:
            return "N"

Si el bot contrario tiene defectos o es neutral, elige defecto. De lo contrario, si este es el primer turno o el robot contrario coopera, elige neutral. No estoy seguro de lo bien que funcionará ...

glietz
fuente
¿Cuál es el intento / excepto?
SIGSTACKFAULT
1
@Blacksilver Supongo que sirve para el mismo propósito que if(last):en su bot Grudger, detectando si hubo una ronda anterior.
ETHproductions
Ahh ya veo. None in "ND"errores
SIGSTACKFAULT
¿Porque if last and last in "ND":era demasiado complicado?
user253751
3

LastOptimalBot

class LastOptimalBot:
    def round(self, last):
        return "N" if last == "D" else ("D" if last == "C" else "C")

Asume que el bot contrario siempre volverá a jugar el mismo movimiento y elige el que tenga la mejor recompensa.

Promedios:

Me   Opp
2.6  2    vs TitForTat
5    0    vs AllC
4    1    vs AllN
3    2    vs AllD
3.5  3.5  vs Random
3    2    vs Grudger
2    2    vs LastOptimalBot
1    3.5  vs TatForTit
4    1    vs NeverCOOP
1    4    vs EvaluaterBot
2.28 2.24 vs NashEquilibrium

2.91 average overall
Spitemaster
fuente
oof. Tal vez T4T haría mejor como return last.
SIGSTACKFAULT
¡Me gustaría eso! Si TitForTat fuera return last, LOB iría 18-9 en 6 rondas en lugar de 13-10 en 5 rondas que está recibiendo actualmente. Creo que está bien como está: no se preocupe por optimizar los bots de ejemplo.
Spitemaster
return lastsería un mejor T4T para este desafío, creo
Sparr
Acabo de intentarlo, el if(last): return last; else: return "C"es peor.
SIGSTACKFAULT
Correcto, pero como decía @Sparr, podría ser más apropiado. Depende de usted, supongo.
Spitemaster
3

CopyCat

class CopyCat:
    def round(self, last):
        if last:
            return last
        return "C"

Copia el último movimiento del oponente.
No espero que esto funcione bien, pero nadie ha implementado este clásico todavía.

MannerPots
fuente
2

Dados Dirichlet mejorados

import random

class DirichletDice2:
    def __init__(self):

        self.alpha = dict(
                C = {'C' : 1, 'N' : 1, 'D' : 1},
                N = {'C' : 1, 'N' : 1, 'D' : 1},
                D = {'C' : 1, 'N' : 1, 'D' : 1}
        )
        self.myLast = [None, None]
        self.payoff = dict(
                C = { "C": 0, "N": 3, "D": -5 },
                N = { "C": -3, "N": 0, "D": 1 },
                D = { "C": 5, "N": -1, "D": 0 }
        )

    def DirichletDraw(self, key):
        alpha = self.alpha[key].values()
        mu = [random.gammavariate(a,1) for a in alpha]
        mu = [m / sum(mu) for m in mu]
        return mu

    def ExpectedPayoff(self, probs):
        expectedPayoff = {}
        for val in ['C','N','D']:
            payoff = sum([p * v for p,v in zip(probs, self.payoff[val].values())])
            expectedPayoff[val] = payoff
        return expectedPayoff

    def round(self, last):
        if last is None:
            self.myLast[0] = 'D'
            return 'D'

        #update dice corresponding to opponent's last response to my
        #outcome two turns ago
        if self.myLast[1] is not None:
            self.alpha[self.myLast[1]][last] += 1

        #draw probs for my opponent's roll from Dirichlet distribution and then return the optimal response
        mu = self.DirichletDraw(self.myLast[0])
        expectedPayoff = self.ExpectedPayoff(mu)
        res = max(expectedPayoff, key=expectedPayoff.get)

        #update myLast
        self.myLast[1] = self.myLast[0]
        self.myLast[0] = res

        return res    

Esta es una versión mejorada de Dirichlet Dice. En lugar de tomar la distribución multinomial esperada de la distribución Dirichlet, dibuja una distribución Multinomial aleatoriamente de la distribución Dirichlet. Luego, en lugar de extraer del Multinomial y dar la respuesta óptima a eso, da la respuesta óptima esperada al Multinomial dado usando los puntos. Por lo tanto, la aleatoriedad se ha cambiado esencialmente del sorteo Multinomial al sorteo Dirichlet. Además, los antecedentes son más planos ahora, para alentar la exploración.

Se "mejoró" porque ahora da cuenta del sistema de puntos al dar el mejor valor esperado contra las probabilidades, mientras mantiene su aleatoriedad al dibujar las probabilidades mismas. Antes, intenté simplemente hacer la mejor recompensa esperada de las probabilidades esperadas, pero eso fue mal porque se quedó atascado y no exploré lo suficiente como para actualizar sus dados. También fue más predecible y explotable.


Presentación original:

Dados Dirichlet

import random

class DirichletDice:
    def __init__(self):

        self.alpha = dict(
                C = {'C' : 2, 'N' : 3, 'D' : 1},
                N = {'C' : 1, 'N' : 2, 'D' : 3},
                D = {'C' : 3, 'N' : 1, 'D' : 2}
        )

        self.Response = {'C' : 'D', 'N' : 'C', 'D' : 'N'}
        self.myLast = [None, None]

    #expected value of the dirichlet distribution given by Alpha
    def MultinomialDraw(self, key):
        alpha = list(self.alpha[key].values())
        probs = [x / sum(alpha) for x in alpha]
        outcome = random.choices(['C','N','D'], weights=probs)[0]
        return outcome

    def round(self, last):
        if last is None:
            self.myLast[0] = 'D'
            return 'D'

        #update dice corresponding to opponent's last response to my
        #outcome two turns ago
        if self.myLast[1] is not None:
            self.alpha[self.myLast[1]][last] += 1

        #predict opponent's move based on my last move
        predict = self.MultinomialDraw(self.myLast[0])
        res = self.Response[predict]

        #update myLast
        self.myLast[1] = self.myLast[0]
        self.myLast[0] = res

        return res

Básicamente, supongo que la respuesta del oponente a mi última salida es una variable multinomial (dados ponderados), una para cada una de mis salidas, por lo que hay un dado para "C", uno para "N" y uno para "D" . Entonces, si mi último lanzamiento fue, por ejemplo, una "N", entonces saco el "N-dice" para adivinar cuál sería su respuesta a mi "N". Comienzo con un Dirichlet antes que asume que mi oponente es algo "inteligente" (es más probable que juegue el que tenga la mejor recompensa contra mi última tirada, menos probable que juegue el que tenga la peor recompensa). Genero la distribución Multinomial "esperada" a partir del Dirichlet apropiado antes (este es el valor esperado de la distribución de probabilidad sobre sus pesos de dados). Lanzo los dados ponderados de mi última salida,

Comenzando en la tercera ronda, hago una actualización bayesiana del Dirichlet apropiado antes de la última respuesta de mi oponente a lo que jugué hace dos rondas. Estoy tratando de aprender iterativamente sus ponderaciones de dados.

También podría haber elegido simplemente la respuesta con el mejor resultado "esperado" una vez que genera el dado, en lugar de simplemente tirar el dado y responder al resultado. Sin embargo, quería mantener la aleatoriedad, para que mi bot sea menos vulnerable a los que intentan predecir un patrón.

Quemadores de puente
fuente
2

Kevin

class Kevin:
    def round(self, last):      
        return {"C":"N","N":"D","D":"C",None:"N"} [last]

Elige la peor opción. El peor bot hecho.

Inútil

import random

class Useless:
    def __init__(self):
        self.lastLast = None

    def round(self, last):
        tempLastLast = self.lastLast
        self.lastLast = last

        if(last == "D" and tempLastLast == "N"):
            return "C"
        if(last == "D" and tempLastLast == "C"):
            return "N"

        if(last == "N" and tempLastLast == "D"):
            return "C"
        if(last == "N" and tempLastLast == "C"):
            return "D"

        if(last == "C" and tempLastLast == "D"):
            return "N"
        if(last == "C" and tempLastLast == "N"):
            return "D"

        return random.choice("CND")

Mira los dos últimos movimientos realizados por el oponente y elige la mayoría de los no hechos, de lo contrario, elige algo al azar. Probablemente hay una mejor manera de hacer esto.

Link1J
fuente
2

Promedio histórico

class HistoricAverage:
    PAYOFFS = {
        "C":{"C":3,"N":1,"D":5},
        "N":{"C":4,"N":2,"D":2},
        "D":{"C":0,"N":3,"D":1}}
    def __init__(self):
        self.payoffsum = {"C":0, "N":0, "D":0}
    def round(this, last):
        if(last != None):
            for x in this.payoffsum:
               this.payoffsum[x] += HistoricAverage.PAYOFFS[last][x]
        return max(this.payoffsum, key=this.payoffsum.get)

Mira la historia y encuentra la acción que habría sido mejor en promedio. Comienza a cooperar.

MegaTom
fuente
Esto podría correr más rápido si no volviera a calcular los promedios en cada ronda.
Sparr
@Sparr cierto. Lo edité para que lo haga ahora.
MegaTom
1

Peso promedio

class WeightedAverageBot:
  def __init__(self):
    self.C_bias = 1/4
    self.N = self.C_bias
    self.D = self.C_bias
    self.prev_weight = 1/2
  def round(self, last):
    if last:
      if last == "C" or last == "N":
        self.D *= self.prev_weight
      if last == "C" or last == "D":
        self.N *= self.prev_weight
      if last == "N":
        self.N = 1 - ((1 - self.N) * self.prev_weight)
      if last == "D":
        self.D = 1 - ((1 - self.D) * self.prev_weight)
    if self.N <= self.C_bias and self.D <= self.C_bias:
      return "D"
    if self.N > self.D:
      return "C"
    return "N"

El comportamiento del oponente se modela como un triángulo rectángulo con esquinas para CND a 0,0 0,1 1,0 respectivamente. Cada movimiento del oponente desplaza el punto dentro de ese triángulo hacia esa esquina, y jugamos para vencer el movimiento indicado por el punto (a C se le da una pequeña porción ajustable del triángulo). En teoría, quería que esto tuviera una memoria más larga con más peso para los movimientos anteriores, pero en la práctica el meta actual favorece a los robots que cambian rápidamente, por lo que esto se convierte en una aproximación de LastOptimalBot contra la mayoría de los enemigos. Publicar para la posteridad; Quizás alguien se inspire.

Sparr
fuente
1

Tetragrama

import itertools

class Tetragram:
    def __init__(self):
        self.history = {x: ['C'] for x in itertools.product('CND', repeat=4)}
        self.theirs = []
        self.previous = None

    def round(self, last):
        if self.previous is not None and len(self.previous) == 4:
            self.history[self.previous].append(last)
        if last is not None:
            self.theirs = (self.theirs + [last])[-3:]

        if self.previous is not None and len(self.previous) == 4:
            expected = random.choice(self.history[self.previous])
            if expected == 'C':
                choice = 'C'
            elif expected == 'N':
                choice = 'C'
            else:
                choice = 'N'
        else:
            choice = 'C'

        self.previous = tuple(self.theirs + [choice])
        return choice

Intenta encontrar un patrón en los movimientos del oponente, suponiendo que también estén viendo nuestro último movimiento.


fuente
1

Apretón de manos

class HandshakeBot:
  def __init__(self):
    self.handshake_length = 4
    self.handshake = ["N","N","C","D"]
    while len(self.handshake) < self.handshake_length:
      self.handshake *= 2
    self.handshake = self.handshake[:self.handshake_length]
    self.opp_hand = []
    self.friendly = None
  def round(self, last):
    if last:
      if self.friendly == None:
        # still trying to handshake
        self.opp_hand.append(last)
        if self.opp_hand[-1] != self.handshake[len(self.opp_hand)-1]:
          self.friendly = False
          return "D"
        if len(self.opp_hand) == len(self.handshake):
          self.friendly = True
          return "C"
        return self.handshake[len(self.opp_hand)]
      elif self.friendly == True:
        # successful handshake and continued cooperation
        if last == "C":
          return "C"
        self.friendly = False
        return "D"
      else:
        # failed handshake or abandoned cooperation
        return "N" if last == "D" else ("D" if last == "C" else "C")
    return self.handshake[0]

Reconoce cuándo está jugando contra sí mismo, luego coopera. De lo contrario, imita LastOptimalBot, que parece ser la mejor estrategia de una línea. Funciona peor que LastOptimalBot, en una cantidad inversamente proporcional al número de rondas. Obviamente sería mejor si hubiera más copias de él en el campo * tos ** guiño *.

Sparr
fuente
Simplemente envíe algunos clones que tengan un comportamiento diferente de no apretón de manos.
SIGSTACKFAULT
Eso parece explotar. Podría enviar uno de esos clones por cada comportamiento simple representado aquí.
Sparr
He agregado una cláusula adicional que dice que solo puedes enviar un máximo de cinco bots.
SIGSTACKFAULT
1

ShiftingOptimalBot

class ShiftingOptimalBot:
    def __init__(self):
        # wins, draws, losses
        self.history = [0,0,0]
        self.lastMove = None
        self.state = 0
    def round(self, last):
        if last == None:
            self.lastMove = "C"
            return self.lastMove
        if last == self.lastMove:
            self.history[1] += 1
        elif (last == "C" and self.lastMove == "D") or (last == "D" and self.lastMove == "N") or (last == "N" and self.lastMove == "C"):
            self.history[0] += 1
        else:
            self.history[2] += 1

        if self.history[0] + 1 < self.history[2] or self.history[2] > 5:
            self.state = (self.state + 1) % 3
            self.history = [0,0,0]
        if self.history[1] > self.history[0] + self.history[2] + 2:
            self.state = (self.state + 2) % 3
            self.history = [0,0,0]

        if self.state == 0:
            self.lastMove = "N" if last == "D" else ("D" if last == "C" else "C")
        elif self.state == 1:
            self.lastMove = last
        else:
            self.lastMove = "C" if last == "D" else ("N" if last == "C" else "D")
        return self.lastMove

Este bot usa el algoritmo de LastOptimalBot siempre que sea ganador. Sin embargo, si el otro bot comienza a predecirlo, comenzará a jugar cualquier movimiento que haya jugado su oponente en último lugar (que es el movimiento que supera el movimiento que vencería a LastOptimalBot). Se desplaza por transposiciones simples de esos algoritmos siempre que continúe perdiendo (o cuando se aburre dibujando mucho).

Honestamente, me sorprende que LastOptimalBot esté en el quinto puesto cuando publico esto. Estoy bastante seguro de que esto funcionará mejor, suponiendo que escribí esta pitón correctamente.

Spitemaster
fuente
0

Apretón De ManosPatrón

from .patternfinder import PatternFinder
import collections

class HandshakePatternMatch:
    def __init__(self):
        self.moves = [None]
        self.other = []
        self.handshake = [None,"N","C","C","D","N"]
        self.friendly = None
        self.pattern = PatternFinder()
    def round(self, last):
        self.other.append(last)
        if last:
            if len(self.other) < len(self.handshake):
                # still trying to handshake
                if self.friendly == False or self.other[-1] != self.handshake[-1]:
                    self.friendly = False
                else:
                    self.friendly = True
                move = self.handshake[len(self.other)]
                self.pattern.round(last)
            elif self.friendly == True:
                # successful handshake and continued cooperation
                move = self.pattern.round(last)
                if last == "C":
                    move = "C"
                elif last == self.handshake[-1] and self.moves[-1] == self.handshake[-1]:
                    move = "C"
                else:
                    self.friendly = False
            else:
                # failed handshake or abandoned cooperation
                move = self.pattern.round(last)
        else:
            move = self.handshake[1]
            self.pattern.round(last)
        self.moves.append(move)
        return move

¿Por qué el patrón coincide contigo mismo? Apretón de manos y cooperar lejos.

Draco18s
fuente
import PatternFinderestá haciendo trampa en mis libros.
SIGSTACKFAULT
@Blacksilver Se hace todo el tiempo en KOTH. No es diferente a copiar el código en una respuesta existente y usarlo. Ruleta de robots: los juegos de apuestas de robots de alto riesgo hicieron que sucediera por todas partes hasta el punto de que los bots detectarían si un oponente llamaba su código y sabotearían el regreso.
Draco18s
Bien entonces. TIL
SIGSTACKFAULT
Haré el crujido mañana.
SIGSTACKFAULT
Aquí hay un ejemplo perfecto del uso del código de otros bots. Por lo general, todo se reduce a "ese tipo resolvió algunas matemáticas complicadas, quiero sus resultados en estas condiciones". (Mi propia entrada lo hizo con bastante buen efecto; UpYours fue más disperso en su enfoque).
Draco18s
0

Codificado

class Hardcoded:
    sequence = "DNCNNDDCNDDDCCDNNNNDDCNNDDCDCNNNDNDDCNNDDNDDCDNCCNNDNNDDCNNDDCDCNNNDNCDNDNDDNCNDDCDNNDCNNDDCDCNNDNNDDCDNDDCCNNNDNNDDCNNDDNDCDNCNDDCDNNDDCCNDNNDDCNNNDCDNDDCNNNNDNDDCDNCDCNNDNNDDCDNDDCCNNNDNDDCNNNDNDCDCDNNDCNNDNDDCDNCNNDDCNDNNDDCDNNDCDNDNCDDCNNNDNDNCNDDCDNDDCCNNNNDNDDCNNDDCNNDDCDCNNDNNDDCDNDDCCNDNNDDCNNNDCDNNDNDDCCNNNDNDDNCDCDNNDCNNDNDDCNNDDCDNCNNDDCDNNDCDNDNCDDCNDNNDDCNNNDDCDNCNNDNNDDCNNDDNNDCDNCNDDCNNDCDNNDDCNNDDNCDCNNDNDNDDCDNCDCNNNDNDDCDCNNDNNDDCDNDDCCNNNDNNDDCNDNDNCDDCDCNNNNDNDDCDNCNDDCDNNDDCNNNDNDDCDNCNNDCNNDNDDNCDCDNNNDDCNNDDCNNDDNNDCDNCNDDCNNDDNDCDNNDNDDCCNCDNNDCNNDDNDDCNCDNNDCDNNNDDCNNDDCDCDNNDDCNDNCNNDNNDNDNDDCDNCDCNNNDNDDCDNCNNDDCDNNDCNNDDCNNDDCDCDNNDDCNDNCNNNDDCDNNDCDNDNCNNDNDDNNDNDCDDCCNNNDDCNDNDNCDDCDCNNNDNNDDCNDCDNDDCNNNNDNDDCCNDNNDDCDCNNNDNDDNDDCDNCCNNDNNDDCNNDDCDCNNDNNDDCNNDDNCNDDNNDCDNCNDDCNNDDNDCDNNDNDDCCNCDNNDCNNDNDDCNNDDNCDCDNNDCNNDNDDCDCDNNNNDDCNNDDNDCCNNDDNDDCNCDNNDCNNDDNDDCDNCNDDCNNNNDCDNNDDCNDNDDCDNCNNDCDNNDCNNDNDDNCDCNNDNDDCDNDDCCNNNNDNDDCNNDDCDCNNDNNDDCDCDNNDDC"
    def __init__(self):
        self.round_num = -1
    def round(self,_):
        self.round_num += 1
        return Hardcoded.sequence[self.round_num % 1000]

Simplemente reproduce una secuencia codificada de movimientos optimizados para vencer a algunos de los mejores bots deterministas.

MegaTom
fuente