jueves, enero 10, 2008

Piedra Papel o Tijera

Hace poco me encontré por casualidad, gracias a un enlace de Reddit (ya no lo encuentro), una página que ofrecía un software para simular Bots. Ésto incluía API y otro montón de cosas, todo ésto montado sobre Excel (PUAGGG). Dentro de los proyectos que habían el que mas me llamó la atención era uno llamado Scissors, Paper and Rock. Éste simulaba un ambiente donde unos bots se movían en forma aleatoria por un campo e iniciaban en posiciones aleatorias de éste. Lo único que cambiaba es que unos bots eran tijeras, otros rocas y otros papeles.

Si un bot Tijeras se topaba con un Papel, el papel se convertía en otro bot de tijeras... eso aplicaba para cualquier combinación de bots bajo las reglas usuales. Si en cambio 2 bots de la misma clase se encontraban no pasaba nada. Mas interesante que la imagen de unas tijeritas desplazándose por un mapa es tal vez la gráfica que el niño (si mal no recuerdo el que hizo ésto tenía 12 o 13 años) realizó de las poblaciones de dichos bots. Si uno piensa a la ligera se espera una gráfica super caótica o nada especial, sin embargo los efectos que cada población ejerce sobre las otras dos hace que la gráfica sea bien interesante.

Algo bueno de la ciencia es tal vez que todo resultado encontrado es sujeto de verificación. Yo realicé un experimento parecido al del niño este (ese niño si sabe divertirse) con algunas diferencias.

1) Como estoy aprendiendo F#, lo hice en F#.
2) Utilicé una matriz que iba recorriendo, mas a modo de automata celular... Dado que la matriz es bien dispersa resulta muy ineficiente.
3) Intente usar algo de teoría de Why Attribute Grammars Matters sin ningún éxito.
4) El grid no tiene bordes... es al estilo de un mapa de Karnaugh

En fin... sin más preámbulos aquí está la gráfica.



A diferencia de los resultados del niño, aqui cada "onda" va creciendo hasta que una población se queda sin bots.

Pero bueno. Mostraré algunas cositas del lenguaje bien sencillas.

Por ejemplo, si quiero definir Tijeras Roca y Papel, es tan sencillo como en Haskell.


type hand = Scissors | Rock | Paper


La función que decide quien gana es igual de fácil.

let rec who_wins i j = 
match i,j with
| Scissors,Paper -> Scissors
| Paper, Rock -> Paper
| Rock, Scissors -> Rock
| i, j when (i = j) -> i
| i, j -> who_wins j i


Sin embargo aún no me acostumbro a los aspectos de evaluación estricta de F#

Es decir... si en Haskell tenemos ésto:
a x = a x
iff a (x,y) = if a then x else y
x = iff True (2,a 3)

La función x termina. Porque con la evaluación perezosa no tenemos que saber cual es el valor de toda la tupla cuando se la pasamos a la función iff. En cambio en F#, tener éste equivalente:
let rec a x = a x
let iff a (x,y) = if a then x else y
let x = iff true (2,a 3)


Con evaluación estricta, tratamos de saber el valor de la tupla y en ese proceso nos quedamos en un loop infinito. En el código inicial para conocer la victoria tenía un código que hacía uso de una función iff. Por esto se llamaba a la función who_wins infinitamente y como resultado... stack overflow CHAAAN CHAAN CHAAAAAAAN.

4 comentarios:

febuiles dijo...

¿Se podría usar el "lazy" y "Lazy.force" de F# para forzarlo a evaluar perezosamente?
Por curiosidad me puse a "Googlear" y encontré esto:
http://books.google.com/books?id=n1DEBdl_oloC&pg=PA50&lpg=PA50&dq=lazy+evaluation+f%23&source=web&ots=784-oDIPas&sig=q4gBXZlUtN5di0X05N6pQ-DVXh0

febuiles dijo...

Blogger me cortó la URL pero podés probar http://tinyurl.com/yp8fnr

diegoeche dijo...

Pues parece que si... todavía no he jugado con esas construcciones

Pocho dijo...

Con algo de teoria de dinamica de sistemas y un simulador podria retornar graficas bastante similares. Ya jugue un rato con esto y siempre el resultado fue un equilibrio bastante elegante y en algun momento un quiebre de alguno que termina con 2 de las 3 manos.