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:
- 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).
- 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.
- 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.
Entradas
7 comentarios:
En la explicación del juego, punto 1, dice C/L, y creo que debería ser C/N... Saludos.
Corregido, ¡gracias!
Me parece un juego muy interesante!
Voy a ver si preparo un algoritmo para participar. No tengo del todo claro si es correcto lo siguiente:
- Entiendo que el paso 1 cuando se repite incluye a todos los jugadores que no se plantaron.
- A través de los puntos logrados por los ya plantados también conozco cuantos jugadores se han plantado.
"- Entiendo que el paso 1 cuando se repite incluye a todos los jugadores que no se plantaron."
Es correcto; los que ya se plantaron no vuelven a lanzar la moneda.
"- A través de los puntos logrados por los ya plantados también conozco cuantos jugadores se han plantado."
Claro, se conoce la lista de todos los puntos mencionados, y por lo tanto su longitud.
Espero que puedas participar (aún no se anotó nadie :(
como viene la participación?
Tengo en "mis pendientes" hacer algo, quizas mañana a la noche me ponga
Por ahora hay casi nada... Pero dejaré abierto el plazo así participa más gente.
Yo ya tengo casi terminado mi algoritmo, de hecho creo que no lo voy a cambiar, así que en muy poco lo envío.
Publicar un comentario