Demonios: resultados (parciales)

Bueno, aún me falta implementar el código de uno de los participantes, pero dado que son pocos bien puedo revelar los resultados parciales.

Ya veremos cómo queda la tabla cuando termine todo, pero creo que queda claro que (hasta ahora) el equipo formado por David Gonzalez Marquez, Andrés Viso y Pablo Terlisky es el ganador indiscutido. ¡Felicitaciones!

Cada par de algoritmos jugó 100 partidas; las combinaciones de N y K que no han resultado en empate global son las siguientes:

N = 25;  K = 2

197  Muerto               (David Gonzalez Marquez, Andrés Viso, Pablo Terlisky)
0    Psicologia Inversa   (Roberto Galache)
0    Libertades           (Cynthia Disenfeld)


N = 25;  K = 5

200  Muerto
24   Libertades
17   Psicologia Inversa


N = 50;  K = 2

198  Muerto
14   Psicologia Inversa
0    Libertades


N = 50;  K = 5

192  Muerto
43   Libertades
25   Psicologia Inversa


N = 50;  K = 10

191  Muerto
33   Psicologia Inversa
26   Libertades


N = 100;  K = 2

200  Muerto
14   Psicologia Inversa
0    Libertades


N = 100;  K = 5

200  Muerto
39   Libertades
23   Psicologia Inversa


N = 100;  K = 10

200  Muerto
44   Psicologia Inversa
30   Libertades


N = 100;  K = 20

197  Muerto
32   Psicologia Inversa
30   Libertades


N = 200;  K = 2

200  Muerto
8    Psicologia Inversa
0    Libertades


N = 200;  K = 5

200  Muerto
57   Libertades
20   Psicologia Inversa


N = 200;  K = 10

200  Muerto
44   Libertades
33   Psicologia Inversa


N = 200;  K = 20

200  Muerto
44   Libertades
34   Psicologia Inversa

Demonios: progreso

Bien, me han llegado varias ideas para Demonios. Aún estoy preparando juez, así que tardaré unos días más en publicar los resultados.

¡Gracias a todos los que enviaron sus algoritmos, y paciencia!

Novena competencia: Demonios

(Update: consideré preferible usar el modo entrada/salida para la interacción entre los programas, al menos en este juego. Leer más abajo los detalles al respecto)

Luego de considerar varias opciones, hemos elegido al fin un juego para la novena competencia (que en realidad serán varias; ya quedará claro más abajo).

El juego elegido, Demonios, es una versión unidimensional, imparcial y simultánea del juego que da origen al Problema del Ángel de John H. Conway.


Reglas del juego

• El tablero es una tira de N casillas de largo.
• Cada jugador tiene un demonio; ambos comienzan en extremos opuestos de la tira.
• Las casillas que hayan sido ocupadas en algún momento de la partida por algún demonio se denominarán quemadas. Las demás casillas se denominarán limpias.
  
• Los movimientos son simultáneos.
• En cada turno, ambos jugadores deberán mover su demonio a una casilla limpia que esté a lo sumo a K casillas de distancia (por ejemplo, si K = 1, podrá moverlo sólo a las casillas contiguas).
• Ambos demonios pueden ocupar una misma casilla.
• Si un jugador no tiene movidas válidas, pierde la partida y su oponente es declarado ganador. Si esto le ocurre a ambos jugadores simultáneamente, se declara empate.

Reglas de la competencia

• Como habrán notado, no hemos especificado los valores de N y de K. Esto es porque habrá varias categorías, con distintos valores (fijos dentro de cada categoría), y en cada una habrá un ganador.
• Cada par de algoritmos jugará de 20 a 2000 partidas en cada categoría (dependiendo del tiempo y/o paciencia disponibles).
• Cada partida ganada valdrá 10 puntos, y cada partida empatada valdrá 1 punto.
• Los algoritmos deberán decidir a qué casilla mueven su demonio, dados los valores de N y K, y las movidas anteriores de ambos jugadores. Podrán almacenar información entre turnos consecutivos de una misma partida, pero no entre distintas partidas.
  
• Cada jugador podrá enviar un solo algoritmo. Habrá tiempo hasta el sábado 10 de mayo inclusive.

Aclaraciones para los que envíen código

Las acciones de cada programa durante la partida serán las siguientes:

1. Leer una línea completa, que contendrá dos números naturales en base decimal, separados por un espacio. Dichos números serán los valores de N y K para la partida, en ese orden. Las casillas estarán numeradas de 1 a N, siendo 1 la posición inicial del demonio propio y N la posición del demonio oponente.
   
2. Escribir una línea completa que contenga un número en base decimal, indicando la casilla a la que se desea mover el demonio propio.
   
3. Leer una línea completa desde la entrada estándar, que contendrá un número en base decimal, indicando la casilla a la que se movió el demonio oponente.
   
4. Volver al paso 2.

Los jugadores podrán dar por sentado que las movidas del oponente enviadas por el juez a su programa son válidas.
Si uno de los programas envía una movida inválida al juez, será descalificado. Por supuesto, antes de correr la competencia real se hará una serie de pruebas para corregir cualquier error en los programas jugadores o el programa juez.