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.
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.
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.
- A continuación deberemos recorrer cada célula, obteniendo la cantidad de vecinos activos y aplicando las siguientes reglas:
- Any live cell with fewer than two live neighbours dies, as if by underpopulation.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overpopulation.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
Que se pueden resumir en:
- Una célula muerta con exactamente 3 células vecinas activas o vivas nace al siguiente turno
- 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:
.png “Celulas 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):
.png “Frontera periodica”)
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:
.png “Conteo de vecinos”).png “Cambios”).png “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/
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.