Ptbsearch

Ptbsearch is a search program by Paul Callahan. It is similar to the search program Catalyst, in that it attempts to perturb a pattern by adding still lifes in its vicinity. Unlike catalyst, ptbsearch is capable of adding transparent catalysts, which disappear for a duration of time before reappearing in their original locations. Many Herschel conduits and stable reflectors have been discovered with the help of ptbsearch.

Details

Ptbsearch uses a depth-first search algorithm to navigate the tree of possible perturbations. By comparison, a breadth-first search would be impractical, since the tree would occupy a staggering amount of memory. The program attempts to either add a catalyst, or to advance to the next generation. Catalysts are only added in places where they react in the current generation, and none of the previous generations.

Opaque catalysts, such as the eater 1, have fixed cells, which are not allowed to disappear. If a fixed cell does disappear, that branch of the search is considered to be a failure, and the search backtracks. Furthermore, the non-fixed cells must be restored shortly after disappearing, or the search backtracks.

Transparent catalysts, on the other hand, can disappear for an arbitrarily long amount of time. Examples include the transparent block found in conduit 1.

Search parameters

Searches are defined with the use of a batch file. The search involves two programs, ptb2.exe and survive.exe. The first of these enumerates the different possible perturbations of an object; the latter ensures that the output pattern fulfils the search criteria.

The various parameters that can be altered include:

• The pattern to perturb (this is passed to the program as a filename);
• The list of possible catalysts (again passed to the program as a filename);
• The maximum generation for adding catalysts;
• The number of catalysts that can be added in the search (technically, the value passed to the program is one less than the number of catalysts);
• The minimum generation for adding catalysts;
• The maximum number of transparent catalysts.

Pattern format

Patterns are specified using a one-line-per-pattern format. The specification is simple enough to be human-readable: it resembles the XLife graphical format, but uses an excalamation mark as a linefeed. This contrasts with RLE, which uses the exclamation mark as an end-of-pattern marker.

The lists of catalysts are stored as a text file, where each line corresponds to a catalyst. For example, the following file:

...*!.***!*!zz!
..*z!.*.z!.*!**!
zz!*!.***!...*!
z*!z.*!..*!..**!
*!***!...*!..zz!
**!.*!.*.z!..*z!
..zz!...*!***!*!
..**!..*!z.*!z*!
zz!zz!

represents all eight orientations of an eater 1, and the only orientation of a transparent block. If opaque blocks are required, four orientations should be specified:

zz!**!
z*!z*!
*z!*z!
**!zz!

This significantly speeds up search time.

However, it can be reduced to just two orientations if three transparent cells are used:

zz!z*!
*z!zz!

The character 'z' represents a transparent cell, whereas an asterisk indicates a fixed cell. This alteration marginally increases search speed by a few percent.

Catalysts

Only still life catalysts are supported, since the program was intended to search for small stable reflectors. Common opaque catalysts include the block, eater 1, eater 2, tub and boat. The block and beehive are commonly used as transparent catalysts, although the loaf and boat occasionally work. The tub and pond are potential transparent catalysts, but no known reaction exploits them.

Too many catalysts can slow the search down, so it is best to limit the number of potential catalysts. Limiting the search to the block and eater accelerates the search considerably, but it may miss some results.

Patterns discovered by ptbsearch

The initial stages of many stable reflectors have been found using ptbsearch. The rectifier uses a combination of ptbsearch, manual discovery and serendipity. The vast majority of Herschel conduits have been found using ptbsearch. Exceptions include the R64 and conduit 1.