תוכנת זיהוי שירים
אגרה ללא מרשםוי
תרגום ליפנית
бинарные опционы рейтинг брокеров
קמגרה גל
интернет магазин ламода отзывы

Tag Archives: Autómata Celular

Juego de la vida

Dicta wikipedia: El juego de la vida es el mejor ejemplo de un autómata celular, diseñado por el matemático británico John Horton Conway en 1970.

No se bien por qué me atraen bastante estos jueguitos, debe ser porque (acá viene un razonamiento serio) leí de muchos laburos con los que logran imitar comportamientos muy complejos con reglas realmente simples, tales como la infección de células con HIV en el organismo humano, o la dinámica de un incendio  o también debe ser (y acá viene la boludez) porque ya terminé de ver todas las temporadas de Capusotto.

El tema surge porque hace un par de días un alumno me consultó sobre este ejercicio y lo planteamos medio por arriba, más por lo laborioso que por su complejidad. Así que, para evitar que me atormente la culpa y la angustia, me repartí la siesta del sábado y del domingo para programarlo en Python y, de paso para hacer unas animaciones y comprender mejor el comportamiento de estos bichos. Además, lo plasmo acá debido al incentivo de un ex profesor y ex jefe que a veces lee este estático blog, Gracias Pablo!

Entonces, el juego consiste en un conjunto de bichos vivos o muertos cuyo estado cambia en el tiempo (de generación en generación) dependiendo de lo que haya a su alrededor, es decir, varía en función de su estado (vivo o muerto) y de sus vecinos.

Las reglas de evolución son la siguientes:

  • Una célula muerta con exactamente 3 vecinas vivas => vive
  • Una célula viva con mas de 3 vecinas vivas => muere
  • Una célula viva con 2 o 3 vecinas vivas => vive
  • Una célula viva con menos de 2 vecinas vivas => muere

Desde el punto de vista de su implementación, lo hice del siguiente modo:

  • La población de células es una matriz de mxn, cuyo valor es 1 o 0 (viva o muerta respectivamente) que se inicia en forma aleatoria.
  • Los vecinos son los que están alrededor, donde hay que tener en cuenta que no todos tienen la misma cantidad de vecinos:
  • Las cuatro células de las esquinas tienen 3 vecinos.
  • Las del borde sin contar las esquinas tienen 5.
  • Las del interior están rodeadas, por lo que se debe controlar el estado de las 8 células vecinas.

Entonces, teniendo en cuenta estos detalles e iterando sobre la cantidad de generaciones para observar su evolución nos queda un hermoso código de aproximadamente 100 líneas:

import numpy as np
import matplotlib.pyplot as plt
import scitools.std as sci

def nuevo_estado(celula_viva,vecinos):
    ''' Reglas de evolucion:
        - celula  muerta  con  exactamente 3 vecinas vivas => vive
        - celula viva con mas de 3 vecinas vivas           => muere
        - celula viva con 2 o 3 celulas vecinas vivas      => vive
        - celula viva con menos de 2 vecinas vivas         => muere
    '''
    vive = 1
    muere = 0
    estado = celula_viva.copy()
    vecinas_vivas = sum(vecinos)

    if celula_viva:
        # celula viva => contemplo solo los casos en los que muere
        if vecinas_vivas > 3:
            estado = muere
        elif vecinas_vivas < 2:
            estado = muere
    else:
        # celula muerta
        if vecinas_vivas == 3:
            estado = vive
    return estado

def main(m,n,generaciones):
    # mi semilla
    np.random.seed()

    poblacion = np.random.randint(2,size=(m,n))
    gen_tempo = np.zeros((m,n), int)

    celulas_vivas = []
    celulas_vivas.append(np.sum(poblacion))
    # BW
    plt.imshow(poblacion, cmap='binary', interpolation='nearest')
    # Grey
    #plt.imshow(poblacion, cmap='binary')
    counter = 1
    plt.savefig('img/tmp%04d.png' %counter)
    #plt.show()

    for g in range(1,generaciones+1):
        # ------------------------------
        # Hay 3 casos para especiales:
        # ------------------------------
        # 1- En las esquinas de la matriz

        # -- Superior e infrerior izquierda
        vecinos = np.array([poblacion[0,1], poblacion[1,1], poblacion[1,0]])
        gen_tempo[0,0] = nuevo_estado(poblacion[0,0],vecinos)

        vecinos = np.array([poblacion[m-2,0], poblacion[m-2,1], poblacion[m-1,1]])
        gen_tempo[m-1,0] = nuevo_estado(poblacion[m-1,0],vecinos)

        # -- Superior e inferior derecha
        vecinos = np.array([poblacion[0,n-2], poblacion[1,n-2], poblacion[1,n-1]])
        gen_tempo[0,n-1] = nuevo_estado(poblacion[0,n-1],vecinos)

        vecinos = np.array([poblacion[m-1,n-2], poblacion[m-2,n-2], poblacion[m-2,n-1]])
        gen_tempo[m-1,n-1] = nuevo_estado(poblacion[m-1,n-1],vecinos)

        # 2- En la matriz sin los bordes
        for i in range(1,m-1):
            for j in range(1,n-1):
                vecinos = np.array([poblacion[i-1,j-1],poblacion[i-1,j],poblacion[i-1,j+1,],
                                    poblacion[i,j-1],poblacion[i,j+1],
                                    poblacion[i+1,j-1],poblacion[i+1,j],poblacion[i+1,j+1]])
                gen_tempo[i,j] = nuevo_estado(poblacion[i,j],vecinos)

        # 3- En los 4 bordes sin las esquinas
        for i in range(1,m-1):
            # Columna izquierdo
            vecinos = np.array([poblacion[i-1,0],
                                poblacion[i-1,1],poblacion[i,1],poblacion[i+1,1],
                                poblacion[i+1,0]])
            gen_tempo[i,0] = nuevo_estado(poblacion[i,0],vecinos)
            # Columna derecha
            vecinos = np.array([poblacion[i-1,n-1],
                                poblacion[i-1,n-2],poblacion[i,n-2],poblacion[i+1,n-2],
                                poblacion[i+1,n-1]])
            gen_tempo[i,n-1] = nuevo_estado(poblacion[i,n-1],vecinos)

        for i in range(1,n-1):
            # Fila superior
            vecinos = np.array([poblacion[0,i-1],
                                poblacion[1,i-1],poblacion[1,i],poblacion[1,i+1],
                                poblacion[0,i+1]])
            gen_tempo[0,i] = nuevo_estado(poblacion[0,i],vecinos)
            # Fila inferior
            vecinos = np.array([poblacion[m-1,i-1],
                                poblacion[m-2,i-1],poblacion[m-2,i],poblacion[m-2,i+1],
                                poblacion[m-1,i+1]])
            gen_tempo[m-1,i] = nuevo_estado(poblacion[m-1,i],vecinos)

        poblacion = gen_tempo.copy()
        plt.imshow(poblacion, cmap='binary', interpolation='nearest')
        #plt.imshow(poblacion, cmap='binary')
        plt.savefig('img/tmp%04d.png' %(counter+g))
    sci.movie('img/tmp*.png', output_file='img/juegoDeLaVida_'+str(m)+'x'+str(n)+'_'+str(generaciones)+'gen.gif')

if __name__ == "__main__":
    filas = 100
    columnas = 100
    generaciones = 200
    main(filas,columnas,generaciones)

Y bueno, el gif generado con el código previo, para una población de 100×100 y una evolución de 200 generaciones (me siento Darwin) se puede observar haciendo click sobre la siguiente imagen.

juegoDeLaVida_100x100_200genBW

Para la visualización usé matplotlib, para la animación scitools, y el laburo de arreglos usando numpy. Nada del otro mundo. Solo le faltaría una interfaz gráfica de usuario, con botoncitos, cuadritos, florcitas y esas yerbas, pero la verdad, detesto programarlas, ya subiré el código a un repositorio público (estoy laburando en eso) para que quien quiera lo modifique o sino que lo pida y capaz lo agarro con más ganas.

Por último, recomiendo hacer como ejercicio inicial este juego para aprender a programar, tiene un mix de todo sin alcanzar una complejidad elevada, y además, una vez concluido permite filosofar sobre la evolución de las especies, los límites del universo y por qué no hay canchas de futbol 5 con el nombre de Messi todavía, todo eso con buen vinito de por medio.

A New Kind of Science

Stephen Wolfram - A New Kind Of Science

Ese es el título del afamado libro de Stephen Wolfram cuyo acceso online es gratuito. Hace rato que lo vengo ojeando pero pocas veces me puse a programar algo de lo que desarrollaba. Hasta hoy!

Domingo lluvioso, ideal para programar pequeños fragmentos de código horrible para reproducir los autómatas celulares (AC) que tanto investigó este tipo. La utilidad de los AC son amplias, tienen aplicaciones diversas que van desde las boludeces aquí presentadas hasta comportamientos mucho más complejos como la modelación del crecimiento de un tumor, por mencionar algo. Sin embargo, acá no nos importa todas las demás aplicaciones, al menos no por ahora, sino empezar con los experimentos del capítulo 2 e ir avanzando con lo que plantea el libro.

Los AC pueden definirse como una grilla de células donde sus estados son finitos y pueden evolucionar en función de su estado actual y del estado de sus vecinos. Bueno, eso es una definición mía agarrada de los pelos, en wikipedia está mejor. En criollo sería algo así como: dime como estás y cómo están con los que te juntas y te diré como estarás mañana.

Yendo un poco más específicamente a lo que plantea Estifen en el capítulo 2 de su libro, una célula puede ser negra o blanca (1 o 0 respectivamente), así de fácil. El tema es el conjunto de reglas que se le imponen para cambiar a blanco o a negro. Por ejemplo, si tenemos en un momento determinado 8 células dispuestas linealmente de este modo: 0001000

En el paso siguiente va a haber algunas que cambian de 0 a 1 y viceversa, evaluando su estado y el de sus inmediatas vecinas, es decir la de la izquierda y de la derecha. Acá surge la duda de qué hacemos con la de los extremos, las obviamos, empezamos tomando las tres primeras (000) para ver qué nuevo valor va a tener la central, luego las tres siguientes (001), las otras tres (010) y así sucesivamente hasta tomar las últimas tres células (000) .

De manera tal que los 3 primeros ceros, 000, van a determinar el nuevo valor de la célula del medio. La regla denominada Rule 30, realiza los siguientes cambios:

000: 0
001: 1
010: 1
011: 1
100: 1
101: 0
110: 0
111: 0

El primer caso se explicaría así: cuando la célula central es 0 y las vecinas son 0, entonces el nuevo valor de la célula será 0. Ahora, por qué se llama regla 30? bueno, si te fijás la columna de la derecha forma el número 30 si convertís a decimal el número 00011110, se entiende? ok, así me gusta.

O sea que ya tenemos casi todo. Cómo se hace? Bueno, vamos tomando de a 3 células y hacemos la actualización. Con el valor inicial dado 0001000, se irían actualizando las nuevas generaciones de la siguiente manera:

 

0011100
0110010
0101110

Con estas reglas tan simples se generan estructuras complejas como las de acá:

rule30-zoomrule73-145x120-zoomrule146-zoom rule150-zoom

El código necesario para generar estas y otras figuras está hecho en Python. Las generaciones serían la cantidad de filas de la imagen, y las reglas van desde 0 hasta 255 generando una figura pbm por cada una.

import ACfunctions as ac
gen=10
for rule in range(256):
    bit_ini='00000100000'
    header = 'P1 '+ str(len(bit_ini)) + ' '+str(gen)
    o = open("rule"+str(rule)+"-"+str(len(bit_ini)) + 'x'+str(gen)+".pbm",'w')

    o.write(header+"\n")
    o.write(bit_ini+"\n")

    new_bit='0'
    for n in range(gen):
        for i in range(len(bit_ini)-2):
            new_bit+=ac.getState(rule,bit_ini[i:i+3])
        new_bit+='0'
        o.write(new_bit+"\n")
        bit_ini=new_bit
        new_bit='0'
    o.close()

Y la función que hice para determinar las reglas, aún no mejorada es esta:

def getState(rule,bits):
    '''Descripcion:
        Devuelve el estado de la celula a partir del estado
        de la cadena representada en bits siguiendo la regla
        representada por rule
        rule : entero entre 0 y 255
        bits: cadena de 3 caracteres de ceros y unos
    '''
    # Convierte el entero rule a binario de 8 bits representado por una cadena
    bin_rule=bin(rule)[2:].zfill(8)
    # Aplica la regla de Wolfram
    if bits=='000':
        b=bin_rule[7]
    elif bits=='001':
        b=bin_rule[6]
    elif bits=='010':
        b=bin_rule[5]
    elif bits=='011':
        b=bin_rule[4]
    elif bits=='100':
        b=bin_rule[3]
    elif bits=='101':
        b=bin_rule[2]
    elif bits=='110':
        b=bin_rule[1]
    elif bits=='111':
        b=bin_rule[0]
    return b

Esta es la primer entrega del capítulo 2 del libro. Algún otro domingo iré continuando con desarrollos que agregan más complejidad. Por lo pronto les dejo el famoso juego de la vida de conway

Social Widgets powered by AB-WebLog.com.

Social Widgets powered by AB-WebLog.com.

Social Widgets powered by AB-WebLog.com.