Tutorials/LLSSS

This is a rough draft of a tutorial for basic LLSSS spaceship searches. Feel free to edit this page.

Lattice Life slice spaceship search (LLSSS) is a part of Keith Amling's rlife search suite available here. It is inspired by Andrew J. Wade's LSSS search program. Any questions about installing and using LLSSS can be asked in this forum thread.

Installing

Prerequisites

LLSSS is written in Rust and requires the Rust compiler. You can install the Rust compiler for your system by following the steps given here. This tutorial assumes that you are using a Unix-like command line terminal with git. Those running Windows may wish to compile and run LLSSS through Windows subsystem for Linux (WSL2). Compilation of LLSSS may take up to 7GB of RAM.

Downloading and compiling the program

First, create a new folder for LLSSS and open a command-line terminal in this folder. Clone the rlife repository with the following command:

git clone https://codeberg.org/amling/rlife

Next, enter the newly created rlife folder by running

cd rlife

To compile the program, run the following command:

cargo build --release

Compilation will take several minutes and may take up to 7GB of RAM. Have patience.

When compilation is complete, the program binary will be contained in the newly created folder target/release. To enter this folder, run

cd target/release

You are now ready to run LLSSS. When running LLSSS in the future, you can simply open a command terminal in the release folder without needing to recompile the program.

A simple example search

rlife actually contains three variants of LLSSS, called llsss, llsss-recentering, and llsss-recentering-wao. Each works slightly differently and requires slightly different input. For this example, we will find the turtle using a front-to-back search with even symmetry using each LLSSS variant.

First, we will set an environment variable that tells LLSSS to stop when it finds a solution. This is accomplished by running

export LLSSS_HALT_ON_ENDS=true

If you wish to turn this feature off again, simply use the same command with true replaced by false. If LLSSS_HALT_ON_ENDS is false, then many searches will run forever. If you want to kill a search while it's running, you can use the keyboard shortcut Ctrl+C.

llsss

To find the turtle using a fixed-width search, you can run the following command:

./rlife llsss --rule 'B3/S23' --left-edge even --filters wcaf c3-f2b '@zero:9' > output.txt

Let's break down the input:

• ./rlife tells the terminal to run the rlife binary that we just compiled.
• llsss tells rlife to run a fixed-width LLSSS search.
• --rule 'B3/S23' sets the rule to Life.
• --left-edge even sets the left edge to have even-width bilateral symmetry.
• --filters wcaf is the "W-cycle avoidance filter". In this case, it stops the search if at some point all partial results have an empty first row (this would mean that no ships exist at the given width).
• c3-f2b is the geometry of the search. In this case we're searching for c/3 orthogonal ships from front to back.
• '@zero:9' is a "magic grid generator" for the geometry (see the start_file section for more details). In this case we are searching for a ship starting from empty ("zero") rows with "width" 9.
• > output.txt sends the output to the file output.txt.

There are two things to note in particular about the above input. First, the "width" of the search is 9, but finding the turtle in an even-symmetric search should only require a width of 6. The extra 3 columns come from the fact that LLSSS includes both the duplicated column on the left (due to symmetry), and two empty columns on the right.

The other thing to note is that --filters wcaf isn't actually necessary for this search. In this example, the turtle will be found regardless of whether it's included. We include it here as a matter of good practice. If we did not include it, and a ship did not exist at this width, then the search would continue forever. To see this, you can try running the above search at width 8 with and without --filters wcaf.

The above search will only take a few seconds to run. To locate the completed spaceship in the output, we need to search output.txt for the first occurrence of [Info] End. In this case, you'll find something like this:

[INFO] End ("LlsssEndsZero"):
[INFO] | ......... | ......... | ......... |
[INFO] | ......... | ......... | ......... |
[INFO] | ......... | **....... | **....... |
[INFO] | ***.*.... | ..*.**... | **.***... |
[INFO] | ***.**... | ....**... | ......*.. |
[INFO] | **....*.. | ...*.*... | ..**.*... |
[INFO] | ***...... | ..**..... | **....... |
[INFO] | ...**.... | **.**.... | **..*.... |
[INFO] | ...*..... | ..*...... | ***.*.... |
[INFO] | ..*.*.... | ....*.... | ...*..... |
[INFO] | ****..... | ....*.... | ......... |
[INFO] | ****..... | ......... | ***.*.... |
[INFO] | ....**... | *****.... | ******... |
[INFO] | ......... | ....**... | ***.**... |
[INFO] | .....*... | ......... | ......... |
[INFO] | **....... | ......... | ......... |
[INFO] | ......... | ......... | ......... |
[INFO] | ......... |           |           |

Notice that this shows just one of the symmetric halves of the turtle in each of its three phases. You will need to construct the complete symmetric spaceship yourself using a Life editing application, such as Golly or LifeViewer.

llsss-recentering

llsss-recentering is a variant of LLSSS that allows the center of the search to drift to the left or right analogously to floating rows in ikpx. The input is almost identical to that for llsss:

./rlife llsss-recentering --rule 'B3/S23' --left-edge even --filters wcaf c3-f2b '@zero' 6 > output.txt

Besides replacing llsss with llsss-recentering, the only other difference is replacing '@zero:9' with '@zero' 6. The new parameter after '@zero' is called the mid_steps and can be thought of as the "width" of a recentering search. In this case, a mid_steps value of 6 is sufficient to find the turtle. To locate the completed spaceship in the output, we can again search output.txt for the first occurrence of [Info] End.

llsss-recentering-wao

llsss-recentering-wao is an alternate recentering variant of LLSSS that uses a different method (other than --filters wcaf) to force live cells in the first row. The input looks somewhat different from the previous two setups:

./rlife llsss-recentering-wao --wao-left-pad 0 --wao-right-pad 0 --wao-idx ALL --rule 'B3/S23' --left-edge even --wao-left-edge-errors c3-f2b '@zero' 6 > output.txt

First, notice that we removed --filters wcaf, as it's no longer necessary. We also added several new options. Most importantly, the new option --wao-left-edge-errors must be included if you set --left-edge to some form of symmetry. It should not be included in an asymmetric search. The options --wao-left-pad, --wao-right-pad, and --wao-idx are not discussed here. We will simply be including them with the respective values 0, 0, and ALL in all wao searches in this tutorial. As before, the completed spaceship is marked by the first occurrence of [Info] End in output.txt.

Basic LLSSS options

This section covers only some of the basic LLSSS options. A complete list of options can be generated by running

./rlife <search-method> --help

where <search-method> is one of llsss, llsss-recentering, or llsss-recentering-wao.

Environment variables

Environment variables must be defined before the search is started. In a Linux terminal they can be set by running the command

export <variable>=<value>

To reset an LLSSS environment variable to its default value, run the command

unset <variable>

A full list of LLSSS-specific environment variables and their current values can be obtained by running

./rlife show-env

Below is a table containing some of the basic LLSSS environment variables:

Variable	Possible values	Default value	Description
LLSSS_HALT_ON_ENDS	true, false	false	If set to true, LLSSS will halt when one of the ends given by the --ends option is found.
LLSSS_INIT_CA_CHECKS	true, false	true	If set to true, LLSSS will check the start_file for validity using the cellular automaton rule give by the --rule option. This limits the size of the start_file, so if you have a very large file that you know is valid, you can set the value of this variable to false.
LLSSS_MAX_TABLE_SIZE	integers ≥ 9	27	Limits the size of rule check tables. These tables are built each time you run LLSSS, and allow the main search to run slightly faster. For some geometries (especially diagonal geometries) these tables can take over a minute to be built, so if you intend to run very short searches it can be beneficial to lower this value. In such cases, a recommended low value is 15.

Positional arguments

The positional arguments are required command line inputs that must be given in a particular order. They are the geometry, start_file, and mid_steps, and are described below. The third argument, mid_steps, only applies to searches run with llsss-recentering or llsss-recentering-wao and should not be included in searches run with llsss.

geometry

The geometry is a string indicating both the velocity of the desired spaceship and the direction in which the search progresses. The substrings f2b, b2f, and s2s mean "front-to-back", "back-to-front", and "side-to-side" respectively, and indicate the direction that the search progresses relative to the direction of travel of the desired spaceship. A complete list of valid geometries is given in the following table, where K is the displacement (empty K if K=1) and N is the period of the desired spaceship:

Geometry	Spaceship direction	Search direction
KcN-f2b	orthogonal north	south
KcN-b2f	orthogonal south	south
KcN-s2s	orthogonal west	south
KcNd-f2b	diagonal northwest	southeast
KcNd-b2f	diagonal southeast	southeast
KcNd-s2s	diagonal northwest	southwest
KcNd-down	diagonal northwest	south (f2b-like)
KcNd-up	diagonal southeast	south (b2f-like)
KcNk-1	knight-wise north-northwest	south (most f2b-like)
KcNk-2	knight-wise west-northwest	south
KcNk-3	knight-wise east-southeast	south
KcNk-4	knight-wise south-southeast	south (most b2f-like)
pN	none (oscillator)	south
raw:...	custom	custom

pN and raw geometries are not described in this tutorial.

start_file

The start_file represents the cells present at the beginning of the search. It can either be a file or a magic grid generator. The construction of an actual start_file can be difficult, and some basic start_file construction is shown in the extending partial results section.

Magic grid generators are simple command line inputs that give us an easy way to set up a search starting from empty rows or from a small selection of predefined agars. For llsss-recentering and llsss-recentering-wao searches, the magic grid generator representing empty rows is '@zero', while the magic grid generator for agars is '@agar:<agar-name>'. Possible values for <agar-name> can be found by running the command

./rlife grid-tool agar-info

The current list of predefined agars is

b0
blocks
horizontal-stripes
vertical-stripes
zero

Searches with an agar background cannot be run naively, as they will need some additional options to run properly. For example, see the B0 search section, which shows how to set up a spaceship search in rules with B0.

For llsss searches, the magic grid generator must also include an additional colon (:) followed by the width of the search. In this case, the width includes some extra columns that are not traditionally considered part of the width of the spaceship. For example, see the simple example search section.

mid_steps

mid_steps is an integer that can be thought of as the "width" of a recentering search, although it does not translate perfectly to traditional notions of spaceship width. This argument must be included in llsss-recentering and llsss-recentering-wao searches, but should not be included in llsss searches. For llsss searches, the width is instead included as part of the start_file.

Options

The following table contains only those options and values used in this tutorial. There are more options and some of the options listed can take more values than are presented here.

Option	Possible values	Default value	Details
--rule '<rule-string>'	a rulestring in Hensel or Callahan notation	B3/S23	Rulestrings should be enclosed in single quotes ('). A list of forbidden neighborhoods can be specified at the end of the birth and survival conditions, preceded by an exclamation mark (!). For example, to search in rule B3/S23 for ships that never contain the B6, S4i, or S5k neighborhoods, use --rule 'B3!6/S23!4i5k'.
--left-edge <boundary-condition>, --right-edge <boundary-condition>	even, odd, gutter, gse, gso, zero, agar:<agar-name>	zero	This defines the boundary condition of the specified side. The value is either a symmetry type, empty (zero), or an agar. Values gse and gso are "glide-symmetric even" and "glide-symmetric odd" respectively. Values for <agar-name> are given in the start_file section.
--wao-left-edge-errors, --wao-right-edge-errors			These options should be included in an llsss-recentering-wao search if the respective --left-edge or --right-edge boundary conditions are set to a symmetry type. They should not be included if the boundary condition is zero or an agar.
--filters <filters>	wcaf, acaf:<agar-name>		These are filters that remove parts of the search state as certain conditions are met. Multiple filters can be included, separated by a comma (,). wcaf is the "W-cycle avoidance filter" that prevents a search starting with empty rows from continuing forever if there are no spaceships. Analogously, acaf is the "agar-cycle avoidance filter". Values for <agar-name> are given in the start_file section.
--partials <partials>	srv2, srv2:<w_min>:<w_max>		This option causes LLSSS to print some extra partial results that have narrowed or have split into to narrow pieces. The printing of these partial results can take some extra time, so this option should not be set unless you think you might use the extra partial results. More details are given in the seam ripper partials section.
--ends <end-conditions>	even, odd, gse, gso, zero, agar:<agar-name>	zero	This option causes LLSSS to print results with the specified end conditions. Multiple ends can be included, separated by a comma (,). For example, --ends zero,even,odd will print any results where the bottom of the search becomes bilaterally symmetric (even and odd) or empty (zero). Values gse and gso are "glide-symmetric even" and "glide-symmetric odd" respectively. Values for <agar-name> are given in the start_file section.
--halts <halt-conditions>	w_pos:<max-w_pos>		This option halts the search when it reaches the given depth (W_pos).
--wao-left-pad <wao-pad>, --wao-right-pad <wao-pad>	nonnegative integers	1	A very technical explanation of these options can be found in two consecutive forum posts starting here. For all searches in this tutorial using llsss-recentering-wao we will set these values to 0.
--wao-idx <indices>	nonnegative integers, ALL		A very technical explanation of this option can be found in two consecutive forum posts starting here. For all searches in this tutorial using llsss-recentering-wao we will set this value to ALL.

An example B0 search

Under construction.

Seam ripper partials

Under construction.

Extending partial results

Under construction.

Saving and loading the search state

Under construction.

See also

Tutorials/LSSS