Conway’s Game of Life

A celebrated Conway Life pattern, the "Gosper Glider"

Years ago, I read a piece in The Atlantic about something demographer Thomas Schelling had figured out:  

In the 1960s he grew interested in segregated neighborhoods. It was easy in America, he noticed, to find neighborhoods that were mostly or entirely black or white, and correspondingly difficult to find neighborhoods where neither race made up more than, say, three fourths of the total. “The distribution,” he wrote in 1971, “is so U-shaped that it is virtually a choice of two extremes.” That might, of course, have been a result of widespread racism, but Schelling suspected otherwise. “I had an intuition,” he told me, “that you could get a lot more segregation than would be expected if you put people together and just let them interact.”

One day in the late 1960s, on a flight from Chicago to Boston, he found himself with nothing to read and began doodling with pencil and paper. He drew a straight line and then “populated” it with Xs and Os. Then he decreed that each X and O wanted at least two of its six nearest neighbors to be of its own kind, and he began moving them around in ways that would make more of them content with their neighborhood. “It was slow going,” he told me, “but by the time I got off the plane in Boston, I knew the results were interesting.” When he got home, he and his eldest son, a coin collector, set out copper and zinc pennies (the latter were wartime relics) on a grid that resembled a checkerboard. “We’d look around and find a penny that wanted to move and figure out where it wanted to move to,” he said. “I kept getting results that I found quite striking.”

Programming computers to play this game, Schelling found that strong residential segregation arose even if he assumed that each member of the set would stay put with only a single neighbor of the same category.  This provided evidence, not only that Schelling might be right about residential segregation, but also that social order in general can arise in ways that do not directly reflect the intentions of any particular member of that society.  All of Schelling’s virtual people wanted to live in integrated neighborhoods, yet it was precisely the actions they took to pursue that goal that inexorably led to the creation of segregated neghborhoods. 

Schelling’s tests reminded me of Conway’s Game of Life, a cellular automaton that mathematician John Conway invented in 1970.  The procedure of Conway is very similar to Schelling’s.  An indefinite number of square cells are arranged in a square grid.  Each cell is in one of two conditions, live or dead.  Each cell is in contact with eight other cells: one directly above, one directly below, one directly to the right, one directly to the left, and one on each of the four corners.  If a cell is alive, it remains alive if and only if it is in contact with two or three other live cells.  If a cell is dead, it remains dead unless it is in contact with exactly three dead cells.    Some very simple initial patterns take a surprisingly long time to stabilize in Conway Life: for example, this fellow (which Conway called the R-pentomino, though others call it the F-pentomino) goes on generating new forms for 1103 generations, and along the way produces a number of spectacular structures:

You can easily test out patterns here; some especially famous patterns are collected here and here.

Conway’s Game of Life came back to mind a couple of weeks ago, when this xkcd strip appeared:

Someone came up with a cellular automaton that could qualify as “Strip Conway’s Game of Life”:

Various commenters tried to put humans in the role of the automated cells, and tried to devise rules based on what the people around each human are wearing that would determine which clothes the human was required to remove.  It occurred to me that a more promising approach would be to have one person start by wearing a great many articles of clothing, leaving those clothes on that were touching either two or three other articles of clothing, removing those that were touching fewer than two or more than three articles of clothing, and putting clothes on bare spots that were bordered by exactly three articles of clothing.  Eventually, somebody might get naked. 

Then yesterday, Alison Bechdel announced on her blog that she’d drawn a comic for McSweeney’s magazine.  The comic represents a modified version of Milton Bradley’s board game called The Game of Life

Bechdel's Life

In the comments on that post, I brought up Conway’s Game of Life.  So, I decided the time had come to post about it here.

Advertisements

6 Comments

  1. vthunderlad

     /  February 19, 2010

    I promise, I haven’t spent more than 10 minutes watching the lithe stripping CA to see if it gets “more naked.” Aside from that, and the general fascination of CA, I think Schelling’s conclusions are interesting but almost completely unrelated to his little CA game.

    Simulations are valuable for expanding our range of thinking, for sure, but I hesitate to call the results “evidence.” If people would act according to simple, rigid sets of rules, and were limits and possible moves in the world constrained as much as in a typical CA example, then mathematicians and logic buffs (and Schelling) would be the first people to consult on all social matters.

    The points raised about unexpected, emergent outcomes based on simple choices are likely true, though pretty general. “People’s choices result in outcomes we might not expect.” OK, sure. Yet there’s huge potential for outcomes from a simulation to dazzle way beyond their real relevance. Same goes for statistics, often.

    Flipping coins (or an arbitrarily more complex computer simulation of human motives) is interesting, but I’d also like to select a lot of humans and let them interact within a simulation.

    This all reminds me of a book I enjoyed: DEVIL’S NIGHT (Zev Chafets), about the race- and class-based evacuation of Detroit since the 1960s. Sad and gripping, it explains why, when I visit my father in suburban Detroit, I find myself surrounded by whites in various enclaves based on ancestry: Polish here, German there, mixed Scandinavian there.

    I also feel a sense of belligerence whenever I visit there that is very different than general Midwestern politeness–my conclusion has always been that the obnoxious white people with the means to do so must have left the inner city to found those amazingly boring suburbs. (Turns out it was more class-based a move than anything, as it turns out minority groups left inner Detroit in similar proportions.)

    Certainly I would like to consult more female mathematicians on various matters–and strip poker is a lively, promising ice breaker. Thanks for that!

  2. acilius

     /  February 19, 2010

    “I think Schelling’s conclusions are interesting but almost completely unrelated to his little CA game.” I don’t agree. What he did was to think through the logical consequences of the fact that the number of possible distributions of residents throughout the space of a neighborhood is finite. It’s in that sense that his simulations are evidence.

  3. vthunderlad

     /  February 19, 2010

    I think the lesson is that even with very constrained choices and conditions it’s hard to predict outcomes of populations. Anyone paying attention should know the real, complicated world is hard to predict. It’s not impossible to be right enough of the time to make a difference: people build up knowledge, rules of thumb, and experience. We can be very accurate based on real-world knowledge and exactly wrong based on simplified, pristine models.

    Finding that it’s hard to predict the world even in boiled-down and abstracted form is interesting and useful in that it shows the perils of simplification.

    The applicability of CA and other simplified models to real problems runs up against big challenges. Example: the faulty analysis that lead to stupid financial bets on real estate securities. In reality, investments don’t fall into a Gaussian curve of performance. In reality, the “quant” models that were so promoted over the last 10-20 years of financial deregulation spawned an enormous credit (and now debt) bubble. Yet those models came from enormously credentialed, highly schooled economists, firmly grounded in logic and “rigorous analysis.” They’d been run through computer simulations. They had firm principles, rules, and parameters to lock in wins and skip losses. They couldn’t be wrong, but they were wrong.

  4. acilius

     /  February 19, 2010

    In general I agree, but the situation Schelling was analyzing was almost as heavily constrained as was the model. Virtually every family in the samples he was looking at was defined as black or white; virtually every household consisted of one family; virtually every dwelling was classified as “neighbor” to certain other dwelling and not to any others. Society could have defined any of those variables differently, so that there would have been a larger number of possible values for it, but those were the definitions that prevailed at the time. So the number of possible distributions was far smaller than was the number of possible distribtions that QA guys run.

  5. vthunderlad

     /  February 20, 2010

    Fair enough. Curious if you’ve ever played/watched someone play “SimCity” at any point? It’s a fun and fascinating simulation whether one plays it straight – as in working toward some ideal city – or as an vengeful bureaucrat who runs up the budget and accepts every offered toxic waste plant and prison into the city center.

  6. acilius

     /  February 20, 2010

    Never played it, but I think I saw you and your old pal Terri play it at one point. Either that, or you were trying to find mathematicians to join you in a game of strip poker.

%d bloggers like this: