Franck Binard
University of Ottawa
Ottawa
Registered: Dec 2003
Posts: 17 |
[NOTE: draft]
interesting rule
Looking at CA rules properties through genetic algorithm, following [Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations, genetic algorithm discovers particle based computation in CA - Mitchell, Hraber, Crutchfield Das as well as Packard and others]. Intent is to limit the size of the space for property search to rule space. in 2D, 2^512 for 1 sized neigh.
One of the questions that one might ask oneself, is what is it that makes a cellular automata interesting as opposed to not ?
While we generally understand Conway’s game of life to be interesting as soon as we look at it, there are many slight variations on the rules that we would immediately discard as being less interesting. But might not the same rules, applied in a different environment become interesting ?
As an example, let's (again) consider the game of life. If the rules are applied to an initially empty grid, is the game still interesting ? no. Because nothing happens therefore nothing interesting happens. What if the grid has only one lit cell ? Now, something happens, but only once. then nothing. And so, we get bored and move on. Thus, it is possible to make the game of life non interesting when the meta rule "and you will be allowed to light any configuration of cells at the start of the game" is not added to the game. However, the totalistic rules that fuel the game have nothing to do with the chosen initial configuration. In that sense, the elements of the game that are external to the rules of the game, elements such as the size of the grid, the border handling and the initial configuration of the game are all part of the environment in which the rule carries out its evolution. Yet, they can still make the difference between whether the game is interesting or not.
As an example of a non-interesting ca, consider rule 119 for 1-dimensional ca (described in NKS, pg 54). As it is shown in NKS, it appears a bit boring. A single lit pixel is the initial configuration, and the evolutions that are produced by the rule with this initial configuration are regular alternating rows of lit cells and rows of unlit cells. One thing that might be noticed about the rule as it is represented in the book, is that the product of its evolution looks exactly like the product of the evolution of rule 127. Yet the two rules are different. So one might ask: "what is the difference between the two rules ? where does it reside ?".
One way to answer the question would be to try different initial configurations and to follow the evolution of the 2 rules until we do see a difference. Since we are studying the rules themselves, there is no law that dictates that we need to start with a single lit cell. If the argument for the single lit cell is based on the simplicity of the initial configuration, then one might point out that both rules would produce the same behaviour if the initial configuration was an even more simple row of all unlit cells. At any rate, since the chosen initial configuration doesn't convey any sense of the information difference between the two rules, changing it until it does would be an appropriate way to find out where and how the two rules differ.
[HAVE TO FIND INITIAL CONFIG THAT DOES CONVEY THE DIFFERENCE].
Another way to find the difference between the two rules is to try to change the working of the rows in which the cells are placed. The environment that is used throughout the NKS book for the elementary rules is a row of cells. But there is an added specification to this environment: The row is a torus. It wraparounds. When a cell reaches a border, its immediate neighbour is the border cell on the other side of the row. This is a specification that is outside the scope of the rule. There is nothing in the rules that goes and gets that opposite cell in order to use it as a neighboring cell. The implementations of the rules do that. This is part of the environment in which the rule is applied. What happens to the evolution of rule 119 when we change that specification? Let’s stay that instead of having the cells placed in rows that are wraparound, we place them in rows that are terminated by cells that always remain unlit.
[WHAT HAPPENS ? STILL HAVE TO CHECK IT OUT. SHOULD PRODUCE A CA THAT HAS THE PROPERTY OF MEASURING THE SIZE OF THE ROW FOR ONE OF THE TWO RULES, AND SOMETHING DIFFERENT FOR THE OTHER ONE. ALSO DON'T FORGET TO SIMPLIFY INITIAL CONFIGURATION TO EMPTY ROW FOR BOTH RULE 119 AND 127]
In any case, both of the methods used above to differentiate the two rules require changes in the environments in which the rules evolve. Therefore, I argue any experiments designed to study the behaviour of any rule will involve nothing more than picking a set of appropriate environments in which to apply the rules. The rules themselves are never modified.
I propose that a fitness function that would evaluate rules for ‘interestingness’, would do so by studying the evolution of a rule in different environments. The elements of the environment being:
- the size of the grid,
- the border handling and
- the initial configuration.
Unfortunatly, there are an infinity of possible environments in which a given rule can be studied. How many of these should a fitness function consider ? Our search space is already (in 2D, moore-1) 2^512 big. Each of the rules, initially picked at random (and eventually crossed with one another) is then studied in e environments. The studying itself requires the evaluation of several evolution steps. What is the optimal e? We think it depends on the rule itself.
I furthermore propose that the chosen environments that the fitness function will use to study the rules be designed specifically based on the rule itself [more on this later]. In other words, not only should the fitness function evaluate the rule for "interestingness", it should also design environments based on the composition of the rule it is studying in order to conduct its evaluation experiments.
Looking at the ways the rules are constructed, and on the effect of each of the 512 bits of the rule on the evolution, we (with Etienne Vincent from the University of Ottawa) think we might have begun to see a pattern in the design of rule specific environments.
In the game of life, the state of each cell is specified by its range 1 moore neigh. As there are 512 possible different configurations for such a neigh., one could specify 2^512 different rules, one of which is the game of life. Of course, of the 2^512, only a small subset are totalistic (including the game of life), but there is no reason to assume that totalistic cas are the only one that are interesting. in fact, there is a plethora of examples in NKS that point to the contrary.
----------------------------
Fitness Function [incomplete].
Algorithm.
Devise a set of grids that are constrained in relation to rule.
for example (2D moore-1):
Given cell and 512 bit rule:
- if bit indicating that cell should light if neigh is completely unlit (half search space), evaluate 0-bordered totally empty (in the fashion of the rule described at beginning of post)
Apply rule to each grid and grade evolution of grid according to [WHAT]
evaluation criteria
So what are the criteria that would tag a rule as being an interesting rule?
- rarity. Noteworthy scarcity is interesting. We know that because we tend to be more interested by the combinations of patterns and rules that produce something unusual or unexpected in some respect. This is however especially true when the behavior has the potential to benefit us by solving a problem. As an example consider rule __ and __ in NKS. What makes them particularly interesting is that...
- emergent computation (or the appearance of). An evolution that reminds us of something of some other process is interesting.
For example, gliders, guns and spaceship are all examples of emergent computations, and the discovery that a rule has the potential to evolve such objects adds to its interestingness.
- the difficulty of predicting futur evolutions. the shorter the repeat length is, the less interesting the rule is. This goes back to the game of life example when started with an empty grid. Since the repeat rate is 1 from the beginning, the game gets boring rather quickly. It is already more interesting with a single lit cell since the first evolution offers some variety.
----------------------------
crossover function
----------------------------
mutation function
---------------------------------------------
Working with Etienne Vincent, we eventually found a rule that didn't require any initial conditions (ie, all initial bits unlit) in order to become (or to appear) complicated. As before, the complication is created from the border handling, but the rule then does the rest.
The 512 bit rule is based on the function:
ith bit = (i mod 3 == 2) OR (i mod 7 == 0)
A binary that illustrates the evolution of the rule can be opened here
i am trying to design a set of experiments that would facilitate the rating of rules by a fitness function for properties such as emergent computations independently of initial state. while evolution part of algorithm is random, the fitness function should be deterministic. Original idea was to evaluate a set of simple cell formation according to yet undecided list of criteria.
hoping this might lead to a good way to explore a rule and its properties independently of its initial state.
Franck Binard
__________________
Franck Binard
www.site.uottawa.ca/~fbinard
Last edited by Franck Binard on 02-23-2004 at 03:04 PM
Report this post to a moderator | IP: Logged
|
12-01-2003 03:45 AM
Attachment: 
