Tutorials/LLSSS
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. This tutorial describes how to set up some simple LLSSS spaceship searches and lists many of the basic LLSSS options. LLSSS has significant functionality beyond what is covered in this tutorial. 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), in which case you will need to find instructions for installing Rust on Linux.
Compilation of LLSSS may take up to 14GB of RAM. If your system does not have this amount available to it, the compilation step may fail after several minutes with an error message stating process didn't exit successfully. In this case, you will need to increase the available amount of swap memory for your system. Guides on how to do this for various operating systems can be found online. An explanation for WSL2 is given below.
To increase the swap memory available to WSL2, you will need to create a file with the name .wslconfig in the folder C:\Users\<UserName>, where <UserName> is your Windows user name. If the file already exists, then you can edit the existing file. The file should contain at least the following lines:
# Settings apply across all Linux distros running on WSL 2 [wsl2] # Sets amount of swap storage space to 16GB, default is 25% of available RAM swap=16GB
Here 16GB was chosen to be sufficient for compiling rlife. After creating or editing this file, you will need to restart WSL2 for the changes to take effect. You can check the total amount of available swap memory in WSL2 by running
free -h
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 14GB 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 bcaf c3-f2b '@bg(9)' > output.txt
Let's break down the input:
./rlifetells the terminal to run the rlife binary that we just compiled.llssstells rlife to run a fixed-width LLSSS search.--rule 'B3/S23'sets the rule to Life.--left-edge evensets the left edge to have even-width bilateral symmetry.--filters bcafis the "background-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-f2bis the geometry of the search. In this case we're searching for c/3 orthogonal ships from front to back.'@bg(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 the background agar ("bg", which defaults to empty rows) with a "width" of 9.> output.txtsends the output to the fileoutput.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 bcaf 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 bcaf.
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 (("LlsssEndsAgar", "zero")):
[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 bcaf c3-f2b '@bg' 6 > output.txt
Besides replacing llsss with llsss-recentering, the only other difference is replacing '@bg(9)' with '@bg' 6. The new parameter after '@bg' 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 bcaf) to force live cells in the first row. The input looks somewhat different from the previous two setups:
./rlife llsss-recentering-wao --rule 'B3/S23' --left-edge even --wao-left-edge-errors c3-f2b '@bg' 6 > output.txt
First, notice that we removed --filters bcaf, as it's no longer necessary. We also added the new option --wao-left-edge-errors, which must be included if you set --left-edge to some form of symmetry. It should not be included in an asymmetric search. 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 filter the initial search state based on 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. This variable should be set to true when using wildcards, which are not covered by this tutorial.
|
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.
|
Required arguments
There are a few required command line arguments that can be placed anywhere among the options, but 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 a small selection of predefined background agars (including empty space). For llsss-recentering and llsss-recentering-wao searches, the magic grid generator representing the background agar is '@bg'. The background agar defaults to empty space in all generations, but can be changed by including --bg-agar <agar-name> in the command line input. 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 one vertical-stripes zero
For an example using a non-default background agar, see the B0 search section.
For llsss searches, the magic grid generator must also include an additional argument of the width of the search (e.g. @bg(9)). 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. N.B. this syntax was changed from @bg:9 to @bg(9) in 1198f91922dc, pushed 2026/04/03. If this new syntax is not working please make sure you're up to date.
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 '<rulestring>'
|
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'.
|
--bg-agar <agar-name>
|
the agars listed in the start_file section | zero
|
This sets the background agar for the search, which determines the behavior of the bg boundary and end conditions and the bcaf filter. The default value is an empty background (zero).
|
--left-edge <boundary-condition>,
|
even, odd, gutter, gse, gso, bg, agar("<agar-name>")
|
bg
|
This defines the boundary condition of the specified side. The value is either a symmetry type, the background agar (bg), or another specified 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,
|
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 bg or an agar.
| ||
--filters <filters>
|
wcaf, bcaf, acaf("<agar-name>")
|
These are filters that remove parts of the search state as certain conditions are met. Multiple filters can be included, in brackets and separated by commas ([filter1, filter2, filter3]). wcaf is the "W-cycle avoidance filter" that prevents a search starting with empty rows from continuing forever if there are no spaceships. Analogously, bcaf and acaf are the background and agar-cycle avoidance filters respectively. 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 two narrow branches. 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, bg, skew_gutter(<skew>), agar("<agar-name>")
|
bg
|
This option causes LLSSS to print results with the specified end conditions. Multiple ends can be included, in brackets and separated by commas ([ends1, ends2, ends3]). For example, --ends '[even, odd, bg]' will print any results where the bottom of the search becomes bilaterally symmetric (even and odd) or matches the background agar (bg). 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). |
B0 searches
In rules with B0 and without S8, the background of the CA universe has period 2, alternating between dead and alive cells. This strobing agar background must be indicated in our inputs if we want to search for spaceships in these rules. This is accomplished by using the option --bg-agar b0.
We assume for this section that the environment variable LLSSS_HALT_ON_ENDS has been set to true.
Here is a setup for a recentering-wao, side-to-side c/2 orthogonal search in B026/S2:
./rlife llsss-recentering-wao --rule 'B026/S2' --bg-agar b0 --ends '[even, odd]' c2-s2s '@bg' 9
Here we have included --bg-agar b0, but all other options are the same as in an ordinary spaceship search. Since this is a side-to-side search, we also include --ends '[even, odd]', because we want the search to report if it finds half of a symmetric ship.
Notice in the output that one phase of the discovered spaceship has live cells on the (non-symmetric) borders, while the other has dead cells on the borders, as should be expected in a rule with B0:
[INFO] End [thinnest] "LlsssEndsReflect(Odd)": [INFO] | ZZZZZZZZZZZZ | ZZZZZZZZZZZZ | [INFO] | ************ | ............ | [INFO] | ************ | ............ | [INFO] | *******...** | ............ | [INFO] | *****..*..** | .......*.... | [INFO] | ***..*..**** | .....*...... | [INFO] | **.*.*.*..** | ...*...*.... | [INFO] | **..*.*...** | ..*......... | [INFO] | ****...***** | ............ | [INFO] | **..*..*.*** | ..*.*....... | [INFO] | **.*...***** | .....**..... | [INFO] | **.**...**** | ...**.*..... | [INFO] | **.....*.*** | ..*..*...... | [INFO] | ****.*.***** | ....*....... |
This is only half of the spaceship. The end is reported as LlsssEndsReflect(Odd), so the complete spaceship has odd-width bilateral symmetry, with the bottom row of the above pattern representing the center of the ship.
Arbitrary-width searches and disproofs
Both llsss-recentering and llsss-recentering-wao can be run without a width limit by setting the mid_steps value to XX. While this can occasionally be used to find spaceships directly, it is more useful in proving that no spaceships of the specified type exist.
For example, the rule B3/S457 contains a small period-4 c/2 orthogonal spaceship, which can be found with an asymmetric llsss-recentering-wao search using geometry 2c4-f2b and a mid_steps value of 21. However, no period-2 c/2 orthogonal spaceships exist. This can be shown by running the following search:
./rlife llsss-recentering-wao --rule 'B3/S457' c2-f2b '@bg' XX
This search finishes quickly with no results found. Such disproofs can depend on the geometry used. For example, a back-to-front search cannot be used to disprove period-2 c/2 orthogonal spaceships in B3/S457 due to the existence of repeating components.
Seam ripper partials
Under construction.
Extending partial results
Under construction.
Saving and loading the search state
Under construction.
See also
| |||||||||||||||||