Dilema ruidoso del prisionero iterado

34

En este desafío, jugarás el ruidoso dilema del prisionero iterado.

El dilema del Prisionero es un escenario en la teoría de juegos donde hay dos jugadores, cada uno con dos opciones: cooperar o desertar. A cada jugador le va mejor si desertan que si cooperan, pero ambos jugadores preferirían el resultado donde ambos jugadores cooperan a aquel en el que ambos jugadores desertan.

El dilema del prisionero iterado es el mismo juego, excepto que juegas contra el mismo oponente repetidamente y sabes lo que ha jugado tu oponente en el pasado. Su objetivo siempre es acumular el puntaje más alto para usted, independientemente de cómo lo haga su oponente.

El ruidoso y reiterado dilema del prisionero introduce algo de ruido en la comunicación. Su conocimiento de lo que ha jugado su oponente en el pasado tendrá algo de ruido introducido. También sabrás qué movimientos hiciste en el pasado. La tasa de ruido es constante durante una ronda contra el mismo oponente, pero diferente entre diferentes rondas.

Reto

En este desafío, escribirás un programa Python 3 para jugar el dilema del prisionero ruidoso iterado.

Su programa recibirá tres entradas:

  • Tus propios movimientos, sin cambios aleatorios aplicados.

  • Los movimientos de tu oponente, con volteos aleatorios aplicados.

  • Una variable de estado, que comienza como una lista vacía en cada ronda, y que puede modificar si lo desea. Puedes ignorar esto si no quieres usarlo.

Su programa debe salir 'c'para cooperar o 'd'para desertar.

Por ejemplo, aquí hay un programa que coopera si el oponente ha cooperado al menos el 60% del tiempo en el pasado, después de que se aplicaron volteos aleatorios y durante los primeros 10 volteos:

def threshold(my_plays, their_flipped_plays, state):
    if len(their_flipped_plays) < 10:
        return 'c'
    opp_c_freq = their_flipped_plays.count('c')/len(their_flipped_plays)
    if opp_c_freq > 0.6:
        return 'c'
    else:
        return 'd'

Si no conoce Python, escriba su envío en pseudocódigo, y alguien (yo u otro miembro del sitio) puede hacer el programa Python correspondiente.

Jugabilidad

El corredor del torneo se puede encontrar aquí: juego ruidoso . Corre noisy-game.pypara correr el torneo. Mantendré ese repositorio actualizado con nuevos envíos. Se pueden encontrar programas de ejemplo en basic.py.

El puntaje general de un programa es el total de su puntaje en más de 100 jugadas del juego.

Un juego consiste en enfrentamientos de round-robin de cada jugador contra cada jugador, incluido él mismo. Un enfrentamiento consta de 100 rondas. Una ronda consta de 300 movimientos, cada uno de los cuales implica la salida 'c'o 'd'.

Su envío jugará un enfrentamiento contra cada envío, incluido el suyo. Cada enfrentamiento consistirá en 100 rondas. Durante cada ronda, se elegirá una probabilidad de volteo de manera uniforme al azar [0, 0.5].

Cada ronda constará de 300 movimientos. En cada movimiento, ambos programas recibirán todas las jugadas anteriores que hayan intentado, y todas las jugadas anteriores que haya realizado el otro programa, después de aplicar los cambios, y una variable de estado, que es una lista mutable que el programa puede modificar si lo desea. Los programas darán salida a sus movimientos.

Los movimientos se puntúan de la siguiente manera: si un programa juega a 'c', el programa contrario obtiene 2 puntos. Si un programa juega un 'd', ese programa obtiene 1 punto.

Luego, cada movimiento se voltea independientemente con una probabilidad igual a la probabilidad de volteo y se almacena para mostrar al oponente.

Después de jugar todas las rondas, sumamos el número de puntos que cada jugador obtuvo en cada enfrentamiento. Luego, utilizamos el siguiente sistema de puntuación para calcular la puntuación de cada jugador para el juego. Esta puntuación se realiza después de completar todos los enfrentamientos.

Tanteo

Utilizaremos la puntuación evolutiva. Cada programa comienza con el mismo peso. Luego, los pesos se actualizan de la siguiente manera, para 100 iteraciones, utilizando los puntos totales del juego:

El nuevo peso de cada programa es proporcional al producto de su peso anterior y su promedio total de puntos, ponderado por los pesos de sus oponentes.

Se aplican 100 de estas actualizaciones, y los pesos finales son el puntaje de cada programa para esa ejecución del juego.

Los puntajes generales serán la suma de más de 100 carreras del juego.

Los jugadores serán todas respuestas válidas a este desafío, además de seis programas básicos para comenzar.

Advertencias

No modifique las entradas. No intente afectar la ejecución de ningún otro programa, excepto mediante la cooperación o el defecto. No haga una presentación de sacrificio que intente reconocer otra presentación y beneficie a ese oponente a su costa. Las lagunas estándar están prohibidas.

EDITAR: los envíos pueden no duplicar exactamente ninguno de los programas básicos o cualquier envío anterior.

Si tiene alguna pregunta, sientase con libertad de preguntar.

Resultados actuales

nicht_genug: 40.6311
stealer: 37.1416
enough: 14.4443
wait_for_50: 6.947
threshold: 0.406784
buckets: 0.202875
change_of_heart: 0.0996783
exploit_threshold: 0.0670485
kickback: 0.0313357
tit_for_stat: 0.0141368
decaying_memory: 0.00907645
tit_for_whoops: 0.00211803
slider: 0.00167053
trickster: 0.000654875
sounder: 0.000427348
tit_for_tat: 9.12471e-05
stubborn_stumbler: 6.92879e-05
tit_for_time: 2.82541e-05
jedi2sith: 2.0768e-05
cooperate: 1.86291e-05
everyThree: 1.04843e-05
somewhat_naive: 4.46701e-06
just_noise: 1.41564e-06
growing_distrust: 5.32521e-08
goldfish: 4.28982e-09
vengeful: 2.74267e-09
defect: 3.71295e-10
alternate: 2.09372e-20
random_player: 6.74361e-21

Resultados con solo respuestas a esta pregunta y programas básicos que ignoran el juego del oponente:

nicht_genug: 39.3907
stealer: 33.7864
enough: 20.9032
wait_for_50: 5.60007
buckets: 0.174457
kickback: 0.0686975
change_of_heart: 0.027396
tit_for_stat: 0.024522
decaying_memory: 0.0193272
tit_for_whoops: 0.00284842
slider: 0.00153227
sounder: 0.000472289
trickster: 0.000297515
stubborn_stumbler: 3.76073e-05
cooperate: 3.46865e-05
tit_for_time: 2.42263e-05
everyThree: 2.06095e-05
jedi2sith: 1.62591e-05
somewhat_naive: 4.20785e-06
just_noise: 1.18372e-06
growing_distrust: 6.17619e-08
vengeful: 3.61213e-09
goldfish: 3.5746e-09
defect: 4.92581e-10
alternate: 6.96497e-20
random_player: 1.49879e-20

Victorioso

La competencia permanecerá abierta indefinidamente a medida que se publiquen nuevas presentaciones. Sin embargo, declararé un ganador (aceptar una respuesta) basado en los resultados 1 mes después de que se publique esta pregunta.

isaacg
fuente
¿Cómo ignora tit_for_whoops el juego del oponente?
Letra de
@LyricLy Supongo que la categoría se refiere a los programas básicos proporcionados por Isaac que ignoran a sus oponentes.
FryAmTheEggman
1
¿Entiendo bien que puede usar la variable de estado para registrar todos sus movimientos a medida que los envía y, por lo tanto, conocer sus movimientos verdaderos y los movimientos invertidos, y estimar la probabilidad de inversión?
xnor
1
@xnor Siempre te dicen tus verdaderos movimientos. Solo los movimientos de los oponentes pueden voltearse.
1
@isaacg Intenté copiar exploit_threshold()varias veces como exploit_threshold1(), etc. y las agregué a la playerslista. ¿Por qué obtengo resultados muy diferentes para estrategias idénticas?
ngn

Respuestas:

4

Genug ist nicht genug

(también podría llamarse enough2o stealback)

def nicht_genug(m,t,s):
    if not s:
        s.append("c")
        return "c"
    if s[0]=="t":
        return "d"
    if m[-42:].count("d")>10 or len(t)+t.count("d")>300:
        s[0]="t"
        return "d"
    if t[-1]=="d":
        if s[0]=="d":
            s[0]="c"
            return "d"
        else:
            s[0]="d"
            return "c"
    else:
        if t[-3:].count("d")==0:
            s[0]="c"
        return "c"

Aprendí que el tit original para dos tats esperaba dos tats consecutivos como lo tit_for_whoopshace, y de hecho parece que deberíamos perdonar y olvidar (bueno, casi ...) tats individuales anteriores. Y muchos jugadores desertan en las últimas rondas. Todavía prefiero ser amable cuando todo ha estado bien hasta ahora, pero la barra de tolerancia del bot sigue bajando.

Christian Sievers
fuente
10

Tit-For-Whoops

Inspirado en una estrategia de ncase.me/trust

def tit_for_whoops(m, t, s):
    if len(t) < 2:
        return 'c'
    else:
        return 'd' if all([x == 'd' for x in t[-2:]]) else 'c'

Defectos solo si el otro jugador ha desertado dos veces seguidas, para evitar malentendidos.

LyricLy
fuente
¡Gracias por tu envío! Tenga en cuenta que dado que la probabilidad de volteo promedia 1/4, habrá un doble volteo una vez cada 16 movimientos más o menos.
isaacg
Agregué una variable de estado, que puedes ignorar si no quieres usarla.
isaacg
9

Cambio de corazon

def change_of_heart(m, t, s):
    return 'c' if len(t) < 180 else 'd'

Tiene un cambio de corazón a medio camino. Lo hace sorprendentemente bien.

qwewqa
fuente
Felicitaciones por tomar la delantera / segundo lugar. Estoy impresionado y sorprendido de que un oponente que ignora la estrategia lo haga tan bien.
isaacg
9

Ladrón de estrategias

Inspirado por suficiente, change_of_heart y tit-for-whoops. Debería ser un poco más indulgente. Traté de ajustar los números para obtener mejores resultados, pero no querían cambiar mucho.

def stealer(mine, theirs, state):
    if len(mine) == 0:
        state.append('c')
        return 'c'
    elif len(mine) > 250:
        return "d"
    elif state[0] == 't':
        return 'd'
    elif mine[-40:].count('d') > 10:
        state[0] = 't'
        return 'd'
    elif theirs[-1] == 'd':
        if state[0] == 'd':
            state[0] = 'c'
            return 'd'
        else:
            state[0] = 'd'
            return 'c'
    elif all([x == 'c' for x in theirs[-3:]]):
        state[0] = 'c'
        return 'c'
    else:
        return 'c'
adebunk
fuente
bienvenido a PPCG!
Giuseppe
¡Felicitaciones por tomar la iniciativa!
isaacg
8

Teta por tiempo

def tit_for_time(mine, theirs, state):
    theirs = theirs[-30:]
    no_rounds = len(theirs)
    return "c" if no_rounds < 5 or random.random() > theirs.count("d") / no_rounds else "d"

Si has pasado la mayor parte del tiempo haciéndome daño, te lastimaré de nuevo. Probablemente.

Azul
fuente
Buena presentación! Actualmente estás en el 1er lugar sin los programas básicos conscientes del oponente.
isaacg
7

Desconfianza creciente

import random

def growing_distrust(mine, theirs, state):
    # Start with trust.
    if len(mine) == 0:
        state.append(dict(betrayals=0, trust=True))
        return 'c'

    state_info = state[0]

    # If we're trusting and we get betrayed, trust less.
    if state_info['trust'] and theirs[-1] == 'd':
        state_info['trust'] = False
        state_info['betrayals'] += 1

    # Forgive, but don't forget.
    if random.random() < 0.5 ** state_info['betrayals']:
        state_info['trust'] = True

    return 'c' if state_info['trust'] else 'd'

Cuanto más me traiciona el oponente, menos puedo confiar en que fuera solo ruido.


fuente
Sí, lo que no es estado es desafortunado, pero quería que las presentaciones fueran uniformes, así que esto es lo mejor que se me ocurrió. ¿Tienes alguna idea de cómo agregar un estado?
isaacg
¿Solo tiene un stateargumento de que por defecto es una lista? Las listas son mutables, por lo que el estado podría modificarse fácilmente.
Letra de
¿Cómo es eso? No veo cómo podría ser eso.
Letra de
@Mnemonic Creo que sé cómo implementar esto. Le daré un giro.
isaacg
Agregué una variable de estado, que inicialmente es una lista vacía, y que puede modificar.
Isaac
7

Jedi2Sith

Comienza todo agradable y desinteresado, pero con el tiempo la influencia del lado oscuro se vuelve cada vez más fuerte, hasta el punto de no retorno. No hay forma de detener esta influencia, pero todas las cosas malas que ve que suceden solo contribuyen al poder del lado oscuro ...

def jedi2sith(me, them, the_force):
  time=len(them)
  bad_things=them.count('d')
  dark_side=(time+bad_things)/300
  if dark_side>random.random():
    return 'd'
  else:
    return 'c'

Pruébalo en línea!

León
fuente
6

Control deslizante

def slider(m, t, s):
    z = [[2, 1], [0, 1], [2, 3], [2, 1]]
    x = 0
    for y in t:
      x = z[x][y == 'c']
    return 'c' if x < 2 else 'd'

Comienza con 'c' y se desliza gradualmente hacia o lejos de 'd'.

millas
fuente
Hice una reescritura funcionalmente equivalente de esto para usar la variable de estado, porque se estaba ejecutando bastante lento. Sin embargo, no necesita cambiar nada.
isaacg
6

Stumbler terco

def stubborn_stumbler(m, t, s):
    if not t:
        s.append(dict(last_2=[], last_3=[]))
    if len(t) < 5:
        return 'c'
    else:
        # Records history to state depending if the last two and three
        # plays were equal
        s = s[0]
        if t[-2:].count(t[-1]) == 2:
            s['last_2'].append(t[-1])
        if t[-3:].count(t[-1]) == 3:
            s['last_3'].append(t[-1])
    c_freq = t.count('c')/len(t)
    # Checks if you've consistently defected against me
    opp_def_3 = s['last_3'].count('d') > s['last_3'].count('c')
    opp_def_2 = s['last_2'].count('d') > s['last_2'].count('c')
    # dist func from 0 to 1
    dist = lambda x: 1/(1+math.exp(-5*(x-0.5)))
    # You've wronged me too much
    if opp_def_3 and opp_def_2:
        return 'd'
    # Otherwise, if you're consistently co-operating, co-operate more
    # the less naive you are
    else:
        return 'c' if random.random() > dist(c_freq) - 0.5 else 'd'

Basado en su estrategia de umbral de explotación con solo jugadas consistentes, se realiza un seguimiento para cambiar entre defectos y cooperar principalmente

ACTUALIZACIÓN: realiza un seguimiento de dos jugadas consecutivas y tres jugadas consecutivas, castigando solo en condiciones más duras y agregando una opción aleatoria cuando no está seguro

ACTUALIZACIÓN 2: condición eliminada y función de distribución agregada

JMigst
fuente
¡Contratulaciones para escribir el primer programa que toma la delantera!
isaacg
6

Ruido Bot

def just_noise(m,t,s):
    return 'c' if random.random() > .2 else 'd'

Definitivamente estoy cooperando bot. Eso es solo ruido.

Chris
fuente
6

Suficiente es suficiente

def enough(m,t,s):
    if not s:
        s.append("c")
        return "c"
    if s[0]=="t":
        return "d"
    if m[-42:].count("d")>10:
        s[0]="t"
        return "d"
    if t[-1]=="d":
        if s[0]=="d":
            s[0]="c"
            return "d"
        else:
            s[0]="d"
            return "c"
    else:
        return "c"

Comienza como tit para dos tats donde los dos tats no tienen que ser consecutivos (a diferencia tit_for_whoops). Si tiene que jugar con ddemasiada frecuencia, va d-total.

Christian Sievers
fuente
¡Felicitaciones por tomar la iniciativa!
isaacg
6

Goldfish Bot

def goldfish(m,t,s):
    return 'd' if 'd' in t[-3:] else 'c'

Un pez dorado nunca perdona, pero se olvida rápidamente.

Chris
fuente
6

tramposo (restablecido de nuevo)

Solo se contabilizan las últimas 10 jugadas, pero se dividen en dos bloques de cinco, que se promedian con cada una clasificada como buena o mala.

Si el oponente juega en promedio "agradable", el tramposo juega cada vez menos agradable. Si los resultados son ambiguos, el tramposo juega bien para atraer al oponente a un lugar seguro. Si el oponente parece estar jugando "mal", el embaucador toma represalias.

La idea es reunir puntos de vez en cuando de jugadores ingenuos, mientras que atrapar a los engañosos temprano.

import random
def trickster(player,opponent,state):
    pBad = 0.75
    pNice = 0.8
    pReallyBad =0.1
    decay = 0.98
    r = random.random()
    if len(player)<20: #start off nice
        return 'c' 
    else: #now the trickery begins
        last5 = opponent[-5:].count('c')/5.0 > 0.5
        last5old = opponent[-10:-5].count('c')/5.0  > 0.5
        if last5 and last5old: #she is naive, punish her
            pBad = pBad*decay #Increase punishment
            if r<pBad:
                return 'c'
            else:
                return 'd'
        elif last5 ^ last5old: #she is changing her mind, be nice!
            if r<pNice:
                return 'c'
            else:
                return 'd'
        else: #she's ratting you out, retaliate
            pReallyBad = pReallyBad*decay #Retaliate harder
            if r<pReallyBad:
                return 'c'
            else:
                return 'd'

Descargo de responsabilidad: nunca he publicado aquí antes, si estoy haciendo algo mal> por favor dígame y lo corregiré.

Hektor-Waartgard
fuente
Bienvenido al sitio! Lamentablemente, su código no funciona actualmente. Tienes un elif después de otro. ¿Podrías arreglarlo? Gracias
isaacg
¿Supongo que todo, desde el elif en adelante, debe sangrarse una vez más?
isaacg
Correcto, lo sangraré.
Hektor-Waartgard
@isaacg He actualizado mi respuesta con un nuevo código. No tengo la reputación suficiente para decírtelo en los comentarios de preguntas. No estoy seguro de que esté usando la variable de estado correctamente, supongo que es una lista vacía a la que puedo agregar lo que quiera, ¿correcto?
Hektor-Waartgard
2
Eso no funcionará. Después de cada turno, se decide si el movimiento actual se voltea o no (independientemente para los dos jugadores). Esa decisión se fija entonces. Siempre verá el mismo primer movimiento que puede ser invertido o no, pero no cambiará.
Christian Sievers
5

Memoria decadente

def decaying_memory(me, them, state):
    m = 0.95
    lt = len(them)

    if not lt:
        state.append(0.0)
        return 'c'

    # If it's the last round, there is no reason not to defect
    if lt >= 299: return 'd'

    state[0] = state[0] * m + (1.0 if them[-1] == 'c' else -1.0)

    # Use a gaussian distribution to reduce variance when opponent is more consistent
    return 'c' if lt < 5 or random.gauss(0, 0.4) < state[0] / ((1-m**lt)/(1-m)) else 'd'

Pesa más la historia reciente. Olvida lentamente el pasado.

qwewqa
fuente
5

Contragolpe

def kickback(m, t, s):
  if len(m) < 10:
    return "c"
  td = t.count("d")
  md = m.count("d")
  f = td/(len(t)+1)
  if f < 0.3:
    return "d" if td > md and random.random() < 0.1 else "c"
  return "c" if random.random() > f+2*f*f else "d"

Algunas ideas vagas ...

Christian Sievers
fuente
Felicitaciones por tomar la iniciativa en la versión en la que se eliminan los hechizos básicos de adaptación.
isaacg
Gracias. Creo que es increíble lo diferente que los dos resultados son!
Cristiano Sievers
4

No realmente obtener todo el "ruido" Cosa

def vengeful(m,t,s):
    return 'd' if 'd' in t else 'c'

Nunca perdona a un traidor.

Chris
fuente
4

sonda:

editar: represalias añadidas en escenarios probablemente de poco ruido

Básicamente, si los 4 primeros movimientos son cooperativos, eso significa que deberíamos esperar menos ruido de lo habitual. desertar un poco de vez en cuando para compensar la menor cantidad de puntos que obtendríamos de no desertar nunca, y poder culpar al ruido. también tomamos represalias si nos fallan

Si nuestro oponente falla mucho en esos turnos (2 o más), simplemente les devolvemos el defecto. si fuera solo ruido, el ruido afectaría nuestros movimientos de todos modos.

de lo contrario, si solo 1 movimiento fue defectuoso, simplemente hacemos tit por tat el resto del juego.

def sounder(my, their, state):
    if len(my)<4:
        if their.count("d")>1:
            return "d"
        return "c"
    elif len(my) == 4:
        if all(i == "c" for i in their):
            state.append(0)
            return "d"
        elif their.count("c") == 3:
            state.append(1)
            return "c"
        else:
            state.append(2)
    if state[0] == 2:
        return "d"
    if state[0] == 0:
        if not "d" in my[-4:]:
            return "d"
        return their[-1]
    else:
        return their[-1]
Limón Destructible
fuente
3

Alterno

def alternate(m, t, s):
    if(len(m)==0):
        return 'c' if random.random()>.5 else 'd'
    elif(len(m)>290):
        return 'd'
    else:
        return 'd' if m[-1]=='c' else 'c'

Elige al azar en la primera ronda, luego alterna Siempre defectos en las últimas 10 rondas.

Chris
fuente
3

Espera 50

def wait_for_50(m, t, s):
  return 'c' if t.count('d') < 50 else 'd'

Después de 50 defectos, ¡déjelos!

MegaTom
fuente
Arreglé tu pitón mientras preservaba tu intención.
isaacg
Felicitaciones por pasar al 3er lugar.
isaacg
2

Somehwat ingenuo

def somewhat_naive(m, t, s):
    p_flip = 0.25
    n = 10
    if len(t) < n:
        return 'c' if random.random() > p_flip else 'd'
    d_freq = t[-n:].count('d')/n
    return 'c' if d_freq < p_flip else 'd'

Solo asumiré que si has desertado menos de la probabilidad de volteo (aproximadamente) en los últimos n turnos, ¡fue ruido y no es que seas malo!

No he descubierto la mejor n , podría investigar más a fondo.

JeroendeK
fuente
2

Cada tres

def everyThree(me,him,s):
    if len(me) % 3 == 2:
        return "d"
    if len(me) > 250:
        return "d"
    if him[-5:].count("d")>3:
        return "d"
    else:
        return "c"

Defectos cada tres turnos independientemente. También defectos los últimos 50 turnos. También defectos si su oponente desertó 4 de 5 de las últimas rondas.

MegaTom
fuente
2

Cubos

def buckets(m, t, s):
    if len(m) <= 5:
        return 'c'
    if len(m) >= 250:
        return 'd'
    d_pct = t[-20:].count('d')/len(t[-20:])
    if random.random() > (2 * d_pct - 0.5):
        return 'c'
    else:
        return 'd'

Se juega bien para comenzar. Mira sus últimos 20, si <25% d, devuelve c,> 75% d, devuelve d, y en el medio elige aleatoriamente a lo largo de una función de probabilidad lineal. Últimos 50, defectos. Tenía esto al menos 10 pero vi muchos últimos 50 defectos.

Primera vez aquí, así que avíseme si hay que arreglar algo (o cómo puedo probar esto).

brian_t
fuente
Si desea probar cosas localmente, puede clonar el repositorio y ejecutar noisy-game.py. Lleva un tiempo, por lo que es posible que desee eliminar algunos de los oponentes playerspara iteraciones rápidas.
isaacg
Gracias Isaac, tendré que jugar con eso y hacer algunos retoques.
brian_t
1

Tit-For-Stat

Defectos si el oponente ha desertado más de la mitad del tiempo.

def tit_for_stat(m, t, s):
  if t.count('d') * 2 > len(m):
    return 'd'
  else:
    return 'c'
RamenChef
fuente