Esta tarea forma parte del primer empuje de programación periódica Premier Puzzle y está destinada a ser una demostración de la nueva propuesta de tipo desafío del rey de la colina .
La tarea es escribir un programa para jugar el dilema del prisionero iterado mejor que otros entrantes.
Mira, Vinny. Conocemos a tu compañero de celda --- ¿cómo se llama? Sí, McWongski, el mafioso nippo-irlandés-ucraniano, está tramando algo y ya sabes lo que es.
Estamos tratando de ser amables aquí, Vinnie. Dándote una oportunidad.
Si nos dice lo que está planeando, veremos que obtenga una buena asignación de trabajo.
Y si no lo haces ...
Las reglas del juego
- El concurso consiste en un round-robin completo (todas las parejas posibles) de dos concursantes a la vez (incluidas las jugadas propias).
- Hay 100 rondas jugadas entre cada par
- En cada ronda se le pide a cada jugador que elija entre cooperar con el otro jugador o traicionarlo, sin conocer las intenciones de los otros jugadores en el asunto, pero con un recuerdo de los resultados de las rondas anteriores jugadas contra este oponente.
- Se otorgan puntos por cada ronda en función de la elección combinada. Si ambos jugadores cooperan, cada uno obtiene 2 puntos. La traición mutua produce 1 punto cada uno. En el caso mixto, el jugador que traiciona recibe 4 puntos y el cooperador es penalizado por 1.
- Una partida "oficial" se ejecutará a más tardar 10 días después de la publicación con todas las presentaciones que pueda poner a trabajar y se utilizará para seleccionar el ganador "aceptado". Tengo una caja Mac OS 10.5, por lo que las soluciones POSIX deberían funcionar, pero hay linuxismos que no funcionan. Del mismo modo, no tengo soporte para la API win32. Estoy dispuesto a hacer un esfuerzo básico para instalar cosas, pero hay un límite. Los límites de mi sistema de ninguna manera representan los límites de las respuestas aceptables, simplemente las que se incluirán en la coincidencia "oficial".
La interfaz del programador
- Las entradas deben tener la forma de programas que se pueden ejecutar desde la línea de comandos; la decisión debe ser la salida (única) del programa en la salida estándar. La historia de rondas anteriores con este oponente se presentará como un argumento de línea de comando.
- Salida es "c" (por callarse ) o "T" (para decir a todos ).
- La historia es una sola cadena de caracteres que representan rondas previas con las rondas más recientes venir antes en la cadena. Los personajes son
- "K" (por guardado la fe significa la cooperación mutua)
- "R" (para rata b @ st @ rd me entradas agotadas )
- "S" (por lechón! Lo que significa que se benefició de una traición)
- "E" (para todo el mundo está mirando hacia fuera para el número uno en la traición mutua)
el soporte
Cuatro jugadores serán proporcionados por el autor
- Ángel - coopera siempre
- Diablo - siempre habla
- TitForTat: coopera en la primera ronda y siempre hace lo que hizo en la última ronda
- Aleatorio - 50/50
a lo que agregaré todas las entradas que pueda ejecutar.
El puntaje total será el puntaje total contra todos los oponentes (incluidas las jugadas individuales solo una vez y usando el puntaje promedio).
Entrantes
(vigente a partir del 2 de mayo de 2011 7:00)
El apretón de manos secreto | Anti-misiles T42T | La desconfianza (variante) | Anti-apretón de manos | El pequeño ceceoso | convergencia | tiburón | Probabimatic | Pavlov - Win Stay, interruptor Pierde | Honor entre ladrones | Ayuda vampiro | druida | Poco Schemer | Lo pasado | Dan las dos Tats | Simpleton |
Goleador
#! /usr/bin/python
#
# Iterated prisoner's dilemma King of Hill Script Argument is a
# directory. We find all the executables therein, and run all possible
# binary combinations (including self-plays (which only count once!)).
#
# Author: dmckee (https://codegolf.stackexchange.com/users/78/dmckee)
#
import subprocess
import os
import sys
import random
import py_compile
###
# config
PYTHON_PATH = '/usr/bin/python' #path to python executable
RESULTS = {"cc":(2,"K"), "ct":(-1,"R"), "tc":(4,"S"), "tt":(1,"E")}
def runOne(p,h):
"""Run process p with history h and return the standard output"""
#print "Run '"+p+"' with history '"+h+"'."
process = subprocess.Popen(p+" "+h,stdout=subprocess.PIPE,shell=True)
return process.communicate()[0]
def scoreRound(r1,r2):
return RESULTS.get(r1[0]+r2[0],0)
def runRound(p1,p2,h1,h2):
"""Run both processes, and score the results"""
r1 = runOne(p1,h1)
r2 = runOne(p2,h2)
(s1, L1), (s2, L2) = scoreRound(r1,r2), scoreRound(r2,r1)
return (s1, L1+h1), (s2, L2+h2)
def runGame(rounds,p1,p2):
sa, sd = 0, 0
ha, hd = '', ''
for a in range(0,rounds):
(na, ha), (nd, hd) = runRound(p1,p2,ha,hd)
sa += na
sd += nd
return sa, sd
def processPlayers(players):
for i,p in enumerate(players):
base,ext = os.path.splitext(p)
if ext == '.py':
py_compile.compile(p)
players[i] = '%s %sc' %( PYTHON_PATH, p)
return players
print "Finding warriors in " + sys.argv[1]
players=[sys.argv[1]+exe for exe in os.listdir(sys.argv[1]) if os.access(sys.argv[1]+exe,os.X_OK)]
players=processPlayers(players)
num_iters = 1
if len(sys.argv) == 3:
num_iters = int(sys.argv[2])
print "Running %s tournament iterations" % (num_iters)
total_scores={}
for p in players:
total_scores[p] = 0
for i in range(1,num_iters+1):
print "Tournament %s" % (i)
scores={}
for p in players:
scores[p] = 0
for i1 in range(0,len(players)):
p1=players[i1];
for i2 in range(i1,len(players)):
p2=players[i2];
# rounds = random.randint(50,200)
rounds = 100
#print "Running %s against %s (%s rounds)." %(p1,p2,rounds)
s1,s2 = runGame(rounds,p1,p2)
#print (s1, s2)
if (p1 == p2):
scores[p1] += (s1 + s2)/2
else:
scores[p1] += s1
scores[p2] += s2
players_sorted = sorted(scores,key=scores.get)
for p in players_sorted:
print (p, scores[p])
winner = max(scores, key=scores.get)
print "\tWinner is %s" %(winner)
total_scores[p] += 1
print '-'*10
print "Final Results:"
players_sorted = sorted(total_scores,key=total_scores.get)
for p in players_sorted:
print (p, total_scores[p])
winner = max(total_scores, key=total_scores.get)
print "Final Winner is " + winner
- Las quejas sobre mi horrible pitón son bienvenidas, ya que estoy seguro de que esto apesta en más de una forma
- correcciones de errores dan la bienvenida
Anotador de cambios:
- Imprima jugadores y puntajes ordenados y declare un ganador (29/04, Casey)
- Opcionalmente, ejecute torneos múltiples (
./score warriors/ num_tournaments)
) predeterminado = 1, detecte y compile fuentes de Python (4/29, Casey) - Se corrigió un error particularmente tonto en el que al segundo jugador se le pasaba un historial incorrecto. (30/4, dmckee; gracias Josh)
Guerreros iniciales
A modo de ejemplo, y para que los resultados puedan verificarse
Ángel
#include <stdio.h>
int main(int argc, char**argv){
printf("c\n");
return 0;
}
o
#!/bin/sh
echo c
o
#!/usr/bin/python
print 'c'
Diablo
#include <stdio.h>
int main(int argc, char**argv){
printf("t\n");
return 0;
}
Aleatorio
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
int main(int argc, char**argv){
srandom(time(0)+getpid());
printf("%c\n",(random()%2)?'c':'t');
return 0;
}
Tenga en cuenta que el anotador puede volver a invocar al guerrero muchas veces en un segundo, por lo que se debe hacer un esfuerzo serio para asegurar la aleatoriedad de los resultados si se usa el tiempo para sembrar el PRNG.
TitForTat
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv){
char c='c';
if (argv[1] && (
(argv[1][0] == 'R') || (argv[1][0] == 'E')
) ) c='t';
printf("%c\n",c);
return 0;
}
El primero que realmente hace algo con la historia.
Ejecutar el anotador solo en los rendimientos de guerreros provistos
Finding warriors in warriors/
Running warriors/angel against warriors/angel.
Running warriors/angel against warriors/devil.
Running warriors/angel against warriors/random.
Running warriors/angel against warriors/titfortat.
Running warriors/devil against warriors/devil.
Running warriors/devil against warriors/random.
Running warriors/devil against warriors/titfortat.
Running warriors/random against warriors/random.
Running warriors/random against warriors/titfortat.
Running warriors/titfortat against warriors/titfortat.
('warriors/angel', 365)
('warriors/devil', 832)
('warriors/random', 612)
('warriors/titfortat', 652)
Ese demonio, es un artesano, y los buenos chicos aparentemente son los últimos.
Resultados
de la carrera "oficial"
('angel', 2068)
('helpvamp', 2295)
('pavlov', 2542)
('random', 2544)
('littleschemer', 2954)
('devil', 3356)
('simpleton', 3468)
('secrethandshake', 3488)
('antit42t', 3557)
('softmajo', 3747)
('titfor2tats', 3756)
('convergence', 3772)
('probabimatic', 3774)
('mistrust', 3788)
('hyperrationalwasp', 3828)
('bygones', 3831)
('honoramongthieves', 3851)
('titfortat', 3881)
('druid', 3921)
('littlelisper', 3984)
('shark', 4021)
('randomSucker', 4156)
('gradual', 4167)
Winner is ./gradual
fuente
return (s1, L1+h1), (s2, L2+h1)
areturn (s1, L1+h1), (s2, L2+h2)
[Nota enL2+h2
lugar deL2+h1
al final]? // Error de cortar y pegar o algo igualmente idiota. Sheesh!Respuestas:
Gradual
Esta estrategia se basa en un artículo de Beaufils, Delahaye y Mathieu . Mi C realmente no es la mejor, así que si alguien tiene alguna sugerencia para mejorar / acelerar el código, ¡hágamelo saber!
[Editar] Vale la pena señalar que Gradual fue diseñado para ser una estrategia que supera a Tit para Tat. Tiene propiedades similares en el sentido de que está dispuesto a cooperar y tomar represalias contra un oponente defectuoso. A diferencia de Tit for Tat, que solo tiene un recuerdo de la última ronda jugada, Gradual recordará la interacción completa y desertará la cantidad de veces que el oponente ha desertado hasta ahora. Sin embargo, ofrecerá cooperación mutua luego nuevamente.
Como de costumbre, el desempeño de la estrategia depende un poco de la alineación de otras estrategias. Además, el documento original no era realmente claro sobre algunos detalles.
fuente
El apretón de manos secreto
La estrategia aquí es sacrificar las primeras 10 rondas para realizar un apretón de manos "secreto". Si estoy celulado conmigo mismo, entonces reconozco la historia de los primeros 10 movimientos y me pongo mi gorra de Ángel por el resto del juego. Tan pronto como reconozco que mi compañero de celda no soy yo mismo, me transformo en un Demonio en un intento de aprovechar a los compañeros de celda demasiado cooperativos.
Si sacrificar las primeras 10 rondas me permitirá superar al Diablo, depende en gran medida de cuántas entradas haya. Para minimizar el daño, solo 3 cooperaciones aparecen en el apretón de manos.
Editar: TAGMATCH dinámico ahora para evitar errores estúpidos como cambiar solo uno de ellos y así puedo hacer que TAG sea dinámico en algún momento en el futuro.
Edición 2: ahora genera aleatoriamente la etiqueta en la primera ejecución y la almacena en el archivo especificado por
sys.argv[0]
(.pyc
reemplazado por.py
lo que va al código, no al código de bytes, archivo). Creo que esta es la única información que tienen todas mis instancias que nadie más tiene, por lo que parece ser la única opción para evitar los parásitos.fuente
TAG
se estaba jugando al revés. Sin embargo, ¿no deberíasTAGMATCH
ser 'KEEEKEEEKE'?"".join({('c', 'c'):'K', ('t', 't'): 'E'}[moves] for moves in zip(TAG, TAG))
.py
archivos su código y extraer la etiqueta. Sin embargo, no haré eso en C ...The Little Lisper
El diablo
Considere el siguiente formato (Player1, Player2)
Suponiendo que P2 es el diablo, no hay forma de que el diablo pueda perder puntos, de hecho, lo peor que puede hacer es ganar solo un punto. Por lo tanto, frente a un oponente puramente aleatorio, la peor puntuación posible del diablo será exactamente (5/2) * n donde n es el número de "juegos" jugados. Su peor caso absoluto es contra sí mismo, donde su puntaje será n, y su mejor caso es contra un ángel, que será 4 * n
Afirmar: optical_strat = devil
Este es un torneo. Apuñalar a mi compañero de celda es una estrategia mucho mejor que la cooperación porque ayuda a MI PUNTUACIÓN más (+4). BONIFICACIÓN: ¡se estrelló (-1)! Si le saco el cuello por él, puedo ganar (+2) y perder (-1). Por lo tanto, estadísticamente la puñalada es recompensada.
¿Pero es óptimo?
No hay ninguna razón para cooperar NUNCA (bajo este sistema de puntuación).
En el sistema KOTH, la maximización de los retornos es esencial. Incluso si tiene dos bots que se sincronizan perfectamente y cooperan, sus puntajes individuales solo se verán aumentados en 200 puntos por su espíritu deportivo. Un demonio, por otro lado, ganará al menos 100 puntos, con un caso promedio de 200 y un máximo de 400, ¡y le costará a sus oponentes hasta 100 puntos cada uno! Entonces, prácticamente, el diablo realmente anota un juego promedio de 300, llegando a 500.
En pocas palabras: el tiempo dirá
Para mí, parece que la puntuación debería reconsiderarse para que el diablo no se tome el día. Aumentar el puntaje de cooperación a 3 todos podría hacerlo. Sin embargo, es posible detectar demonios y evitar que obtengan sus 400 completos, como muestran pavlov y rencor. ¿Puedo probar que cualquiera de los dos obtendrá suficientes puntos para su cooperación para justificar su fe? no. Todo eso depende del campo final de los contendientes.
Y por favor, haz lo peor con esta publicación. Quiero escribir mi trabajo principal sobre esto cuando todo esté dicho y hecho.
Historial de versiones
VERSIÓN OFICIAL DE LISPER
DESARROLLAR LA VERSIÓN DE LISPER
fuente
fink install clisp
:: tocando los dedos repetidamente ::There is no reason to EVER (under this scoring system) co-operate
es solo medio correcto. Si sabes que tu oponente no tiene en cuenta el historial (ángel, demonio, aleatorio), entonces siempre debes desertar. Si tu oponente toma en cuenta el historial y puedes sincronizar, entonces puedes hacerlo mejor. Tengo un par de ideas que giran en torno a detectar si el oponente es racional o superracional.(random 20)
da 2, 5 u 8,(/ (+1 rand-num) 10)
es 0.3, 0.6, 0.9, y el resto de la división con 0.3 es 0; Entonces(floor *dbag* *margin*)
muere.Desconfianza (variante)
Este salió por primera vez en mis propias pruebas hace años (en aquel entonces estaba en el 11 ° grado e hice una pequeña tesis sobre exactamente esto, usando estrategias diseñadas por otros estudiantes también). Comienza con la secuencia
tcc
(y juega como Tit para Tat después de eso.Disculpas por el horrible código; si alguien puede hacer eso más corto sin jugar golf exactamente, estaría agradecido :-)
fuente
case 1: case2: printf(...); break;
. Y gcc quiere una declaración explícita destring.h
usostrlen
. En cualquier caso lo tengo funcionando.Popen(p+" "+h,stdout=subprocess.PIPE,shell=True)
cuándoh = ''
. Supongoargc=1
.Misil anti-T42T
Lo hace razonablemente bien contra el conjunto base de guerreros: mata a Angel, ligeramente derrotado por Devil (pero mantiene su puntaje bajo), generalmente vence a RAND fácilmente y apenas le gana a Tit por Tat. Hace mal cuando juega contra sí mismo.
fuente
Convergencia
Inicialmente agradable, luego juega al azar con un ojo en la historia del oponente.
He intentado incluir la ponderación en la historia, pero no la he optimizado correctamente.
fuente
Tiburón
Lo hace bastante bien contra la lista base.
fuente
Pavlov - Gana la estancia, pierde el interruptor
En el primer turno coopera, y luego coopera si y solo si ambos jugadores optaron por la misma opción en el movimiento anterior.
fuente
hist[0]
(hist[-1]
es siempre el primer movimiento de la ronda)?Honor entre ladrones
Tenga en cuenta que
THIEVES_CANT
es esencialmente un apretón de manos, aunque solo surgirá cuando juegue contra un cooperador. Sin embargo, evita el problema del parásito al buscar cruces posteriores. Lo hace bastante bien contra la lista base.fuente
"Probabimatic"
Comienza cooperando, luego elige la opción que le dé el valor más alto esperado. Simple.
Solía comenzar por cooperar, pero ahora parece que los defectos funcionan mejor. EDITAR: Oh, espera, en realidad no lo hace.
fuente
for (char c = *str;
achar c; for (c = *str;
gcc, compilará esto sin quejarse de que debe ponerse en modo C99.Avispa hiperracional
Implementado en Java porque no estaba seguro de cuán complejas iban a terminar las estructuras de datos. Si esto es un problema para alguien, entonces creo que puedo portarlo a bash sin demasiados problemas porque al final solo usa matrices asociativas simples.
Nota : He eliminado esto de un paquete en línea con la última versión de mi parche al anotador para manejar Java. Si desea publicar una solución Java que use clases internas, entonces deberá parchear el parche.
Los cambios que hice al anotador para ejecutar esto son:
Gracias a @rmckenzie por desplegar mi función de desafío.
fuente
Exception in thread "main" java.lang.NoClassDefFoundError: //warriors/HyperrationalWasp Caused by: java.lang.ClassNotFoundException: ..warriors.HyperrationalWasp at java.net.URLClassLoader$1.run(URLClassLoader.java:217) at java.security.AccessController.doPrivileged(Native Method) at java.net.URLClassLoader.findClass(URLClassLoader.java:205) at java.lang.ClassLoader.loadClass(ClassLoader.java:321) at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:294) at java.lang.ClassLoader.loadClass(ClassLoader.java:266)
Soft_majo
Ah, bueno, otra de las estrategias estándar, solo para completar la alineación.
Éste elige el movimiento que más ha hecho el oponente; si es igual coopera.
fuente
Lechón aleatorio
Éste fallará si el oponente lo hace con demasiada frecuencia (umbral), pero de vez en cuando intentará apuñalar por la espalda.
Funciona bastante bien contra todos excepto los jugadores de Java y Lisp (que no puedo ejecutar, ya que ni Java ni Lisp están en la máquina de prueba); la mayoría de las veces al menos.
fuente
Pasado
No he encontrado el mejor valor por el
bygones
momento. No espero que esto sea un estrategia ganadora , pero estoy interesado en el desempeño de una estrategia algo así como lo que creo que es "bueno" en la vida real. Una revisión futura también puede incluir verificar el número de deserciones mutuas.fuente
Vampiro de ayuda
Tiene un resultado divertido y asimétrico cuando se enfrenta a sí mismo. Si tan solo esta solución pudiera aplicarse en la vida real.
fuente
druida
Funciona razonablemente bien contra el roster base.
fuente
Simplón
Está bien contra la lista base.
fuente
Pequeño Schemer
Lo hace mal contra el conjunto base, pero bastante bien contra su objetivo. Obviamente, no está escrito en Scheme.
fuente
Teta para dos tatuajes
otro viejo favorito
fuente
sys.exit(0)
? O simplemente déjalo terminar. Editar: también la primera invocación a su programa es sin ningún historial, lo que provoca unIndexError
cuando lo haceargv[1]
.len(history)<2
cláusula, porque esa última se parece a laelse
parte.return
especialmente!