15

Reading Assignment and Discussion Topics
Computer Science 111

for class on Tuesday March 28, 2000

Please read Sections 7.1 through 7.4 (pp. 291-307) of the Schneider and Gersting text, and be prepared to discuss the following:

Imagine an extremely large square grid on each of whose squares there may be exactly one or zero organisms (hereafter, "critters"). Each square has 8 "neighbors", namely, the squares above and below it, to its left and right, plus the four at the corners. This population of critters evolves, generation by generation, as follows:

• Survival. A critter survives to the next generation if it has exactly 2 or 3 neighbors.
• Death. In the next generation a critter will die from loneliness if it has 1 or fewer living neighbors, and from overcrowding if it has 4 or more. When a critter dies, its square becomes empty.
• Birth. In an empty square with exactly 3 living neighbors ("parents"?) a critter is born in the next generation.

This is The Game of Life, devised by Princeton math professor John Conway about 30 years ago. From these simple rules come extraordinarily interesting and complex behaviors, depending on the locations of the starting population of critters.

You can simulate the evolution of a small population of critters with paper and pencil. Just draw a small grid, decide on some starting arrangement of critters, write 1's or dots or something in their squares, and figure out what will happen in the next generation. When you've figured this out, change the squares appropriately, and go around again.

To prepare for this class, simulate some small patterns of critters to get a feel for how the Game works. A "pattern" need not be symmetrical; it can be any arrangement of critters on squares in any shape or non-shape whatever, and the occupied squares need not be next to each other. Find a small pattern that will die in a few generations. Find a pattern that will survive unchanged from generation to generation. Try to find a pattern that will oscillate between two different patterns.

Finally, figure out how you would structure a program to simulate the Game, and if this is easy for you, go ahead and work out the details. How would you represent the board in memory? One challenge for the program is to keep track of the planned changes for the next generation without actually making them in the current generation.