Difference between revisions of "Apgsearch"
(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 | * 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:
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:
- Support for isotropic non-totalistic rules.[5]
- Support for the von Neumann neighbourhood (implicitly as isotropic rules).[6]
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.[7]
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:
- Detection of methuselahs lasting longer than 25,000 generations in Conway's Game of Life. (v4.54)[10]
- Support for BSFKL rules. (v4.56)[11]
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)[12]
- 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)[13]
- Detection of diehards lasting longer than 500 generations in Conway's Game of Life. (v4.69)
The following features are planned for subsequent releases:
- Support for searching toroidal universes.[14]
See also
References
- ↑ "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.
- ↑ 5.0 5.1 Re: apgsearch v3.1 (discussion thread) at the ConwayLife.com forums
- ↑ 6.0 6.1 6.2 Re: apgsearch v3.1 (discussion thread) at the ConwayLife.com forums
- ↑ 7.0 7.1 7.2 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 v4.0 (discussion thread) at the ConwayLife.com forums
- ↑ 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
- ↑ Re: Hacking apgsearch (discussion thread) at the ConwayLife.com forums
External links
- About - Catagolue
- apgsearch - Catagolue (contains links to both v4.x and v1.x)
- Soup search results (discussion thread) at the ConwayLife.com forums