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.