Continuamos hablando de algoritmos, en esta ocasión exploraremos los Autómatas Celulares de la mano del “Juego de la Vida” de John Conway (Conway’s Game Of Life), vamos a implementar este algoritmo utilizando WASM y HTML para poder visualizarlo.

Autómatas Celulares

Un autómata celular (A.C.) es un modelo matemático para un sistema dinámico que evoluciona en pasos discretos. Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros.

https://es.wikipedia.org/wiki/Aut%C3%B3mata_celular


Un autómata celular es esencialmente una regla de evolución temporal sobre un conjunto discreto, es decir, dado un punto de este conjunto, presentamos una regla que le asocia otro punto del conjunto.

www.revistaciencias.unam.mx/…

Es decir, un autómata celular es un conjunto de valores distribuidos dentro de un espacio (celdas en una rejilla) en donde el estado siguiente de cada elemento (célula) está determinado por el estado actual del mismo y de los vecinos que lo afectan; la manera en que el estado de cada elemento afecta a sus vecinos está determinado por una serie de reglas que se aplican de manera uniforme a todo el conjunto cada vez. Esto quiere decir que, a partir de un estado inicial y aplicando las mismas reglas a cada elemento de manera individual podremos determinar el siguiente estado de todo el conjunto y de cada elemento en particular; si este procedimiento lo repetimos de manera constante tendremos un sistema que evoluciona a través del tiempo de forma más compleja, comparado con el comportamiento de una sola célula.

La primera vez que se trató formalmente el tema fue al final de la década de los 40s del siglo XX, por John von Neumann en su libro: “Theory of Self-reproducing Automata”. Como detalle adicional, este también inspiró el juego Core War, mismo que dio origen a los virus informáticos.

El juego de la vida & John Conway

John Conway

John Horton Conway (nacido en Liverpool, Reino Unido, el 26 de diciembre de 1937). Prolífico matemático activo en la teoría de grupos (teoría de grupos finitos), teoría de nudos, teoría de números, teoría de juegos y teoría de códigos. Se formó en la Universidad de Cambridge.

https://es.wikipedia.org/wiki/John_Horton_Conway

Conway’s Game of Life (GOL)

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.

The game is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves, or, for advanced players, by creating patterns with particular properties.

https://en.wikipedia.org/wiki/Conway’s_Game_of_Life#Algorithms

El Juego de la Vida, también conocido simplemente como Life, es un autómata celular diseñado por el matemática británico John Horton Conway, en 1970.

Se trata de un juego zero-player, lo que significa que su evolución está determinada por su estado inicial, sin necesitar ninguna entrada de datos adicional. La forma de interactuar con el Juego de la Vida es creando una configuración inicial y observando como es que esta evoluciona, o, para los usuarios avanzados, creado patrones con características específicas.

Implementación

  • Para comenzar, deberemos construir una retícula bidimensional en donde cada espacio será considerado una célula, el estado inicial podrá determinarse de manera aleatoria o activando un determinado grupo de células.
    Retícula bidimensional
    Retícula bidimensional
  • A continuación deberemos recorrer cada célula, obteniendo la cantidad de vecinos activos y aplicando las siguientes reglas:
  1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overpopulation.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

Que se pueden resumir en:

  1. Una célula muerta con exactamente 3 células vecinas activas o vivas nace al siguiente turno
  2. Una célula activa o viva con 2 o 3 células vecinas se mantiene así, de lo contrario muere.

En el conteo de vecinos, consideraremos a las 9 células que rodean a célula que estaremos evaluando, es decir, las que se encuentran a los 4 lados, además de las diagonales:

Células vecinas
Células vecinas

En caso de evaluar una célula que se encuentra al borde de nuestra área de trabajo, evaluaremos como vecinos a las células del lado opuesto del área, como si todos sus lados estuvieran conectados (Frontera periódica):

Frontera periódica
Frontera periódica

Siguiendo con el ejemplo inicial, el conteo de vecinos activos y los cambios que sucederán en la siguiente generación se verían de la siguiente manera:

Estado inicial
Estado inicial
Conteo de vecinos
Conteo de vecinos
Cambios
Cambios
Siguiente estado
Siguiente estado

Repetiremos el mismo proceso de manera periódica sobre cada nuevo estado para obtener el siguiente.

Ejemplo



App en Go / WASM

Vamos implementar este algoritmo utilizando emojis, para ello vamos a seguir los pasos anteriores pero considerando que la salida del programa va a ser una cadena de texto que se irá actualizando conforme los estados de las células varíen:

La aplicación se encuentra funcionando en el siguiente link, pero la animación muestra algunas generaciones de muestra.

/experimentos/emojis-game-of-life/

Emojis Game Of Life
Emojis Game Of Life

Y este es el código de la primera versión:

Palabras finales

Existen otras versiones de este algoritmo en donde la cantidad de vecinos a evaluar o la forma de cada célula varía; además existen otros autómatas celulares con características variada que generan todo tipo de resultados; estas herramientas además de ser entretenidas por los resultados que genera su representación, son utilizados para simular comportamientos complejos como: el flujo de tráfico, la dispersión de un gas o el comportamiento de una colonia de bacterias, en donde cada elemento del conjunto se rige por algunas reglas simples pero el comportamiento general es difícil de predecir.

Por último

Quiero invitarte a que te unas a nuestro chat en Discord, en donde platicamos de estas cosas y otras relacionadas con la tecnología y la seguridad, la invitación la puedes encontrar en la sección Comunidad o dando click en el enlace.

Déjame un comentario más abajo o en mis redes sociales si te gusta este contenido o si tienes alguna sugerencia.

@umarquez