El Juego de la Vida de Conway

En 1970 el matemático británico John Conway creó el "Juego de la Vida", un conjunto de reglas que imitan el caótico pero reglado crecimiento de una colonia de organismos biológicos. El "juego" tiene lugar en una cuadrícula bidimensional formada por células "vivas" y "muertas". Las reglas para pasar de una generación a la siguiente son sencillas:

  • Superpoblación: si una célula viva está rodeada por más de tres células vivas, muere.
  • Permanencia: si una célula viva está rodeada por dos o tres células vivas, sobrevive.
  • Despoblación: si una célula viva está rodeada por menos de dos células vivas, muere.
  • Reproducción: si una célula está rodeada exactamente por tres células, se convierte en una célula viva.

Aplicando estas reglas en pasos sucesivos pueden aparecer patrones curiosos e inesperados.

Vamos a experimentar con el Juego de la Vida.

Insertamos las figuras en la notebook, en lugar de que cada figura abra una ventana nueva.

In [1]:
%matplotlib inline

Importamos los módulos matplotlib.pyplot y numpy

In [2]:
import numpy as np
import matplotlib.pyplot as plt

Ejercicio 1

Nuestra primera tarea es definir una función que implemente un paso del Juego usando bucles y condicionales que hagan cumplir las reglas que enumeramos.

La entrada es una matriz booleana que indica donde hay una célula viva (True) y donde no (False).

In [3]:
np.random.seed(0)                   
X = np.zeros((30, 40), dtype=bool)
r = np.random.random((10, 20))
X[10:20, 10:30] = (r > 0.75)

plt.imshow(X, cmap=plt.cm.binary, interpolation='nearest');

Tenemos que visitar cada elemento (célula) de la matriz y comprobar cual de las cuatro reglas se cumple examinando el cuadrado $3\times 3$ centrado en la celda y aplicar el nuevo estado de la célula.

Para las célula del borde, suponemos que los vecinos que caen fuera del rectángulo son aquellos que se encuentran el el borde opuesto. Por ejemplo, los vecinos de $X[0,10]$ son:

$$X[29,9],\; X[29,10],\;X[29,11],\; X[0,9],\; X[0,11],\; X[1,9],\; X[1,10],\; X[1,11].$$
In [4]:
%run vecindad.py

Tener en cuenta que $X[29,\cdot]$ también se pued indexar como $X[-1,\cdot ]$.

Empezaremos construyendo un programa, que a partir de una distribución inicial de células vivas y muertas, calcule el número de vecinos de una célula y lo almacene en la casilla correspondiente de una matriz, del mismo tamaño que X, llamada vecinos.

Para comprobar que el programa es correcto, incluso en los bordes, lo probaremos con la matriz $Y$ generada de la siguiente manera

In [5]:
np.random.seed(0)                   
Y = np.random.random((10, 10))
Y = (Y > 0.75)

plt.imshow(Y, cmap=plt.cm.binary, interpolation='nearest');

La matriz vecinos de $Y$ sería

In [6]:
%run Ejercicio1a.py

plt.imshow(vecinos, cmap='coolwarm', interpolation='nearest') 
plt.colorbar()
plt.show()

A partir del código del programa anterior, definir la función un_paso_en_la_vida_1(X). La salida debe ser una matriz del mismo tamaño con el estado nuevo de las células. De momento, para comprobar que el programa es correcto vamos a incluir en la salida la matriz vecinos.

Para el ejemplo de arriba conseguimos

In [7]:
%run Ejercicio1.py

nuevoX, vecinos = un_paso_en_la_vida_1(X)

plt.imshow(vecinos, cmap='coolwarm', interpolation='nearest');
plt.colorbar()
plt.show()

Y la nueva matriz de células es

In [8]:
plt.imshow(nuevoX, cmap=plt.cm.binary, interpolation='nearest');

Ejercicio 2

En este ejercicio, continuamos con el programa de arriba incorporándole un bucle de tiempo. Definimos el número de pasos (40 en este ejemplo) y vamos actualizando el estado de las células en X con la función un_paso_en_la_vida_1(X) dentro del bucle. Mostrar una figura de evolución del estado de X. Para ello, aparte de plt.imshow hay que usar plt.pause(0.001) dentro del bucle.

Se puede ejecutar en consola escribiendo:

python Ejercicio2.py

El resultado obtenido debería ser parecido, aunque no el mismo si no se fija la misma semilla, al siguiente

In [9]:
# Herramienta de animación tomada de https://github.com/jakevdp/JSAnimation

import libJuegoDeLaVida

libJuegoDeLaVida.animacion(X, dpi=10, frames=40, mode='once')
Out[9]:


Once Loop Reflect

Una de las ventajas principales de numpy es su velocidad en la manipulación de matrices.

Usa la siguiente función para reemplazar un_paso_en_la_vida_1(X):

In [10]:
def un_paso_en_la_vida_2(X):
    """Juego de la Vida usando scipy tools"""
    from scipy.signal import convolve2d
    num_vecinos = convolve2d(X, np.ones((3, 3)), mode='same', boundary='wrap') - X
    return (num_vecinos == 3) | (X & (num_vecinos == 2))    
    # | y & son para "or" y "and" bit a bit (usado para arrays)
    # devuelve True si num_vecinos = 3 o (X[i,j] = 1 y num_vecinos = 2)

Ejercicio 3

  • Comprobar que las dos funciones dan el mismo resultado usando np.max(np.abs(X1-X2)), donde X1 y X2 son las salidas de un_paso_en_la_vida_1(X) and un_paso_en_la_vida_2(X), para el mismo X de entrada.
  • Comparar los tiempos de ejecución (comentar las líneas que contienen plt.imshow y plt.pause porque la renderización de los gráficos enlentece el código). Para ello, usar el paquete timeit como sigue
In [11]:
import timeit

tic=timeit.default_timer()
for i in range(0,1000):
    i += 1                       # reemplazar con los comandos adecuados
toc=timeit.default_timer()
print "Tiempo = %f" % (toc - tic )         

Tiempo = 0.000298

Si llamamos t1 al tiempo que tarda en ejecutarse el bucle con el primer programa y t2 al tiempo para el segundo programa, para el ordenador con el que se construyó esta notebook los tiempos de ejecución son

In [12]:
%run Ejercicio3.py

X1 = un_paso_en_la_vida_1(X)
X2 = un_paso_en_la_vida_2(X)
diferencia = np.max(np.abs(X1-X2))
print "Diferencia entre las dos funciones = %i" % diferencia

t1 = tiempo_1(40)
print "Tiempo 1 = %f " % t1

t2 = tiempo_2(40)
print "Tiempo 2 = %f " % t2

Diferencia entre las dos funciones = 0
Tiempo 1 = 0.317797 
Tiempo 2 = 0.002570

Ejercicio 4

Escribe una función que contenga un_paso_en_la_vida_2 y animacion_vida (bajarla aquí) y úsala con los datos de abajo. Comprueba que tus resultados coinciden con los mostrados aquí.

Configuraciones Estáticas

Se conocen varias configuraciones estáticas: mostramos aquí algunas de las unidades estáticas más pequeñas. Mostraremos unas cuantas frames para comprobar que, efectivamente, son estáticas.

In [13]:
X = np.zeros((6, 21))
X[2:4, 1:3] = 1
X[1:4, 5:9] = [[0, 1, 1, 0],
               [1, 0, 0, 1],
               [0, 1, 1, 0]]
X[1:5, 11:15] = [[0, 1, 1, 0],
                 [1, 0, 0, 1],
                 [0, 1, 0, 1],
                 [0, 0, 1, 0]]
X[1:4, 17:20] = [[1, 1, 0],
                 [1, 0, 1],
                 [0, 1, 0]]

libJuegoDeLaVida.animacion(X, dpi=5, frames=3)
Out[13]:


Once Loop Reflect

Algunos osciladores sencillos: El Parpadeador (The Blinker) y El Sapo (The Toad)

Un oscilador es un patrón que vuelve a su configuración inicial después de un determinado número de pasos. Los patrones estáticos podrían ser considerados osciladores de periodo uno. Aquí se muestran dos conocidos osciladores de periodo dos:

In [14]:
parpadeador = [1, 1, 1]
sapo = [[1, 1, 1, 0],
        [0, 1, 1, 1]]

X = np.zeros((6, 11))
X[2, 1:4] = parpadeador
X[2:4, 6:10] = sapo
libJuegoDeLaVida.animacion(X, dpi=5, frames=4)
Out[14]:


Once Loop Reflect

Otro oscilador: el Púlsar

Existen osciladores más complicados. Aquí se muestra un oscilador de periodo tres conocido como "El Púlsar", que muestra una simetría interesante.

In [15]:
X = np.zeros((17, 17))
X[2, 4:7] = 1
X[4:7, 7] = 1
X += X.T         # sumamos la matriz transpuesta
X += X[:, ::-1]  # sumamos la matriz simétrica respecto al eje vertical
X += X[::-1, :]  # sumamos la matriz simétrica respecto al eje horizontal
libJuegoDeLaVida.animacion(X, frames=6)
Out[15]:


Once Loop Reflect

El Planeador (The Glider)

Hay otra clase de objetos que no sólo oscilan, sino que también se mueven mientras oscilan. Uno de los primeros descubiertos fue El Planeador (The Glider), que después de 4 pasos vuelve a su configuración inicial pero desplazado una celda tanto en dirección x como en dirección y. Esta configuración aparece a menudo en configuraciones iniciales aleatorias.

In [16]:
import  libJuegoDeLaVida
planeador = [[1, 0, 0],
          [0, 1, 1],
          [1, 1, 0]]
X = np.zeros((8, 8))
X[:3, :3] = planeador
libJuegoDeLaVida.animacion(X, dpi=5, frames=32, interval=100)
Out[16]:


Once Loop Reflect

Crecimiento ilimitado

Una pregunta que se planteó al principio sobre el Juego de la Vida fue si existía alguna configuración que tuviera un crecimiento ilimitado. Pronto se concluyó que la respuesta era sí. Aunque no fue la primera descubierta, la siguiente es una de las más compactas. De todas formas, esto es cierto únicamente en un tablero infinito, no en el caso implementado aquí. En cualquier caso, las cien primeras generaciones no resultan afectadas.

In [17]:
ilimitado = [[1, 1, 1, 0, 1],
             [1, 0, 0, 0, 0],
             [0, 0, 0, 1, 1],
             [0, 1, 1, 0, 1],
             [1, 0, 1, 0, 1]]
X = np.zeros((30, 40))
X[15:20, 18:23] = ilimitado
libJuegoDeLaVida.animacion(X, dpi=10, frames=100, interval=200, mode='once')
Out[17]:


Once Loop Reflect

Pistola de planeadores de Gosper (Gosper Glider Gun)

El patrón que primero se descubrió de crecimiento ilimitado fue la Pistola de Planeadores (Glider Gun) de Bill Gosper. Es un patrón oscilante que crea una serie infinita de Planeadores.

In [18]:
pistola_planeadores =\
[[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],
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1],
 [1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
 [1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,0,1,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,1,0,0,0,0,0,0,0,1,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,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,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]

X = np.zeros((50, 70))
X[1:10,1:37] = pistola_planeadores

libJuegoDeLaVida.animacion(X, dpi=15, frames=180, interval=50, mode='once')
Out[18]:


Once Loop Reflect

Más allá

A pesar de (o tal vez debido a) su simplicidad, el Juego de la Vida ha inspirado una comunidad que estudia sus propiedades. Ha influenciado campos tan diferentes como las matemáticas, la computación, la biología, la epidemilogía y la sociología.

El interés ha llevado al descubrimiento de configuraciones con propiedades sorprendentes.

Incluso se ha demostrado que la Máquina Universal de Turing se puede crean con las reglas del Juego de la Vida. Es decir, un ordenador que calcula pasos del Juego de la Vida, en teoría, podría usar este proceso para calcular cualquier cosa.

A continuación otros patrones que puedes probar.

In [19]:
diehard = [[0, 0, 0, 0, 0, 0, 1, 0],
           [1, 1, 0, 0, 0, 0, 0, 0],
           [0, 1, 0, 0, 0, 1, 1, 1]]

boat = [[1, 1, 0],
        [1, 0, 1],
        [0, 1, 0]]

r_pentomino = [[0, 1, 1],
               [1, 1, 0],
               [0, 1, 0]]

beacon = [[0, 0, 1, 1],
          [0, 0, 1, 1],
          [1, 1, 0, 0],
          [1, 1, 0, 0]]

acorn = [[0, 1, 0, 0, 0, 0, 0],
         [0, 0, 0, 1, 0, 0, 0],
         [1, 1, 0, 0, 1, 1, 1]]

spaceship = [[0, 0, 1, 1, 0],
             [1, 1, 0, 1, 1],
             [1, 1, 1, 1, 0],
             [0, 1, 1, 0, 0]]

block_switch_engine = [[0, 0, 0, 0, 0, 0, 1, 0],
                       [0, 0, 0, 0, 1, 0, 1, 1],
                       [0, 0, 0, 0, 1, 0, 1, 0],
                       [0, 0, 0, 0, 1, 0, 0, 0],
                       [0, 0, 1, 0, 0, 0, 0, 0],
                       [1, 0, 1, 0, 0, 0, 0, 0]]

Referencias