Difference between revisions of "Apgsearch"

From LifeWiki
Jump to navigation Jump to search
(Mention hexagonal rules)
(Diehards)
Line 72: Line 72:


Version 4.5 was released in August, 2018:
Version 4.5 was released in August, 2018:
* Detection of [[methuselah|methuselahs]] lasting longer than 25,000 generations in [[Conway's Game of Life]]. (v4.54)<ref name="post65133" />
* Detection of [[methuselah]]s lasting longer than 25,000 generations in [[Conway's Game of Life]]. (v4.54)<ref name="post65133" />
* Support for [[BSFKL]] rules. (v4.56)<ref name="post65313" />
* Support for [[BSFKL]] rules. (v4.56)<ref name="post65313" />


Line 78: Line 78:
* Support for higher-range [[outer-totalistic Life-like cellular automata]], up to a range of 5. (v4.63)<ref name="post65440" />
* Support for higher-range [[outer-totalistic Life-like cellular automata]], up to a range of 5. (v4.63)<ref name="post65440" />
* Support for isotropic non-totalistic rules using a [[hexagonal neighbourhood]], though with higher symmetries disabled as they are currently incompatible with a hexagonal grid. (v4.66)<ref name="post66090" />
* Support for isotropic non-totalistic rules using a [[hexagonal neighbourhood]], though with higher symmetries disabled as they are currently incompatible with a hexagonal grid. (v4.66)<ref name="post66090" />
* Detection of [[diehard]]s lasting longer than 500 generations in [[Conway's Game of Life]]. (v4.69)


The following features are planned for subsequent releases:
The following features are planned for subsequent releases:

Revision as of 10:15, 12 December 2018

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 16x16, and runs them until stabilization, recording any resulting still lifes, oscillators, spaceships, periodic linear infinite growth patterns, and "unusual growth" patterns. Version 1.x and later upload the results to the online database Catagolue.

Versions

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.[1] 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.[2] 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_x1
  • D8_1, D8_4
  • 8x32

C++ versions

Three versions of apgsearch, versions 2.x through 4.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 and AVX1 instructions sets on x86_64 CPUs. It can only searches asymmetric (C1) 16×16 soups in Conway Life (B3/S23).[3]

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 both the SSE2, AVX1 and AVX2 instruction set 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.[4]

Version 4.x

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

  • Support for B0 rules.[5]
  • Support for Generations rules (without B0).[6]
  • Cleaner separation of the different algorithmic layers.[7]
  • Support for two different containers, based on HashLife and vlife respectively.[7]
  • 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:
    • Support for extended ("greedy") apgcodes
    • Proper detection of oscillator and spaceship periods up to 1,048,576 (220)[8]

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.[6]
  • Support for "inflating" soups of arbitrary symmetry (v4.15).[9]
    • 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.
    • Much faster handling of slow 'tail' soups across all rules.
    • Faster oscillator and spaceship classification.
  • Reduced memory consumption.

Version 4.5 was released in August, 2018:

Version 4.6 was released in October, 2018:

The following features are planned for subsequent releases:

See also

References

  1. "apgsearch: a high-performance soup searcher". Retrieved on June 12, 2016.
  2. "apgsearch v1.0". Retrieved on June 12, 2016.
  3. "apgsearch v2.2". Retrieved on June 12, 2016.
  4. "apgsearch v3.1". Retrieved on June 12, 2016.
  5. 5.0 5.1 Re: apgsearch v3.1 (discussion thread) at the ConwayLife.com forums
  6. 6.0 6.1 6.2 Re: apgsearch v3.1 (discussion thread) at the ConwayLife.com forums
  7. 7.0 7.1 7.2 Re: Extending apgcodes to larger patterns (discussion thread) at the ConwayLife.com forums
  8. lifelib v1.22, classifier.h line 434
  9. Adam P. Goucher. Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  10. Adam P. Goucher. Re: apgsearch 4.0 (discussion thread) at the ConwayLife.com forums
  11. Apple Bottom (2018-11-03). Re: apgsearch v4.0 (discussion thread) at the ConwayLife.com forums
  12. Adam P. Goucher. Re: Thread for basic non-CGOL questions (discussion thread) at the ConwayLife.com forums
  13. Adam P. Goucher (December 1, 2018). Re: Non-totalistic hex rules (discussion thread) at the ConwayLife.com forums
  14. Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums

External links