Ants and Chips

Go/Golang | Programming

Imagine a bunch of wood chips randomly distributed on a surface. Now add an ant, randomly walking around amongst the chips. Whenever it bumps into a chip, the ant picks up the chip; if it bumps into another chip, it drops the one it is carrying and keeps walking.

How will such a system evolve over time?

We can speculate: since the ant drop its loads when bumping into another chip, piles of chips should grow. But as these piles grow, it is more likely that the ant will pick up a chip from one pile and then drop it on another pile: in other words, we should not expect all chips eventually to end up on a single pile; instead, we should reach a steady state, where piles (on average) neither grow nor shrink. The problem is that it might take a while to reach the steady state!

I first became aware of this system through the book “The Computational Beauty of Nature” by Gary William Flake, quite a few years ago. At that point, waiting long enough to reach the steady state took a lot of patience, now it is a matter of seconds, for realistic system sizes.

Here are two movies for 1000 chips, distributed on a 100x100 field, with periodic boundary conditions. The simulation was carried through to 35 million steps taken by the ant.

Starting from random config Starting from five heaps

The movies differ in the initial configuration: on the left, chips are initially randomly distributed, on the right, they start out in 5 equally sized heaps. It takes a while, but eventually, both systems reach “equivalent” (or: equivalent looking) steady states.

To make the notion of “equivalence” a bit more rigorous, we can evaluate the correlation function $g(r)$: this is essentially the probability to find a chip at a distance $r$ from another. By construction, correlation functions obey: $g(0) = 1$ and $g(r \to \infty) = \rho$, where $\rho$ is the overall density of chips (for 1000 chips on a 100x100 field: $\rho = 0.1$).

Correlation function

Correlation functions typically decay exponentially: $g(r) = \exp(-x/b)$, where the correlation length $b$ is a measure for the distance over which chips are correlated — we can think of it as a measure of the “radius” of the piles.

A rough estimate for $b$ can be obtained by examining the initial decay of the correlation function near the origin: by equating it to the derivative $g^\prime(r) = -\exp(-r/b)/b \to -1/b$, we obtain a simple estimate for $b$. (This rough estimate is entirely deterministic and does not require iteration. With more effort and attention, it is of course also possible to fit a functional form of the correlation function over more data points.)

The results are shown below for the systems in the movies. It is evident that the correlation function (and that means: the typical cluster size) tend towards the same limit, regardless of initial configuration. (Notice that the correlation length grows when starting from the random configuration, indicating the growing of clusters; but for the other configuration it shrinks as the initial set up disappears).

Evolution of correlation length

More movies, for different chip densities can be found here.

Implementation

The simulation code can be found below. The program uses a goroutine to calculate the correlation function concurrently to the main simulation loop; thus leading to improved CPU utilization.

The code includes a feature to give the ant a “sense of direction”. In this case, the ant does not decide at each step which direction to choose next, but instead has a (adjustable) higher probability to continue in the direction of the last step. I would expect that this leads to the system reaching its steady state faster, but I have not experimented with this option.