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.py
para 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.
fuente
exploit_threshold()
varias veces comoexploit_threshold1()
, etc. y las agregué a laplayers
lista. ¿Por qué obtengo resultados muy diferentes para estrategias idénticas?Respuestas:
Genug ist nicht genug
(también podría llamarse
enough2
ostealback
)Aprendí que el tit original para dos tats esperaba dos tats consecutivos como lo
tit_for_whoops
hace, 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.fuente
Tit-For-Whoops
Inspirado en una estrategia de ncase.me/trust
Defectos solo si el otro jugador ha desertado dos veces seguidas, para evitar malentendidos.
fuente
Cambio de corazon
Tiene un cambio de corazón a medio camino. Lo hace sorprendentemente bien.
fuente
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.
fuente
Teta por tiempo
Si has pasado la mayor parte del tiempo haciéndome daño, te lastimaré de nuevo. Probablemente.
fuente
Desconfianza creciente
Cuanto más me traiciona el oponente, menos puedo confiar en que fuera solo ruido.
fuente
state
argumento de que por defecto es una lista? Las listas son mutables, por lo que el estado podría modificarse fácilmente.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 ...
Pruébalo en línea!
fuente
Control deslizante
Comienza con 'c' y se desliza gradualmente hacia o lejos de 'd'.
fuente
Stumbler terco
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
fuente
Ruido Bot
Definitivamente estoy cooperando bot. Eso es solo ruido.
fuente
Suficiente es suficiente
Comienza como tit para dos tats donde los dos tats no tienen que ser consecutivos (a diferencia
tit_for_whoops
). Si tiene que jugar cond
demasiada frecuencia, vad
-total.fuente
Goldfish Bot
Un pez dorado nunca perdona, pero se olvida rápidamente.
fuente
fuente
Memoria decadente
Pesa más la historia reciente. Olvida lentamente el pasado.
fuente
Contragolpe
Algunas ideas vagas ...
fuente
No realmente obtener todo el "ruido" Cosa
Nunca perdona a un traidor.
fuente
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.
fuente
Alterno
Elige al azar en la primera ronda, luego alterna Siempre defectos en las últimas 10 rondas.
fuente
Espera 50
Después de 50 defectos, ¡déjelos!
fuente
Somehwat ingenuo
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.
fuente
Cada tres
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.
fuente
Cubos
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).
fuente
players
para iteraciones rápidas.Tit-For-Stat
Defectos si el oponente ha desertado más de la mitad del tiempo.
fuente