miércoles, noviembre 21, 2007

Encuesta: ¿A qué jugamos ahora?

Decidí abrir una encuesta para ver qué juego usaremos en la próxima competencia. Estas son las opciones:
  1. versión dinámica del Intervalo
  2. versión dinámica del FootSteps
  3. otros juegos que propongan (que sean originales en lo posible)
Espero sus votos y/o sugerencias en los comentarios. Me reservo el derecho de desempate y/o elección compulsiva de algún juego nuevo que me seduzca.

¡A votar!

martes, noviembre 20, 2007

Resultados del FootSteps

Ya tenemos un ganador. Se trata de Pablo Diaz Rebaque, desde Madrid, con su algoritmo ijugador, escrito en C++. ¡Felicitaciones, Pablo!

Pueden ver la tabla de puntajes, una partida de muestra entre cada par de algoritmos, y el código fuente completo.

Hice el torneo a 20 rondas (a pesar de que había dicho que iba a ser una sola) porque la modalidad “procesos separados” no fue tan lenta como yo pensaba.

Gracias a todos los participantes, por las ideas y por la paciencia en el proceso de implementación, con mis idas y venidas.

Los que hayan presentado solamente código fuente están invitados a explicar en detalle sus estrategias (aunque no es obligatorio).

Me encantó la variedad de acercamientos que hubo, a pesar de ser un juego tan simple. Estoy seguro de que en la versión dinámica habrá mucha más tela para cortar.

lunes, noviembre 19, 2007

Progresos

Ayer terminó la inscripción para el FootSteps. Aún tardaré un día o dos más en terminar de probar cómo interacciona el juez con los programas presentados, e implementar algunos algoritmos que me enviaron en lenguaje coloquial.

Mientras tanto, podemos ir pensando en la siguiente competencia. Por mi parte, pensaba que quizá amerite una reedición del Intervalo, pero esta vez con algoritmos dinámicos (que puedan ver la historia de la partida en lugar de sólo el tablero).

¿Qué les parece?

sábado, noviembre 17, 2007

Ya casi...

Mañana vence el plazo para el FootSteps. ¡Qué suspenso!

Aviso que tardaré unos días en presentar los resultados.

jueves, octubre 18, 2007

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.

Quinta competencia: FootSteps

Varios amigos me han recomendado este juego, y realmente me encantó. Es excelente para jugar en persona; además, promete ser muy fecundo para diseñar jugadores artificiales.
Lo pueden probar en este sitio, contra otros jugadores humanos o contra algunos «bots» que tienen hechos.

Reglas del juego

Se coloca una ficha en la casilla central de una tira de siete casillas:

El objetivo de uno de los jugadores es llevar la ficha a la casilla en el extremo izquierdo, y el del otro es llevarla a la casilla en el extremo derecho.
Al comienzo de la partida, cada jugador dispone de cincuenta puntos.
En cada turno, se hace una pequeña licitación: cada jugador oferta en secreto una cantidad de puntos; luego, se revelan las ofertas, y el que ofertó más tiene derecho a mover la ficha una casilla hacia su objetivo. Si ambos ofertan la misma cantidad, ninguno de ellos mueve la ficha.
En cualquier caso, cada jugador pierde la cantidad de puntos que ofertó.
Las ofertas deben ser de al menos un punto, mientras se tengan puntos. Si un jugador se queda sin puntos antes que el otro, debe seguir jugando, ofertando cero puntos en cada turno.
Cuando un jugador logra su objetivo, es declarado ganador. Si ambos jugadores se quedan sin puntos antes de que esto suceda, se declara empate (sin importar dónde haya quedado la ficha).

Reglas para la competencia

La competencia entre algoritmos se llevará a cabo de esta manera:
  1. Cada algoritmo competirá una vez contra cada uno de sus oponentes. El que gane más partidos será el vencedor.
  2. En caso de empate, se vuelve al punto 1. Los contadores de partidos ganados serán acumulativos.
Los algoritmos solamente podrán referirse al estado de la partida actual. Esto es: posición de la ficha, cantidad de puntos restantes de cada jugador e historial de las ofertas de cada jugador.
No tendrán memoria de lo que ocurrió en partidas pasadas. Dependiendo de los resultados de la competencia y de la complejidad que alcancen los algoritmos (y de pedidos o sugerencias de los participantes) podremos organizar en el futuro una competencia con algoritmos más flexibles, que puedan aprender de las partidas que jueguen.

Cómo y cuándo presentar los algoritmos

Habrá tiempo de presentar algoritmos (sólo uno por persona) hasta el 18 de noviembre de 2007 al mediodía (hora de Argentina).

Como en las competencias anteriores, no es necesario presentar algoritmos en forma de código fuente. Una buena descripción de la idea será suficiente (en la mayoría de los casos) para que yo escriba lo necesario.
No obstante, los jugadores que así lo deseen podrán facilitarme la tarea presentando código fuente, en un solo archivo compilable o interpretable.
Podrán escribir sus programas en Unicon, C, C++, D, Java, Ruby o Python. Si desean usar algún otro lenguaje, consúltenme antes por favor.

Los programas deberán respetar el siguiente protocolo de entrada/salida:
  1. Imprimir la oferta en la salida estándar, en forma de número decimal. La salida deberá ser una línea de texto completa (con el carácter de fin de línea incluido).
  2. Leer de la entrada estándar una línea de texto completa.
  3. Si la línea dice «fin» significa que la partida terminó (ya sea normalmente o por una jugada inválida de alguno de los jugadores). El programa deberá terminar su ejecución.
    De lo contrario, la línea leída será un número decimal igual a la oferta que hizo el oponente.
  4. Volver al paso 1.
Si un programa hace una oferta ilegal (menor que uno o mayor que la cantidad de puntos que tenga, o distinta de cero si ya no tiene puntos) perderá la partida. Por supuesto, yo probaré cada programa que me envíen antes de la competencia, y daré tiempo a los jugadores a que modifiquen su código si se presenta algún problema.

Ante cualquier duda, no duden en consultar.

Espero sus algoritmos. ¡Suerte y no olviden reclutar a sus amigos y conocidos!

viernes, octubre 12, 2007

Resultados del Intervalo

Tenemos un indiscutible algoritmo ganador: «Fixed». ¡Felicitaciones a su creadora, Cythia Disenfeld!


Detalles

Se jugaron 300 partidas entre cada par de algoritmos.
A modo de control, agregué al plantel dos algoritmos que juegan puramente al azar (aunque con distribuciones diferentes).


Tabla de posiciones

AlgoritmoAutorpartidas
ganadas
%
FixedCythia Disenfeld289610.257%
JJorge Alvaro24038.5116%
Politicamente CorrectoJuan23848.4443%
AntiLogaritmicoCarlos Luna Mota23438.2990%
EquilibradoNicolás Tarazona21447.5942%
IntervazarPablo Suárez21137.4844%
EspiralCarlos Luna Mota20897.3994%
MedianaMarisa Morales20057.1018%
DobleWinLeandro Tar18056.3934%
Azar1BeeR14825.2493%
Pequeritmo07Markelo14615.1749%
BalanzaArmando Vicente13984.9518%
Azar0BeeR11273.9919%
LogaritmicoCarlos Luna Mota9893.5031%
MidaderoJean Morales8543.0249%
ZigzagMarcos7392.6175%


Una tabla más detallada puede verse aquí.
Agregué extra-oficialmente una variante reality-show (gracias Iván por la idea). Es muy interesante ver cómo van variando las posiciones a medida que se van eliminando algoritmos de la lista.

Para tener una impresión visual del torneo, pueden ver una partida de muestra entre cada par de algoritmos.
¿No son lindos los dibujitos que forman? Se podría idear una forma de arte basada en juegos de tablero...


Código fuente

Todo el sistema y los algoritmos están escritos en Unicon.
Aquí pueden curiosear el código de los jugadores y el código principal.


Comentarios

Me gustó mucho la variedad de ideas que hubo: aunque muchos usaron el concepto «ocupar el centro primero», es notable las muy diversas maneras que hay de implementar la idea.
Entre los algoritmos que no usaban el centro en seguida, está nada menos que el ganador. Quizá se anticipó al pensamiento de los demás...


Conclusiones

Me dan ganas de reeditar este mismo juego, pero en una versión dinámica (es decir, con memoria de las jugadas anteriores), y quizá en dos dimensiones (el juego Frames original). Pero primero jugaremos otros juegos que están esperando. Mañana mismo comentaré el juego y las reglas para la próxima competencia.

¡Muchas gracias a todos por participar!

¡No dejen de enviar comentarios e ideas para nuevas competencias!

jueves, octubre 11, 2007

Intervalo: plazo final

Ya hay bastantes participantes, así que pongo el plazo definitivo: la recepción de algoritmos para el Intervalo cierra el miércoles 17 a medianoche (hora de Argentina).

Suerte a todos, y mantengan la sintonía.

viernes, octubre 05, 2007

Va creciendo el plantel

No sé si fue por mi lloriqueo del post anterior, pero estos días me han llegado algunos algoritmos más para el Intervalo.

Presten atención que se viene la gran batalla... ¡Y sigan mandando material!

miércoles, septiembre 26, 2007

Falta poco y somos pocos

Hola, les cuento que aún son pocos los algoritmos que me han llegado para el Intervalo, así que cambiaré el plazo de recepción.

Haré esto: cuando tenga siete algoritmos en total, lo anunciaré aquí y esperaré una semana más para los rezagados. ¿Por qué siete? Quizá sea un arrebato místico.

Así que ¡a reclutar gente! No dudo que los que ya me han mandado material conocerán posibles participantes.

sábado, septiembre 15, 2007

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.

Progresos del Intervalo

Un breve reporte del progreso del torneo de Intervalo.

Ya me han enviado dos algoritmos jugadores, y tengo uno propio que seguramente es bastante defectuoso, pero no lo tocaré más dado que sería injusto modificarlo a la luz de los que me han presentado.

Algunos participantes me han consultado sobre detalles de interpretación; parece que no quedaron muy claras las reglas del juego. Mañana publicaré todas las aclaraciones necesarias, junto con un ejemplo de partida.

Les recuerdo que hay tiempo de presentar algoritmos hasta el 9 de octubre.

¡No se queden afuera!

martes, septiembre 11, 2007

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.

domingo, septiembre 09, 2007

Cuarta competencia: Intervalo


Intervalo es un juego bipersonal de movimientos simultáneos (es la versión unidimensional del Frames, juego que diseñé hace unos años).

Reglas del juego

Intervalo se juega en un tablero con forma de tira de 64 casillas, numeradas del 1 al 64. Al comienzo todas las casillas están vacías.
Cada jugador usa fichas de un color que lo represente. Se usan también algunas fichas de color neutral.
En cada turno, ambos jugadores eligen simultáneamente una de las casillas libres de la tira. (Si los que juegan son personas, pueden escibir en secreto el número de la casilla en un papel y luego mostrarlos al mismo tiempo).
Pueden darse dos casos:
  • Que elijan la misma casilla. En este caso, se coloca en la casilla una ficha neutral y termina el turno.
  • Que elijan casillas distintas. En este caso, se coloca en cada casilla una ficha del color correspondiente al jugador que la eligió, y se cuentan las fichas de cada jugador que estén entre las dos casillas recién elegidas. El que tenga más fichas propias entre ambas casillas obtiene un punto.
La partida termina cuando ya no hay casillas libres. El que tenga más puntos es el ganador.

Reglas para el torneo

En esta versión de la competencia, los algoritmos deberán ser estáticos. Es decir, deberán calcular su jugada teniendo en cuenta exclusivamente el contenido de la tira de casillas. No tendrán «memoria» del orden de las movidas de la partida.
Dependiendo de las ideas, sugerencias y vicisitudes que surjan en este torneo, decidiremos si hacemos la versión dinámica.

Cada algoritmo se enfrentará N veces con cada uno de sus oponentes. N dependerá de cuestiones técnicas, pero supongo que será al menos 100.

El ránking final se armará usando la cantidad total de partidas ganadas. Las partidas empatadas no se tendrán en cuenta.

El plazo de entrega de algoritmos será de un mes a partir de la fecha de este post.

¡Espero sus algoritmos!

lunes, septiembre 03, 2007

Juego se busca

Hola a todos, aquí estoy intentando revivir este proyecto. Además de terminar de programar lo que falta del minoría, que ya es poquito, ando con ganas de seleccionar un juego nuevo para la próxima competencia, porque el juego Demofobia no resultó ser tan interesante como esperaba.

Así que si alguno conoce un juego simple pero no trivial, ingenioso y no azaroso, que lo comente aquí así vamos preparando el próximo torneo.

domingo, abril 15, 2007

Resultados parciales del torneo de Minoría

He dejado pasar demasiado tiempo sin poder terminar de programar el torneo de Minoría, así que he decidido publicar los resultados parciales con los algoritmos que he podido programar hasta ahora.

Mis disculpas a los que han quedado fuera. Eventualmente iré programando los algoritmos que queden y actualizando la tabla de puntajes. Si algún participante se ofrece para terminar los demás algoritmos, será más que bienvenido. Este torneo lo he programado en Python.

La partida fue a 500000 turnos. La tabla de posiciones quedó como sigue:

104922 100.0 J (Jorge Alvaro)
104838 99.9 Nash (Luis Silvestre)
104322 99.4 Salva (Salvador Cases)
95621 91.1 El Contra (German Zorba)
93663 89.3 Psicologico (Ivan Skvarca)
48442 46.2 Segundo Plato (Guido Bernardo)
24194 23.1 A por el Crater (Carlos Luna Mota)
24194 23.1 Julian (Julian Antonacci)

lunes, marzo 05, 2007

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

viernes, enero 05, 2007

Resurrección

Hola a todos. Ahora que he usado algunos días de mis vacaciones para dormir, estoy mejor capacitado para terminar por fin de escribir lo que falta del código para el torneo de Minoría.

En unas horas, algunos de los participantes recibirán un mensaje pidiendo algunos detalles de sus algoritmos.

Desde ya pido disculpas por mi cuelgue involuntario; mi vida laboral se había extendido un tanto últimamente. No es una excusa, sino una aclaración para tranquilizar a algunas gentes que temían por mi integridad física.