A peek at cellular automata (1)

To follow up on evolutive models, I wanted to talk about cellular automata. Broadly speaking, a cellular automaton is a discrete model that is defined by a grid of cells – each in a given state – that changes generation after generation according to one or more evolution rules.


When modeling our world, it is common practice to discretize things. Why? Because it makes things simpler and computable for our machines – you can’t really simulate an infinite number of points! We usually discretize space- and / or time-wise.

And since one picture is worth a thousand words, here is a small illustration of both discretization, and of the mix:

Space discretization
continuous-space-time
Time discretization
continuous-space-time
Space-time discretization
continuous-space-time

 

In cellular automata, we do both discretizations:

  • the cells correspond to a space discretization
  • the process of step-by-step generations evolution is a time discretization

The idea is to start from a given initial state and then have the grid evolve iteration after iteration.

Conway’s Game of Life

A famous example of cellular automaton is Conway’s Game of Life – designed by John Horton Conway in 1970. The Game of Life consists of cells that are “alive” or “dead”; then, at each step, the new state of every cell is defined by the states of its neighbors, depending on the chosen rules. These rules are:

  • the “birth rule” that determines how many alive cells have to surround a dead cell for it to be born at the next iteration
  • the “survival rule” that determines how many alive cells have to surround an alive cell for it to stay alive at the next iteration

It is common to regroup these rules into a short code of the form “Bx/Sy” to quickly indicate the specific values. So, for example, if your “birth rule” asks for 3 or 4 alive neighbors for the cell to be born and your “survival rule” asks for 2 alive neighbors for it to survive, then the code would be “B34/S2”. Conway’s original values were “B3/S23”.

Conway’s Life is a deterministic process: after setting an initial state and the rules to apply, you know exactly how the automaton will evolve at each generation. Plus, launching the process two times in the same conditions will result in the same outcome.

Since it was invented, it has been studied a lot and over the years some patterns have been found. In particular, people have identified 3 pattern types: the “still lifes” (that stay exactly the same, no matter how long you wait), the “oscillators” (that evolve with the rules but in a periodic way, so that they always go through the same steps) and the “spaceships” (little blobs that glide and fly around). It is even possible to have “guns” that produce spaceships! You can see examples of these on the Wikipedia page.

What is very interesting with Life is that is a chaotic process, i.e. a tiny change in the initial state can result in completely different outputs after only a few iterations. For example, compare these two initial states:

Left: State A  /  Right: State B

Well, for a given set of rules, after 200 iterations, these two starters evolve into completely different models:

Left: State A  /  Right: State B

 

It has been shown that Life is as powerful as a universal Turing machine, meaning that any algorithm can be simulated by this automaton. But this also means that the Game of Life is undecidable: when you take an initial state and a specific pattern, you have no way of asserting this patter will appear.

Plus, it’s also possible to make Life create… Life. Basically, you can have a Game of Life instance where each cell is itself a small instance of Game of Life!

A bit of code to create Life!

Here, I give some Python code to simulate the Game of Life.

[projectinfo languages=”python” team=”1″ duration=”2 days”]

If you just want to see some results, you can use it like a black box and don’t need to change anything in the code; just use the command line arguments to specify your Life’s parameters and create a new simulation – it will automatically be exported as a gif animation in the end:

  • <help> shows the program help
  • <w> is the number of cells in a row of the grid (default: 100)
  • <h> is the number of cells in a column of the grid (default: 100)
  • <birth> is the “birth rule” in the form of one or more numbers separated by the “,” character (default: 3)
  • <survive> is the “survival rule” in the form of one or more numbers separated by the “,” character (default: 2,3)
  • <f> or <figscale> is the multiplier of the grid size for the exported file (default: 3)
  • <n> or <niters> is the number of iterations to run the instance for (default: 200)
  • <s> or <steps> is the number of steps to take at each iteration (“acceleration” parameter) (default: 1)
  • <t> or <types> is the number of available types for alive cells (default: 1)
  • <i> or <init> is a type of grid initialization (see below for more details)

You can also get this list of all possible parameters by showing the program help with python main.py --help.

So, for example, to create a simulation of Life with a 200×200 grid that runs for 100 iterations but four times as fast as a “normal” instance (meaning it takes 4 steps at each iteration), you would run the following in your console:

python main.py -w 200 -h 200 -n 100 -s 4

Here is an animation I got with these parameters:

Example of Life simulation on a 200×200 grid, for 100 iterations (with 4 steps per iteration)

Of course, by default, the script randomly initializes some cells in the middle of the grid to an “alive” state… so depending on your rules and on the run, you may get a model that evolves for a lot of iterations or that dies really quickly. If you want to have a specific initialization, you can use the init parameter with one of the following values:

  • “”: this asks for a random initialization
  • “demo”: this is the default value, you will get various well-known patterns on your grid
  • “spacestation”: you will get lots of famous patterns that look a bit like space suff spread across the grid (spaceships, oscillators…)
  • a string of at most 9 zeros and ones separated by the “,” character (e.g. “0,1,1,0,1”): this specifies the “dead” and “alive” cells in the little 9×9 square at the center of the grid; if you give less than 9 values, then only the first cells of the grid will be initialized, starting in the top-left corner and going from top to bottom, from left to right (see the images below)

Left: an initialization with 9 variables: “1,0,1,1,0,0,0,1,1”  /  Right: an initialization with only 7 variables: “1,0,1,1,1,1” (the rest is set to 0)

If you dive into the code a bit more, you will see that you are provided with some functions in the patterns.py file to make special well-known patterns of Life (oscillators, spaceships, etc.). You even have a generic make_pattern() method that will redirect to the correct generation function. Take a look at the init_grid() function in the main.py file to see how they are used!

It’s also possible to have more than one type of alive cells (represented by different gray tints); for example, here is a simulation with 2 types – we can see it as two populations competing for the same piece of land and eventually growing away from each other:

Example of Life simulation with 2 types of “alive” cells

Want to learn more about the Game of Life?

There is still a lot more to tell about Life!

Besides changing the birth and survival rules, you can also have other variants: some systems take hexagonal cells instead of square ones, some go from 2D to 3D, the discretized space can be periodic (meaning the cells that “go out of bounds” on the right can reappear on the left), you can consider more states than just the two “dead” or “alive”…

Life has even been used to create music by generating MIDI patterns!

Anyway, if you want to see a great video about the Game of Life (in French), I suggest you look at Science Etonnante’s, or if you prefer you can read the article that goes with it (David Louapre is truly one of the best French popularizer of science I know!).

References
    1. I. Wikimedia Foundation, “Cellular automaton” (https://en.wikipedia.org/wiki/Cellular_automaton), August 2018. [Online; last access 23-September-2018].
    2. I. Wikimedia Foundation, “Conway’s Game of Life” (https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life), September 2018. [Online; last access 23-September-2018].
    3. I. Wikimedia Foundation, “Chaos theory” (https://en.wikipedia.org/wiki/Chaos_theory), September 2018. [Online; last access 23-September-2018].
    4. Science Etonnante (David Louapre)’s video on Life, in French: https://www.youtube.com/watch?v=S-W0NX97DB0
    5. Science Etonnante (David Louapre)’s article on Life, in French: https://sciencetonnante.wordpress.com/2017/12/08/le-jeu-de-la-vie/

Leave a Reply

Your email address will not be published. Required fields are marked *