Hormiga de Langton

Comportamiento

La hormiga de Langton es un automata celular 2D inventado por Christopher Langton en 1986. Consiste en una rejilla cuadrada infinita con cuadros blancos y una hormiga que sigue estas reglas:

• En un cuadrado blanco, la hormiga gira 90º a la derecha, cambia el color a negro y avanza un cuadrado.
• En un cuadrado negro, la hormiga gira 90º a la izquierda, cambia el color a blanco y avanza un cuadrado.

En un principio, la hormiga se mueve caóticamente alrededor del origen y, tras 10,000 pasos, comienza a formar un patrón periódico cada 104 pasos.

Patrones como este se suelen denominar autopistas, y es el objetivo principal de esta página identificarlas y clasificarlas.

Extensión a varios colores

Una extensión sencilla de la hormiga de Langton consiste en permitir que los cuadrados puedan tener más de dos colores — a partir de ahora estados. Cada vez que la hormiga pasa por un cuadrado, actualiza el estado al siguiente de forma cíclica y gira a la derecha o a la izquierda dependiendo del estado anterior. Representamos estas reglas mediante una secuencia de "R"s y "L"s, donde cada letra determina si la hormiga debe girar a la derecha o izquierda en un estado concreto. Por ejemplo, la regla LLRR hará que la hormiga gire a la izquierda en los estados 0 y 1, y a la derecha en los estados 2 y 3.

Número de regla

Otra forma de representar las reglas es mediante un número. Para convertir una cadena de "R"s y "L"s a un número, estos son los pasos a seguir:

1. Si la cadena acaba en una L, cambiar todas las letras: RRLL → LLRR.
2. Convertir la cadena a binario, cambiando L por 0 y R por 1: LLRR → 00112.
3. Invertir la cadena binaria y convertir a decimal: 00112 → 11002 → 1210.

Esta transformación garantiza que el número binario comienza con un 1 y que no haya dos reglas con el mismo número. Invertir el número hace que el bit 0 corresponda con el estado 0, el bit 1 con el 1, etc.

Acerca de este proyecto

Este es un proyecto de computación distribuído que trata de clasificar todas las autopistas que aparecen en la extensión multicolor de la hormiga de Langton. Actualmente, hemos testeado más de 370 millones de reglas y encontrado más de 43 millones de reglas que forman autopistas, agrupadas en más de 875,000 tipos de autopistas diferentes.

¿Cómo puedo contribuir?

Puedes dirigirte a la página de descargas y seguir las instrucciones para correr un simulador optimizado en Java para detectar autopistas.

Cómo funciona

El servidor asigna a cada usuario un conjunto de reglas para testear. Estas son ejecutadas secuencialmente en el cliente durante al menos 100 millones de iteraciones cada una. Cada pocos minutos, los resultados se mandan al servidor y pueden ser visualizados en la base de datos.

Clasificación de autopistas

En un principio, las autopistas sólo se clasificaban por periodo. Sin embargo, hay muchas autopistas fundamentalmente diferentes que pueden tener el mismo periodo. Es por eso que utilizamos multiples parametros para tratar de distinguirlas:

• Periodo: El número de iteraciones que tarda en repetirse un patrón.
• Tamaño (dx,dy): El desplazamiento en cada eje de la hormiga tras un periodo, con dx ≥ dy.
• Giro: El número neto de vueltas que realiza la hormiga tras un periodo. Cada giro a la derecha suma 1/4, y cada giro a la izquierda resta 1/4.

Estos parametros no son suficientes para distinguir por completo todas las autopistas, y es por eso que estamos explorando nuevos parametros para diferenciarlas. El objetivo principal es diferenciar autopistas fundamentalmente diferentes. Por ejemplo, las reglas LR y LRLR, aunque una tenga 2 estados y la otra 4, ambas siguen exactamente la misma trayectoria. He aquí algunas ideas propuestas, ordenadas de menor a mayor impacto en el rendimiento y almacenamiento. Estos parametros se presentan como complemento a los anteriormente expuestos (periodo, tamaño y giro), no por sí solos. Nótese que mientras que estos parametros pueden ayudar a reducir colisiones, no tienen por qué garantizar una clasificación perfecta.

• Número máximo de estados: El número máximo de veces que la hormiga visita un cuadrado. Muy compacto (1-2 bytes), pero no es suficiente por sí solo.
• Histograma de estados: Un histograma que representa el número de veces que la hormiga pasa por cada estado. La longitud de la lista es igual al número máximo de estados, y los valores son proporcionales al periodo. Costoso de almacenar y puede que sea capaz de clasificar las autopistas.
• Lista de giros: Una lista completa de los giros de la hormiga durante un periodo (0 izquierda y 1 derecha). Necesita 1 bit por cada paso (tamaño = periodo/8). Clasifica por completo las autopistas, pero imposible de almacenar para periodos enormes.

Próximos pasos

Estas son algunas cosas planeadas o en las que estamos trabajando:

• Implementar alguno de los parametros discutidos para distinguir autopistas.
• Enumerar mejor las reglas hexagonal, 3D and 4D para evitar trabajo duplicado.
• Sistema similar a Catagolue para correr muchas configuraciones aleatorias para una misma regla y ver que clase de autopistas puede formar.
• Cálculo del periodo 100% funcional. Actualmente, el algoritmo no funciona en el 100% de los casos y existe la posibilidad de que se salte el periodo y no termine de correr nunca. Todas las autopistas que tienen este problema son guardadas en la base de datos con ID Autopista 1.
• Paralelización en la GPU para descartar rápidamente reglas que permanecen acotadas, y sólo testear en la CPU las reglas que se escapan rápido del origen.

Enlaces

He aquí algunos recursos relacionados:

• Langton's Ant (Video): Vídeo de Aldo Cavini explicando en inglés e italiano el comportamiento de la extensión multicolor de la hormiga de Langton.
• Langton's Ant (Wikipedia): Articulo de la hormiga de Langton en la Wikipedia en inglés.
• Softology blog — hormiga 3D: Post de Softology explorando muchas autopistas en la hormiga de Langton en 3D.
• Softology blog — hormiga 45º: Post de Softology explorando una nueva variación de la hormiga de Langton que gira 45º en vez de 90º.
• brtmr blog — Langton's Ant on hexagonal grid: Post de brtmr explorando diferentes reglas y autopistas en la hormiga de Langton con rejilla hexagonal.

Otros enlaces que han inspirado este proyecto:

• Langton's Ant - Numberphile: Explicación breve del funcionamiento de la hormiga de Langton por Katie Steckles.
• Great Internet Mersenne Prime Search (GIMPS): Un proyecto de computación distribuído que trata de descubrir nuevos primos de Mersenne.
• Catagolue: Un proyecto de computación distribuído que se encarga de tabular todos los patrones que surgen en el juego de la vida de Conway a partir de configuraciones iniciales aleatorias.