Introduction to

CAMBRIA: Two-Dimensional Cellular Automaton Tool

for Self-Organization Research

version 1.2

Tomoaki Suzudo


Quick Start

Welcome to the Cambria. This program was written for pursuing the study of self-organization. The Cambria is not only a tool to execute some preset cellular automata, but also a programable environment to create your own cellular automata. With this tool, you can browse the world of self-organization and even can start your own research project.

If you are a new user, try the Launcher program. (Sorry, the Launcher is available only for MSWindows and MacOSX users.) To do this, double-click Launcher.bat in \[Installed directory]\Cambria\win directory for MSWindows. In MacOSX, start the Terminal and change directoty to /[Installed directory]/Cambria/macosx and type
> sh Launcher.sh
Then, you are able to launch some demonstrations of the cellular automata. If you have already tried an older version of the Cambria, please check out what's new in this release. See modification history of Cambria.

Because you have downloaded this tool, I expect you are already familiar with the basics of cellular automata. If not, please browse tutorial web sites listed in my personal site (You need Internet connection).



Contents


  1. What is Cambria?
  2. Getting Ready
  3. Input Parameters
  4. Making your own CAs
  5. Design structure
  6. Benchmark
  7. Searching for CA Rules Using GA
  8. Known problems and wishing list

What is the Cambria?

The following is an introduction of this tool. The infomation written here is important for deciding whether or not you want to use this tool.

The Cambria is a programmable environment of the 2-dimensional cellular automata (CA). The whole program is written in Java language; this means that you do not have to worry about what operating system you are using. At the moment, this software is built by using the jdk1.1.8, so you are able to run the Cambria on Java Vertial Machine (JVM)1.1 or later. (I reccomend to use JVM 1.2 or later.) I assume that most of the operating systems are able to run JVM 1.2 (or sometimes called Java2). Please check JVM you are able to use on your machine.

The Cambria is not a Java applet but a Java application, so you may not execute the Cambria on WWW browsers.

Main functionalities are:


Getting Ready to Start the Cambria

You need Java Virtual Machine (JVM) to run the Cambria, which is included in the recent Win32 machines, and can be invoked by typing "java" (or jview) on the command window. I think Solaris and MacOSX also has JVM in their common installations. Please serach for an executable file called "java", that is the JVM you need.

If this is not the case, download JDK(Java Development Kit), such as JDK for Windows 95/98/NT/2000, Solaris and Linux and MRJ for Macintosh. Please follow the instructions in each tool kit to install. After the successful installation, you have to set up the two important paths, "path" and "classpath". The "path" is the command search path, and it must contain "bin" directory under the installed directory. The "classpath" must include the "classes" directory under the "cambria" directory. In case of MRJ for MacOS 8 or 9, you need not worry about these settings. After the setup of JVM, you are ready to execute the Cambria.

If you can choose your platform, read this paragraph. The JVM in Windows gives the best animation amongst the common operating systems. If you can choose your platform, I would recommend Windows machine. The JVM in Macintosh gives the speed comparable to that of Windows, but the animation is less smooth. If you use the Cambria in the non-graphic mode, Macintosh is a good choice as well. I do not follow all the JVMs available on Linux, but I experienced the Sun Microsystems JVM for Linux (Java 1.2) was terribly slower than that of Windows even in the same machine. Unless you know a fast JVM of Linux, you should give up this choice.

After expanding the compressed file you downloaded, you will find Cambria directory, and in this directory are five subdirectorties. The contents of each subdirectory are First of all, I would reccommend you to run the benchmark test, called Life300., then you can ensure that your installation is suceccfull. Needless to say, this is also useful to check the performance of your JVM. In Windows, to do this, start the command window and move to the current directory to win directory, and type
     > Life300
In case of MacOSX, start the Terminal and move to the current directory to macosx directory and type
     > sh Life300.sh
For the platforms other than these two, no script is available, but it is still possible to run Life300 by chatacterizing the Cambria. Read the Benchmark.

The simplest way of starting the Cambria is: to edit Cambria.init located at the same directory as Cambria.class exists, this file contains the input parameters to chatacterize the Cambria; and to type
     >cd [Cambria installed directory]/classes
>java Cambria ("jview Cambria" for some Windows machines)
Use "\" as a directory separator in Windows. In MacOS 8 or 9, drag the Cambria.class onto JBindery, then set the classpath and run.

On starting, the Cambria reads Cambria.init. So remember to edit this file using an common editor in advance. The information on how to prepare "Cambria.init" is also written in the file "Cambria.init". See also below for the meaning of the input parameters.

At the command line, you can add or override input parameters on top of the parameters defined in Cambria.init such as
     >java Cambria ruleClass="AquaRule" cellSize=2
In this case, the Aquarium rule is selected as a rule with the unit cell size of 2x2 pixels.

Input Parameters

This section explains meaning of each input parameter of Cambria. If you do not know how to hand over these parameters the application, read the previous section 'Getting Ready'. The followings are the parameters for the rule search using genetic algorithm.


Making Your Own CAs

As you see in the following, there are three ways to make your own CAs.
  1. von Neumann neighborhood rule description
    If the rule class of "VNRule" is selected, you must describe the Rule String which set the detail of von Neumann rule. The examples are seen in ./classes/ directory. The Rule String is composed of 'Rule Header' which is the first line and 'Rule Content, the remaining. Each line is completed by a semicolon. Any sentences of Rule Content starting by "%" and completed by ";" do not effect the execution, i.e., they become comment. Mind that comment lines also need to end with ";", which is a little different from common programming practice. I chose this grammar as you can transfer rules between different platforms.
    1. Rule Header
      In the Rule Header only the state-per-cell shall be written such as
        3;
      The state-per-cell must be an integer value between 2 and 256. Remember that the more state-per-cell you use, more memory space you need and the slower the execution becomes.
    2. Rule Content
      To write Rule Content, follow this numerical format
      <home state> <north state> <east state> <south state> <west state> <next state>;
      and
      <home state> rot <north state> <east state> <south state> <west state> <next state>;
      is an extension of the numerical format to three other rotationaly symmetric entries.

      Some "macro" descriptions are available as shown below. Remind that these macros are merely temporal and likely to be changed in the future.
      • <home state> any <next state>;
        Always outputs <next state>.
      • <home state> etotal <sum1> <sum2> <next state>;
        If the total of 1-value cell is <sum1>, that of 2-value cell is <sum2>, then outputs <next state>. If <next state> is described such as arb_0_1, outputs arbitrary number out of 0 and 1. The selected number does not change between the applied entries.
      • home <home state>;
        Define the current <home state>. Under this definition, <home state> of each command can be omitted. Note that each command's <home state> has more priority. To undo this definition set <home state> at -.
      • <home state> mixAll <state1>;
        If all the defined states are included in the outer neighbors, then outputs <state1>.
      • <home state> mix2 <state1> <state2> <state3>;
        If each outer neighbor is either <state1> or <state2>, then outputs <state3>.
      • <home state> mix3 <state1> <state2> <state3> <state4>;
        If each outer neighbor is <state1>, <state2> or <state3>, then outputs <state4>.
      • <home state> noOuter <state1> <state2>;
        None of the outer neighbors is <state1>, outputs <state2>.
      • <state> offset <value>;
        <state> is recognized as <state>+<value>. When this command is used, no other "macro" command can be used.
      • <home state> outerTot <sum> <next state>;
        If the total of the outer neighbors is <sum> <, outputs <next state>.
      • <home state> oneOuter< state1> <state2>;
        At least one outer neighbor is <state1>, outputs <state2>.
      • <home state> randomize;
        randomize the outputs.,
      Note1:When any two rule descriptions interfere each other, one described later overrides one described before. For instance, consider you write the rule such as
        2;
        0 0 0 0 0 1;
        ...........
        0 0 0 0 0 0;
      In this case, the output of this entry is set at 0.
      Note2: On-line editing of Rule Content is possible by clicking the "rule" button in the Option window.


  2. Programming of block-rules

    Block-rule is an extension of common cellular automaton, and its local rule is defined as all the cells inside a neighborhood can be updated simultaneously. The ruleClass satisfying this implements PartitionIF, e.g. BlockVNRule, Block4Rule, and Block9Rule The rule program is given to Cambria through the parameter of ruleFile whose filename must ends with ".par". This file is supposed to contain the detailed rule description. I put some examples in this directory. Among these example are:
    1. acrystal25.par making a checkerboard pattern.
    2. piller01.par making a piller.

    The rule string is a sequence of `rule words' devided by a blank such as:
    When you actually write a rule, do not write the parentheses '(' and ')'. Also do not include any blank within a word, otherwise the part after the blank will be recongnized as another word. The "states per cell" and "total number of neighbors" are given by an integer. The "state per cell" assumes an integer between 0 and 9 including 0 and 9. The total number of neighbor" is 4 (2x2 cells), 5(cross shape) or 9 (3x3 cells); They are called Margolus, von Neumann and Moore neighborhoods, respectively. The simplest form to describe the "transition rule" is: where each neighbor state is described by an entry code which is explained below. In the case of Moargolus neighborhood, the entry code is given by the letter 'c' following four consecutive digits such as (Northwest state)(Northeast state)(Southwest state)(Southeast state). For example, if only the Northwest state is 1 and the remainings are 0, its entry code is `c1000'. Similarly, the entry code of Moore neighborhood is given by 'c(Northwest)(North)(Northeast)(West)(Home)(East)(Southwest)(South)(Southeast)'. The entry code of von Nuemann neighborhood is a bit different and given by 'c(Home)(North)(East)(South)(West)'.

    I often use Rotationally symmetric rules. For this purpose, some special function is prepared. The transition staring with 'r:' is equivalent to four rotationally symmetric transitions. For instance, r:c0123:c0123 is equivalent to c0123l:c0123, c1302:c1302, c3210:c3210 and c2031:c2031.

    Anther convenient macros are totalistic rule. The `old neighbor state' can be described such as `t310' which means the neighbor is composed of three `zero' cells, a `one' cell and no `two' cell. You are not able to apply this to `new neighbor state'.

    Each transition can become a comment by starting with '!". The transitions starting with the letter '%' is also comment.

    Stochastic APCA rules (version 1.0 only)

    For APCA (and only for APCA at the moment) some stochastic rules are available. To use this functionality, set the parameter ruleClass to be "StochasticPartitionRule" instead of "PartitionRule". Insert a `word' to define the probability such as `tp=0.1' before each transition rule. The key word 'tp' stands for transition probability. With this insertion, the transition rule is applied in the probability of 0.1. In the `rule string', the word for probability is effective until a new definition is inserted. For example,
      (state per cell) (total number of neighbors) (TransitionRule_1) (tp=0.1) (TransitionRule_2) (TransitionRule_3) (tp=0.2) (TransitionRule_4)
    means the probabilities of TransitionRule_1 through TransitionRule_4 are 1.0, 0.1, 0.1 and 0.2, respectively. Note that the default probability is 1.0. You can also write such as
      tp=$mobility
    The value of $mobility is given during the execution.


  3. More general rule description by Java
    In this method, you directly write a Java-class file for the rule you want to make. Look at a sample program of Game of Life which is a notorious cellular automata. Please analyze this Java file and modify as you want. You will find it easy, if you are a skilled at Java programming

    You have to compile the Java file by using Java compiler (javac). The name of the file must end with "Rule.java", then include the compiled class file into ./Classes directly.
         > cd ./Cambria/classes
         > javac -d . [java file you made]
    

    When launching the Cambria program, choose the class file you made in "Cambria.init".

    As you can see in LifeRule.java, Rule classes are loaded by default constructor. Unfortunately dynamic class loading in JDK1.1 is only done by default constructor, so it is not possible to pass arguments to Rule classes. If you would like to describe the rule dynamically, override "setupOption()" and "setRule(String)" methods which are executed right after the Rule classes' loading.
If you made some interesting rules for the Cambria, please email to me.


Design Structure of Cambria (for folks who want to hack Cambria)

There are several viewpoints to hack Cambria as seen in the following. Note that italic words denote java class name.

Root: The root class of Cambria is Cambria. This means Cambria includes 'main()' method.

Rule: A most important class is CARule. This is a template of the definition of the updating rule of cells. Each rule must be defined in a class extending CARule. I named all the rule classes as ending with 'Rule'. According to the input parameter, one rule class is loaded after Cambria starts. This design is quite useful for extending the program by adding any new rules. In the case of the partition type neighborhood, such rule class must also implement PartitionIF interface.

Thread: For the grapgical CA execution, a thread different from 'main' thread is created and used. We call this here 'Thread'. Note that the thread is not necessary for the Batch mode. The abstract class for 'Thread' is CARunner and implements Runnable interface.

Config: A cellular auotmaton states are preserved by CAConfig class.
Panel: A graphical representation of cellular automaton is given by CAPanel class. See Fig. 1
Localization: An essential feature of cellular automata is that their dynamics are developed only by pre-defined local interactions, and every single event occurs inside a block of cells, usually called "neighbor". To be flexible, actually, it is necessary to define many types of neighbors. In the actual programming, I defined an interface called "BlockOfCells", which all the classes created for neighbors implement.

Fig. 1
Fig. 1 Class diagram of Cambria

You can modify the Cambria as you like, but I would appreciate if you give me the information on what you have done. The non-graphic verision of Cambria does not use CAPanel, CARunner, CAGraphic and all the dialog classes. Cambria is not an applet.

Benchmark

The elasped time of a batch job can be measured. The batch job update 300x300 cell space 300 times by the Life rule. For this reason, this benchmark is specially called Like300. To run Life300, type
prompt> java Cambria ruleClass=LifeRule userMode=Batch batchNumber=1 x_max=300 y_max=300
After a while, you will see the result in which the performance of your machine is compared to others. Note that this benchmark excludes any graphic operations, thus this is purely numerical. I, personally, do not care how fast graphic operations can be executed.

A shell script to run Life300 is available for MacOSX. Change the directory to the top directory, typically "/usr/[your username]/Cambria" and type this.
prompt> sh Life300.sh
For MSWindows user, Life300.bat to run Life300 is available.


Searching for CA Rules Using GA

This is the functionality of automatically searching, using genetic algorithm, for the rules you want. This is an inverse problem; you decide what you want a CA to do and search for the CAs that satisfy you. In fact, this research field still have many interesting topics left unexplored, especially for the 2-dimensional cellular automata. Thus, if you are looking for an interesting topic, how about considering the possibility for applying this inverse problem to something.

Because what you must do is new, and it hasn't been done anybody, you must extend the Cambria's source code by yourself, and perhaps you need my help.

At the momemt, only BlockVNRule can be applied to this study. Thus, I will concentrate on writing about how to optimize BlockVNRule in the following. However, although it is more complicated, it is possible to optimize other kinds of rules through the similar procedure.

What you need to know in advance is:
  1. Java programming, and
  2. Basics of genetic algorithm.
If you can clear these two conditions, it is not difficult to enjoy yourself in this field. The following is the explanation of how to extend the Cambria to apply the inverse problem.

The extension of the Cambria is devided into three steps as follows:
  1. The rule you want to optimize must implement Optimized interface. You naturally must override all the methods Optimized interface has.
  2. The fitness function for the genetic algorothm is defined witghin the class of CAConfig which implements FitnessLandscape. You define the fitness function by overriding the methods FitnessLandscape has in CAConfig.
  3. In Cambria.init, if you want to optimize 2-state and 5-neighborhood BlockVNRule starting from random configuration of density=0.3, choose
    	ruleClass=BlockVNRule
    	ruleFile=empty25.par
    	initType=random_0.3
    	userMode=Search
    
    	populationSize=20
    	eliteSize=10
    	mutationRate=0.005
    	crossoverRate=0.05
    	maxIter=10
    	goalOfHs=0.6
    	runNumber=???
    	
After a successful run, two new files, "careport???.txt" and "lasrRuleFile???.dat", will be created in classes directory. The formar file is a log-file for each run, and the latter one is the rule file found through the optimization. The "???" sign is a runNumber defined above. Note that runNumber is a String variable composed of 3 characters which do not have to be an interger. Figure below shows the classes related to this functionality. In this case, BlockVNRule is optimized. I know the explanation above is terribly short and unkind. Please wait for the next version of this manual and contact me for more detail before the new version is released.

GAExample.gif
Fig. 1 Note: you must synchronize an object instanciated from BlockVNRule in GA and that in CAConfig.


Known problems

Wish list


The copyright of Cambria belongs to Tomoaki Suzudo, Tokai-mura, Japan. Cambria is still under the development, and does include unknown bugs. Please use this program at your own risk. Any comments for Cambria are welcome. If you redistribute the software, please let me know by sending an email to me.

Dr. Tomoaki SUZUDO
Tokai-mura Japan
The email address can be found in my home page.



Last update on August 30 2004

Go to top