Autómatas celulares unidimensionales en Python

Estaba yo leyendo este verano un libro titulado Think Complexity cuando en un capítulo empezó a hablar de los autómatas celulares unidimensionales. El tema me interesó y por eso esta entrada. Veamos primero a qué nos referimos cuando hablamos de esto.

Cuando hablamos a autómatas celulares, nos referimos a pequeñas entidades independientes pero que interaccionan entre sí. Celulares porque son la unidad elemental del universo donde van a existir y autómatas porque deciden por ellas mismas, basadas en un conjunto de reglas predefinido, cuando el tiempo avanza de forma discreta (es decir, a pasos).

Este concepto abstracto puede visualizarse con facilidad si nos imaginamos una rejilla. Cada celda es una célula capaz de cambiar su estado según su entorno.

Los autómatas celulares fueron objeto de estudio de Stephen Wolfram, matemático conocido por haber diseñado el programa Mathemathica y Wolfram Alpha.

Los autómatas celulares unidimensionales son aquellos que forman parte de un universo unidimensional. Es decir, cada célula tiene una vecina a su izquierda y a su derecha. En los bordes se pueden definir varios comportamientos pero el concepto no varía. Pensemos en ello como una tira de celdas.

El estudio de estos autómatas es interesante, ya que pueden generarse patrones/situaciones muy complejas en base a unas reglas sencillas.

¿Cómo se definen las reglas?

Wolfram usó un sistema para definir las reglas de estos autómatas que hoy conocemos como Wolfram Code. Se basa en definir una tabla con los estados presentes de la célula y sus vecinas así como el valor que deberá adoptar en esa situación la célula. Como Wolfram usó células con solo dos estados, todo está en binario, y la parte baja de la tabla es un número de 8 bits. Este número se suele pasar a decimal y así se identifica.

Estados presentes 111 110 101 100 011 010 001 000
Estado futuro 0 0 1 1 0 0 1 0

Esta tabla representa la Regla 50, porque 00110010 en binario es 50.

¿Cómo se representan?

Una manera muy interesante de representar estos autómatas es poner cada paso en una fila distinta dentro de una imagen.

Una vez que sabemos esto vamos a hacer un programa en Python que nos permita observar la evolución de estos autómatas.

Usaremos el procedimiento original, que es empezar con todos los estados de los autómatas en 0 salvo el del autómata central, que será 1.

La clase Automata

La clase autómata va a contener las reglas, así como un ID y el estado que posee. Además, por cuestiones técnicas conviene guardar el estado anterior que tuvo.

Como podéis ver, rules no lleva self, es decir, va a ser una variable compartida entre todas las instancias de Automata. Esto es porque las reglas son idénticas a todos los autómatas.

La clase World

Ahora vamos a definir el universo donde residen estos autómatas. Este universo almacena una lista con los autómatas, se encarga de actualizarlos según las normas y de dibujarlos usando PIL. También he insertado el código que codifica las normas según el número en decimal.

Con esto ya lo tenemos casi todo. Ahora faltaría poner en marcha todo. La idea es simplemente crear una instancia de World, hacer unas cuantas llamadas a add, y después ir haciendo el ciclo update/draw_row. Una vez hayamos acabado, hacemos save y obtendremos un PNG con la imagen.

Código completo

Algunas reglas importantes

Regla 30

Una de las más importantes a nivel matemático. Ha sido objeto de mucho estudio, sin embargo no vamos a entrar en detalles más allá de su aspecto visual.

Vista ampliada

Regla 110

Esta regla es también muy interesante. ¡Se demostró que era Turing completa!

Vista en detalle

Regla 126

Esta regla no es tan importante, pero personalmente me parece muy bonita.

Vista ampliada

Reglas 57 y 99

Son dos reglas isomorfas. Es decir, son en realidad la misma regla pero aplicada a lados distintos. Elijo estas dos porque se aprecia muy bien el isomorfismo.

Regla 57
Regla 99

Regla 169

Vista en detalle

Regla 129

Regla 90

Es el famoso triángulo de Sierpinski.

Regla 150

Regla 105

Esta regla no tiene isomorfo.

En este artículo no he querido entrar en las complejidades matemáticas de todo esto. Es algo que todavía no entiendo así que no sería sincero por mi parte exponerlo.

Bonus: Richard Feynman y Steve Jobs

Quien me conoce sabe de sobra que uno de los personajes de la historia que más ha influido en mi vida es Richard Feynman. Debo reconocer que entré en un estado de éxtasis al descubrir que Feynman y Wolfram no solo trabajaron juntos, sino que lo hicieron alrededor de la regla 30 antes mostrada. También me sorprendió que Steve Jobs y Wolfram resultasen ser amigos de toda la vida. No dejo de sorprenderme de los contactos de ciertos personajes históricos entre sí.

Feynman a la izquierda, Wolfram a la derecha

Anrokku, un videojuego tipo puzzle

Anrokku es un juego de puzles que he programado estas semanas. Las reglas son simples, somos una ambulancia y tenemos que salir del parking debido a una emergencia. Desafortunadamente el parking es un caos y los coches bloquean la salida. Tu labor es ir moviendo los coches para lograr que la ambulancia salga del parking. Y cuantos menos movimientos hagas mejor.

En el menú principal podremos seleccionar a cuál de los 20 niveles queremos jugar. No podremos jugar a todos a la vez, es necesario habernos pasado los niveles anteriores para desbloquear el siguiente.

Ya en el juego tenemos que ir arrastrando los coches con el ratón para que la ambulancia pueda irse por la derecha. El juego está programando en Python 2.7 usando GTK. El renderizado está hecho en un GtkDrawingArea donde he usado Cairo. ¿Quiéres jugar? El juego completo es gratuito y open source bajo la liencia MIT en GitHub. No obstante, puedes descargar el archivo ZIP con el juego desde este enlace.

Descargar Anrokku

Después de descargar y descomprimir el archivo. Ejecuta el fichero main.py haciendo doble click o desde la terminal:

python2 main.py

¡Quiero ver muchas pantallas como esta!

 El juego almacena los récords obtenidos en cada nivel. Puede ser interesante repetir los niveles para hacerlo en el menor número posible de movimientos. En el primer nivel he conseguido ganar en 32 movimientos, ¿alguien se atreve a superarme?

Mandando paquetes ICMP ECHO personalizados con Python

Estos días he estado experimentando un poco con una característica de las redes. En concreto he intentando ver si era posible lanzar un paquete a la red cuyo origen es una dirección broadcast y el receptor, al mandar la respuesta, lo hiciera sin darse cuenta a todos los equipos de la red. Esto en efecto podría usarse para inutilizar una red por Denial of Service.

ICMP ECHO

La prueba la he hecho con un ICMP ECHO pero podría hacerse con otros protocolos también, como DHCP.

Un ICMP ECHO es lo que hace el famoso comando pingping6 (en IPv6). Se trata de un protocolo de la capa de red (capa 3 en TCP/IP). ICMP dispone de varias operaciones para funcionar correctamente (Internet Control Message Protocol, controlar la red) pero la mayoría de ellas no se utilizan. Una que sí se usa es el ECHO, que permite mandar una información a un host y el host nos tiene que devolver lo mismo.

¿Cómo sabe a donde tiene que enviar la respuesta? A la IP de origen del primer paquete claro, pero ¿y si mentimos? ¿Y si le ponemos que la IP de origen es la IP de broadcast? Supuestamente, enviaría la respuesta a todos los demás hosts de la subred.

Script en Python

Para poder hacer los datagramas IP personalizados y poder mentir, usé raw sockets. Estos solo me han funcionado en Linux. El código es muy simple, la parte que más me costó fue el checksum pues las operaciones con bytes en Python son un poco curiosas, no existiendo el tipo byte pero si bytes.

Espero que a alguien le resulte interesante el código. Es un ejemplo de como generar datagramas sin la ayuda del sistema operativo. Además es importante saber que este tipo de programas solo pueden ejecutarse como root. Yo, por las pruebas que pude hacer, creo que los sistemas operativos actuales no son tontos y este tipo de ataques ya son conocidos. No pude capturar con Wireshark ninguno que fuese respuesta a broadcast, mientras que si la IP, aun siendo falsa, parecía real, sí que podía capturarla.