Searching for Glider Guns
I received "Game of Life Cellular Automata" as a Christmas gift, and it was a fun read. (Unfortunately there are some points at which it was poorly edited or produced.) A paper by Emmanuel Sapin, "Gliders and Glider Guns Discovery in Cellular Automata", especially provoked my interest--- particularly because I had undertaken a small-scale effort along those lines as an undergraduate.
The basic idea is to look for cellular automata rule-sets that support gliders (moving oscillators, or "spaceships") and glider guns (patterns which produce an infinite stream of gliders). Many rules are known to support gliders, but glider guns are somewhat harder to find. The known glider guns in Conway's Life are the result of careful engineering--- although there are now a cornucopia of glider guns known. Guns exist for every period 14 and higher, and true-period guns are known for many periods below 62 (and all periods greater than 62.) Rule sets which support glider guns are good candidates for computation--- it is usually feasible to find ways to make streams of gliders interact to perform logical operations, although the "memory" required for universal computation can be more challenging.
Sapin used an evolutionary algorithm to find rule sets that produced gliders and glider guns. Crucially, he decided that the population to search was the set of rules, not the set of patterns--- due to the difficulty in defining an appropriate metric for patterns. So what he selects for is not "rule sets which support gliders and glider guns" but rather "rule sets which tend to produce gliders and glider guns in random initial configurations". This is a not-insubstantial distinction: Life is a rule set which we know has an abundance of glider guns but is very unlikely to exhibit one from a random starting state.
But, I think his paper does a good job demonstrating that there is a wealth of interesting behavior in the space of CAs he studied. Complexity theorists tend to focus on complex behavior as a fine balance between chaos and order. Showing that glider- and gun-supporting CAs are not "fine-tuned" but instead rather abundant suggests that there may in fact be relatively large portions of the state space which exhibit complexity.
Unfortunately, Sapin's approach doesn't help us find glider guns for *specific* CA's. And automatic spaceship or oscillator searches have mainly been successful for low-period structures. (See David Eppstein's paper "Searching for Spaceships" for a relatively successful approach that produced novel forms.) If we had a good algorithm for finding high-period oscillators, we could use it to find glider guns--- simply by fixing a portion of the pattern to be a glider and an eater.
But, the difficulty of such a search is very challenging. The period-22 Life glider gun, for example,
is 45 cells wide and 23 tall, so the raw search space is of size 2^1035. As Sapin mentions, identifying a metric for any kind of hill-climbing search is very difficult. For example, rewarding a pattern for producing identical cells 22 generations later may lead to local optima that are just a collection of short-period oscillators and still lifes. Rewarding the production of a glider in the correct place at time 22 is likely to tend toward patterns that just contain a chain of gliders or other pre-glider forms that don't truly oscillate. And, the large state space means that any feasible collection of starting points for the search are likely quite far from *any* solution, so it may be very difficult to make progress.
Good low-period search algorithms take advantage of knowledge of Life rules by ensuring that each row (or group of rows separated by time) can only be put together in a particular way. (If a cell is 1 in generation N+1, then its neighbors can only be a restricted set of possibilities in generation N.) But for long-period searches this too quickly becomes unmanageable. You could imagine the elements of the oscillator as a set of overlapping "cones" composed of each final 1x1 cell, its parent 3x3 square, the previous 5x5 square, etc. (Expanding at the "speed of light" backwards in time.) If you could quickly identify, for each NxN square, what NxN squares may overlap, then you could efficiently search. But for period 22 we are talking about a 45x45 square, worse than the original search space!
So, I had been thinking of playing around a bit in this area, but I think I have just about talked myself out of all the approaches I've come up with. Simulated annealing or even GA seems far too unlikely to converge on good candidates without some clever ideas about how to define fitness/goodness.
The thing that has occurred to me recently is that we might be able to build a two-phase process. Use a randomized search to build cones which "fit" well with the existing population. Then from this set of building blocks, perform conventional search to see if the results can be assembled into a long-period oscillator. This could then inform the first phase about what sort of building blocks were more highly desired.
(Note that you don't need to make the cone have a 1x1 tip, either. It could have a 3x3 tip, which makes the bigger end 47x47 instead, but you need fewer cones to create the same-sized pattern.)
The basic idea is to look for cellular automata rule-sets that support gliders (moving oscillators, or "spaceships") and glider guns (patterns which produce an infinite stream of gliders). Many rules are known to support gliders, but glider guns are somewhat harder to find. The known glider guns in Conway's Life are the result of careful engineering--- although there are now a cornucopia of glider guns known. Guns exist for every period 14 and higher, and true-period guns are known for many periods below 62 (and all periods greater than 62.) Rule sets which support glider guns are good candidates for computation--- it is usually feasible to find ways to make streams of gliders interact to perform logical operations, although the "memory" required for universal computation can be more challenging.
Sapin used an evolutionary algorithm to find rule sets that produced gliders and glider guns. Crucially, he decided that the population to search was the set of rules, not the set of patterns--- due to the difficulty in defining an appropriate metric for patterns. So what he selects for is not "rule sets which support gliders and glider guns" but rather "rule sets which tend to produce gliders and glider guns in random initial configurations". This is a not-insubstantial distinction: Life is a rule set which we know has an abundance of glider guns but is very unlikely to exhibit one from a random starting state.
But, I think his paper does a good job demonstrating that there is a wealth of interesting behavior in the space of CAs he studied. Complexity theorists tend to focus on complex behavior as a fine balance between chaos and order. Showing that glider- and gun-supporting CAs are not "fine-tuned" but instead rather abundant suggests that there may in fact be relatively large portions of the state space which exhibit complexity.
Unfortunately, Sapin's approach doesn't help us find glider guns for *specific* CA's. And automatic spaceship or oscillator searches have mainly been successful for low-period structures. (See David Eppstein's paper "Searching for Spaceships" for a relatively successful approach that produced novel forms.) If we had a good algorithm for finding high-period oscillators, we could use it to find glider guns--- simply by fixing a portion of the pattern to be a glider and an eater.
But, the difficulty of such a search is very challenging. The period-22 Life glider gun, for example,
is 45 cells wide and 23 tall, so the raw search space is of size 2^1035. As Sapin mentions, identifying a metric for any kind of hill-climbing search is very difficult. For example, rewarding a pattern for producing identical cells 22 generations later may lead to local optima that are just a collection of short-period oscillators and still lifes. Rewarding the production of a glider in the correct place at time 22 is likely to tend toward patterns that just contain a chain of gliders or other pre-glider forms that don't truly oscillate. And, the large state space means that any feasible collection of starting points for the search are likely quite far from *any* solution, so it may be very difficult to make progress.
Good low-period search algorithms take advantage of knowledge of Life rules by ensuring that each row (or group of rows separated by time) can only be put together in a particular way. (If a cell is 1 in generation N+1, then its neighbors can only be a restricted set of possibilities in generation N.) But for long-period searches this too quickly becomes unmanageable. You could imagine the elements of the oscillator as a set of overlapping "cones" composed of each final 1x1 cell, its parent 3x3 square, the previous 5x5 square, etc. (Expanding at the "speed of light" backwards in time.) If you could quickly identify, for each NxN square, what NxN squares may overlap, then you could efficiently search. But for period 22 we are talking about a 45x45 square, worse than the original search space!
So, I had been thinking of playing around a bit in this area, but I think I have just about talked myself out of all the approaches I've come up with. Simulated annealing or even GA seems far too unlikely to converge on good candidates without some clever ideas about how to define fitness/goodness.
The thing that has occurred to me recently is that we might be able to build a two-phase process. Use a randomized search to build cones which "fit" well with the existing population. Then from this set of building blocks, perform conventional search to see if the results can be assembled into a long-period oscillator. This could then inform the first phase about what sort of building blocks were more highly desired.
(Note that you don't need to make the cone have a 1x1 tip, either. It could have a 3x3 tip, which makes the bigger end 47x47 instead, but you need fewer cones to create the same-sized pattern.)