Video Game / Conway's Game of Life

The "glider" is a pattern that moves 1 cell diagonally every 4 generations.

The Game of Life (often referred to as "Conway's Game of Life" for clarity, or just "Life" for short) is not, technically, a game (or if it is, it's a zero-player game with no objective). The title is a somewhat romantic way of referring to a specific cellular automaton invented by mathematician John Conway in 1970.

A cellular automaton is a large grid of simple "cells", each of which has a state that can change depending on how it interacts with its neighbors. In the case of the Game of Life, the rules are extremely simple:

• Each cell can be either alive (on) or dead (off).
• If a dead cell has exactly 3 neighboring cells, it becomes alive (birth).
• If a live cell has either 2 or 3 neighboring cells, it stays alive (survival).
• In all other situations, a cell dies (or remains dead).

Although these rules are trivial, the surprise of the Game of Life is that the resulting cell interactions are remarkably complex. From the chaotic interactions, stable patterns can be seen to form; tiny formations of cells that stabilise each other, oscillating formations that "blink" over and over, and perhaps most interesting of all, cell formations that can move called "spaceships", autonomously of other cells. The Game of Life could be considered a simulation of a unique "universe" with its own physical laws.

By carefully arranging cells in the Game of Life, it is even possible to build new things: "guns" which fire streams of "gliders" continuously, "reflectors" which can bounce gliders around, patterns that grow continuously, and more. Eventually, it was discovered that one can implement logical structures in the Game of Life and build a universal computer; that is, the Game of Life is Turing-complete. Conway also proved that it is possible to create a universal constructor in the Game of Life; that is, a pattern that can construct other patterns, including itself. Various attempts have been made to build such self-replicators.

Even decades later, the Game of Life has a strong hobbyist following, and new discoveries are still being made.

See this page on The Other Wiki for more information.

A website allowing you to play with Life patterns can be found here. program allowing you to play with Life and several other similar games can be found here.

Not to be confused with Milton Bradley's board game. For stories about your everyday world suddenly taking on these rules, see Life Is A Game.

---

Tropes

• Awesome, but Impractical: Many contraptions created in the Game of Life use complex and extremely wasteful techniques to perform relatively simple calculations, and the interest in them mainly comes from the fact that they successfully perform their job at all.
  • Adam P. Goucher's pi and phi calculators take billions or even trillions of generations to calculate just a few decimal digits.
  • Any universal computer, such as Paul Rendell's Turing machines. Even a regular Turing machine is an extremely inefficient way to perform calculations, and adding another layer of abstraction by emulating it in Life only makes it orders of magnitude slower.
  • In 2013, a challenge was posted on Stack Exchange to "build a working game of Tetris in Conway's Game of Life". The resulting pattern, the "Quest for Tetris Processor", was completed in 2017 thanks to the combined efforts of at least nine different Stack Exchange users. However, it uses one more layer of abstraction than is probably necessary - it uses metacells to simulate a custom-made cellular automaton called VarLife, which in turn uses its own metacells to simulate a game of Tetris.
  • Goucher's 0E0P^note 0E0P = "zero encoded (by) zero population" metacell. Unlike previous examples of unit cells, this one "dies" by completely and cleanly self-destructing. Notably, this proves that certain exotic types of patterns known to exist in other cellular automata must therefore also exist in Conway's Game of Life. However, the metacell is simultaneously orders of magnitude larger (~262,000 cells across) and takes orders of magnitude slower (over 68 billion generations just to simulate a single metageneration). To prove that it works, Goucher created a specialized algorithm called "StreamLife" which is optimized for this specific type of pattern. Even still, it took about a month running StreamLife to confirm that a single metacell would stay alive for a single metageneration.
  • The reverse caber-tosser, which Goucher was also heavily involved in creating, theoretically allows any conceivable glider synthesis to be encoded in a single glider.^note Specifically, the glider's exact distance from the rest of the mechanism contains the data that allows an arbitrary glider synthesis to be recreated. As of November 2022, this proves that no pattern takes more than 15 gliders to synthesize, unless it is completely unsynthesizable. The problem is that the reverse caber-tosser takes a prohibitively long time to simulate, as the length of time the construction takes increases exponentially as the recipe gets longer. Even synthesizing a relatively simple object requires an extremely long recipe, as all the leftover debris has to be cleaned up somehow.
• Boring, but Practical:
  • The humble block is a very simple and very common 4-cell stable pattern. Despite this simplicity, it has a lot of uses from stabilization to conduits.
  • Technology is called "spartan" if it only uses common patterns. While it is less optimized size-wise and speed-wise than non-spartan technology, it is much easier to create using glider collisions, which makes it useful for replicators, by reducing the amount of data needed to code themselves.
• Cap: The Speed of Light, known as "c" by analogy to real life, is the maximum speed at which an information of any sort can travel, whether it is a spaceship, a signal, or else. Due to the Game of Life using Moore neighbourhood, it is of 1 cell per generation, either orthogonally or diagonally. However, finite spaceships are constrained by lower limits. As such, it can be proved that their maximum orthogonal speed is c/2, their maximum diagonal speed is c/4, and their maximum knightwise speed (that is, how many generations it takes for a knightship to do a knight move) is c/6.
• Colour-Coded for Your Convenience: Some implementations of Life have multiple cell colors to convey additional information besides "on" and "off":
  • "LifeHistory", which uses dark blue to indicate the "envelope" of cells which were previously alive, and also has three additional colors to be used for annotating patterns. "LifeSuper" and "LifeUltra" are extensions of this, and each contain dozens of colors.
  • "SlowLife", in which the pattern only advances every other generation. In odd-numbered generations, cells that will be born are highlighted in green, while cells that will be killed are highlighted in red. This can help to illustrate the concept that the entire grid is supposed to be updated at the same time, rather than cells being modified as you go along.
  • "DoubleB3S23" and "TripleB3S23" are effectively multiple Life universes overlaid on top of each other, and thus require additional cell colors to indicate which universes the cell is currently alive in. This is particularly useful for showing similarities and/or differences in evolution between two different patterns.
  • "Colorized" versions of Life allow living cells to be one of a number of different colors. The most famous of these is "Immigration", where each living cell can be either red or blue and inherits its color from a majority of its initial neighbors. Other variants (such as "QuadLife" and "SpectralLife") have more cell colors and use different rules to resolve conflicts when birthing a new cell. Ignoring the colors, however, all of these function identically to the original Life.
• Cool of Rule: Despite the simplicity of the rules, extremely complex constructions are nonetheless possible and have been successfully built.
• Diagonal Speed Boost: Diagonally adjacent cells are treated the exact same as orthogonally adjacent ones. Thus the fastest possible speed that information can travel at, in terms of Euclidean distance, is specifically one cell diagonally per generation, as the distance between diagonally adjacent cells is √2 (~1.414) instead of 1.^note However, a finite spaceship cannot maintain this speed indefinitely. In fact, the speed limit for diagonal spaceships is actually slower in this regard than orthogonal spaceships - orthogonal spaceships can travel up to one cell every two generations, whereas diagonal spaceships can only travel √2 cells every four generations.
• Early-Installment Weirdness:
  • The early emphasis on "pure glider generators", which are patterns that eventually evolve into one or more gliders without producing any stationary objects. It turned out that most of these weren't particularly useful for anything, and so interest in them waned after the 1970s.^note One notable exception is a subcategory of pure glider generators known as "splitters", which consist of one glider colliding with a constellation of still lifes to produce multiple new gliders.
  • Initially, "fuses" (repeating patterns with an instability at one end that propagates along the fuse) were considered to be notable for their own sake, but were later found to be so common so as to be generally uninteresting. However, "reburnable" fuses (where the output is the same as the input, possibly offset by some amount) are still extremely useful as they can be turned into spaceships (albeit extremely large ones). The basic diagonal-line fuse (which burns at lightspeed, leaving no debris behind) is also sometimes found in glider syntheses, as it can transport a signal through a narrow area.
  • The emphasis on "polyominoes", which are (usually unstable) patterns consisting entirely of orthogonally connected cells. The first issue of the Lifeline newsletter in 1971 even began with a request for readers to work out the evolutions of four "heptominoes" (7-cell polyominoes) whose fates had not yet been determined. Since then, efforts to comprehensively track the evolutions of patterns up to a given size have generally expanded the search space to all non-trivial patterns of a given population or bounding box, rather than just polyominoes. Although many polyominoes are still extremely important (such as the 5-cell R-pentomino, and the 7-cell pi-heptomino and B-heptomino), they are only polyominoes by happenstance, and in fact many of their smallest predecessors are not polyominoes.
• Explosive Overclocking: Signal conduits and converters have a safe "recovery time" where, if the input signals are separated by at least that many generations, they will not self-destruct. Trying to "overclock" them by inputting signals faster than this runs the risk of the device exploding, depending on how exactly consecutive signals interact.
• Explosive Results: Adding or removing even a single cell from an otherwise stable pattern more often than not results in it exploding into a mess of debris.
• Extra Parent Conception: Cells are always born to exactly three parents.
• Extreme Graphical Representation:
  • Brice Due's OTCA metapixels, which can simulate any "Life-like" cellular automaton within Conway's Game of Life. Whereas previous "unit cells" required you to squint really hard to determine if they were living or dead, Due's metapixels each produce a grid of thousands of spaceships so that, when zoomed out, the viewer can easily see the resulting metapattern.
  • Similarly, Adam P. Goucher's pi and phi calculators go above and beyond merely calculating fundamental mathematical constants: they also print out the decimal digits using a matrix of blocks which can be found at the top of the pattern.
• Faster-Than-Light Travel: The Fast Forward Force Field is a subverted example. While the reaction seems to make a LWSS briefly move at 11c/6, which is faster than the Speed of Light, a closer look reveals that the apparition of the "teleported" LWSS starts regardless of the presence or not of an "about to be teleported" LWSS. Information within the reaction actually only travels at the Speed of Light to determine whether or not the "teleported" LWSS will fully form or be destroyed.
• Fusion Dance: Glider synthesis, in which gliders are collided together to produce other objects.
• Fusion Dissonance: Zig-zagged with glider synthesis. Due to the chaotic nature of the Game of Life, the end result of a glider synthesis usually bears little or no resemblance to the initial gliders. Individual steps of a glider synthesis, also known as "components", can avert this by changing only a few cells at a time. These components are often broadly applicable across many patterns featuring common motifs, and so search programs (such as Alex Greason's collisrc) have been made to search for them by randomly hitting still lifes with gliders. On rare occasions, however, collisrc will stumble upon a solution in which a complex still life is completely destroyed by gliders, and then the resulting mess later reforms into a new, entirely different still life, making this trope apply once again.
• Giant Flyer: Engineered spaceships, sometimes generically referred to as "gliders", can reach millions of cells in size, so large that they become impractical to simulate using general-purpose algorithms.
• Healing Factor:
  • The block can survive any single cell being removed, recovering in just one generation.
  • Eaters are a class of patterns capable of destroying certain objects while repairing the resulting damage to themselves. The most common of them is the eater 1 or fishhook, which can destroy a variety of objects such as loaves, pre-beehives, gliders, blinkers, and can attack another eater to form a period 3 oscillator.
  • Edge-repairing spaceships are a class of spaceships capable of repairing some kinds of damage, giving them capabilities to perturb other objects without being destroyed themselves.
• Long-Lived:
  • Methuselahs are unstable patterns which are noted for lasting an unusually long time relative to their size. The most famous of these is the "R-pentomino", a 5-cell pattern which lasts for a total of 1,103 generations before finally stabilizing into a mess of still lifes, blinkers, and escaping gliders.^note For comparison, all eleven other pentominoes stabilize in ten generations or fewer.
  • Whereas typical methuselahs only "die" in a somewhat figurative sense (by settling into a pattern of stable, non-interacting objects), diehards are a subset of methuselahs which end their lifespan by disappearing completely.
• Luck-Based Mission: One of the simplest ways to research new patterns in Conway's Game of Life is to simply create a (typically 16x16) area of random on and off cells called a "soup" and watch it evolve. Catagolue, the largest database of such soup results, has more than three hundred trillion entries.
• Magic A Is Magic A: Cells are born to three parents, and patterns can grow infinitely without a fuel source. Ultimately, the entire Life universe is governed by the four rules listed above.
• Mascot Mook: While the glider isn't exclusive to the exact rule of the Game of Life, it is undoubtedly the first pattern that comes to mind when thinking about this rule.
• Merging Mistake: Can happen when creating a glider synthesis. Gliders coming from different directions might cross paths and collide when they're not supposed to, or components of the synthesis might interact too early or too late.
• Mook Maker: Some patterns continuously produce spaceships (most often gliders). The first discovered, and most famous, is the Gosper's Glider Gun, which produces a glider every 30 generations. Another kind is Rakes, which are moving patterns continuously producing spaceships. Some types of Breeders^note patterns having a quadratic rather than linear infinite growth like the previous patterns take it even further by continuously making guns or rakes, which themselves make spaceships.
• No Plot? No Problem!: No plot of any kind to be found here, just a set of rules on a grid.
• Not the Intended Use:
  • LifeHistory's gray cells, originally intended to be used as a boundary between two regions of the Life universe. They are invulnerable, and instantly kill off any living cells next to them. This turned out be useful for creating all sorts of patterns not possible in ordinary Life, so much so that an entire forum thread was made dedicated to it.
  • The intended use of SlowLife is for even-numbered generations to contain exclusively white cells so that the pattern will function like a regular Life pattern, albeit at half the speed. However, by offsetting part of the pattern by a "half-generation", causing different parts of the universe to be updated at different times, new patterns can be made.
• One to Million to One: A SMOS, or "spaceship made of spaceships", is a spaceship which, during at least one of its phases, is made exclusively out of smaller spaceships which proceed to crash and form a structure that recreates the swarm at a different spot. One such example is known in the game of life, and is made out of 144,221 gliders in the "spaceships" phase. Taking this trope even further are SMOSMOS, of which some are known in specific rules. These SMOS have a phase where they are made out entirely of spaceships that are themselves SMOS.
• Organic Technology: Everything is made of cells.
• Player Versus Player: Some implementations of Conway's Game of Life (such as Game of Life and Death and Conway's Multiplayer Game of Life) are in the form of a PvP game. In both of these games, players have a finite number of cells they can modify at a time, and the objective is generally to have more living cells than your opponent(s).
• Random Drop Booster: Using different symmetry options when soup searching can make certain objects (usually those exhibting some form of symmetry themselves) far more common. apgsearch in particular even supports custom symmetries^note in which arbitrary patterns are fed into the program via standard input for if one is looking for specific types of objects.
• Randomly Generated Loot: Once a soup has permanently stabilized, what's left behind could be anything that happens to exhibit periodic behavior. Soup searching programs will then try to give these objects unique identifiers, such as "apgcodes" which are used by apgsearch.
• Rare Random Drop: There are infinitely many distinct objects which can theoretically appear in a soup, and therefore there is no limit to how rare they can get. Some objects, such as the loafer, have only appeared a handful of times in hundreds of trillions of soups, and others such as the Gosper glider gun have never appeared as of July 2022.
• Recursive Reality: Unit Cells are large patterns which, when set in a grid, are capable of computing the Game of Life itself by interacting with each other. More advanced variants are capable of simulating any life-like cellular automata, any non-totalistic rule, and even to "birth" and "die" like an actual cell. And yes, a large enough array of Unit Cells can simulate a Meta-Unit Cell, which may itself be part of a Meta-Meta-Unit Cell, and so on. This website demonstrates the eternal recursion, with OTCA metapixels, that, when zoomed in, reveal themselves to be made of metapixels too, which are themselves made of smaller metapixels, endlessly.
• Time Abyss: Engineered diehards can reach truly absurd longevities before disappearing entirely. One of the longest known has a longevity that's not known exactly, but it's known to be higher than the 10^950th tetration of 121. Said otherwise, it's 121 to the 121th power, the result becoming the power of 121, itself becoming the power of 121, and so on, 10^950 times. Even with a computer capable of calculating googols of generations per second, it wouldn't even make a dent in this pattern's longevity if it ran until the end of the Universe.
• Trope Codifier: The Game of Life was not the first cellular automaton - the concept originated in the 1940s, and the first actual cellular automaton was devised by John von Neumann in the 1950s. However, Conway's automaton is the best-known and most widely explored. Part of this is due to its simplicity: the automaton can be summed up in just a few sentences and implemented in only a few lines of code.
• Unnecessarily Large Vessel: Many spaceships can be extended arbitrarily, sometimes in both length and width, though this usually does not give them additional functionality.
• Video Game Cruelty Potential: Patterns in Life are extremely fragile; adding or removing just one cell to a stable pattern is generally enough to destabilize it such that it completely unravels and decomposes into a chaotic mess.
• Video Game Randomizer: Soup searching programs. The most notable of these is apgsearch, which randomly generates 16x16 soups using a hashing algorithm and runs them until completion.
• Wrap Around: It is common for implementations of the Life grid to wrap around at the edges by transplanting the game on a torus, as otherwise the edge of the grid can interfere with the automaton (a cell at the edge can only have at most 5 neighbors, or 3 in the corners). However, other more exotic wrap arounds exist, such as playing the game on a sphere or a Klein bottle.

---