apgsearch

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 as well as soups with large final populations.[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.

apgsearch
Homepage Click here
Purpose Soup search program
Created by Adam P. Goucher
Platform Unix; platform-independent

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.

Higher symmetries
<html><div class="rle"><div class="codebox"><div style="display:none;"><code></html>6bo11bo$7b2o7b2o$3bobob2o7b2obobo$2bobo15bobo$3bo17bo$2bo19bo$o9b2ob2o 9bo$b2o8bobo8b2o$b2o6bobobobo6b2o$8bobo3bobo$6bo2bo5bo2bo$6b3o7b3o2$6b 3o7b3o$6bo2bo5bo2bo$8bobo3bobo$b2o6bobobobo6b2o$b2o8bobo8b2o$o9b2ob2o 9bo$2bo19bo$3bo17bo$2bobo15bobo$3bobob2o7b2obobo$7b2o7b2o$6bo11bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THEME 6 GRID GRIDMAJOR 0 THUMBLAUNCH AUTOSTART GPS 4 THUMBSIZE 2 WIDTH 480 HEIGHT 480 ]]<html></code></div></div><canvas width="200" height="300" style="margin-left:1px;"><noscript></html>
Please enable Javascript to view this LifeViewer.
<html></noscript></canvas></div></html>
112P15 (click above to open LifeViewer)
RLE: here Plaintext: here
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.[1]

Inflation of a toy 4×4 soup.

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.[2]

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.[3]

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.

GPU searching

As of version 5.x, apgsearch supports soup searching on a GPU using CUDA which, depending on the GPU used, can process soups several times faster than a standard CPU search. The GPU deems soups "interesting" which meet certain criteria, and these are then fully censused by the CPU.[note 4] Therefore, the results are uploaded to separate symmetries on Catagolue to avoid distorting the main census statistics, with C and D replaced with G and H respectively.[4] The symmetries currently supported are:

  • G1 (counterpart to C1)
  • H2_+1, H2_+2 (D2_+1 and D2_+2)[5]
  • H4_+1, H4_+2, H4_+4[6]

Versions 5.061 and above allow GPU searching for any outer-totalistic rule, but not all of them can be searched easily in practice due to common objects meeting the criteria for "interestingness."[5]

Notable patterns
<html><div class="rle"><div class="codebox"><div style="display:none;"><code></html>x = 13, y = 10, rule = B3/S23 4bo3bo$2b2obobob2o$bo3bobo3bo$o3b2ob2o3bo$obo7bobo$bo9bo2$4b2ob2o$3bob obobo$4bo3bo! #C [[ THUMBSIZE 2 THEME 6 GRID GRIDMAJOR 0 SUPPRESS THUMBLAUNCH ]] #C [[ THEME 6 GRID GRIDMAJOR 0 THUMBLAUNCH AUTOSTART GPS 4 THUMBSIZE 2 ]]<html></code></div></div><canvas width="200" height="300" style="margin-left:1px;"><noscript></html>
Please enable Javascript to view this LifeViewer.
<html></noscript></canvas></div></html>
Rich's p16 (click above to open LifeViewer)
RLE: here Plaintext: here
Also see: Catagolue#Results in Conway's Game of Life

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.[7] 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.[8]
  • 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.[9]
  • 112P15 was first discovered in the ash of a symmetric soup in April 2016 by thunk.[10]
  • Rich's p16 was first discovered in the ash of a symmetric soup in July 2016 by Rich Holmes.[11]
  • 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.[12]
  • 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.[13]
  • 68P9 was first discovered in the ash of a symmetric soup in October 2018 by carybe.[14]
  • 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.[15] A month later, this was followed by Homer, discovered by Adam P. Goucher and lasting 42883 generations.[16]
  • Dueling banjos was first discovered in the ash of a symmetric soup in January 2019, in a tetramer form by Apple Bottom.[17]
  • The record-breaking methuselah 47575M was first discovered in February 2019 by Adam P. Goucher, outlasting Homer by nearly 5000 generations.[18]
  • Liston's p16 was first discovered by Rob Liston in February 2020 via GPU search, becoming the smallest known p16 oscillator and the first asymmetric object discovered by soup search since the 1980s.[19]
  • The record-breaking methuselah 49768M was first discovered in April 2020 by Rob Liston, outlasting 47575M by over 2000 generations.[20]

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, the lightweight Schick engine, the sidecar, and the loafer. Sample soups submitted to Catagolue have also led to cheaper glider syntheses for many patterns, including tumbler, eater 2, smiley, and unix. 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.[21]

Other rules
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:

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.

Hexagonal symmetries

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

The symmetries C3_3 and D6_3, as well as various gutter symmetries, are also possible but have yet to be implemented.[22]

Limitations
Also see: Catagolue#Limitations

Although apgsearch has bespoke support for flotillae composed of standard spaceships in Conway's Life, (with the exceptions of MWSS on HWSS 15 and HWSS on HWSS 10[23]) 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.[24]

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 and 5.x); higher-period objects are classified as PATHOLOGICAL. High-period linear-growth patterns may not be identified and instead reported as zz_LINEAR. Additionally, the maximum bounding box for any spaceship, oscillator or still life in versions 3.x and before is 40×40 due to the limits of the standard apgcode format; larger objects are classified as ov_ (oversized) in these versions.

Version history

Python versions

Two versions of apgsearch, versions 0.x and 1.x, were written in Python for use in Golly.

Version 0.x

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.[25] 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.

Version 1.x

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.[26] apgsearch 1.x supports the following different (pseudo-)symmetries:

  • C1
  • C2_1, C2_2, C2_4
  • C4_1, C4_4
  • D2_+1, D2_+2
  • D2_x
  • D4_+1, D4_+4
  • D4_x1, D4_x4
  • D8_1, D8_4
  • 8x32

C++ versions

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.

Version 2.x

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).[27]

Version 3.x

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.[28]

Version 4.x

apgsearch v4.x, codenamed apgluxe and based on lifelib, introduced the following features:

  • Support for B0 rules.[29][30]
  • Support for Generations rules (without B0).[31]
  • Cleaner separation of the different algorithmic layers.[32]
  • Support for two different containers, based on HashLife and vlife respectively.[32]
  • Support for 4×64, 2×128 and 1×256 soups.[33]
    • 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:
    • Support for extended ("greedy") apgcodes
    • Proper detection of oscillator and spaceship periods up to 1,048,576 (220)[34]

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.[31][35]
  • Support for "inflating" soups of arbitrary symmetry (v4.15).[2][36]
    • 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:

Version 4.3 was released in June, 2018:

Version 4.4 was released in June, 2018:

  • General speed improvements:
    • Special backend for Conway's Game of Life based on a 19-operation circuit by Tomas Rokicki.[42]
    • Much faster handling of slow 'tail' soups across all rules.
    • Faster oscillator and spaceship classification.
  • Reduced memory consumption.[43]

Version 4.5 was released in August, 2018:

Version 4.6 was released in October, 2018:

Version 4.7 was released in December, 2018:

Version 4.8 was released in January, 2019:

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.[59][60]

Version 5.x

apgsearch v5.x was first published on March 20, 2019.[4] 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.[61]
  • Various refactoring and simplification of the underlying code.
  • Detection of 'megasized' methuselahs with a final population exceeding 3000 in Conway's Game of Life. (v5.03)[62][63]

Version 5.1 was released in April, 2020:

  • Improved CUDA implementation, making b3s23/G1 searching roughly twice as fast as before.[64][65]

Upcoming features

The following features are planned for subsequent releases:

gollark: The obvious solution is dangerous experimental gene therapy.
gollark: And they say you have low blood sugar and/or low blood pressure for no particular reason? I see.
gollark: You really should see a doctor? That sounds extremely bad.
gollark: Bees 7 through 13.
gollark: I could, if I was to.

See also

Notes
  1. Only methuselahs lasting at least 25,000 generations, diehards lasting at least 500 generations, and soups with final populations of at least 3,000 are reported, and only in Conway's Game of Life.
  2. 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.
  3. The 25% pseudo-symmetry was also briefly used but abandoned due to conflicts with percent-encoding for URIs/URLs.
  4. A soup is deemed interesting if it fails to stabilize with period 6 within 12,000 generations or reaches the boundary of the finite universe (excluding escaping spaceships) considered by the GPU. Large still lifes, low-period oscillators, and diehards are therefore usually ignored.

References
  1. Adam P. Goucher (August 4, 2017). Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums
  2. Adam P. Goucher (September 2, 2017). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  3. "Census results for B3/S23/"Saka_Test"". Catagolue. Retrieved on December 21, 2016.
  4. Adam P. Goucher (March 20, 2019). apgsearch v5.0 (discussion thread) at the ConwayLife.com forums
  5. Adam P. Goucher (March 30, 2019). Re: apgsearch v5.0 (discussion thread) at the ConwayLife.com forums
  6. Arie Paap (April 1, 2019). Re: apgsearch v5.0 (discussion thread) at the ConwayLife.com forums
  7. Adam P. Goucher (August 26, 2014). "Re: Thread For Your Accidental Discoveries". ConwayLife.com forums. Retrieved on June 12, 2016.
  8. Richard Schank (November 24, 2014). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  9. gameoflifeboy (September 28, 2015). "Re: Soup search results". ConwayLife.com forums. Retrieved on June 12, 2016.
  10. thunk (April 5, 2016). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  11. Ivan Fomichev (July 5, 2016). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  12. Apple Bottom (November 17, 2016). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  13. Aidan F. Pierce (October 11, 2018). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  14. Aidan F. Pierce (October 2, 2018). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  15. Ian07 (October 31, 2018). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  16. Adam P. Goucher (November 30, 2018). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  17. Matthias Merzenich (January 11, 2019). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  18. Ian07 (February 10, 2019). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  19. Matthias Merzenich (February 10, 2020). Re: Oscillator Discussion Thread (discussion thread) at the ConwayLife.com forums
  20. Ian07 (April 23, 2020). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  21. Apple Bottom (April 4, 2016). Re: Soup search results (discussion thread) at the ConwayLife.com forums
  22. Adam P. Goucher (December 20, 2018). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  23. Adam P. Goucher (July 18, 2019). Re: Thread for basic questions (discussion thread) at the ConwayLife.com forums
  24. Bag Sinhwan (박신환) (November 28, 2016). "Re: Soup search results". ConwayLife.com forums. Retrieved on November 28, 2016.
  25. Adam P. Goucher (September 8, 2014). "apgsearch: a high-performance soup searcher". Retrieved on June 12, 2016.
  26. Adam P. Goucher (February 20, 2015). "apgsearch v1.0". Retrieved on June 12, 2016.
  27. Adam P. Goucher (July 28, 2015). "apgsearch v2.2". Retrieved on June 12, 2016.
  28. Adam P. Goucher (March 19, 2016). "apgsearch v3.1". Retrieved on June 12, 2016.
  29. Adam P. Goucher (August 3, 2017). Re: apgsearch v3.1 (discussion thread) at the ConwayLife.com forums
  30. Adam P. Goucher (August 19, 2017). "B0 support". GitLab.
  31. Adam P. Goucher (August 4, 2017). Re: apgsearch v3.1 (discussion thread) at the ConwayLife.com forums
  32. Adam P. Goucher (August 13, 2017). Re: Extending apgcodes to larger patterns (discussion thread) at the ConwayLife.com forums
  33. Adam P. Goucher (August 11, 2017). "More symmetries". GitLab.
  34. lifelib v1.22, classifier.h line 434
  35. Adam P. Goucher (August 21, 2017). "Larger than Life". GitLab.
  36. Adam P. Goucher (September 2, 2017). "Inflated symmetries". GitLab.
  37. Adam P. Goucher (September 10, 2017). "Supports non-totalistic rules". GitLab.
  38. Adam P. Goucher (June 3, 2018). "LtL Generations". GitLab.
  39. Adam P. Goucher (June 3, 2018). "Isotropic Generations". GitLab.
  40. Adam P. Goucher (June 3, 2018). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  41. Adam P. Goucher (June 3, 2018). "Support genera". GitLab.
  42. Adam P. Goucher (June 12, 2018). "Merge branch 'b3s23life' into 'master'". GitLab.
  43. Adam P. Goucher (June 4, 2018). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  44. Adam P. Goucher (October 28, 2018). Re: apgsearch 4.0 (discussion thread) at the ConwayLife.com forums
  45. Adam P. Goucher (October 28, 2018). "Preliminary support for methuselahs". GitLab.
  46. Apple Bottom (2018-11-03). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  47. Adam P. Goucher (October 29, 2018). "BSFKL rulespace". GitLab.
  48. Adam P. Goucher (November 6, 2018). Re: Thread for basic non-CGOL questions (discussion thread) at the ConwayLife.com forums
  49. Adam P. Goucher (November 7, 2018). "Higher-range outer-totalistic rules". GitLab.
  50. Adam P. Goucher (December 1, 2018). Re: Non-totalistic hex rules (discussion thread) at the ConwayLife.com forums
  51. Adam P. Goucher (December 1, 2018). "Hexagonal rules". GitLab.
  52. Ian07 (December 11, 2018). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  53. Adam P. Goucher (December 11, 2018). "Detect messless methuselahs". GitLab.
  54. Adam P. Goucher (December 19, 2018). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  55. Adam P. Goucher (December 19, 2018). "Support two more hexagonal symmetries". GitLab.
  56. Adam P. Goucher (December 20, 2018). "More hexagonal symmetries". GitLab.
  57. Adam P. Goucher (January 9, 2019). "Support for custom rules and neighbourhoods". GitLab.
  58. Adam P. Goucher (January 15, 2019). "Native support for Extended Generations and Deficient rules courtesy of M. I. Wright". GitLab.
  59. Adam P. Goucher (February 4, 2019). Re: apgsearch v4.9 (discussion thread) at the ConwayLife.com forums
  60. Adam P. Goucher (February 4, 2019). "Escaping glider detection". GitLab.
  61. Adam P. Goucher (March 20, 2019). "Working GPU version". GitLab.
  62. Adam P. Goucher (March 24, 2019). Re: apgsearch v5.0 (discussion thread) at the ConwayLife.com forums
  63. Adam P. Goucher (March 24, 2019). "Log soups with final population exceeding 3000 -- thanks to 'testitemqlstudop' for the suggestion". GitLab.
  64. Adam P. Goucher (April 24, 2020). Message in #tools on the Conwaylife Lounge Discord server
  65. Adam P. Goucher (April 24, 2020). "Include faster GPU implementation". GitLab.
  66. Adam P. Goucher (August 5, 2017). Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums

Code repositories

Forum threads
This article is issued from Conwaylife. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.