Artificial Life pt1
Last Edited: Mon Mar 04 19:06:20 UTC 2024
The series
In this series of articles I'll be learning and exploring some approaches to simulating life and aspects of life with computers. Keep an eye out for future installments where I will progress in sophistication and complexity.
Elementary Cellular Automata
What are they?
Whenever we think of artificial life, Conway's game of life is one of the first things to come to mind. While this is a great starting point, it's not the simplest one out there; it's got not just 1 but 2 dimensions.
Enter Elementary Cellular Automata, or ECA's. An ECA is defined as:
- A strip of cells where
- each cell has 2 possible states and
- each cell is only cognizant of itself and its immediate neighbors and
- the next state of the cell is determined based only what it is cognizant of
For my purposes, this strip loops around (so it's more of a ring), but it's also permissible to define the cells at indices -1 and n+1 as zeros or ones or some combination. An interesting property of ECA's is that each ECA can be defined with just a single byte!
Consider: for each cell, there are only 8 possible configurations of on/off for itself and its neighbors: 111, 110, 101, 100, 011, 010, 001, 000. Because the next state can only be on or off, we only need a single byte where each bit represents the next state given a configuration (traditionally numbered from 7-0 as listed previously).
A neat implementation
The implementation of an ECA is not inherently complicated, so I went ahead and did it using relational programming.
Fundamentally, it's just a relation between the current state, the state after, and the given rule. The implementation in core.logic is also quite simple. To make the implementation easier (and faster), I made the strip only 8 cells long.
This is the core of what I want to make work:
(l/run* [?q]
(l/fresh [?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7]
(l/== ?q [?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7]) ;Set up the "output" variable
(stepo state ?q rule)))
For simplicity, I have gone ahead and understood the rule as a vector with 8 members. This is reflected in the stepo constraint:
(defn stepo [curr aftr rule]
(l/fresh [?c0 ?c1 ?c2 ?c3 ?c4 ?c5 ?c6 ?c7
?a0 ?a1 ?a2 ?a3 ?a4 ?a5 ?a6 ?a7
?r7 ?r6 ?r5 ?r4 ?r3 ?r2 ?r1 ?r0]
(l/== curr [?c0 ?c1 ?c2 ?c3 ?c4 ?c5 ?c6 ?c7])
(l/== rule [?r7 ?r6 ?r5 ?r4 ?r3 ?r2 ?r1 ?r0])
(conde-gen 0)
(conde-gen 1)
(conde-gen 2)
(conde-gen 3)
(conde-gen 4)
(conde-gen 5)
(conde-gen 6)
(conde-gen 7)
(l/== aftr [?a0 ?a1 ?a2 ?a3 ?a4 ?a5 ?a6 ?a7])))
It is a relation between the current state, the state after the rule is applied, and the rule. because it's limited to only 8 possible cells, it's easy enough to just have a logic variable for each cell in the current state and successor states. We bind the current state to the current ?c logic variables we want to work with, the rule to each rule index (corresponding to the aforementioned configurations), and the after just like the current (but with aftr and ?a).
conde-gen is a macro, much like the one in my macros article, that expands to a conde statement of the form:
(l/conde
[(l/== ?c7 1)
(l/== ?c0 1)
(l/== ?c1 1)
(l/== ?a0 ?r7)]
...)
Given how repetitive it is, I'm sure it's obvious why it was good to write a macro for this.
And that's literally it! But thanks to the power of relational programming we can do some really powerful stuff!
Using the relation
Suppose we want to just run a rule on the cells, we can do it with a very simple recursive function:
(defn dosteps [all numsteps rule]
(if (zero? numsteps)
(reverse all)
(let [curr (first all)
aftr (first (step curr rule))]
(dosteps (cons aftr all) (dec numsteps) rule))))
We can also run it backwards (i.e. find all or some possible prior states given the current state and some rule):
(l/run* [?q]
(l/fresh [?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7]
(l/== ?q [?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7]) ;define the output variable
(stepo ?q [1 1 1 1 1 1 1 1] (rulegen 229)))) ;relation
;Repl output:
([1 1 1 1 1 1 1 1]
[0 1 0 1 0 1 0 1]
[1 0 1 0 1 0 1 0]
[0 0 0 0 0 0 0 0])
Finally, the coolest benefit to writing this as a relation. Suppose we have some states and we want to figure out what rule was used for this. Well, we just, write it like that. In this example I wanted a rule that given some arbitrary random state I wanted to give, becomes all 1s, then all 0s, and oscillates between those two from there on out.
(l/run* [?q]
(l/fresh [?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7] ;Create the output vector's terms
(l/== ?q [?0 ?1 ?2 ?3 ?4 ?5 ?6 ?7]) ;Bind it to the output variable
(stepo [1 0 1 0 0 0 0 1] [1 1 1 1 1 1 1 1] ?q) ;current random state, step1, potential rule
(stepo [1 1 1 1 1 1 1 1] [0 0 0 0 0 0 0 0] ?q) ;step1, step2, potential rule
(stepo [0 0 0 0 0 0 0 0] [1 1 1 1 1 1 1 1] ?q))) ;step2, step3, potential rule
And when we run this we get ([0 1 1 1 1 1 1 1]) which is just rule 127!
Some interesting rules
110
Perhaps the most interesting of the ECA rules is rule 110. If you've spent any time in esoteric programming language circles, you will have surely come across rule 110. For me, implementing an ECA interpreter(?) was what finally made it click.