Ignotum: código para probar estrategias

Hay otros sitios de competencias entre algoritmos que publican el código del «referí» para que los participantes puedan probar sus ideas antes de la competencia final; me pareció buena idea y la usaré en esta y también en futuras competencias.

En este archivo (update: corregí un sutil bug en el código, bajen el nuevo archivo) está el código básico del torneo. Los que sepan programar en Python podrán aprovecharlo para probar sus estrategias y elegir la mejor para enviar, y los que no quizá puedan usarlo igualmente para mirar la lógica y despejar dudas y, quién sabe, animarse y aprender a programar en Python :)


Aclaraciones:
El script necesita la versión 3 del lenguaje. Pueden usar el script especificando la cantidad de rondas a correr, así como los valores de N y K, en la línea de comandos.

Ante cualquier duda pueden comentar aquí o enviarme un mensaje.

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.

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!

Plazo para el Overcut

Ya me han llegado 5 algoritmos para el Overcut, así que pongo el plazo prometido.

Podrán anotarse hasta el 24 de agosto, y cada participante podrá presentar hasta 3 estrategias distintas, que no estén diseñadas en forma "mafiosa", es decir, que no dependan una de la otra para jugar bien.

¡Suerte a todos!

Update: me late que tendré bastantes participantes como para armar un torneo "reality show": comienzan todos los algoritmos, y cada 1000 rondas se elimina al peor de todos y se resetean los puntajes globales. ¿Qué les parece?

Inactividad

Sé que ha habido poca actividad últimamente en BeeR; pero no se preocupen: sigo interesado en armar nuevas competencias. Lo único que pasa es que tengo poco tiempo, y serán más cadenciosas.

Como siempre, son bienvenidas ideas nuevas así como algoritmos para las dos competencias que siguen activas (hay participantes para ambas, pero demasiado pocos como para ser ejecutadas).

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?

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...

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.

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!

Pequeña corrección

Como bien señaló uno de los participantes del Intervalo, había un error en la tabla detallada, en la parte donde se indican los resultados entre cada par de algoritmos.

Ya pueden ver la versión corregida.

Aclaración: Podrán notar que las cifras de la tabla oficial no son iguales a las que puse antes aquí; esto es porque al correr de nuevo el programa los algoritmos que contenían azar se comportaron distinto. De todas formas, el orden de los resultados oficiales no ha cambiado, cosa que me sorprendió bastante.

Partida de ejemplo de Intervalo

Para aclarar algunas dudas que han surgido, pongo aquí una partida de Intervalo de ejemplo, con una tira de sólo 20 casillas, por brevedad.

Aclaro que la partida es totalmente ficticia, es decir, no usé ningún algoritmo de los que me han presentado hasta ahora para generar las movidas.

Simbología:

x    =    casilla con una ficha del jugador x
w    =    casilla con una ficha del jugador w
.    =    casilla vacía
*    =    casilla con una ficha neutral
()   =    marcan el intervalo formado por las fichas puestas en un turno

Partida:

 . . . . . . . . . . . . . . . . . . . .        (comienzo de la partida)
 . . . . .(*). . . . . . . . . . . . . .        (nadie gana el turno)
 . . . . . * . .(x w). . . . . . . . . .        (nadie gana el turno)
 . . . . . * . . x w(w . . . . . . . x).        (nadie gana el turno)
 . . . .(x * . . x w w . . . w). . . x .        (el jugador w gana el turno)
 . . . . x * . . x w w . . . w . . . x(*)       (nadie gana el turno)
 . .(w . x * . . x w w . . x)w . . . x *        (nadie gana el turno)
 . . w . x *(w . x w w . . x w x). . x *        (el jugador w gana el turno)
 . . w . x * w(*)x w w . . x w x . . x *        (nadie gana el turno)
 .(x w . x * w * x w w w). x w x . . x *        (el jugador w gana el turno)
 . x w . x * w * x w w w . x w x .(*)x *        (nadie gana el turno)
(x x w . x * w * x w w w w)x w x . * x *        (el jugador w gana el turno)
 x x w(x x * w * x w w w w x w x w)* x *        (el jugador w gana el turno)

El jugador w ganó 5 turnos y el jugador x no ganó turno alguno; por lo tanto el jugador w es el ganador de la partida.

Recordemos que, a los fines de este torneo, las partidas ganadas valen 1 punto, y las perdidas o empatadas valen 0 puntos.
El algoritmo que gane más partidas será, pues, el ganador del torneo.
Todos los algoritmos se enfrentarán la misma cantidad de veces con todos sus oponentes.

Intervalo: detalles para programadores

Para la competencia de Intervalo, los jugadores que quieran escribir su propio código podrán hacerlo.
Obviamente, los que no sepan o no quieran programar pueden enviarme simplemente la idea del algoritmo, y yo la implementaré.

Las reglas para presentar código serán las siguientes:

Se aceptará sólo código fuente, con instrucciones precisas sobre cómo compilarlo/interpretarlo.

El lenguaje que usen deberá disponer de un compilador o intérprete gratuito que corra bajo Linux de 64 bits (mi sistema es un Ubuntu 7.04, versión para amd64).

El programa será llamado con un argumento de 64 caracteres, con el siguiente formato:

. = casilla vacía
n = casilla ocupada por una ficha neutral
p = casilla ocupada por una ficha propia
a = casilla ocupada por una ficha ajena

Ejemplo de la línea de comandos usada:

prog ...na..p...a..p..a.np....a...npn...a.nn.p....p.......a..........

Los caracteres del argumento serán el contenido de la casilla 1 a la 64, respectivamente.

El programa calculará su movida, la imprimirá en la salida estándar como número decimal entre 1 y 64 inclusive, y terminará. La salida deberá ser terminada con un carácter de fin de línea.

Ejemplo en C/C++:
printf("%d\n", casilla_elegida);

Ejemplo en Python:
print casilla_elegida

Los programas que devuelvan el número de una casilla ocupada, o un número fuera del rango, serán descalificados. Por supuesto, antes de hacer la competencia definitiva haré algunas pruebas y avisaré a los autores sobre posibles problemas.

Señales de vida

Este post es sólo para aclarar que estoy vivo, aunque sigo sin poder dedicar todo el tiempo que quisiera a programar.
Eventualmente lograré hacerlo; hasta entonces gracias por la paciencia...

Más demoras

Me he demorado más de lo habitual con el Minoría. Quizá no esté de más una pequeña explicación/excusa.

Sucede que había empezado a programar todo en javascript (para que todos pudieran probar el código sin tener que usar nada más que un navegador), pero me encontré con sutiles (y no tan sutiles) dificultades en ese lenguaje y en mi conocimiento de ese lenguaje.

Por lo tanto comencé a reprogramar todo en Unicon, donde me manejo mejor.

Pido una vez más disculpas por la demora. Pero para que no sientan ansiedad alguna, decidí inaugurar la cuarta competencia mientras termino la tercera. En el próximo post pondré las reglas del Demofobia, el nuevo juego.

Plazo

El plazo para la entrega de algoritmos para la competencia de Minoría vence el viernes 3 de noviembre.
Hasta el momento tengo cinco algoritmos. ¡Espero el resto prontamente!

Aclaraciones sobre las reglas del Minoría

Algunos participantes me han preguntado esto, y me di cuenta de que no estaba del todo claro en las reglas que publiqué.
Donde dice "en caso de empate" me refiero a empate entre cantidades de votos de dos opciones.

Ejemplos:
Si A tiene 10 votos, B 5 y C 5, nadie gana nada porque hay dos opciones que tienen la menor cantidad de votos.
Si todos votan por B, tampoco nadie gana nada, porque aunque es la única opción votada, no es minoritaria.
Si A tiene 7 votos, B 2 y C 3, los dos que votaron B suman un punto.

Espero que quede clara ahora la mecánica del juego. No duden en consultar por cualquier duda.

Minoría: detalles

Olvidé agregar una cosa respecto a la competencia de Minoría: habrá dos partidas; una entre algoritmos cualesquiera, y otra entre algoritmos determinísticos solamente.

Si envían algoritmos determinísticos, especifiquen por favor si quieren participar en ambas competencias o sólo en la determinística.

Y no olviden ponerle nombre a sus creaciones; es más divertido así.