Volver arriba
2013-09-15
Hace
varios artículos, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Con toda la infraestructura que tenemos ya montada, podemos
construir con pocas líneas uno de los autómatas más conocidos y
populares: el juego de la vida de Conway. Este autómata tiene las
siguientes características:
- consiste en un retículo bidimensional cartesiano;
- las celdas tienen dos estados posibles: 0 o muerta y 1 o viva;
- el vecindario de una celda es su vecindario de Moore (las celdas
que están en inmediato contacto con ella, lo que incluye contacto en
diagonal) unido a la propia celda;
- el próximo estado depende del valor de la propia celda y la suma
de los valores del vecindario de Moore.
La última característica hace que digamos que la regla es totalista
(depende de la suma de los valores del vecindario y no de los valores
individuales) exterior (también depende del propio estado de la celda
en cuestión). Como ya tenemos una función
(deterministic-rule) que nos construye reglas deterministas
a partir de una tabla que asocia conjuntos de vecinos con estados
futuros, podemos reutilizarla y construir vecindarios que en realidad
consisten en la suma de los estados vecinos.
Vecindarios totalistas
Podemos reutilizar la
función cyclic-cartesian-neighbourhoods que ya definimos
para obtener vecindarios en retículos cartesianos cíclicos; lo que
hacemos es sumar los estados vecinos que devuelve y así obtenemos
lo que le interesa a una regla totalista. La función que vamos a
hacer, cyclic-cartesian-totalistic-neighbourhoods, acepta
una lista de celdas cells, una lista de
dimensiones sizes y una lista
desplazamientos offsets, todo de forma
análoga cyclic-cartesian-neighbourhoods. El código en
Scheme es así:
(define (cyclic-cartesian-totalistic-neighbourhoods cells sizes offsets)
(map (lambda (neighbourhood) (map + neighbourhood))
(cyclic-cartesian-neighbourhoods cells sizes offsets)))
El equivalente en Python es así:
def cyclic_cartesian_totalitic_neighbourhoods(cells, sizes, offsets):
return map(lambda neighbourhoods: sum(neighbourhood),
cyclic_cartesian_neighbourhoods(cells, sizes, offsets))
Vecindarios totalistas externos
El juego de la vida de Conway no es meramente totalista, sino
totalista externo. Esto significa que tenemos que conocer no
solamente la suma del vecindario, sino también el valor de la propia
celda. Podemos construir un vecindario «artificial» que contiene el
valor de la propia celda y el valor de la suma de las celdas vecinas
que calculamos
con cyclic-cartesian-totalistic-neighbourhoods. El
resultado es una función de nombre tan largo:
(define (cyclic-cartesian-outer-totalistic-neighbourhoods cells sizes offsets)
(zip cells
(cyclic-cartesian-totalistic-neighbourhoods cells
sizes
offsets)))
El equivalente en Python es así:
def cyclic_cartesian_outer_totalistic_neighbourhoods(cells, sizes, offsets):
return zip(cells,
cyclic_cartesian_totalistic_neighbourhoods(cells,
sizes,
offsets))
Reglas de Conway
En el juego de la vida de Conway, una celda muerta pasa a estar
viva si tiene exactamente tres celdas vecinas vivas, mientras que una
celda viva continúa con vida si tiene dos o tres celdas vecinas vivas;
en todos los demás casos, la celda está muerta en el siguiente turno.
Podemos interpretar esto como que tres celdas (no más, no menos) en
contacto con una posición pueden reproducirse en esa posición,
mientras que las celdas vivas se mueren cuando están solas y sin apoyo
o cuando hay superpoblación. Con la estructura de vecinos que
generamos
con cyclic-cartesian-outer-totalistic-neighbourhoods,
podemos crear una regla determinista así:
(deterministic-rule '(((0 0) 0)
((0 1) 0)
((0 2) 0)
((0 3) 1)
((0 4) 0)
((0 5) 0)
((0 6) 0)
((0 7) 0)
((0 8) 0)
((1 0) 0)
((1 1) 0)
((1 2) 1)
((1 3) 1)
((1 4) 0)
((1 5) 0)
((1 6) 0)
((1 7) 0)
((1 8) 0)))
Esto es tan largo que es muy incómodo. Podemos escribir una
función para que sea la máquina quien escriba la tabla. Ya puestos,
podemos generalizar un poco el modelo. Hay reglas alternativas a la
de Conway que dan resultados muy diversos. Podemos usar una notación
sencilla para estas reglas en la que especificamos los números de
celdas vecinas vivas que necesita una celda muerta para nacer y los
números de celdas vecinas vivas que necesita una celda viva para
mantenerse con vida. Definimos una función llamada
generalised-conway-rule que construye la regla determinista
que buscamos a partir del valor máximo maximum-sum que
puede tomar la suma, la lista born de sumas que provocan
nacimiento y la lista stay-alive de sumas que provocan que
la celda permanezca con vida:
(define (generalised-conway-rule maximum-sum born stay-alive)
(define (half-rule current-state alive-list)
(map (lambda (sum)
(list (list current-state sum)
(if (member sum alive-list)
1
0)))
(range 0 (+ maximum-sum 1) 1)))
(deterministic-rule (append (half-rule 0 born) (half-rule 1 stay-alive))))
Como el número de sumas es pequeño en principio, esta técnica de
generación, que tiene un coste cuadrático, es aceptable. Podemos
construir la regla de Conway convencional así:
(generalised-conway-rule 8 '(3) '(2 3))
El primer argumento puede adoptar valores diferentes al empleado
si definimos autómatas en más de dos dimensiones o si usamos
vecindarios más amplios; en cuanto a los parámetros born
y stay-alive, tienen más valores que dan lugar a
comportamientos complejos. La regla
(generalised-conway-rule 8 '(2) '(7)), por ejemplo, da
lugar a muchas estructuras móviles.
La traducción más o menos literal del código anterior a Python 2 es
así:
def generalised_conway_rule(maximum_sum, born, stay_alive):
def half_rule(current_state, alive_list):
return map(lambda sum:
[(current_state, sum), 1 if sum in alive_list else 0],
range(0, maximum_sum + 1, 1))
return deterministic_rule(dict(half_rule(0, born)
+ half_rule(1, stay_alive)))
El juego de la vida de Conway
Ahora podemos poner en marcha el juego de la vida de Conway.
Tenemos que generar un tablero interesante. Vamos a hacer uno de 9
filas y 11 columnas con un planeador justo en el medio. Los nombres
de funciones tan larguísimos que estamos usando hacen que todo sea un
poco engorroso. El código es así:
(let* ((rule (generalised-conway-rule 8 '(3) '(2 3)))
(initial-cells '(0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0))
(sizes '(9 11))
(ccotn cyclic-cartesian-outer-totalistic-neighbourhoods)
(offsets '((-1 -1) (-1 0) (-1 1)
(0 -1) (0 1)
(1 -1) (1 0) (1 1)))
(neighbourhoods (lambda (cells)
(ccotn cells sizes offsets)))
(display-function (lambda (cells)
(translate-and-display-cartesian-2d cells
sizes
".*"))))
(interactive-step rule
initial-cells
neighbourhoods
display-function))
Los primeros estados salen así:
- ...........
...........
...........
.....*.....
......*....
....***....
...........
...........
...........
- ...........
...........
...........
...........
....*.*....
.....**....
.....*.....
...........
...........
- ...........
...........
...........
...........
......*....
....*.*....
.....**....
...........
...........
- ...........
...........
...........
...........
.....*.....
......**...
.....**....
...........
...........
- ...........
...........
...........
...........
......*....
.......*...
.....***...
...........
...........
- ...........
...........
...........
...........
...........
.....*.*...
......**...
......*....
...........
- ...........
...........
...........
...........
...........
.......*...
.....*.*...
......**...
...........
- ...........
...........
...........
...........
...........
......*....
.......**..
......**...
...........
- ...........
...........
...........
...........
...........
.......*...
........*..
......***..
...........
- ...........
...........
...........
...........
...........
...........
......*.*..
.......**..
.......*...
- ...........
...........
...........
...........
...........
...........
........*..
......*.*..
.......**..
- ...........
...........
...........
...........
...........
...........
.......*...
........**.
.......**..
- ...........
...........
...........
...........
...........
...........
........*..
.........*.
.......***.
- ........*..
...........
...........
...........
...........
...........
...........
.......*.*.
........**.
- ........**.
...........
...........
...........
...........
...........
...........
.........*.
.......*.*.
- ........**.
...........
...........
...........
...........
...........
...........
........*..
.........**
- ........***
...........
...........
...........
...........
...........
...........
.........*.
..........*
- .........**
.........*.
...........
...........
...........
...........
...........
...........
........*.*
- ........*.*
.........**
...........
...........
...........
...........
...........
...........
..........*
- *.........*
.........**
...........
...........
...........
...........
...........
...........
.........*.
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/09/15/jugando-con-automatas-celulares-13/
Volver arriba
