jueves, octubre 18, 2007

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!

5 comentarios:

Héctor dijo...

Acabo de descubrir este blog a través del podcast de soliloquios... Un gran proyecto :) me ha encantado desde el principio.

Bueno, como diría el señor Lobo "dejemos de..." y vamos a lo que vamos ;)
El problema que estoy encontrando con footsteps para pensar un algoritmo con posibilidades de ganar, es que, dado que no se juegan varias partidas contra el mismo algoritmo (o por lo menos no se puede recordar) y que el juego consiste en "adivinar" el juego del oponente, el hecho de que las partidas sean tan cortas impide recolectar una mínima información como para que el juego sea algo menos que una partida aleatoria que depende mucho más del metajuego que del juego en sí, y como el metajuego no lo conocemos (porque no posteamos las ideas de algoritmos que tenemos), más que un algoritmo, la competencia se convierte en intentar adivinar cuál va a ser la estrategia predominante en el torneo para hacer un algoritmo en su contra.

Posiblemente lo más interesante sería que se jugaran un número alto de partidas entre los dos algoritmos y que pudieran recordar (lo cual complicaría sobremanera su funcionamiento, lo se :S), aunque una modificación más sencilla y que podría ayudar a resolver el problema sería, hacer el tablero mucho más grande (unas 1000 casillas) y dar muchos más puntos a los jugadores (por ejemplo un millón), de manera que la partida se alargue lo suficiente como para que se puedan recolectar datos relevantes.

Un saludo, y aun así seguiré pensando alguna manera de abordar el problema tal y como está ahora mismo :)

Muchas gracias por un blog tan interesante

Marcos dijo...

Gracias H�ctor por tus comentarios.
Es muy sensato lo que dec�s; de hecho, pienso hacer otra edici�n del FootSteps permitiendo algoritmos con "memoria", as� que and� preparando el tuyo :)
Por ahora, veamos qu� tal nos las apa�amos armando estrategias "ciegas", que tienen su encanto tambi�n.
Espero tu algoritmo, mucha suerte y gracias de nuevo!

Acido 69 dijo...

yo también me apunto, aunque es una lastima solo poder mandar un algoritmo, yo tengo 3 maneras, aunque el inicio marca mucho la táctica a seguir, tendré que hacer un random nada más empesar para elegir tipo de juego. Esta manera no me convence mucho.
Un saludo a todos.

Marcos dijo...

No te preocupes ácido por no poder madar más de un algoritmo... Ya habrá más lugar en la futura edición (dinámica).

Saludos y espero tu código!

Markelo dijo...

Ya mandé mi algoritmo.

Suerte para todos, la van a necesitar para poder ganarme :-)

Aguante el pequeritmo!!