~rlr/Courses/ICPSR-01/Handouts/intro-xlife.txt ---------------------------------------------- Introduction ------------ Conway's Game of Life (GoL) is an example of a 2-dimensional Cellular Automata. (Its not a "game" in the usual sense.) Cellular automata (CA) are discrete dynamical systems. A 2D CA is a lattice of cells, extending infinitely in both directions. In the simplest 2D CA's, each cell is in one of two states, On or Off (Live or Dead, 1 or 0). (More generally, each cell could be in any of a finite number of discrete states.) Thus the system is discrete in space and state. Time also advances discretely. Each time step T, each cell calculates what its state at time T+1 will be, based on the states of its neighbors at time T. Thus the cells change their state *synchronously*, as if all change in the same instant. Also note that all cells use the same rule to update their state. There are many possible update rules. Conway's GoL uses a neighborhood of the 8 cells surrounding each cell. The update rules for GoL can be stated as follows: - A Dead cell with exactly 3 Live neighbors becomes Live next step (birth). - A live cell with exactly 2 or 3 Live neighbors stays alive (survival). - All other cells die or remain dead (loneliness or overcrowding). That's it! Thus given a starting state for the CA (a pattern of cells Live and Dead), the entire future of the CA dynamics is determined, and can easily be calculated, using the above rules. However, trying to predict what even the simplest starting patterns will do is extremely difficult. In general, it is impossible to "predict" what the system will do, without just running it! The best way to a appreciate this is to actually run the GoL, as described below. The above mentioned unpredictability follows from this fact: the CoL is computationally complete, i.e., given any computer program and input stream, written in any language, it is possible to create an input pattern in the GoL which will behave exactly the same as the original computer/input!! Think about that...think some more...! The implications are very deep, for all of mathematics, computation, modeling, etc. Note their are many possible "neighborhoods" one could use. And there are many other rules. For example, birth could occur when there are 2 or 3 Live neighbors. Some of the software described below, as well as the websites mentioned below, provide easy ways to change the rules, to see the effects. (How many rules are there for an 8-neighborhood?) --------------------------------------------------------------------- Running the GoL --------------- On the CSCS computers, one program which you can use to run the GoL is "xlife". It can be run as follows: First, enter this once per session: export LIFEPATH=/appl/xlife5.0 Then enter this to run xlife: /appl/xlife5.0/xlife & A window should pop up. With your mouse in that window, you can get a summary of the commands by pressing the ? key. You can find a full description of these commands at www.pscs.umich.edu/education/summerSchool-ICPSR-01/Handouts/xlife-man.txt The most useful commands (most are single characters or mouse button presses) are: MB1 draw (i.e., toggle dead <-> live state) g Start/Stop running f m s speed = fast medium slow o do one step = - zoom in / zoom out . center on cursor C clear all (set it to dead) l load a pattern from a file. You can get a list of files by entering this command in your command (xterm) window: ls /appl/xlife5.0/life after you type l (el character) in the xlife window, you will note a prompt at the bottom of that window for the name of a file...enter any of the ones listed with the above command (you don't need the directory path, just the file name, e.g., glider.l ). Q quit One way to start is to zoom in so you can easily click on individual cells. Then try a couple of basic patterns (one of these at a time): x x x x x x x x x x x x x x x x x x x x x x x x x Take the end point from the right-most, and make it into 4 + patterns. First step thru one step at a time for a bit (o), then press s to slow G to go G to stop Then clear with C, then use the mouse to load another. Then perhaps just use MB1 to draw some random patterns, lots of them, and see what they do. (You might want m medium or f fast speed). Then try to load some of the named patterns (from the files mentioned above). Then perhaps load more than one at once, modify loaded patterns with the MB1, etc. Another program you can run on the CSCS computers is xautomalab. This program makes it easy to change the birth/death rules. To run it, enter: /appl/xtoys1.7/xautomalab & A description of this program and its controls is at: www.pscs.umich.edu/education/summerSchool-ICPSR-01/Handouts/xautomalab.txt This program starts running immediately, with a rule birth: 2 5 or 6 neighbors on death: 4 or 5 neighbors on neighborhood: 6 of the 8 (see the display) Note the edges cells are all forces "Live" so it continues to pump activity into the cellular automata. When you are tired of a run, press pause, change rules, change boundry conditions, etc, and see what happens. Note that zoom in/out is done with the cell size (1,2,4,8). The tracer shows cells current state (live dead), and state one back (was live, now dead, etc) with different colors. See the writeup for details. Note there are many thousands of rule/neighborhood combintations you can try!! Can you set it so that you get Conway's Game of Life? You can test it by entering familiar patterns, e.g., the glider. Imagine trying to search these for combinations that lead to "interesting" behavior (called "at the edge of chaos" in some of the readings Scott will cover later in the lectures). ------------------------------------------------------------------------ How are CA's used? ------------------ Besides being fun screen savers, CA's are used as models of dynamical processes in many fields. CA's are also used as abstract models to explore properties of "complex systems" in general. In the social and biological sciences, CA's are often used for models of systems that involve agents in some kind of 2D space. For example, there are many CA models used for Urban planning and ecological models. A web search on the terms Cellular Automata, Social, Model (or similar terms) will bring up many interesting pages and references to papers an books. A few of note include: Cellular automata in the social sciences: perspectives, restrictions and artefacts. Hegselmann, R. (1996) In Modelling and simulation in the social sciences. R. Hegselmann, U. Mueller and K. G. Troitzsch (eds.) Computer modeling of social processes. Wim B.G. Liebrand, Andezej Nowak, and Rainer Hegselmann (eds). Thousand Oaks, Calif. : SAGE, 1998. Dynamical systems in social psychology. Robin R. Vallacher, Andrzej Nowak (eds). San Diego : Academic Press, c1994. Cellular automata and consumer behaviour Jean-François Rouhaud European Journal of Economic and Social Systems 14(1) pp37-52 (2000). --------------------------------------------------------------------- Here are some websites that have more information about the Game of Life (GoL), and about Cellular Automata in general. Some have java applets that can be run online, both to run the GoL itself with various starting pattersn, and to run other 2D cellular automata rules of your own choice. http://www.bitstorm.org/gameoflife/ This has a nice java demo http://hensel.lifepatterns.net/ lots of pointers to more info nice online demo, with adjustable rules pointers to free GoL versions for lots of computers http://www.math.com/students/wonders/life/life.html a detailed description of CAs in general, and GoL a nice demo ----------------------------------------------------------------------------- Note that one way GoL type rules are described is as follows: Rules are named by the list of neighbor counts required for a dead cell to become live (Birth), followed by the list of neighbor counts required for a live cell to remain alive (Survival). Conway's Life, for example is: B3/S23 For a list of known spaceships in any rule, look in David Eppstein's Glider Database: http://fano.ics.uci.edu/ca/rules/ You can look in a database of known movers, for a given rule, on that page! ----------------------------------------------------------------------------------