********CELLULAR AUTOMATA AND CONWAY'S GAME OF LIFE******** (Visit http://hensel.lifepatterns.net/ ) ***OVERVIEW Conway's game of life is the most well known Cellular Automaton; hence we shall describe it in detail here. The viewer can then investigate some of the other cellular automata ("CA") illustrated in this web site. Conway's game of Life was invented by John Horton Conway and was described in Scientific American's Mathematical Games column back in the early 70's. The "game" (placed in quotes because there are actually no players - the outcome is decided by the pattern initially chosen) is played on a grid of "cells" which are represented as squares). Each cell is either "alive" or "dead". The cells live or die from generation to generation depending upon whether they are already alive or not, and how many living neighbors (hereafter called simply "neighbors") they currently have. ***THE NEIGHBORHOOD RULES FOR CONWAY'S "GAME" Deaths: A live cell will die if it has either too few or too many neighbors: 0 or 1 neighbor: the cell will die. 4 or more neighbors: the cell will die. (hence, if a living cell has two or three neighbors, it will remain alive for the next generation.) Births: A cell will become alive if it has exactly 3 neighbors. ***A CONVENIENT SHORTHAND The shorthand way for writing this "rule" is 2,3/3 , meaning that a living cell remains alive next generation if it has 2 or 3 neighbors, and a non-living cell comes to life if it has exactly three neighbors. (Note: this shorthand allows us to write many rules - e.g. 1,2,4/2,4, etc. But only 2,3/3 is the "Conway life" rule, which is a subset of a large number of "Cellular Automata" rules.) ***NEIGHBORHOOD DEFINED The neighborhood will be each square that a king could move to on a chessboard. That is, a cell can have vertical, horizontal, and/or diagonal neighbors. ***A SIMPLE EXAMPLE Look at the grid below. The dots are dead cells, the O's are live cells. We start with three live cells in a central column. (Note: here our grid, or "universe" is only a five by five array, but in general, the grid can be infinite.) . . . . . . . O . . . . O . . . . O . . . . . . . Now we count the neighbors that each cell has. Here we have placed the neighbor count inside the cell position. 0 1 1 1 0 0 2 1 2 0 0 3 2 3 0 0 2 1 2 0 0 1 1 1 0 You see that the middle cell was alive and has two neighbors, so that it stays alive. The cells directly above and below the center have only one neighbor so they die. The cells to the right and left of the center (currently not alive) have three neighbors, so they become alive. There are other cells with one or two neighbors but they were not alive to start with so they stay dead. Hence, the next generation looks like this: . . . . . . . . . . . O O O . . . . . . . . . . . Note that this pattern will flip back and forth, There are many interesting patterns in the life universe - most of them have been given rather whimsical names such as "glider", "spaceship", etc. The above pattern is called a "blinker." Below is another pattern. See if you can work out what it does. . . . . . . . . . O . . . . . . . O . . . . . O O . . . . . . . . . . . . . . . . . When you understand the above explanation, visit http://hensel.lifepatterns.net/ ***OTHER GRIDS Conway's game is played on a square grid (Cartesian coordinate system). Other rules can be utilized in this grid, but these rules are not as rich as Conway's rule. Note that we do not need to confine ourselves to a grid of squares. We may, for example, use a grid of triangles, where there are several interesting game of life rules. There are also games of life on a hexagonal grid, and on a pentagonal grid. And there are several 3 dimensional rules. Links to all these variations have been provided on the CA home page. ------------------------------------------------------------------ ***ADVANCED COMPUTER TECHNIQUES FOR SPEEDING UP THE EVALUATION. Here we are confining our discussion to the cartesian universe (the universe of square cells) but the techniques can apply to any grid. To go from one generation to the next, the grid of cells must be scanned in some way (except for some exotic methods, which we shall not discuss.) The simplest (and slowest) method is to look at each cell, determine whether it is alive or not, count its live neighbors, and decide its fate for the next generation according to the rule at hand. A better method is to store within the cell its live neighbor count along with whether the cell itself is alive or dead (simple way: let the cell be an integer element in an array. We will have between zero and 8 (in the case of the square grid) live neighbors. Then, we can also add 100 if the cell is alive. Hence, a value of "105" would mean that the cell is alive and has 5 live neighbors. Now, to evaluate for the next generation, we look at the status of the cell (alive or dead) and then check its neighbor count to see if, when the indicated rule is applied, there is a change in the status of the cell. ONLY IF THERE IS A CHANGE do we need to do anything; namely update the neighbor counts for all the neighboring cells. Note that we thus scan thru a (mostly empty) array quite quickly, since most cells are dead and have no live neighbors. This method works best for sparse grids. ***OTHER RULES It is also possible to greatly speed up the evaluation of the application of the rule at hand. Consider the square grid. Suppose we are applying the rule "2,3,4/4,6" (Recall: Conway's rule would be "2,3/3") . We have two arrays - Fertility[0 . . . 8] and Environment[0 . . . 8]. For the rule "2,3,4/4,6" we would store in Fertility: 0 0 0 0 1 0 1 0 0 ("1" is stored at position 4 and 6); and in Environment: 0 0 1 1 1 0 0 0 0 Then, if we determine, for example, that a cell is alive, we use its neighbor count (first subtracting 100 - see above ) as an index into the "Environment" array. If there is a "1" at this position, the cell remains alive; otherwise it dies. A similar determination is made when the cell is dead (via the "Fertility" array). We can eliminate one more step by creating one array, A[0 . . . 108]. We store the fertility data in A[0] thru A[8] and the environment data in a[100] thru A[108]. Then we do not have to check whether the cell is alive or not - just map its value thru the array A. Here I have used "100" as the value to indicate that a cell is alive - we could just as easily have used, in the case of the square grid, ten. In that case array "A" would contain 19 values, given below for rule "2,3,4/4,6 position = 0 1 2 3 4 5 6 7 8 10 12 14 16 18 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 | fertility | | environment | | portion | | portion | | (cell is | | (cell is | | currently dead) | | currently alive)| | we check for | | we check for | | 4 or 6 | | 2, 3 or 4 | Of course, we would still have to check to see if the status of the cell changes (but there are exotic ways of avoiding this too). SIGNATURES Though not uniquE, OBtaining signatures of forms that appear on a grid provides a means of distinguishing between different shapes. Basically, a signature is a vector containing neighbor information about all cells in the grid. The signature is represented as shown below: (left part) (right part) neighbors of live cells <> neighbors of dead cells Each part gives the number of cells in the entire grid with a given count of live neighbors. To obtain the signature, we examine every cell in the grid (live or dead) and tally how many live neighbors it has. Consider the "blinker" (Conway's Life). . . . . . . . . . . . . . . . . . . . . . . . . O . . . . . . O . . . . . . O . . . . . . . . . . . . . . . . . The neighbor count for each live cell and each dead cell is given below: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 2 1 2 0 0 0 0 3 2 3 0 0 0 0 2 1 2 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 Notice that most dead cells have no live neighbors; hence this count is omitted from the right part of the signature. the signature for the "blinker" would thus be: 0 0 0 0 0 0 1 2 0 <> 6 4 2 0 0 0 0 0 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 (the numbers on the line directly above are for reference only. These numbers are indices that indicate the count.) Thus, there are two live cells with one neighbor; one live cell with two neighbors; six dead cells with one neighbor; four dead cells with two neighbors; two dead cells with three neighbors. We can omit all leading (and trailing) zeros, giving: 1 2 0 <> 6 4 2 Which is the actual way the signature would be read. An important characteristic of signatures is that a given shape has the same signature no matter how it is oriented. Of course, different phases of the same oscillator usually will have different signatures. In the case of the "blinker", the two phases are identical; hence the signature for the two phases it the same. **Note that when we add up the numbers in the left part, we get the total count of live cells.