The Ash Pattern Generator Search program, more commonly known as apgsearch, is an automated search program created by Adam P. Goucher. It generates soups, which by default are asymmetric and 16×16, and runs them until stabilization, recording any resulting still lifes, oscillators, spaceships, periodic linear infinite growth patterns, and "unusual growth" patterns. More recent versions also detect soups which are long-lived methuselahs and diehards.[note 1][note 2] Version 1.x and later upload the results to the online database Catagolue and have a peer-review process for verifying hauls submitted to the site.
Versions 4.x and later of apgsearch use a backend known as lifelib to simulate soups, and can simulate various types of rules and symmetric soups.
- 1 Higher symmetries
- 2 Notable patterns
- 3 Other rules
- 4 Limitations
- 5 Version history
- 6 See also
- 7 Notes
- 8 References
- 9 External links
- Also see: Symmetry
In addition to asymmetric (C1) soups, apgsearch can also run various types of symmetric soup searches and submit the data to Catagolue:
- C2_1, C2_2, C2_4: 180° (two-fold) rotational symmetry
- C4_1, C4_4: 90° (four-fold) rotational symmetry
- D2_+1, D2_+2: reflectional symmetry along an orthogonal line
- D2_x: reflectional symmetry along a diagonal line
- D4_+1, D4_+2, D4_+4: reflectional symmetry along two perpendicular orthogonal lines
- D4_x1, D4_x4: reflectional symmetry along two perpendicular diagonal lines
- D8_1, D8_4: reflectional symmetry along four orthogonal/diagonal through a common center
Furthermore, the following pseudo-symmetries are used for asymmetric soups of different sizes:
- 8x32, 4x64, 2x128, 1x256: for 256-cell soups of size 8×32, 4×64, 2×128 and 1×256
8x32 was one of the initial (pseudo-)symmetries the site handled; support for 4x64, 2x128 and 1x256 was added in August 2017.
All symmetries can be "inflated" using the "i" prefix, replacing each cell in the sample soup with a 2×2 alignment of cells in the same state and resulting in soups of size e.g. 32×32 for iC1 instead of 16×16 for C1. Multiple "i" prefixes can be stacked to "inflate" cells to 4×4, 8×8, etc.
The 25pct and 75pct pseudo-symmetries were used in the past to investigate soups with initial densities of 0.25 and 0.75 respectively, but they fell into disuse and are not supported by v3.x and above.[note 3] Other pseudo-symmetries such as 25p, 32x32, 1x256X2+1 etc. have been used, but are not considered standard. apgsearch and Catagolue encourage users to use designated "test" symmetries to test modifications to the client.
Although various orthogonal and diagonal gutter symmetries are possible in Conway's Game of Life, apgsearch does not currently have official support for searching with them. However, various users have modified apgsearch in order to search these symmetries and have submitted the results to Catagolue under custom symmetry names.
A variety of notable natural and semi-natural (i.e. appearing in symmetric soups) patterns were first discovered using apgsearch:
- The first known natural occurrence of a nonstandard spaceship was found during alpha testing of the script. The soup, which produced an LWSS on HWSS 1, was submitted to the conwaylife.com forums on August 26, 2014 by Adam P. Goucher. Many other nontrivial spaceship flotillae have since been found.
- The pufferfish was discovered in the ash of a symmetric soup in November 2014 by Richard Schank.
- The first known natural occurrence of a puffer other than the block-laying or glider-producing switch engine, a p1152 made from two switch engines dubbed the pony express, was found in September 2015 by Apple Bottom.
- 112P15 was first discovered in the ash of a symmetric soup in April 2016 by thunk.
- Rich's p16 was first discovered in the ash of a symmetric soup in July 2016 by Rich Holmes.
- thunk's discovery of a period 28 pre-pulsar-shuttle variant in November 2016 enabled the construction of smaller (in terms of minimum population) period 26 and period 28 pre-pulsar-shuttles.
- 34P14.1 was first discovered in the ash of a symmetric soup in September 2018 by carybe, but was not noticed on Catagolue until October.
- 68P9 was first discovered in the ash of a symmetric soup in October 2018 by carybe.
- 42100M was first discovered in October 2018 by Dave Greene, only two days after apgsearch added support for detecting methuselahs, becoming the longest-lasting known methuselah within a 16×16 bounding box at the time. A month later, this was followed by Homer, discovered by Adam P. Goucher and lasting 42883 generations.
- Dueling banjos was first discovered in the ash of a symmetric soup in January 2019, in a tetramer form by Apple Bottom.
- The record-breaking methuselah 47575M was first discovered in February 2019 by Adam P. Goucher, outlasting Homer by nearly 5000 generations.
Other rare objects found by apgsearch in asymmetric soups are smiley, Achim's p8, Elkies' p5, heart, Silver's p5, phoenix 1, the Coe ship, and the lightweight Schick engine. Sample soups submitted to Catagolue have also led to cheaper glider syntheses for many patterns, including tumbler, eater 2, and smiley. Additionally, the copperhead first emerged from a D2_+2 soup in April 2016 only a month after its initial discovery by zdr, followed by several more later in the year.
- Main article: List of rules investigated on Catagolue
apgsearch has the ability to run soup searches for various rules other than Conway's Game of Life. In the past, this was restricted to outer-totalistic rules with two states, but versions v4.x and later have added support for various families of rules over time. However, only non-exploding rules can reasonably be investigated in practice unless a certain symmetry can be assured to never explode.
As of v4.86, apgsearch officially supports the following types of cellular automata:
- Arbitrary outer-totalistic rules.
- Isotropic non-totalistic rules. (in Hensel notation)
- Isotropic von Neumann neighbourhood rules. (implicitly by isotropic non-totalistic Moore neighbourhood rules)
- Higher-range outer totalistic (HROT) rules. (up to range 5)
- Larger than Life rules. (up to range 7)
- Totalistic and isotropic hexagonal neighbourhood rules.
- Generations variants of all rules listed above.
- Outer-totalistic B0 rules with two states.
- BSFKL rules.
- Deficient rules.
- Extended Generations rules.
- Custom Golly ruletables.
The Moore neighbourhood and hexagonal neighbourhood are the currently the only directly supported neighbourhoods, although the von Neumann neighbourhood can be indirectly simulated by isotropic Moore rules and the Margolus neighbourhood (specifically block cellular automata) can be simulated by inflated soups on specific rules.
Symmetric soups can also be run for rules other than Conway's Game of Life. However, many of the symmetries of the Moore neighbourhood do not apply to the hexagonal grid, and hexagonal rules must therefore use a separate set of symmetries. As of January 2019, this includes the following:
- C1, 8x32, 4x64, 2x128: for asymmetric 256-cell soups of size 16×16, 8×32, 4×64, and 2×128 respectively
- C2_1, C2_2: 180° (two-fold) rotational symmetry
- C3_1: 120° (three-fold) rotational symmetry
- C6: 60° (six-fold) rotational symmetry
- D2_x, D2_xo, 1x256: reflectional symmetry along a single line
- D4_x1, D4_x4: reflectional symmetry along two perpendicular lines
- D6_1, D6_1o: reflectional symmetry along three lines through a common center
- D12: reflectional symmetry along six lines through a common center
- Also see: Catagolue#Limitations
Although apgsearch has bespoke support for flotillae composed of standard spaceships in Conway's Life, it can fail to properly separate larger non-interacting groups, or groups of any size in non-Life rules. Pseudo still lifes composed of many constituent parts may also fail to be separated properly.
The maximum period for spaceships and oscillators is 1,000 in apgsearch 1.x, 4,000 in apgnano (apgsearch 2.x), 1,280 in apgmera (apgsearch 3.x), and 1,048,576 in apgluxe (apgsearch 4.x); higher-period objects are classified as PATHOLOGICAL. The maximum bounding box for any spaceship, oscillator or still life is 40×40; larger objects are classified as ov_ (oversized). High-period linear-growth patterns may not be identified and instead reported as zz_LINEAR.
Two versions of apgsearch, versions 0.x and 1.x, were written in Python for use in Golly.
apgsearch v0.x was the initial version of the script, first published on September 8, 2014. When running the script, the user is first prompted to enter the number of soups to be searched, the rule under which to search, and the initial seed for soup generation. The script proceeds to search soups in sets of 100 until either the specified number of soups has been exceeded, or the user stops the search by pressing <q>. After the search finishes, Golly opens an HTML window which displays the results. Aidan F. Pierce modified this version to allow soup-searching non-totalistic Life-like cellular automata, and made a later modification to allow the results to be uploaded to Catagolue.
apgsearch v1.x was first released on February 20, 2015. The main improvements from version 0.x are the ability to search symmetrical soups and the periodic uploading of results to Catagolue. apgsearch 1.x supports the following different (pseudo-)symmetries:
- C2_1, C2_2, C2_4
- C4_1, C4_4
- D2_+1, D2_+2
- D4_+1, D4_+4
- D4_x1, D4_x4
- D8_1, D8_4
Four versions of apgsearch, versions 2.x through 5.x, were written in C++. These versions are much faster, and are intended to be run from the command line of a Unix shell.
apgsearch v2.x, codenamed apgnano, was first published on July 19, 2015 and released onto the conwaylife.com forums on July 28. It uses a bespoke algorithm called Life128, partially written in assembly language for speed, and can utilize both the SSE2 instruction set on x86_64 CPUs. It can only searches asymmetric (C1) 16×16 soups in Conway Life (B3/S23).
apgsearch v3.x, codenamed apgmera, was first published on March 3, 2016 and released onto the conwaylife.com forums on March 19. It uses an algorithm called vlife, and unlike version 2.x, it supports arbitrary outer-totalistic rules, as well as the full range of symmetries from apgsearch 1.1. It can use any of the SSE2, AVX1 and AVX2 instruction sets on x86_64 CPUs.
Although the main program is written in C++, version 3.x contains a shell script and a Python file to generate assembly code for different rules and symmetries.
apgsearch v4.x, codenamed apgluxe and based on lifelib, introduced the following features:
- Support for B0 rules.
- Support for Generations rules (without B0).
- Cleaner separation of the different algorithmic layers.
- Support for two different containers, based on HashLife and vlife respectively.
- Support for 4×64, 2×128 and 1×256 soups.
- Indirect support for some one-dimensional cellular automata using one-cell-thick soups (for example, b026s1 simulates Wolfram rule 2166637080)
- An 8% increase in speed in Lifelib compared to vlife in version 3.x.
- Improved object detection, including:
Version 4.1 was released on August 21, 2017, and incorporated another rule family, namely:
- Support for Larger than Life rules with a range of up to 7.
- Support for "inflating" soups of arbitrary symmetry (v4.15).
- Indirect support for certain Margolus rules, using said inflated soups alongside rules simulating block cellular automata.
Version 4.2 was released on September 10, 2017:
- Support for isotropic non-totalistic rules.
Version 4.3 was released in June, 2018:
- Support for Larger than Life rules with >2 states (i.e. Generations-LtL rules).
- Support for isotropic non-totalistic Generations rules.
- Support for custom backends.
Version 4.4 was released in June, 2018:
- General speed improvements:
- Reduced memory consumption.
Version 4.5 was released in August, 2018:
- Detection of methuselahs lasting longer than 25,000 generations in Conway's Game of Life. (v4.54)[note 2]
- Support for BSFKL rules. (v4.56)
Version 4.6 was released in October, 2018:
- Support for higher-range outer-totalistic Life-like cellular automata, up to a range of 5. (v4.63)
- Support for totalistic, isotropic non-totalistic, and Generations rules using a hexagonal neighbourhood, though with higher symmetries disabled as they had yet to be redesigned to be compatible with the hexagonal grid. (v4.66)
- Detection of diehards lasting longer than 500 generations in Conway's Game of Life. (v4.69)
Version 4.7 was released in December, 2018:
- Support for certain higher symmetries in hexagonal neighbourhood rules, particularly:
Version 4.8 was released in January, 2019:
- Support for custom cellular automata using Golly rule tables and trees.
- Native support for Deficient and Extended Generations rules. (v4.83)
Version 4.9 was released in February, 2019:
- Approximate 50% speed improvement for Conway's Game of Life and certain related rules due to detection of escaping gliders.
apgsearch v5.x was first published on March 20, 2019. The salient new features are:
- Improved methodology for splitting work between CPU cores, ensuring threads are not idle.
- Support for soup searching on a GPU using CUDA (currently restricted to b3s23/C1).
- Various refactoring and simplification of the underlying code.
The following features are planned for subsequent releases:
- Support for C3_3 and D6_3 symmetries for the hexagonal neighbourhood.
- Support for searching toroidal universes.
- Only methuselahs lasting at least 25,000 generations and diehards lasting at least 500 generations are reported, and only in Conway's Game of Life.
- apgsearch estimates the lifespan of each soup before testing it more precisely, and is not guaranteed to detect all methuselahs with a lifespan of less than 26,000 generations.
- The 25% pseudo-symmetry was also briefly used but abandoned due to conflicts with percent-encoding for URIs/URLs.
- Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums
- Adam P. Goucher. Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
- "Census results for B3/S23/"Saka_Test"". Catagolue. Retrieved on December 21, 2016.
- Adam P. Goucher (August 26, 2014). "Re: Thread For Your Accidental Discoveries". ConwayLife.com forums. Retrieved on June 12, 2016.
- Richard Schank (November 24, 2014). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- gameoflifeboy (September 28, 2015). "Re: Soup search results". ConwayLife.com forums. Retrieved on June 12, 2016.
- thunk (April 5, 2016). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- Ivan Fomichev (July 5, 2016). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- Apple Bottom (November 17, 2016). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- Aidan F. Pierce (October 11, 2018). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- Aidan F. Pierce (October 2, 2018). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- Ian07 (October 31, 2018). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- Adam P. Goucher (November 30, 2018). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- Matthias Merzenich. Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
- Ian07 (February 10, 2019). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- Apple Bottom (April 4, 2016). Re: Soup search results (discussion thread) at the ConwayLife.com forums
- Adam P. Goucher (December 20, 2018). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
- Bag Sinhwan (박신환) (November 28, 2016). "Re: Soup search results". ConwayLife.com forums. Retrieved on November 28, 2016.
- "apgsearch: a high-performance soup searcher". Retrieved on June 12, 2016.
- "apgsearch v1.0". Retrieved on June 12, 2016.
- "apgsearch v2.2". Retrieved on June 12, 2016.
- "apgsearch v3.1". Retrieved on June 12, 2016.
- Re: apgsearch v3.1 (discussion thread) at the ConwayLife.com forums
- Re: apgsearch v3.1 (discussion thread) at the ConwayLife.com forums
- Re: Extending apgcodes to larger patterns (discussion thread) at the ConwayLife.com forums
- lifelib v1.22, classifier.h line 434
- Adam P. Goucher. Re: apgsearch 4.0 (discussion thread) at the ConwayLife.com forums
- Apple Bottom (2018-11-03). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
- Adam P. Goucher. Re: Thread for basic non-CGOL questions (discussion thread) at the ConwayLife.com forums
- Adam P. Goucher (December 1, 2018). Re: Non-totalistic hex rules (discussion thread) at the ConwayLife.com forums
- Adam P. Goucher (December 19, 2018). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
- Adam P. Goucher (February 4, 2019). Re: apgsearch v4.9 (discussion thread) at the ConwayLife.com forums
- Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums
- apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
- apgsearch v3.1 (discussion thread) at the ConwayLife.com forums
- apgsearch v2.2 (discussion thread) at the ConwayLife.com forums
- apgsearch v1.0 (discussion thread) at the ConwayLife.com forums
- apgsearch: a high-performance soup searcher (discussion thread) at the ConwayLife.com forums (original discussion thread)
- Hacking apgsearch (discussion thread) at the ConwayLife.com forums
- Soup search results (discussion thread) at the ConwayLife.com forums