Line #131 VideoGame/ConwaysGameOfLife


1	[[quoteright:150:https://static.tvtropes.org/pmwiki/pub/images/GameOfLife_glider_9201.png]]
2	[[caption-width-right:150:The "glider" is a pattern that moves 1 cell diagonally every 4 generations.]]
3
4	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.
5
6	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:
7
8	* Each cell can be either alive (on) or dead (off).
9	* If a dead cell has exactly 3 neighboring cells, it becomes alive (birth).
10	* If a live cell has either 2 or 3 neighboring cells, it stays alive (survival).
11	* In all other situations, a cell dies (or remains dead).
12
13	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.
14
15	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.
16
17	Even decades later, the Game of Life has a strong hobbyist following, and new discoveries are still being made.
18
19	See [[https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life this page]] on Website/TheOtherWiki for more information.
20
21	A website allowing you to play with Life patterns can be found [[https://playgameoflife.com here.]] program allowing you to play with Life and several other similar games can be found [[https://sourceforge.net/projects/golly here.]]
22
23	Not to be confused with [[TabletopGame/GameOfLife Milton Bradley's board game]]. For stories about your everyday world suddenly taking on [[FridgeHorror these rules]], see [[SuddenGameInterface Life Is A Game]].
24
25	----
26	!!Tropes
27	* AwesomeButImpractical: Many contraptions created in the Game of Life use [[TheAllegedComputer 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.
28	** Adam P. Goucher's [[ExactlyWhatItSaysOnTheTin pi and phi calculators]] take billions or even trillions of generations to calculate just a few decimal digits.
29	** Any universal computer, such as Paul Rendell's [[UsefulNotes/AlanTuring 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.
30	** In 2013, a challenge was posted on Stack Exchange to "build a working game of ''{{VideoGame/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 [[RecursiveReality metacells]] to simulate a custom-made cellular automaton called [=VarLife=], which in turn uses its own metacells to simulate a game of ''Tetris''.
31	** Goucher's 0E0P[[note]]0E0P = "zero encoded (by) zero population"[[/note]] 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.
32	** 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.[[/note]] 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.
33	* BoringButPractical:
34	** 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.
35	** 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.
36	* {{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 [[TabletopGame/{{chess}} knight]] move) is c/6.
37	* ColourCodedForYourConvenience: Some implementations of Life have multiple cell colors to convey additional information besides "on" and "off":
38	** "[=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 ''[[ExaggeratedTrope dozens]]'' [[ExaggeratedTrope of colors]].
39	** "[=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.
40	** "[=DoubleB3S23=]" and "[=TripleB3S23=]" are effectively [[AlternateUniverse 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.
41	** "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.
42	* CoolOfRule: Despite the simplicity of the rules, extremely complex constructions are nonetheless possible and have been successfully built.
43	* DiagonalSpeedBoost: 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.[[/note]]
44	* EarlyInstallmentWeirdness:
45	** 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.[[/note]]
46	** 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.
47	** 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.
48	* ExplosiveOverclocking: 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.
49	* ExplosiveResults: 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.
50	* ExtraParentConception: Cells are always born to exactly three parents.
51	* ExtremeGraphicalRepresentation:
52	** 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.
53	** 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.
54	* FasterThanLightTravel: The Fast Forward Force Field is a [[SubvertedTrope 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.
55	* FusionDance: Glider synthesis, in which gliders are collided together to produce other objects.
56	* FusionDissonance: [[ZigZaggingTrope 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 [[AvertedTrope 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.
57	* GiantFlyer: 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.
58	* HealingFactor:
59	** The block can survive any single cell being removed, recovering in just one generation.
60	** 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.
61	** 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.
62	* LongLived:
63	** 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.[[/note]]
64	** 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 [[NoBodyLeftBehind disappearing completely]].
65	* LuckBasedMission: 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. [[https://catagolue.hatsya.com/home Catagolue]], the largest database of such soup results, has more than ''three hundred trillion'' entries.
66	* MagicAIsMagicA: 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.
67	* MascotMook: 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.
68	* MergingMistake: 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.
69	* MookMaker: 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[[/note]] take it even further by continuously making guns or rakes, which themselves make spaceships.
70	* NoPlotNoProblem: No plot of any kind to be found here, just a set of rules on a grid.
71	* NotTheIntendedUse:
72	** [=LifeHistory=]'s gray cells, originally intended to be used as a boundary between two regions of the Life universe. They are [[CompleteImmortality invulnerable]], and [[TouchOfDeath 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 [[https://conwaylife.com/forums/viewtopic.php?f=11&t=390 an entire forum thread]] was made dedicated to it.
73	** 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, [[https://conwaylife.com/forums/viewtopic.php?f=11&t=5231 new patterns can be made]].
74	* OneToMillionToOne: 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.
75	* OrganicTechnology: ''Everything'' is made of cells.
76	* PlayerVersusPlayer: 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).
77	* RandomDropBooster: 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[[/note]] for if one is looking for specific types of objects.
78	* RandomlyGeneratedLoot: 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.
79	* RareRandomDrop: 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.
80	* RecursiveReality: 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. [[https://oimo.io/works/life/ 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.
81	* TimeAbyss: Engineered [[NoBodyLeftBehind 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. [[ExaggeratedTrope 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.
82	* TropeCodifier: 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.
83	* UnnecessarilyLargeVessel: Many spaceships can be extended arbitrarily, sometimes in both length and width, though this usually does not give them additional functionality.
84	* VideoGameCrueltyPotential: 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.
85	* VideoGameRandomizer: Soup searching programs. The most notable of these is apgsearch, which [[RandomlyGeneratedLevels randomly generates]] 16x16 soups using a hashing algorithm and runs them until completion.
86	* WrapAround: 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.

Context VideoGame / ConwaysGameOfLife