Fondo
El juego de Morra es un juego simple. En la versión "original", varios jugadores tiran simultáneamente un número 0-5 con sus manos mientras adivinan la suma total de las manos de todos. La versión que usaré aquí se ha modificado para aumentar el potencial de una estrategia no trivial, y se describe a continuación:
- Hay dos jugadores
- Como en piedra, papel o tijera, los jugadores se mueven simultáneamente.
- Cada turno, cada jugador elige un número 0-5 y también adivina la elección de sus oponentes de 0-5. Esto significa que se emiten dos números cada turno. Para aclarar, la salida de ambos números debe estar en el rango 0-5, inclusive.
- Si adivina correctamente la elección de su oponente pero su oponente no adivinó correctamente, gana un cierto número de puntos igual a la suma de los dos números jugados. Por ejemplo, si los números jugados fueron 3 y 5, una suposición correcta valdría 8 puntos.
- Si ambos o ninguno de los jugadores adivinan correctamente, no se otorgan puntos.
- La persona con más puntos después de 1000 rondas gana ese juego.
El torneo
El torneo se realizará en un estilo de todos contra todos y se realizará creando cada posible pareja de concursantes. Por cada victoria, el concursante gana 2 puntos de victoria. Cada empate resulta en 1 punto de victoria. No se ganan puntos de victoria por una pérdida.
Intuitivamente, el ganador del torneo será el concursante con más puntos de victoria contra otros.
Cómo entrar
Habrá dos métodos para enviar bots para competir. El primer método, y muy preferido, es implementar una interfaz Java provista por el controlador. El segundo método es escribir un programa independiente.
Cubramos primero el método Java. La interfaz que tendrá que aplicar es Player
y define dos métodos: public String getName()
identifica su bot, y public int[] getMove(String[] args)
toma args
como una matriz de seis cuerdas, mychoices myguesses myscore opponentchoices opponentguesses opponentscore
. Un ejemplo es el siguiente:
042 045 0 324 432 6
Esto significa que elegí 0 en la primera ronda y supuse que mi oponente iba a lanzar un 0. Mi oponente lanzó un 3 y supuso que lanzaría un 4. En la tercera ronda, mi oponente hizo la suposición correcta de que lanzaría un 2, lo que significa que gana 2 + 4 = 6 puntos.
Su método devolverá una matriz de dos enteros, que son su elección y suposición, respectivamente. Un ejemplo es {4,2}
para una elección de 4 y una suposición de 2.
Aquí hay un ejemplo de un bot Java completo escrito como método. Si lo desea, su envío solo debe incluir lo que está pasando en el getMove
método.
import java.util.Random;
/**
* A simple example Morra bot to get you started.
*/
public class ExampleBot implements Player
{
public String getName()
{
return "ExampleBot";
}
public int[] getMove(String [] args)
{
//easiest way I know to break down to create a move history
//(just contains their throw history)
char[] theirThrowsC = args[3].toCharArray();
int[] theirThrows = new int[theirThrowsC.length];
for(int i = 0; i < theirThrowsC.length; i++)
{
theirThrows[i] = Integer.parseInt(Character.toString(theirThrowsC[i]));
}
//get my score
int myScore = Integer.parseInt(args[2]);
Random r = new Random();
int guess = r.nextInt(6);
if(theirThrows.length > 0)
{
guess = theirThrows[theirThrows.length-1];
}
//throws a random number, guesses what they threw last
return new int[] {r.nextInt(6),guess};
}
public static int otherMethod(int example) //you can write additional static methods
{
return 0;
}
}
Como un programa independiente
Actualmente estoy limitado en mi soporte de idiomas adicionales. Además de Java, puedo aceptar programas escritos en Python 3.4, Perl 5 o Ruby 2.1.5. Si hay un idioma que varias personas parecen desear, haré todo lo posible para agregarlo.
La entrada a su programa serán argumentos en la línea de comando. Podría verse así:
perl awesomebot.plx 042 045 0 324 432 6
La salida de su programa debe ser su elección seguida de su conjetura, cada uno seguido de espacios en blanco.
Incluya en su respuesta el comando exacto necesario para ejecutarlo. Tenga en cuenta que estoy ejecutando Windows 8.1.
Reglas extra
Ahorro de estado y tiempos de espera
Su programa podrá crear un archivo de texto en el directorio local, donde puede almacenar información. Esta información se mantendrá durante todo el torneo pero se eliminará después. Dale al archivo un nombre que pueda identificar.
Hay un límite de tiempo de 500 milisegundos para que su código responda. No responder en el límite de tiempo (o dar un movimiento no válido) resultará en la pérdida de ese partido en particular. Los envíos de Java actualmente tienen un tiempo de espera pasivo (que puedo actualizar a activo), mientras que los envíos que no son de Java tienen un tiempo de espera activo donde su proceso finaliza después de 500 milisegundos.
Más reglas de presentación
- Se le permiten múltiples envíos, siempre que cumplan con las reglas y no etiqueten al equipo.
- Cada entrada debe ser única. No puedes hacer una copia exacta de la lógica de otro bot en un idioma diferente.
- Los bots no pueden interactuar entre sí (para formar un equipo de cualquier tipo).
- No puede usar la lógica de los otros bots dentro de su bot para, por ejemplo, identificar a su competidor y predecir sus acciones. Por supuesto, puedes tratar de determinar la estrategia de tu oponente.
- No intente meterse con el controlador, otros concursantes o mi computadora. No se conecte a fuentes de información externas.
El controlador
La versión actual del controlador se encuentra aquí . Está escrito en Java 8. El archivo "Torneo" es el controlador principal, que también contiene la lista de competidores (si desea organizar sus propias competiciones).
Tabla de clasificación
Realmente no he podido actualizar la tabla de clasificación con mucha frecuencia. Estoy bastante ocupado este fin de semana. Por "bastante ocupado" quiero decir que no hay acceso a una computadora de 6:30 a.m. a 9:30 p.m. Aquí están los puntajes después de 5 carreras. El bot "Echo" siguió perdiendo por alguna razón (podría ser mi culpa, aún no lo he investigado).
170 - Quinn and Valor
158 - Historian
142 - DeltaMax
140 - MorraCowbell
132 - Extrapolator
115 - Rainbolt
102 - Popularity
100 - Interpolator
83 - CounterBot
80 - Basilisk
76 - Erratica
65 - Trendy
63 - Scholar
62 - RandomGuesser
60 - KingFisher
59 - NullifierBot
55 - EvolvedBot
48 - Confused
Crédito
Muchas gracias a Rainbolt y Peter Taylor por su ayuda con el controlador.
fuente
Respuestas:
Morra Cowbell
Para cualquiera que busque importancia en el nombre de este bot, el nombre Morra me hace pensar en el espacio italiano , por lo que pensé que necesitaba un nombre que jugara en eso. Otros candidatos incluidos Morra te engañaron a ti y a Morra por mí .
Esta es una clase completa que implementa la
Player
interfaz. Explicación a continuación.Explicación
Comencé analizando juegos con menos dedos. El más simple no trivial permite llamadas de
0
o1
y tiene la siguiente tabla de pagos (los valores son pagos para el jugador de la fila):La
(0,0)
estrategia está dominada por(0,1)
, por lo que podemos reducir la tabla aAhora la
(1,0)
estrategia está dominada por(0,1)
, por lo que podemos reducir aún más la tabla aY ahora
(1,1)
está dominado por(0,1)
, así que terminamos conPor lo tanto, jugar siempre
(0,1)
es un equilibrio de Nash. Pero lo curioso es que no es el único. Este es un juego simétrico de suma cero, por lo que el resultado esperado es 0, y cualquier combinación de estrategia mixta(0,1)
y(1,0)
dónde(0,1)
se elija al menos el 50% del tiempo logra esa recompensa. Entonces tenemos un espacio unidimensional de equilibrios de Nash.Parece ser el caso, aunque no lo he probado, que el
n
dedo Morra tiene unn
politopo tridimensional de equilibrios de Nash que son estrategias mixtas entre losn+1
(pick, guess)
pares para los cualespick + guess = n
.Los números mágicos en el código anterior codifican los 32 vértices del politopo 5-dimensional de equilibrios de Nash. Los encontré configurando una instancia de programación lineal que representaba el politopo y luego usando funciones objetivas aleatorias. La razón para codificar los 32 en lugar de elegir uno es simple: el resultado esperado es 0, por lo que necesito hacerlo mejor de lo esperado para obtener una victoria. Básicamente, supongo que el otro jugador está usando una estrategia mixta y calculo la distribución en función de su historial de selección. Luego selecciono el vértice del politopo que maximiza mi ganancia esperada contra esa distribución estimada.
QuinnAndValor demuestra la vulnerabilidad de la suposición de que el otro jugador está usando una estrategia mixta. Al detectar a un jugador que usa las estrategias de los equilibrios de Nash, puede cambiar a un modo de caminata aleatoria donde, jugando una estrategia de no equilibrio, es probable que pierda en promedio, pero solo necesita ganar una ventaja de vez en cuando puede volver a jugar pares para los cuales
pick + guess = n
. Por lo tanto, los equilibrios de Nash para un solo juego no se generalizan trivialmente a los equilibrios de Nash para el juego repetido, lo que permite estrategias más complejas.fuente
Quinn y Valor (actualizado)
Quinn y Valor son un equipo de guardabosques de élite. Con ballesta y garra, destrozan a todos los oponentes que se atreven a desafiarlos.
Casi siempre ganan contra todas las soluciones Java en mi máquina.
Editar:
Admito que Quinn y Valor no pudieron pelear contra el Historiador, pero todavía tengo buena fe en ellos para ganar el torneo.
Mi principio es, para cualquier solución con
choice + guess == 5
, también jugar con loschoice + guess == 5
beneficiarios manteniendo su ventaja.Actualizar:
Bueno ... todo se volvió complicado.
fuente
Erudito
El erudito intenta aprender de los movimientos de su oponente, eligiendo el que su oponente menos adivinó y adivinando el que más usó su oponente. Pero la teoría no lo es todo, por lo que Scholar no lo hace muy bien ...
fuente
DeltaMax
(Se actualizó para no usar archivos y se agregó una nueva sección. También se modificó para no quedarse atascado en la primera sección).
Consiste en un par de estrategias que comienzan de manera simple y luego se vuelven más complejas; si borra una, se pasa a la siguiente sección.
{0, 5}
constantemente(choice, guess)
par que tenga la mejor expectativa, ponderado para que las rondas recientes sean más importantesPara averiguar qué estrategia se utilizó al final, descomente el
línea.
Disculpas por el horrible Java, pasé la tarde juntando partes y volviendo a aprender el idioma :)
fuente
private int strat;
es decir, es lo suficientemente bueno.Historiador
(Actualizado: la misma lógica, código más corto y 100 veces más rápido, pero solo puedes usar un bot Historian en un torneo).
Utiliza ponderación aleatoria para elegir un par de tiro y conjetura basado en la efectividad de usar solo ese par contra la historia previa de los oponentes. Los pesos son los cuadrados de las puntuaciones alcanzables.
Golpea
Quinn and Valor
(ya no) y pierdeMorra Cowbell
. En el torneo con la mayoría de los botsHistorian
ocupa el segundo lugarQuinn and Valor
.fuente
Morra Cowbell
. Editado el post. Sin embargo, puede eliminar comentarios si se vuelven obsoletos.Extrapolador (v1.1)
Extrapolación extrema de uno de los equilibrios de Nash de un juego más simple.
¡Apoyo el formato de respuesta breve! (En estilo pitón).
Parece vincularse con la Vaca Mágica (Morra Cowbell) y supera otras entradas que verifiqué.
fuente
De moda
Trendy echa un vistazo a los movimientos pasados del oponente, ponderándolos por lo reciente. Adivina el más pesado, y escoge uno cambiado ligeramente de eso. Aquí está, en todo su esplendor:
Lo único con lo que puedo compararlo ahora es Cowbell. Pierde por un pequeño margen la mayoría de las veces, pero aparece en la parte superior con la frecuencia suficiente para mi gusto. Veremos cómo le va con más competidores.
fuente
Adivinador aleatorio
Esto es realmente sencillo. Efectivamente tira un d6, y agrega otro rollo al rollo anterior para su suposición. No ganará, pero proporcionará un buen punto de referencia.
fuente
Confundido, Python 3
Una entrada innecesariamente complicada. Incluso yo no sé lo que hace.
Aunque este algoritmo avanzado parece funcionar peor que al azar en este torneo, y utiliza una memoria y un tiempo de ejecución significativos, tiene resultados sorprendentes para ciertos valores de 5 ;-)
fuente
Perno de lluvia
Toma la diferencia entre los dos últimos números que adivinó nuestro oponente, agrega eso a la última suposición de nuestro oponente, encuentra el módulo y evita elegir ese número a toda costa. Por ejemplo, si adivina {5,4,3} (disminuyendo en uno), entonces evitaríamos elegir 2 a toda costa.
Toma la diferencia entre los dos últimos números que eligió nuestro oponente, agrega eso a la última opción de nuestro oponente y adivina ese número. Por ejemplo, si adivina {1,4,5,2} (aumentando en tres), entonces adivinaríamos 5.
Evita rollos sin sentido o muy cerca de rollos sin sentido.
fuente
getMove()
método sea estático. No puede implementar un método no estático como ese (al menos no en Java 8).Bot evolucionado
Desarrollé este bot para que sea el mejor bot aleatorio.
fuente
Popularidad, Python 3
Calcule las suposiciones basadas en números populares usados en el pasado por el oponente. Los números utilizados recientemente tienen más peso. La elección del número es a menudo la misma que la suposición.
fuente
Interpolador
(Cambió a Java ya que Python estaba causando problemas)
Utiliza la interpolación polinómica en las últimas 10 elecciones del oponente para calcular el siguiente número del oponente, luego hace lo mismo con sus propias elecciones y evita elegir ese número. Además, Interpolator tiene un ligero sesgo en contra de elegir 0 o 5, y su elección a veces se ve afectada por su suposición:
fuente
CounterBot
No contrarresta a nadie, sino que cuenta hasta 0-5 en un círculo (
0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4 ...
)fuente
Basilisco, Python
Según la leyenda, el basilisco es el rey de las serpientes. ( fuente ) Supuse que ese es un nombre apropiado para un bot que juega "The Noble Game Of Kings" y está escrito en python. = D Este bot infunde miedo en el corazón de los otros bots y causa la muerte con una sola mirada.
Esto se ejecuta en una estrategia bastante simple. No espero que gane, pero fue divertido escribirlo. Este es también mi primer desafío de KoTH, así que estoy emocionado de ver qué tan bien funciona.
Cómo elige su próximo movimiento.
El basilisco siempre hace el movimiento que su oponente ha adivinado la menor cantidad de veces. En caso de empate, elegirá el número más pequeño. (para minimizar el número de puntos del oponente).
Cómo elige su próxima suposición.
El basilisco elegirá la respuesta más probable a su suposición anterior. Por ejemplo, si la última vez, adivinó un 3, volverá a través de todas las veces anteriores que adivinó un 3, y luego devolverá el movimiento más común del oponente que viene después de una suposición de 3. En caso de empate , elegirá el número más grande (para maximizar el número de puntos que podría hacer).
En una nota técnica, ¿funcionará esto correctamente? ¿Es suficiente print (), o debería usar algo como sys.stdout.write () como lo han hecho los otros Pythonistas?
fuente
Ídem
Esto se convierte en el oponente, pero detrás por una conjetura / elección.
fuente
NullifierBot, Java
Siempre lanza 0 para minimizar las ganancias de cualquier oponente. Si el oponente alguna vez adivina mi número, solo gana lo que arrojó.
Siempre adivina 5 para maximizar mis ganancias. Como no puedo obtener ningún punto de mi lanzamiento, quiero obtener tantos puntos del oponente. Podría adivinar al azar, pero ¿dónde está la diversión en eso?
fuente
Erratica, Java
No es genial, pero originalmente fue diseñado para ser mayormente aleatorio, hasta que el valor de la compensación se me ocurrió. Se las arregla para perder constantemente vs. Counter Bot> _ <
fuente
Echo, Ruby
Juega la última jugada que hizo el oponente, según la teoría de que cualquiera puede hacer un bot que no puede predecir. Suposiciones basadas en el valor esperado utilizando una muestra de cien movimientos.
fuente
echo.rb:3:in
<principal> ': método indefinidosize' for nil:NilClass (NoMethodError)
. Parece ocurrir solo en la primera ronda, cuando no hay historial de movimientos.if (mychoices.size > 990 && myscore == '0') nextchoice = rand(1..5)
parte?REY PESCADOR
Este tipo consiste en malos algoritmos de adivinanzas que utilizan principalmente matrices ponderadas.
fuente
Uh uh Sé lo que estás pensando. "¿Va a elegir cinco o algo más?" Bueno, para decirte la verdad en toda esta emoción, no estoy seguro de mí mismo, pero siendo este un método .44, el método más poderoso del mundo y sobrecargaría tu stack de inmediato, debes hacerte una pregunta : "¿Me siento afortunado?"
¿Bien, punk?
fuente