Another Stator Optimizer

[Sokwe]

I have written a Python script that utilizes lifelib and OR-Tools to optimize the stator of patterns in Life-like CA. It is available here:

https://github.com/Matthias-Merzenich/stator-optimizer

This script was inspired by, and meant to be a much faster and more memory-efficient replacement for, Jeremy Dover's OR-Tools-based stator optimizer. I think I've recreated all of the features while simplifying the input.

The script takes as as input a file containing a pattern in RLE (.rle), macrocell(.mc) or rotor descriptor format and the number of ticks to advance the pattern in order to identify the rotor and stator. The script will automatically detect the input format. If the input uses a history rule, you can use the extra cell states to force particular stator cells to be on or off in the solution as follows:

Code: Select all

------------------------------------------------
 history state | input state | solution state
---------------+-------------+------------------
 0 (black)     | off         | either on or off
 1 (green)     | on          | either on or off
 2 (blue)      | off         | off
 3 (white)     | on          | off
 4 (red)       | off         | on
 5 (yellow)    | on          | on
 6 (gray)      | off         | either on or off

This only applies to stator cells, so if a cell with state 2, 3, 4, or 5 is determined to be a rotor cell, then the solution state will be ignored. This allows the script to still work properly even if, for example, you apply it to the history patterns (complete with state-2 cells) from the Catagolue gun collection.

The `-a` option expands the search box. By default, the search box is the original bounding box. If the input pattern is a history pattern, all non-zero states (excluding state 6) will be used to determine the initial bounding box. The `-a` option takes four integers as input representing the amount to extend the search box to the left, right, top, and bottom respectively. Negative values contract the search box.

The option `-b any` tells the optimizer not to check the CA rules at the search boundary (i.e., the boundary cells can be anything). If a search run with `-b any` gives a valid solution, then it's proven to be minimal regardless of bounding box. By "valid" solution, I mean one that is actually stable. If the search bounds are too close to the rotor, then the optimizer can find solutions that intersect the boundary where the CA rules aren't checked, which can result in "stators" that aren't actually stable. If this happens, just increase the search box with the `-a` option and try repeat until you get a valid stator.

There are some other options which are described in the repository's readme.

One issue is that if the input is a rotor descriptor, the script requires lifelib 2.5.9 or higher, but the version on PyPI (i.e., the one pip installs) is version 2.5.6. If you give a rotor descriptor as input, the script will check your lifelib installation, and if it's too low it will use git to automatically clone the latest version to your current working directory and use that. Subsequent runs from the same directory will continue to use the cloned version. If you don't have git (and for some reason don't want to get it), you can also just download the lifelib repository from GitLab and place it into the stator-optimizer folder.

Many thanks again to Jeremy Dover for the idea and original implementation.

[Sokwe]

I've updated stator_optimizer.py to have (I think) all of the features of Jeremy Dover's version while running much faster, using much less memory, and having simpler (in my opinion) input. Below are some example searches:

Checking minimality of a unique father solution:
This is a good example of using forced cells. Obviously without forced cells any still life will just be optimized to nothing. However, we want to require the self-forcing patch to still be present in the solution. To do this we can use state-2 (blue) and state-5 (yellow) cells for the self-forcing patch and state-0 (black) and state-1 (green) cells for the cells that are allowed to change, like so:

Code: Select all

x = 23, y = 22, rule = LifeHistory
6.2A$5.A2.A3.2A$4.BE2BEB2.A3.2A$3.AEB2EB2EBEB.E2.A$3.E2BE2BE2B2E2BE2B
E$.AE2BE2BE2BE2B2EB2EBA$A.B2EB2EB2EBE2BE2BEBA$.A.E2BE2BE2B2E2BE2BE$2A
.2BE2BE2BE2B2EB2EB$.A.B2EB2EB2E2BE2BE2B.2A$.A.E2BE2BE2B2E2BE2BA2.A$2.
ABE2BE2BE2BEB2EBAEBA$3.B2EB2EB2E2BE2BE2BE$3.A2BE2BE2B2E2BE2BEB$3.2A.
2BE2BE2B2EB2EB$7.2EB2E2BE2BE2B$6.A2BE2B2E2BE2BE$5.A.E2BE2BEB2E.2A$5.A
.2EB2E2BEB.A$6.A.BEB4.A.A$7.A.A6.A$8.A!

Now it might be possible that any solution with a smaller population has a larger bounding box. To guarantee that the solution is minimal, we can choose large `-a` values and use `any` boundary. Since this is a still life, we don't need to advance it at all, so we set `ticks` to 0. Here is our input and the resulting output (where the above pattern was saved as unique-father.rle):

Code: Select all

$ ./stator_optimizer.py unique-father.rle 0 -a 10 10 10 10 any
Analyzing pattern...

Initial objective values:
  Stator population: 154

Setting up optimization search...
  Undetermined cells: 1729
  Variables: 2025
  Constraints: 3882
Beginning optimization search...

Optimal solution found.

Input pattern is already optimal.

Note that if we did not include `-a` (or if we instead used small values), the search would find a new "optimal solution", but it wouldn't be valid, because it would intersect the boundary and the `-b any` option tells the search not to apply the CA rules at the boundary.

Minimizing the Snark:
The input pattern does not need to be and oscillator or a gun. Consider the following snark variant, which is not minimal in population:

Code: Select all

$ ./stator_optimizer.py snark.rle 50 -a 0 5 5 0
Analyzing pattern...

Initial objective values:
  Stator population: 38

Setting up optimization search...
  Undetermined cells: 493
  Variables: 642
  Constraints: 2192
Beginning optimization search...

Optimal solution found.

Final objective values:
  Stator population: 35

x = 18, y = 23, rule = B3/S23
8b2o$8bobo5b2o$10bo4bobo$6b4ob2o2bo$6bo2bobobob2o$9bobobobo$10b2ob
obo$14bo2$2o$bo7b2o$bobo5b2o$2b2o6$5b3o$7bo4b2o$6bo5bo$13b3o$15bo!

Here is the output pattern by itself:

Code: Select all

x = 18, y = 23, rule = B3/S23
8b2o$8bobo5b2o$10bo4bobo$6b4ob2o2bo$6bo2bobobob2o$9bobobobo$10b2ob
obo$14bo2$2o$bo7b2o$bobo5b2o$2b2o6$5b3o$7bo4b2o$6bo5bo$13b3o$15bo!

Reducing the bounding box of a p24 gun:
Normally, stator_reducer.py will only print a solution if it is smaller than the input. However, if the input stator is not within the search bounds it will print the solution. Consider the following p24 gun, which is minimized for population, but not bounding box:

Code: Select all

x = 21, y = 20, rule = LifeHistory
.A$.3A$4.A9.2A.2A$3.2A8.B2A.A$3.5B5.3B.A$5.4B3.B3A.A.2A$3.A3B2A4B3A.A
.A$2.A3B2A2B2.A.B.2A.A$2.A7B3.2A3.A$2.BA6B5.3A$4.5A2B4.A$3.2B3A3B$3.
3BA2B.B2A$3.6B.BA.A$3.6B4.A$4.5B4.2A$2.B.5B$B3A2.3BA$3AB3.3BA$.B6.3AB
!

The input pattern has 72 on cells, and if we try to optimize this without the `-a` option, we will get the message "Input pattern is already optimal." Now if we contract the right side of the search box by one cell we instead get

Code: Select all

$ ./stator_optimizer.py p24-gun.rle 24 -a 0 -1 0 0
Analyzing pattern...

Initial objective values:
  Stator population: 37

Setting up optimization search...
  Undetermined cells: 277
  Variables: 402
  Constraints: 1731
Beginning optimization search...

Optimal solution found.

Final objective values:
  Stator population: 39

x = 20, y = 20, rule = B3/S23
bo$b3o13b2o$4bo9b2o2bo$3b2o9b2obo$17b2o$13b3obo$3bo3b2o4b3obo$2bo
3b2o4bo3b2obo$2bo10b2o3b2o$3bo11b2o$4b5o6bo$5b3o9bo$6bo4b2o3b2o$
11bobo$13bo$13b2o2$b3o5bo$3o7bo$8b3o!

Despite being larger in population, the solution is printed, because the original stator extends outside of the search area. Here is the output pattern by itself:

Code: Select all

x = 20, y = 20, rule = B3/S23
bo$b3o13b2o$4bo9b2o2bo$3b2o9b2obo$17b2o$13b3obo$3bo3b2o4b3obo$2bo
3b2o4bo3b2obo$2bo10b2o3b2o$3bo11b2o$4b5o6bo$5b3o9bo$6bo4b2o3b2o$
11bobo$13bo$13b2o2$b3o5bo$3o7bo$8b3o!

[Sokwe]

I added the `-b any` option, which tells the search not check the CA rules at the search boundary. This means that if the search finds a valid solution (i.e., one that is actually stable), then that solution is minimal regardless of bounding box. If the search finds an invalid solution, just increase the search area and repeat until a valid solution is found.

I also added the `-d <distance>` option which forces the stator to be within the given distance of the rotor in the taxicab metric. This is useful for large, irregularly shaped patterns where a rectangular search area would have a lot of space in the corners that should obviously be off, but can sometimes waste the solver's time. When using the `-d` option, the search is still limited by the bounding box. If you want to avoid this, extend the rectangular search area by large amounts with the `-a` option (e.g., `-a 100 100 100 100`). Then the `-d` option will be the only thing limiting the search. If there is no rotor (like, for example, the unique father example above), then the distance is measured from the forced cells, rather than the rotor.