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!