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 c3-f2b '@zero:9' --rule 'B3/S23' --left-edge even --filters wcaf > 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.
• 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 options section for more details). In this case we are searching for a ship starting from empty ("zero") rows with "width" 9.
• --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).
• > 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 c3-f2b '@zero' 6 --rule 'B3/S23' --left-edge even --filters wcaf > 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.

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 c3-f2b '@zero' 6 --wao-left-pad 0 --wao-right-pad 0 --wao-idx ALL --rule 'B3/S23' --left-edge even --wao-left-edge-errors > 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.

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. These arguments are described below in the order they must be given. The third argument 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 can be either a file or a magic grid generator.

mid_steps

mid_steps can be thought of as the "width" of a recentering search