Logic Life Search (LLS)

[Scorbie]

One thing that's not obvious is that most JLS settings, including symmetry, are not read by LLS, so they need to be set manually in the command line.

oops... Thank you (I couldn't test this as my computer is currently busy, but I did not set symmetry on so I'm pretty sure this was the problem.)

[LaundryPizza03]

Why can't I search D2\ anymore?

Code: Select all

% ./lls -S cadical -b 15 15 -s p26 x8 y8 -s 'D2\\' -p "=3" -r pB0c1ce2a345678/S0123456-a
Getting search pattern...
Traceback (most recent call last):
  File "/Users/gb/logic-life-search/./lls", line 277, in <module>
    assert transformation in ["RE-", "RE/", "RE|",
AssertionError: Symmetry argument "D2\\" not recognized

EDIT: fixed by deleting the quotes.

[Macbi]

Why can't I search D2\ anymore?

Code: Select all

% ./lls -S cadical -b 15 15 -s p26 x8 y8 -s 'D2\\' -p "=3" -r pB0c1ce2a345678/S0123456-a
Getting search pattern...
Traceback (most recent call last):
  File "/Users/gb/logic-life-search/./lls", line 277, in <module>
    assert transformation in ["RE-", "RE/", "RE|",
AssertionError: Symmetry argument "D2\\" not recognized

EDIT: fixed by deleting the quotes.

Yes, nothing between single quotes needs to be escaped. So you could also write

Code: Select all

./lls -S cadical -b 15 15 -s p26 x8 y8 -s 'D2\' -p "=3" -r pB0c1ce2a345678/S0123456-a

[LaundryPizza03]

This search returns null instead of finding the dot:

Code: Select all

 ./lls -S cadical -r B0148/S6 -b 1 1 -s p2 -a p1 -p ">=1"
 

Compare:

Code: Select all

./lls -S cadical -r B0148/S6 -b 2 1 -s p2 -a p1 -p ">=1"

EDIT April 13: Found another example.

Code: Select all

% ./lls -S cadical -r B01347/S6 -b 4 4 -s p2 -a p1 -p ">=1"
Getting search pattern...
Done

Preprocessing...
Done

Width: 6
Height: 6
Duration: 3

Number of undetermined cells: 32
Number of variables: 97
Number of clauses: 5456

Unsatisfiable

Total solver time: 0.0070149898529052734
% ./lls -S cadical -r B01347/S6 -b 5 4 -s p2 -a p1 -p ">=1"
Getting search pattern...
Done

Preprocessing...
Done

Width: 7
Height: 6
Duration: 3

Number of undetermined cells: 40
Number of variables: 121
Number of clauses: 7808

x = 7, y = 6, rule = B01347/S6
bbbbbbb$
bbobbob$
bbboobb$
bbboobb$
bbobbob$
bbbbbbb!


Total solver time: 0.009531974792480469

[Sokwe]

To simplify the use of jls-to-lls.py, I made the following patch that allows LLS to read JLS status files (.jdf files) directly:

I went ahead and merged these into LLS (version 5).

I've made a major improvement that allows LLS to read settings directly from the input .jdf file (before it only read the grid). If the input is a .jdf file and the -j option is used to save output to .jdf files, then the output files will have the same settings as the input file (before it only saved .jdf files with default settings). Any settings given to LLS on the command line will override the settings obtained from the .jdf file; however, these command line settings will not be copied to the output .jdf files created by the -j option.

Here is the patch. I did not update the version number.

jls-to-lls-v2-patch.zip

(4.76 KiB) Downloaded 48 times

Several JLS settings are still unsupported. Here is the list of currently supported settings:

• Rule (limited to Life-like rules)
• Subperiods
• Static symmetry
• Max pop in generation 0
• Max active cells (i.e. rotor cells) per layer

[LaundryPizza03]

What we really need is INT support in JLS. Then we can translate such problems to LLS.

[Sokwe]

Inspired by discussion on Discord, here is a patch to LLS that allows searching for polyomino predecessors.
Edit: the following description for polyomino searching has been superseded by the modification described in this post.

jls-to-lls-v3-patch.zip

(5.4 KiB) Downloaded 62 times

Including the command line option

Code: Select all

--polyomino <column> <row>

Forces generation 0 of the solution to be a polyomino with an ON cell at the location specified by <column> <row>. The reason for the specified initial cell is to reduce the time it takes to generate all of the clauses for the search. In fact, when using this feature you almost certainly want to include the following option as well:

Code: Select all

--polyomino_max_path <max_path_length>

Here <max_path_length> is the maximum (taxicab) length of a path through the polyomino starting from the initially specified point. By default, this is set to width*height - 1, which is so large that it makes both the preprocessing and searching take a long time. You can typically just set the initial cell to be near the center of the pattern and set <max_path_length> to approximately width+height. This can reduce a search that would take several minutes using the default setting down to just a few seconds.

I also added two other features in this patch:

• With this patch, LLS can now run a predecessor search from a JLS status file (i.e., one where "After the last generation is..." is set to "Unknown")
• JLS subperiods 4, 5, and 6 no longer apply to the layer_max_rotor limits described here. This allows the user to specify such bounds, but then ignore those bounds in a specified area. This might be useful when search for a catalytic oscillator where the rotor near the point of contact must be wide, but you want to reduce the rotor width outside of that nearby area. However, this means that you must be very careful when using the layer_max_rotor in conjunction with subperiods, as the limits will only apply if using the full period or subperiods 1, 2, or 3. That is, if you want to search with subperiod 5, and limit the rotor per layer, you will need to set one of subperiods 1, 2, or 3 to be period 5.

I went ahead and merged these into LLS (version 5).

Can you add this latest patch to the LLS repository? It incorporates all previous patches mentioned in this thread. I relinquish all copyrights, of course.

[Macbi]

Thanks. I'll merge that eventually but I'm a bit busy to do it right now. It would be faster if you could make a merge request in GitLab: https://gitlab.com/OscarCunningham/logic-life-search.

[Sokwe]

It would be faster if you could make a merge request in GitLab

Alright, I've done that, simply using the latest patch as a single commit. I did not update the version number. Let me know if I did anything wrong or if there's anything I could do to make the process better.

Edit:
I modified the polyomino predecessor code so that you no longer need to specify a starting cell. Instead, you simply use

Code: Select all

--polyomino [max_radius]

where max_radius is optional and has the same meaning as max_path_length. If you think of the polyomino as a graph whose vertices are the ON cells with edges representing cell adjacency, then max_radius is the maximum allowed radius of this graph.

This modification is available in this fork of LLS.

[Sokwe]

Is it maybe possible to find another set of bait still lifes that allows the signal to escape while causing an even smaller change to the end of the wire?

It is not so difficult to find similar "controlled collapse" terminations for the wire using LLS, with many possibilities for signal extraction.... here is my LLS input file if someone wants to have a look (use with the -s "D2-" option)

Code: Select all

...

This gives an excellent demonstration of JLS fixed cells. When a cell is set fixed in JLS, it takes the state of the cell at the same position in the previous generation. I've recreated your LLS input as a JLS status file if anyone is interested:

fixed-cell-example.zip

(1.88 KiB) Downloaded 52 times

I generally don't use fixed cells, so I've been looking for an interesting example search that utilizes them.

[Macbi]

Thanks, merged. (Version 6)

[Sokwe]

I pushed some preliminary new features to my fork of LLS. This adds the following options:

Code: Select all

--forbid_cell_frequencies <cell_frequency_list>
--forbid_cell_subperiods <cell_frequency_list>
--allow_cell_subperiods <cell_subperiods_list>
--strictly_volatile

the cell_frequency_list and cell_frequency_list are space-sparated lists of positive integers.

The purpose of --allow_cell_subperiods is to allow subperiods of subperiods that would be forbidden by --forbid_cell_subperiods. For example, if `forbid_cell_subperiods 2` is used, it will forbid cells from having period 2 or 1, since period-1 cells have the same state after 2 generations, so get counted as period-2. By using `forbid_cell_subperiods 2 -- allow_cell_subperiods 1`, the search will allow stator cells, but will not allow p2 cells.

I doubt these features will see much use outside of some specific silly attempts to find low-period oscillators with unusual cell frequency/subperiod properties.

The features could be integrated with my undocumented use of the JLS subperiod table to ignore restrictions in regions marked with subperiods 4, 5, and 6, but it would be slightly more work, so I don't plan to do it at the moment, especially since I doubt anyone is desperate to use such a feature.

[yaochen2]

Can someone add the ability to search for agars and the ability to set a minimum density for the pattern?

[Sokwe]

Can someone add the ability to search for agars and the ability to set a minimum density for the pattern?

I'm not about to do this right now, but if someone wants to, I think they would only need to edit the function neighbours_from_coordinates() in src/literal_manipulation.py. This function returns the neighbours of the parent of a given cell (or the neighbours of the cell itself if you pass t_offset=0). At the boundary it uses the background grid to determine neighbours. It could instead be rewritten to connect to another part of the board.

[LaundryPizza03]

I get this warning on every run while running LLS with Python 3.13.5:

Code: Select all

~/logic-life-search/./lls:40: SyntaxWarning: invalid escape sequence '\ '
  help="""Impose a symmetry on the pattern Examples: "D4x" enforces reflection symmetry about both axes, "p7" enforces period 7, "p2 RE\ x1" imposes the glide-reflect symmetry of a glider."""

Updating every literal backslash in strings to \\ should fix this.

[Sokwe]

I've tried LLS and it seems to be going slow, but maybe that's an issue with either my patience, my computer, or the existence of p5s and p7s in that rule.

The difficulty is often in setting up an effective search. I suspect LLS could at least find both p5 and p7 oscillators fairly quickly with the right setup. Here's what I recommend.

First, get a good SAT solver. The fastest I'm aware of is AE_kissat2025_MAB available here. You will need to compile it from the source code. Let me know if you have any difficulties at this step.

Second, get Karel Suhajda's get JavaLifeSearch program. This is a search program with a nice graphical user interface written in Java. Unfortunately, it only supports Life-like rules, not INT rules like you want, but that's okay, because we only need to use it to set up the search which we can then run with LLS.

The steps below explain how to set up a simple symmetric p5 search with JLS and run it with LLS. I'll let you figure out the p7 search. We will need to perform two searches, although only the first one is really difficult. In the first search we find the rotor. In the second search we complete the stator. Don't be intimidated by the length of these instructions. I simply went into perhaps greater than necessary detail to make them more clear.

Finding the rotor:

1. Run JavaLifeSearch. This should bring up a window with a grid, some menus at the top, and a generations slider at the bottom. We will want to change a few settings for our search:
   • Go to "Search->Options...", and under the "Processing" tab uncheck "Preprocess while editing". This feature is only useful for Life-like rules, but we are searching an INT rule.
   • Go to "Edit->Properties...", and under the "Edit Field" tab change the "Generations (depth)" to 5 (this is the period) and change symmetry to "vertical mirror".
2. Next we need to edit the grid. I've broken this down into a separate set of steps:
   1. Pick a rotor width. It should be something small to start with. If that fails, we can make it larger until it succeeds or takes too long. I'll start with a rotor width of 5. The central 5 rows of the grid will be our rotor (we haven't made any changes to the grid yet).
   2. Set all the cells above and below the rotor to be stator cells (i.e., period-1). To do this, highlight the cells and press the '1' (one) key. These cells will then be period-1 and will be highlighted in yellow. If you want to change stator cells back to rotor cells, select them and press the '0' (zero) key.
   3. Set the leftmost 4 columns to be stator cells.
   4. Leave two layers of stator cells around the rotor just as they are (i.e., EMPTY), then set the next two layers to UNSET by highlighting them and pressing shift+U. Holding shift when pressing 'U' causes the cells to be UNSET in all generations, not just the current generation. These UNSET cells are marked with a hash mark (#). These UNSET cells do not have to obey the given CA rules. This allows us to find a rotor with only a partial stator that we can complete later.
      
      If you want to set cells back to EMPTY, highlight them and press shift+C (or just 'C' to only clear the cell in the current generation).
   5. Set the rightmost two columns to be UNSET.
   6. Set all outer layers to OFF in all generations (highlight and press shift+A or shift+right-click).
   7. Now we need to set a leftmost rotor cell. To do this, choose a cell in the leftmost rotor column (I chose the center cell), and left-click to set it ON in the current generation (should be gen. 0). Then change the generation to gen. 1 with the slider at the bottom of the window and set the cell in the same position to OFF (right-click).
   After the above steps, your grid in gen. 0 should look something like this:

   

   example-grid.png (3.89 KiB) Viewed 3374 times

   The grid in gen. 1 will look almost the same, except the filled blue circle should instead be an empty blue circle. Notice that the right side of the rotor is not bounded by stator cells. This means that if the search returns "unsatisfiable", then there are no possible solutions at this rotor width. You could then increase the rotor width by 1 and try again. Unfortunately, this may also lead to incomplete "solutions" work only up until they hit that edge. In that case, you might want to set the right side to also be stator cells in order to (hopefully) find a complete solution.
3. Go to "File->Save..." and save the state in your LLS folder with a .jdf file extension. I called it "example-p5-search.jdf", but you might want a more descriptive name.
4. Run LLS using the saved file as input, and use the `-j <folder-name>` option to save the output in .jdf format. Since JLS does not support INT rules, you will also need to add the rule to your LLS command. For example, your command line might look like this:

   Code: Select all

   ./lls example-p5-search.jdf --rule B2-an4cew5i6-ae8/S12-ik3j4en5cijn6-ae78 -j p5-output

   This will search until it finds a single solution, which it will save as a .jdf file called "p5-output_0.jdf". Hopefully the solution will become stable on the right side at some point, despite the fact that we did not specify that the right end be part of the stator. If not, you may need to set the right side to be stable as well and run the search again.

Assuming we got a solution from our first search, we now need to complete the stator.

Completing the stator:

1. Open the output .jdf file from the first search.
2. Since this search was in an INT rule, the grid will have red all over it, indicating errors. To clear these errors, go to "Search->Options...", make sure "Preprocess while editing" is unchecked, and click "OK". Even if this option is already unchecked, it will still show errors until you go to this menu and click "OK".
3. Presumably the search will have found some complete rotor surrounded by stator cells. Rotor cells can be identified by their thicker black border. Identify the rotor cells you want to keep, and set all other cells to stator cells (select them and press '1', which highlights them in yellow). There may be some disconnected rotors or partial rotors at the right side that you don't want to keep. Set these to be stator cells as well.
4. Clear all stator (yellow) cells by selecting them and pressing shift+C.
5. Optionally, set some of the outer cells to be OFF by selecting them and pressing shift+A. This is to limit the bounding box of the oscillator (overly large bounding boxes are generally considered less desirable).
6. Go to "File->Save..." and save the state in your LLS folder with a .jdf file extension. For example, you might save it as "p5-stator.jdf".
7. Run the search with LLS. Since the output will be a complete oscillator, there's no need to use the `-j` option. Simply copy the RLE output into your favorite Life editing software. Your command line might look something like this:

   Code: Select all

   ./lls p5-stator.jdf --rule B2-an4cew5i6-ae8/S12-ik3j4en5cijn6-ae78

8. If the stator search returns unsatisfiable, you may need to remove some of the OFF cells around the edges to make the bounding box bigger. If you've already removed all of the OFF cells and the search is still returning "unsatisfiable", you will likely need to expand the search area. Go to "Edit->Properties..." and increase the "columns (width)" and "rows (height)" as needed. You will then need to move your rotor cells away from the edges. You can do this by selecting the whole grid and using ctrl+shift+arrow-keys. Unfortunately, the stator cell designations (yellow highlighting) does not move with the pattern, so you will need to make those changes manually after moving the pattern (use the '0' key to set a cell as a rotor cell).
9. Optionally, you can limit the number of cells in gen. 0 of the solution using the `-p` option in LLS. For example, running

   Code: Select all

   ./lls p5-stator.jdf --rule B2-an4cew5i6-ae8/S12-ik3j4en5cijn6-ae78 -p '<=50'

   will only give solutions that have a population of 50 or less in generation 0. Lower population solutions are generally preferred by the community.

Let me know if you have any difficulty following any of these steps.

[UnbihexiumFan]

[*] Run LLS using the saved file as input, and use the `-j <folder-name>` option to save the output in .jdf format. Since JLS does not support INT rules, you will also need to add the rule to your LLS command. For example, your command line might look like this:

Code: Select all

./lls example-p5-search.jdf --rule rule B2-an4cew5i6-ae8/S12-ik3j4en5cijn6-ae78 -j p5-output

I assume you mean

Code: Select all

./lls example-p5-search.jdf --rule B2-an4cew5i6-ae8/S12-ik3j4en5cijn6-ae78 -j p5-output

? Edit by Sokwe: yes, thank you. It has now been corrected.


When I try the command without `-j`, it gives me this:

Code: Select all

$ ./lls p5_width_5.jdf --rule B2-an4cew5i6-ae8/S12-ik3j4en5cijn6-ae78
Getting search pattern...
Traceback (most recent call last):
  File "/home/.../logic-life-search-master/./lls", line 338, in <module>
    grid, ignore_transition = src.search_patterns.search_pattern_from_string(input_string)
  File "/home/.../logic-life-search-master/src/search_patterns.py", line 11, in search_pattern_from_string
    grid, ignore_transition = src.formatting.parse_input_string(input_string)
  File "/home/.../logic-life-search-master/src/formatting.py", line 40, in parse_input_string
    assert (all(
AssertionError: Search pattern is not cuboidal

And when I try it with `-j`, it gives me this:

Code: Select all

$ ./lls p5_width_5.jdf --rule B2-an4cew5i6-ae8/S12-ik3j4en5cijn6-ae78 -j p5-output
usage: lls [-h] [-b BOUNDS [BOUNDS ...]] [-s [SYMMETRY ...]]
           [-a [ASYMMETRY ...]] [-c [FORCE_CHANGE ...]]
           [-p [constraint [GEN_0 ...]]] [-o OUTPUT_FILE_NAME] [-M METHOD]
           [-S SOLVER] [-t TIMEOUT] [--csv] [-V] [-v VERBOSITY]
           [-n [NUMBER_OF_SOLUTIONS]] [--save_dimacs [SAVE_DIMACS]]
           [--save_state [SAVE_STATE]] [--dry_run] [--parameters PARAMETERS]
           [-r RULE] [--background BACKGROUND]
           [--background_offset BACKGROUND_OFFSET BACKGROUND_OFFSET BACKGROUND_OFFSET]
           [--max_change MAX_CHANGE] [--max_decay MAX_DECAY]
           [--max_growth MAX_GROWTH]
           [input_file_name]
lls: error: unrecognized arguments: -j p5-output

[Sokwe]

When I try the command without `-j`, it gives me this:

Code: Select all

...

And when I try it with `-j`, it gives me this:

Code: Select all

...

This is because you don't have the latest version of LLS. Please update LLS and try again.

[UnbihexiumFan]

Thank you so much! I was able to find a p5:

Code: Select all

x = 12, y = 15, rule = B2-an4cew5i6-ae8/S12-ik3j4en5cijn6-ae78
5bo$3b3obo$o3b4obo$ob8obo$3b4ob3o$2bo4b4o$4b2ob4o$b2obob5o$4b2ob4o$2b
o4b4o$3b4ob3o$ob8obo$o3b4obo$3b3obo$5bo!

But when I tried p7 at width 7, it gave me the trivial solution where all the rotor cells are on.

The input was:

p7_width_7.zip

(1.26 KiB) Downloaded 40 times

The output was:

p7-output_3.zip

(1.24 KiB) Downloaded 40 times

Do you know what's going on?

[Sokwe]

when I tried p7 at width 7, it gave me the trivial solution where all the rotor cells are on.

Do you know what's going on?

You set the first rotor cell ON in gen. 0, which is good, but you also need to set it OFF in gen. 1. Go to the slider at the bottom of the window and change it to gen. 1. Then right-click on the cell that you set ON in gen. 0 to set it OFF in gen. 1.

[UnbihexiumFan]

Thank you so much! I found a p7:

Code: Select all

x = 14, y = 13, rule = B2-an4cew5i6-ae8/S12-ik3j4en5cijn6-ae78
4bo4bo$b2obob2obob2o$2o10b2o$4b2o2b2o$3bob4obo$2bo8bo$2bob2o2b2obo$2b
o8bo$3bob4obo$4b2o2b2o$2o10b2o$b2obob2obob2o$4bo4bo!

[Rhombic]

Are there any ways to use LLS to generate partials for high-period oscillators or spaceships? It would seem like, understandably, with every generation the clauses grow so much that it blows up unless you limit the search to a few cells (which limits its usefulness). However, I would imagine that there should be some strategy to at least get some useful results when starting from a known partial solution - imagine we had another "almost knightship" but of much higher period. Wrong tool for that sort of problem?

[dvgrn]

Are there any ways to use LLS to generate partials for high-period oscillators or spaceships? ... imagine we had another "almost knightship" but of much higher period. Wrong tool for that sort of problem?

For a lot of these kinds of questions it seems useful to think in these terms:

Suppose we had a tool that could successfully solve Difficult Problem X. What is the list of Not-So-Difficult Problems that that hypothetical tool would also solve?

In this case, we do have the (2,1)c/6 and (2,1)c/7 almost knightships. All other things being equal, for every result from a hypothetical search tool at a much higher period like (2,1)c/18 or some such, we're very likely to see a whole lot of results (either positive or negative) at lower periods like (2,1)c/6 and (2,1)c/7. Those lower periods are much smaller search spaces, hugely easier to deal with, so the odds are that the same search resources could find thousands of interesting new small medium-period spaceships before turning up the first c/18 knightship.

So,,, if a tool like LLS doesn't yet seem to have produced an enormous pile of results on your Not-So-Difficult Problem list, then in practice it's pretty unlikely to be able to tackle your Difficult Problem X. Every now and then somebody will skip over some easy problems and solve a harder problem out of order, but that isn't the way it usually happens. Loafer before copperhead (because loafer is lower period); copperhead before walrus, because copperhead is smaller; etc.

There are exceptions, as usual...
As seen in the Great Oscillator Discovery Project, that rule of thumb doesn't apply to "roll the dice and hope" type searches, where you're not looking for any one specific period in advance. But high-period spaceships seem to be so highly unlikely and so delicately balanced, that these kinds of random fishing expeditions just don't ever turn up much of anything in practice.

Sorry if not helpful -- this LLS question is just something I try to think about occasionally, and then fail to come up with any clever new ideas.

[TheWayOfTheCon]

Recently installed LLS and was trying to find p8 oscillators in a life-like rule, but I kept getting results that were more like a mix of period-2 oscillators. How do I prevent that from happening? Here were the commands I used.

Code: Select all

python lls -s p8 x0 y0 -c 1 8 -b 15 15 -r B3/S13 -p ">12" -s "D2|"

[EvinZL]

Recently installed LLS and was trying to find p8 oscillators in a life-like rule, but I kept getting results that were more like a mix of period-2 oscillators. How do I prevent that from happening? Here were the commands I used.

Code: Select all

python lls -s p8 x0 y0 -c 1 8 -b 15 15 -r B3/S13 -p ">12" -s "D2|"

can you try adding

Code: Select all

--force-change 0 4

to the options? This should tell LLS to make generations 0 and 4 different.