miércoles, julio 02, 2008

Oráculo desierto

El concurso de Oráculo ha quedado desierto, ya que no he recibido participaciones.

Hay dos posibles soluciones: empezar un nuevo concurso, con algún juego que se me ocurra o que me propongan, o extender el plazo para el Oráculo.

¿Qué les parece?

lunes, mayo 19, 2008

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

lunes, mayo 12, 2008

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!

viernes, marzo 28, 2008

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.

Monedero II: las vueltas de la vida

Sabíamos que la vida da sorpresas, pero esto es muy gracioso.

Dani Rodrigo nos ha señalado otro error en el código. Esto de por sí no es sorprendente (errar es humano); lo que es curioso es que corregir este error no afectó demasiado los resultados del Monedero I, pero sí los del Monedero II.

Y como en una especie de justicia poética, ¡esta segunda corrección ha restaurado a Dani Rodrigo como ganador del Monedero II!

De todas maneras reconozcamos que los puntajes obtenidos por los algoritmos punteros son sumamente parecidos. Como comenta Juan Zubieta, habría que efectuar quizá muchísimas más partidas para que los porcentajes fueran menos ambiguos. Pero atengámonos a las 100 partidas que especificamos en las reglas.

Aquí están el código fuente corregido y los puntajes finales (esperemos que no surjan más sorpresas):


Puntaje         Algoritmo               Autor

3855 (14.61%) Panzeta Dani Rodrigo
3716 (14.08%) Programación_Dinámica Javier Gómez
3541 (13.42%) PotenciaDos Juan Zubieta
3426 (12.98%) Jean_3 Jean Morales
3184 (12.06%) Jesanz_3 Jesús Sanz
3179 (12.05%) Pequeritmo_03 Markelo
2865 (10.86%) Arroyito Bernardino Romera
2626 (9.95%) Colorado_el_9_revisado Pablo Coll


Y como siempre, gracias a todos por participar y por estar tan atentos...

miércoles, marzo 26, 2008

Monedero I y II: resultados corregidos

Luego de corregir la implementación de la mecánica del juego, he aquí los resultados corregidos.

Felicitaciones a Markelo y a Javier Gómez, que resultaron ser los ganadores de cada versión. Y gracias a todos nuevamente por participar, y en particular a Javier por señalar el error que habíamos cometido.


Para el Monedero I (puntajes acumulados):

Puntaje         Algoritmo         Autor/a

11086 (8.48%) Pequeritmo_02 Markelo
10856 (8.31%) Pequeritmo_01 Markelo
10744 (8.22%) Colorado_el_9 Pablo Coll
10032 (7.68%) Arroyito Bernardino Romera
9993 (7.65%) Jesanz_2 Jesús Sanz
9928 (7.60%) Jean_1 Jean Morales
9559 (7.32%) Pozuelon Bernardino Romera
9444 (7.23%) Jean_2 Jean Morales
9228 (7.06%) Ten Cynthia Disenfeld
8904 (6.81%) Jesanz_1 Jesús Sanz
8746 (6.69%) Negro_el_10 Pablo Coll
7957 (6.09%) Eleven Cynthia Disenfeld
6968 (5.33%) A Alejandro Donnantuoni
5110 (3.91%) B Alejandro Donnantuoni
2111 (1.62%) Optimista Sistema



Para el Monedero II (puntajes tabicados):

Puntaje         Algoritmo                Autor/a

3721 (14.04%) Programación_Dinámica Javier Gómez
3508 (13.24%) PotenciaDos Juan Zubieta
3475 (13.12%) Panzeta Dani Rodrigo
3407 (12.86%) Pequeritmo_03 Markelo
3215 (12.13%) Jesanz_3 Jesús Sanz
3167 (11.95%) Jean_3 Jean Morales
3095 (11.68%) Arroyito Bernardino Romera
2908 (10.98%) Colorado_el_9_revisado Pablo Coll

Erratas

Javier Gómez señala, con razón, que la implementación del Monedero (en ambas versiones) adolece de un error conceptual: ambos jugadores arrojan la misma secuencia de caras y cruces.

Fue una decisión equivocada de nuestra parte, por querer hacer más "justo" el juego. Las reglas especifican claramente que en su turno, cada jugador lanza una moneda, de manera que hemos modificado el código y en breve publicaremos los resultados corregidos.

¡Gracias Javier por el aviso!

Midiendo la elegancia

Una de las cosas más estimulantes y sorprendentes de este proyecto es la comparación de la complejidad y eficiencia de los distintos algoritmos que se presentan. Algunos son simples y directos, pero logran un desempeño pobre. Otros son complicados o lentos, pero su complejidad se ve premiada por la victoria.

Pero cada tanto hay alguno de sencillez prístina que además gana limpiamente la competencia; y aunque eso puede indicar una pobreza de estructura del juego en cuestión, también indica estilo y elegancia.

Esto hace pensar que quizá sería interesante definir, para futuras competencias, categorías basadas en la complejidad intrínseca de los distintos algoritmos.

No es atractiva la idea de poner límites al tiempo de ejecución o uso de memoria, como hacen en otras competencias de este tipo; más bien sería deseable dividir los algoritmos según su uso de los recursos y luego, dentro de cada categoría, declarar un vencedor.

No queda claro cómo sería la mejor manera de hacerlo; si alguno se imagina un método elegante, que lo indique aquí y lo discutiremos.

Monedero II: Resultados

Como recordaremos, las reglas del Monedero II eran las del Monedero, pero con el sistema de puntajes "tabicado": las partidas ganadas valen 10 puntos, las empatadas 1 punto y las perdidas 0 puntos.

Se efectuaron 100 partidas entre cada par de algoritmos, y cada partida duró 1000 turnos.

Aquí están los resultados:


Puntaje         Algoritmo               Autor

4405 (18.21%) Panzeta Dani Rodrigo
4148 (17.15%) Programación_Dinámica Javier Gómez
3523 (14.56%) PotenciaDos Juan Zubieta
3266 (13.50%) Jesanz_3 Jesús Sanz
2744 (11.34%) Jean_3 Jean Morales
2311 (9.55%) Pequeritmo_03 Markelo
2087 (8.63%) Colorado_el_9_revisado Pablo Coll
1708 (7.06%) Arroyito Bernardino Romera


¡Felicitaciones a Dani Rodrigo! Y como siempre, gracias a todos por participar con su ingenio.

El código fuente completo de la competencia se puede ver aquí. Cualquier duda y/o corrección serán bienvenidas.

martes, marzo 11, 2008

Nueva competencia: Monedero II

Como anuncié en el post anterior, en esta competencia jugaremos otra versión del Monedero.

Las reglas serán las mismas que las originales, salvo que esta vez, los puntajes globales se irán acumulando de esta manera:
  • Diez puntos por cada partida ganada
  • Un punto por cada partida empatada
  • Cero puntos por cada partida perdida
Habrá tiempo de enviar algoritmos hasta el 25 de marzo.

Esta vez aceptaré solamente un algoritmo por jugador, por sencillez.

¡Espero sus participaciones!

Monedero: Resultados

Bien, el Monedero demostró ser un juego interesante: surgieron estrategias bastante diferentes, y una inquietud.

Los Resultados

Luego de 100 febriles partidas entre cada par de algoritmos enviados (aumenté la cantidad de partidas porque algunos son bastante parejos), aquí están finalmente los puntajes finales:

puntaje algoritmo autor/a

11192 (8.25%) Arroyito Bernardino Romera
11064 (8.16%) Pozuelon Bernardino Romera
10992 (8.11%) Pequeritmo_02 Markelo
10930 (8.06%) Pequeritmo_01 Markelo
10692 (7.88%) Colorado_el_9 Pablo Coll
10676 (7.87%) Jean_1 Jean Morales
10420 (7.68%) Jean_2 Jean Morales
9649 (7.11%) Jesanz_2 Jesús Sanz
9552 (7.04%) Ten Cynthia Disenfeld
8927 (6.58%) Negro_el_10 Pablo Coll
8588 (6.33%) Jesanz_1 Jesús Sanz
8419 (6.21%) Eleven Cynthia Disenfeld)
7000 (5.16%) A Alejandro Donnantuoni
5310 (3.92%) B Alejandro Donnantuoni
2208 (1.63%) Optimista Sistema

¡Felicitaciones a Bernardino Romera, el ganador!

Y como siempre, gracias a todos por participar.


La Inquietud

Señala Markelo, y con razón, que la estrategia del juego debería variar notablemente con otra modalidad de puntaje:
Si mi contrincante se planta en un determinado valor, solo necesito superarlo por uno para ganarle en caso de que valiese cada triunfo. Pero si lo que busco es puntos, entonces debería idear una forma de seguir sumando.
Por lo tanto, no publicaré el código de los algoritmos actuales, sino que armaré una nueva versión del torneo para ver cómo varían las estrategias cuando sólo se busca ganar las partidas.

En el próximo post especificaré la modalidad de puntaje usada.

lunes, febrero 25, 2008

Séptima competencia: el Monedero

El Monedero tiene una reminiscencia al juego del Uno, que fue el primer juego que jugamos aquí.
Aunque es bastante más simple, confío en que dé lugar a estrategias interesantes.


Reglas del juego

Se juega de a dos. La cantidad de turnos es limitada. Cada jugador comienza con 0 puntos.

En su turno, cada jugador lanza una moneda. Si sale cara, su puntaje aumenta en 1. Si sale cruz, su puntaje queda dividido por dos (y se redondea hacia abajo).
En lugar de lanzar la moneda, el jugador puede decidir plantarse con el puntaje que tenga; deberá esperar hasta que termine la partida o su oponente también decida plantarse.

El jugador con más puntaje al final de la partida es el ganador.


Reglas de la competencia


En esta competencia, los algoritmos jugarán 10 partidas contra cada uno de sus oponentes, a 1000 turnos cada una.
Los puntajes de cada partida se irán acumulando en un puntaje del torneo; el que sume más puntos en total, será el ganador.

Cada participante podrá presentar hasta 2 algoritmos.

Cada algoritmo usará los siguientes datos referidos a la partida en curso:
  • un entero, con el puntaje propio
  • un entero, con el puntaje del oponente
  • un entero, con la cantidad de turnos que quedan por jugar
  • un booleano, verdadero si su oponente ya se plantó, o falso si aún no se plantó
Y deberá devolver un valor booleano, verdadero si decide plantarse, o falso si decide no plantarse.

Los algoritmos no podrán tener «memoria» de las partidas anteriores ni acceso a los puntajes globales.

Habrá tiempo para enviar algoritmos hasta el 10 de marzo de 2008. Pueden enviarlos a mi dirección.

Mientras más algoritmos haya, será más divertido, así que ¡háganle propaganda al juego!

domingo, febrero 17, 2008

Resultados del torneo de Doble y Nada

¡Tenemos ganador! Aquí está la tabla final de posiciones:

96.8% PE (Pablo Coll)
1.5% J (Jorge Alvaro)
1.5% DoublesMedia (Cynthia Disenfeld)
0.0% Doblerone (Bernard Romera)
0.0% Trentenna (Jean Morales)
0.0% Pequeritmo01 (Markelo)
0.0% Pequeritmo02 (Markelo)
0.0% Pite (Alejandro Donnantuoni)
Cada link lleva al código fuente del algoritmo respectivo.

Aquí pueden ver el código fuente del sistema y de algunas funciones auxiliares.
La partida completa puede verse aquí.

¡Felicitaciones Pablo Coll, y a todos muchas gracias por participar! Ya andamos buscando un juego adecuado para la próxima competencia. No duden en enviar sus ideas.

martes, febrero 12, 2008

Doble y Nada: plazo revisado

No sé qué miré cuando puse la fecha límite para este concurso. No existe tal día.

La fecha final para el Doble y Nada será el sábado 16 de febrero de 2008, que sí existe.

¡Suerte a todos los participantes!

lunes, febrero 11, 2008

Doble y Nada: progreso

Ya tenemos aproximadamente cinco algoritmos en la competencia. Estoy terminando de programar el juez y algunos detalles de los algoritmos. Pronto haré las primeras competencias de prueba...

miércoles, enero 02, 2008

Sexta competencia: Doble y Nada

Bueno, ha pasado algún tiempo y la encuesta no ha dado resultados definidos; así que me tomo la libertad de elegir un juego nuevo para la sexta competencia, mientras pondero los demás juegos y propuestas pendientes.
El juego lo adapté de una discusión en el foro de Little Golem; es de naturaleza numérica.


Reglas del juego


En Doble y Nada juegan todos los participantes simultáneamente. En cada ronda, cada jugador elige un número entero positivo a gusto; el que elige el mayor gana un punto. Pero atención: si dicho número es mayor o igual que el doble del segundo mayor, se lo anula y se vuelve a evaluar el ganador.
Dicho de otro modo: gana el que elige el número más grande que sea menor que el doble del número inmediatamente menor elegido por otro jugador.

En caso de que varios jugadores elijan un mismo número ganador, todos ellos ganan el punto.

Un ejemplo:
  • Los jugadores eligen los números 8, 10, 20 y 1000.
  • Como 1000 es mayor o igual que 20 * 2, se anula el 1000.
  • Como 20 es mayor o igual que 10 * 2, se anula el 20.
  • Queda como ganador el 10, que es menor que 8 * 2.

Cómo participar

Podrán enviarme sus algoritmos en formato verbal, o en forma de código fuente, antes del sábado 12 de febrero de 2008.

El protocolo que deberán cumplir los programas presentados en forma de código es el siguiente:
  1. Escribir la jugada, en formato de número decimal, hacia la salida estándar (incluyendo un carácter de fin de línea).
  2. Leer una línea completa desde la entrada estándar. Si dicha línea es la palabra "fin", terminar normalmente. En caso contrario, dicha línea será el conjunto de números elegidos por todos los jugadores, en formato decimal, separados por un espacio.
    Ejemplo:
    43 8866 300 1 23894 1 44
    El orden de las jugadas siempre será el mismo; vale decir que el primer número de la lista siempre será el correspondiente al jugador A, el segundo al B, etc.
  3. Volver al paso 1.