CSCI 150: PreLab 7 Answer Key

In this optional prelab (you do not have to turn this in, it is just an additional resource), we will formulate some of the ideas necessary to complete Lab 7.

The Game of Life

The Game of Life, created by mathematician John Conway, is what is referred to as a cellular automaton. It is a set of rules rules which are used to generate patterns that evolve over time. Despite the name, the Game of Life is not a game; it is really a simulation. In some ways, it can be thought of as an extremely simplified biological simulator which produces unexpectedly complex behavior.

The Game of Life is played on an infinite board made up of square cells. It takes way too long to draw an infinite board, so we'll make do with a small finite piece. Each cell can be either live or empty. We'll indicate a live cell as a red square, and a empty cell as a white one. The board begins in some initial configuration, which just mean a setting of each cell to be either live or empty (generally we'll start mostly empty cells, and only a few live cells).

The board is repeatedly updated according to a set of rules, thereby generating a new configuration based on the previous configuration. Some empty cells will become live, some live cells will disappear, and some cells will be unchanged. This configuration is then updated according to those same rules, producing yet another configuration. This continues in a series of rounds indefinitely (or until you get bored of running your simulation).

Rules of Life

The rules are pretty simple: to figure out whether a cell (x,y) will be live or empty in the following round, you just look at the 8 neighbors of that cell (those that share a corner or an edge, so N, S, W, E, NW, NE, SW and SE). What happens to (x,y) next round depends on the number of its neighbors who are live and whether it is currently live or not. In particular:

• If a cell has 4 or more live neighbors, it disappears (overcrowding).
• If a cell has 0 or 1 live neighbors, it disappears (loneliness... *sniff*).
• If a cell has exactly 2 live neighbors, nothing changes (if it was live, it stays live, if it was empty, it stays empty).
• If a cell has exactly 3 live neighbors, it comes to life (I don't have a good explanation for this one, but it does seem to make for cool patterns).

For example, consider the following 3 initial configurations, and the two configurations that follow each.

In the first example, both live cells have only one live neighbor, so they both disappear. Any empty cell has at most two live neighbors, so no new live cells spawn. Thus in one step, there are no live cells. Clearly, at this point, the configuration is stable.

In the second example, two live cells have only one neighbor, so both disappear. But the third cell lives, and the cell to its immediate left has exactly 3 live neighbors, so it spawns. On the next iteration, we find ourselves in a case similar to the previous example, and all cells disappear.

Note that we can't set a cell to be live or empty the instant we determine its status for the subsequent round; we will likely need to know whether it is alive or empty on this round to determine the future status of other nearby cells. To see this, consider the second example. We can immediately tell that the top-most live cell will disappear. But had we set it to empty immediately, then when we got to the second live cell, it would have only had 1 live neighbor and we would have (erroneously) determined that it too must disappear. Thus it is critical that we first determine for every cell whether or not it will be live, and only after doing so update the status of each.

In the last example, all currently living cells disappear; the middle cell has too many neighbors, and the other have too few. However, four empty cells have exactly 3 live neighbors, and so those cells spawn. In the following round, there are neither cells that disappear nor cells that spawn, so we have a stable configuration. In general, a pattern that doesn't change is called a still-life.

While all of these patterns stabilized quickly, some patterns take a long time to stabilize, and some never do. Of those that never stabilize, some at least have a regularity to them; they eventually eventually repeat states. These are said to be oscillators. Others never repeat the same state again, and produce an infinite number of configurations.

Describe the Problem:

In this lab, you will create a visual simulation of the game of life for a number of preset starting conditions.

Understand the problem:

Consider the following four intial configurations. Initial configurations A, B, C and D. For each of these, you should specify the next four generations of each. You can either draw pictures, or type solutions. If you do the latter, I suggest you use a fixed width-font (like courier) and use a period (.) for a empty cell, and an X for a live cell. For example, the initial configurations would look like: ..... ..... ..... .X... ..... .XXX. .XX.. ..X.. .XXX. XXX.. .XX.. XXX.. ..... ..... ..... ..... ..... ..... ..... .....

.....   .....   .....   .....
.....   ..X..   .....   ..X..
.XXX.   ..X..   .XXX.   ..X..
.....   ..X..   .....   ..X..
.....   .....   .....   .....
                        

..X..   .....   ..X..   .....
X..X.   .XXX.   X..X.   .XXX.
X..X.   XXX..   X..X.   XXX..
.X...   .....   .X...   .....
.....   .....   .....   .....
                        

.....   .....   .....   .....
.XX..   .XX..   .XX..   .XX..
.XX..   .XX..   .XX..   .XX..
.....   .....   .....   .....
.....   .....   .....   .....
                        

.....   .....   .....   .....
X.X..   ..X..   .X...   ..X..
.XX..   X.X..   ..XX.   ...X.
.X...   .XX..   .XX..   .XXX.
.....   .....   .....   .....
                        

Honor Code

If you followed the Honor Code in this assignment, write the following sentence attesting to the fact at the top of your homework.

I affirm that I have adhered to the Honor Code in this assignment.