A Superset of Conway's Life Game

If you're at this site you've probably heard of John Conway's Game of Life. It's a simple cellular automata that displays surprisingly complex behaviors in spite of being defined by very simple rules. In the classic game we have an infinite grid of cells that can be either on or off, either "dead" or "alive". The rules governing the evolution of the game grid are as follows, if a cell is currently on (alive) and it has 2 or 3 living neighbors, it remains alive. If has more or less it dies. If a cell is currently dead and it has exactly 3 neighbors, it comes to life. A neighbor is defined as one of the 8 cells within one grid unit of the cell. There are many variations on the game too with different rules for cell birth and death. People have even developed a notation for them. The classic one is written B3/S23, meaning a dead cell is born if and only if it has 3 neighbors and a live cell survives if it has 2 or 3. The classic game and it's derivatives though, make no distinction between neighbors. They are all considered the same and their count is all that matters.

I got to thinking about this. How could we make a Life game variant that is more flexible? What if we could take position into account? Well, we can. In fact we can take arbitrary characteristics of the cell's neighborhood into account by noticing that with 8 neighbors there are exactly 2^8 different possible configurations of live and dead neighbor cells for each cell. We can think of each neighbor as a single bit within a byte. If a neighbor is alive it's a 1. If it's dead, it's a 0. We can thus potentially turn any configuration of neighbors into a 1 byte integer. If we can do that, we could construct a pair of arrays of 256 rules each that will decide the fate of a cell given any random configuration of neighbors. There need to be 2 arrays because we may need different ways to handle cells that are currently alive as opposed to currently dead. A given "rule" in this construction can be just a single bit. If the cell's fate in the next iteration of the game is to become or remain alive, we have a 1 there. If the cell becomes or remains dead, we code that as a 0. The full ruleset for the entire game can thus be encoded in 2 x 256 bits or 2 x 32 bytes.

You may have noticed that this construction of the game can actually be used (with a bit of combinatorial mathematics) to encode not only Conway's original game but all the variants as well. The trick is to realize that when you say that a cell has 3 live neighbors what you are really saying is that it has one of a certain specific set of neighborhood configurations. Specifically, it has one of the set of eight bit numbers that have 3 bits on and 5 off. We can actually tabulate all of these though and get a list of 1 byte integers. As it happens there are exactly 56 such numbers. So to represent the B3 part of the classic Conway game rules we simply turn all the corresponding bits in the dead cell rule array on and leave all the other bits off. To make the S23 part of the Conway ruleset we just tabulate all the patterns of neighbors that have either 2 or 3 bits on. This is a superset of the previous rules and contains an additional 28 "on" bits for a total of 84 on bits. We thus turn on all of these bits in the array of rules applied to the live cells.

There's one little detail I'm leaving out here which is that there are quite a number (8! or 40320 in fact) of different ways to map the 8 neighbors of a cell to the bit values in a byte. The position of a bit is all important as it determines which of the 8 possible powers of 2 it represents. So which do we pick? Well it turns out not to matter which mapping we choose as long as we remain absolutely consistent once we have picked a mapping. There are some obvious ways to choose a mapping though such as just starting from the upper left of the square of neighbors and then scanning as though reading a typical Western written language. This is what I've done. Thus, from least to most significant bit we have the neighbors at the top left, top center, top right, center left, center right, bottom left, bottom center, and bottom right respectively.