Langton's Ant

Behaviour

Langton's Ant is a 2D cellular automaton invented by Chris Langton in 1986. It consists on an infinite 2D square grid of white squares and an ant that follows these simple rules:

On a white square, the ant turns 90º clockwise, changes the square's color to black, and moves forward one square.
On a black square, the ant turns 90º counter-clockwise, changes the square's color to white, and moves forward one square.

Animation of the first 200 steps of Langton's Ant

Initially, the ant travels chaotically in a blob-like pattern, but after around 10,000 steps, it begins to form a predictable pattern that repeats every 104 steps.

Patterns like this are usually referred to as highways, and it is the main purpose of this project to identify and classify them.

Multicolor extension

A simple extension to Langton's Ant is to allow more colors — from now on states — in the grid. Each time the ant passes through a square, it updates the square's state to the next one in a cyclic sequence and it turns either right or left depending on the previous state. We represent these rules as a sequence of "R"s and "L"s, where each letter indicates whether the ant should turn right or left in a given state. For example, the rule LLRR makes the ant turn left in states 0 and 1, and right in states 2 and 3.

Rule number

Another way to represent rule strings is with a rule number. To convert a rule string into a rule number, follow these steps:

If the string ends in an L, swap all the letters: RRLL → LLRR.
Convert the rule string to binary by replacing L with 0 and R with 1: LLRR → 0011₂.
Reverse the binary string and convert it to decimal: 0011₂ → 1100₂ → 12₁₀.

This transformation ensures that the binary number starts with a 1 and that no two rules map to the same rule number. The reversal accounts for the fact that text is read left to right, while number values increases from right to left.

About this project

This is a distributed computing project aimed at classifying all highways found in the multicolor extension of Langton's Ant cellular automaton. So far, we have tested more than 370 million rules and found more than 43 million rules that form highways, grouped into over 875,000 distinct types.

How do I contribute?

You can go to the downloads page and follow the steps to run a highly optimized Java program to detect highways.

How it works

The server assigns each user a set of rules to be tested. These are then sequentially simulated on the client side for at least 100 million iterations each. Every few minutes, the results are sent back to the server and can be viewed in the online database.

Highway classification

In the beggining, highways where classified solely by period. However, many highways are fundamentally different even if they shaare the same period. Currently, we use three parameters to classify them:

Period: The number of iterations required for the pattern to repeat.
Size (dx,dy): The displacement of the ant along each axis after one period, with dx ≥ dy.
Winding: The net number of turns the ant makes in one period. Each right turn adds 1/4, and each left turn substracts 1/4.

These parameters are still not sufficient to uniquely identify all highways, so we are exploring additional invariants to further distinguish them. The main objective is to differentiate fundamentally distinct highways. For example, the rules LR and LRLR, although they have a different number of states, both follow the same trajectory. Here are some proposed ideas, ordered from small to large impact on performance and storage. These are intented to be used in conjunction with the previously discussed parameters (period, size and winding), not as standalone identifiers. Note that while these may help reduce collisions, they are not guaranteed to uniquely identify highways.

Maximum number of states: The maximum number of times the ant visits a cell. Very compact (1-2 bytes), but insufficient on its own.
Histogram of states: A histogram representing how many times the ant visits each different state. The array length equals the maximum state count, and values are proportional to the period. Costly to store and still maybe likely to classify highways.
List of turns: A full list of the ant's turns during one period. Requires one bit per step (i.e., size = period/8). Uniquely classifies highways, but impossible to store for large periods.

Future work

These are some things that we are planning to or currently working on:

Implementing the previously discussed parameters to distinguish highways.
Better enumerate hexagonal, 3D and 4D rules to eliminate duplicate ant behaviour.
System similar to Catagolue to run many random configurations for the same rule to see how many different highways can it form.
100% working period calculator. Right now the algorithm is slightly broken and there is a chance that the period might be skipped. All highways that have this problem are stored with Highway ID 1.
GPU parallelization to quickly discard all rules that stay bounded, and only test on the CPU the rules that grow quickly.