Plantación

En un artículo de Scientific American, Ted Hill menciona un problema abierto (según parece inventado por Y.H. Chow y Herbert Robbins) que nos encantó para plantear un torneo.

El problema

Ud. debe arrojar una moneda, tantas veces como desee. Una vez que se "planta" (es decir, deja de arrojar la moneda), recibe como premio tanto dinero como la proporción de caras que haya logrado. Ejemplo: si la primer vez sale cara, le convendría plantarse y recibir un peso. Si sale ceca, en cambio, le conviene seguir tirando. Si la segunda vez sale cara, podría plantarse y recibir medio peso, o arriesgarse a lanzar una tercera vez y poder ganar dos tercios (si sale otra cara, claro). Y así sucesivamente. El problema es justamente encontrar una estrategia que maximice la ganancia esperada tras plantarse.

El juego: Plantación

Podemos transformar este problema en un juego muy fácilmente:

Se juega de a muchos. Cada jugador posee su propia moneda. Todos comienzan con 0 puntos.
En cada ronda, se aplican estos pasos:

1. Todos los jugadores lanzan su moneda y deciden si se plantan o no. Los que se plantan reciben C/L puntos, donde C es la cantidad de caras que lograron y L el número de veces que lanzaron la moneda (ambas cantidades tomadas en la presente ronda, claro).
2. Si la mayoría de los jugadores ya se plantó, se produce la plantación forzada: termina la ronda, y los que aún no se hayan plantado reciben 0 puntos.
3. Si aún no se plantó la mayoría, se vuelve al punto 1.

La mayoría mencionada es un parámetro del juego; para el torneo usaremos una mayoría del 95% aproximadamente (puede cambiar por razones técnicas).

El torneo

Los participantes deberán enviar un algoritmo que tome como entrada los siguientes datos:

• La cantidad total de jugadores.
• El número de turno de la ronda actual.
• Los puntajes logrados por los que ya se plantaron en la ronda actual.
• La cantidad de caras logradas por los que aún no se plantaron en la ronda actual.

En base a estos datos, el algoritmo deberá producir como salida la decisión de si se planta o no.

Las rondas serán independientes; los puntajes se acumularán para calcular el ganador del torneo, pero los algoritmos no tendrán información sobre rondas anteriores.

Recibiremos algoritmos y consultas hasta próximo aviso.

Uniq: resultados

Bueno, se han presentado sólo 4 participantes, pero ha sido interesante preparar el sistema y correr el torneo.

Hemos hecho 2 partidas (ida y vuelta) para cada par de algoritmos, y cada tamaño de pila entre 4 y 500. Como todos los algoritmos eran deterministas, no ha habido necesidad de hacer repeticiones.

Felicitaciones al ganador, Federico Hermo. He aquí la tabla de puntajes:


2030 34.03% hermo
1363 22.85% desequilibrio
1293 21.68% galicia
1278 21.42% gerbasio

El código del torneo está algo feo, pero creo que es entendible. Cualquier duda pueden consultar en los comentarios.

Prepárense para una nueva competencia prontito...

Uniq: deadline

Bueno, hemos llegado al plazo final del Uniq. En unos días tendré todo listo y publicaré los resultados. Suspenso...

Uniq: progreso

Les cuento que ya hay tres participantes en el torneo. No daré aún detalles sobre sus estrategias, por supuesto.

En otro orden de cosas, analizando un poco el juego calculé la cantidad de posiciones finales que tiene el juego en función de la cantidad de fichas inicial; obtuve una serie que ha sido analizada anteriormente pero al parecer, nunca desde el punto de vista de los juegos bipersonales. Quizá a alguien le sirva la información.

Nueva competencia: Uniq

Para la siguiente competencia, he elegido nuevamente reducir a 1D un juego 2D.
El Uniq es una versión unidimensional del Zuniq, que se puede jugar con pilas de fichas, al modo del Nim.
(No pude encontrar referencias ni análisis de este juego en la web. Agradeceré cualquier información que puedan tener.)

Reglas del juego

Uniq es un juego para dos jugadores; se juega por turnos. Inicialmente, se coloca cierta cantidad de fichas formando una pila en la mesa.
Por turno, cada jugador debe elegir una pila de más de una ficha (al comienzo sólo estará disponible la pila inicial, claro) y dividirla en dos pilas más pequeñas.
La única restricción es que tras cada jugada, todas las pilas deben tener una cantidad distinta de fichas. Aquel que en su turno no pueda jugar cumpliendo esta restricción (o que juegue sin cumplirla) es el perdedor.

Reglas para la competencia

Cada participante podrá presentar sólo una estrategia.
La estrategia deberá decidir, dado un conjunto de pilas, qué pila dividir en dos y qué tamaños tendrán las dos pilas resultantes.
Por simplicidad (y porque es más interesante) sólo aceptaré estrategias estáticas, es decir, que no impliquen la evaluación de jugadas virtuales o hipotéticas.

La cantidad de fichas inicial será variable; habrá partidas con más fichas y otras con menos.
Para cada cantidad de fichas inicial, cada estrategia jugará al menos 10 partidas con cada otra estrategia como primer jugador, y otras tantas como segundo jugador.
Cada partida ganada valdrá 1 punto. La estrategia que acumule más puntos en total será la ganadora.

Aceptaré estrategias hasta el día 30 de junio de 2011. Pueden enviarla a este e-mail.

Overcut 2: Resultados

Bueno, tras demasiado tiempo al fin pude ponerme y programar el torneo.

He aquí los resultados de una partida representativa, de 10000 turnos:

1. Josu con 8123.25 puntos
2. Danih con 4733.91 puntos
3. Nostradamus, con 3487.91 puntos
4. Berreta, con 3351.91 puntos
5. DonCorleone, con 2812 puntos
6. Cynthia, con 2498 puntos
7. Flamechampion con 0 puntos

El ganador es por tanto Josu. ¡Felicitaciones! Y Gracias a todos por la paciencia...

Seguimos como siempre

Hace un tiempo me había propuesto hacer un sitio dedicado a los concursos, con un sistema automatizado de recepción/compilación/ejecución de los algoritmos, pero la verdad es que no me dan los tiempos para diseñar y/o mantener un sistema así.

Seguiremos pues con el sistema más "casero".

Próximamente habrá nuevos torneos. Y por supuesto se aceptan sugerencias para juegos.

Plazo para el Overcut 2

Bueno, ya hay suficientes participantes como para dar un plazo final: habrá tiempo para presentar nuevas estrategias para Overcut 2 hasta el viernes 6 de noviembre (que incidentalmente es mi cumpleaños).

¡Espero sus mensajes!