Stator Reduction and OR Tools

[jeremydover]

OR Tools is an operations research optimization package, and one its key components is CP-SAT, a constraint programming interface to a SAT solver. Leveraging this package, I've written a python program that can input an RLE file of an oscillator or gun, and determine the minimum size of a stator for that object that preserves the rotor. (Caveat: "minimum" is a nuanced word here...it can minimize over its search space.) Some key features:

1. By default, the bounding box is the search space, but the boundaries can be adjusted larger, or smaller (to find reduced width/height variants).
2. For oscillators, the actual bounding box is determined from the pattern, even if the input pattern is smaller. Guns require the bounding box to be accurate, since the code assumes any growth outside the original is a spaceship leaving.
3. Sections of the original pattern can be preserved, e.g. clearance around sparks.
4. Stator cells in the original pattern can be forced blank, e.g., to create clearance around a spark.

Already sold? You can download it from my git repository at https://github.com/jeremydover/CGOL-Stator-Reducer. Please note this is barely an alpha version, so please don't hesitate to criticize (constructively, please), or offer up bugs or improvements.

Need more convincing? I've gone through all of the named p3 oscillators in LifeWiki, and was able to find minimum stators based on population, width, and height. When I say minimum, I likely mean it...I increased the search space by 20 cells on each side of the original bounding box. Some of the more interesting reductions:

Karel's domino sparker, 246P3 (246 -> 235):

Code: Select all

x = 30, y = 24, rule = B3/S23
14b2o2$4b2o3bob2o4b2obo3b2o$3bo3bobo3b4o3bobo3bo$3bobo5bo2b2o2bo5bobo$
2obo6b2o2b2o2b2o6bob2o$bo2b3o4b2o4b2o4b3o2bo$bo5b3o3b4o3b3o5bo$2b4ob3o
10b3ob4o$8bo4b4o4bo$4bo3b2o10b2o3bo$4b3o3bo2bo2bo2bo3b3o$2b2o3b2o3b6o
3b2o3b2o$3bobo4b2o2b2o2b2o4bobo$3bob2obobo3b2o3bobob2obo$2b2o2bob5o4b
5obo2b2o$bo2bob2o4b6o4b2obo2bo$2bobobobobo8bobobobobo$b2obo6b2o2b4o6bo
b2o$4b2o2b2o2bo2bo4b2o2b2o$b2obo2bo2b2o6b2o2bo2bob2o$bo3b2o2bo7bo2bo2b
2o3bo$2b3o5bobo5b2o5b3o$4bo6b2o12bo!

Mini pressure cooker (28 -> 23):

Code: Select all

x = 9, y = 10, rule = B3/S23
4bo$2b3o$bo3b2o$o2bo3bo$b3obo2bo$7b2o$3b2o$3bo$4bo$3b2o!

Protein (40 -> 30):

Code: Select all

x = 10, y = 10, rule = B3/S23
5bo$4bobob2o$4bob2obo$b2obo$2bobob3o$2bo6bo$2o2b2o2b2o$bobo$bobo$2bo!

It also works for larger periods, e.g.,
124P21 (124 -> 120):

Code: Select all

x = 34, y = 25, rule = B3/S23
21bo$21bo$10bo2bo7bo$10b4o6b2o$8b2o8bo$4b2obobob2obo2bo4bo$4b2obo3bob
2o2bo$7b2o10b3o$4b3o$3bo2bo20b2o$3b2o14bo7bobo$b2o10b3o2bobo8bo2bo$2bo
b2o22b2obobo$2bobo8bobo2b3o10b2o$b2o2bo8bo14b2o$4b2o21bo2bo$27b3o$12b
3o4b2o4b2o$16bo2bo2bo3bob2o$11bo4bo4b2obobob2o$15bo8b2o$12b2o6bob2o$
12bo7b2obo$12bo$12bo!

This code was also used with a period 56 hassler in this post.

[dvgrn]

Unfortunately I don't have a whole lot of time to dive into this just at the moment, but there's a question that seems somewhat along the constraint-programming / SAT solver lines, that I've been wanting to figure out.

The problem involves finding a pattern that's the most distant possible ancestor of an arbitrary starting pattern. Assume the starting pattern isn't glider-constructible, or at least not known to be glider-constructible, since otherwise there's an obvious candidate for "rewinding" the starting pattern for any number of ticks you might want.

The size of the ancestor isn't all that important, in the sense that a larger but more distant ancestor always trumps a smaller but more recent one.

Does it seem like there might be a way to apply OR-Tools to that problem?

I don't want to take attention away from the stator-reduction use described above -- just interested to see what other problems it might be applicable to.

[jeremydover]

I put together a relatively naive constraint program to run the distant ancestor problem, and while I successfully got back 10 generations overnight, I'm reaching the point of diminishing returns, and I'm pretty sure my generation 10 is a garden of eden.

This is just, like, my opinion, but in my experience constraint programming does very well when the program is fairly tightly coupled, and flails otherwise. When I say tightly coupled, think of the stator reduction problem: there's a fixed rotor, whose evolution is going to require stator cells nearby, and even though far away cells are allowed to be stator cells, the solver is disincentivized from picking them by the minimization criteria. In the distant ancestor problem, the further back we go the less coupled any individual cell is to the boundary condition.

So a much better approach would probably be to use a SAT solver to find all of the 2 generation ancestor patterns within a certain bounding box, and then run each of those for two steps, and so forth. You can use SAT to take the individual steps, and possibly to score the candidates for promise in some sense, but to guide the search itself outside SAT.

[Sokwe]

I made a fork of this project that breaks many of the features but simplifies the model, allowing the solver to run faster and use less memory.

Basically, the original code uses a model that simulates the entire pattern in all generations. When the period is large, this results in a slow search that requires gigabytes of memory. Instead of simulating the whole pattern, its much more efficient to apply the CA rules to the stator cells and all transitions that occur in rotor cells that border a stator cell. For small, high-period patterns the time bottleneck is now in simulating the pattern, expanding the grid, and analyzing the cells.

At the moment, I only intend for this modification to be used to reduce the Catagolue gun collection, so it makes some assumptions that might not be ideal in other situations. At least some (possibly all) of the options are broken.

[jeremydover]

Not sure how much you've gone through, but I've run the original code on the guntrue base up to 192. I don't really know how to update Catagolue, but am glad to share my data if it would spare you some time.

[Sokwe]

Not sure how much you've gone through, but I've run the original code on the guntrue base up to 192. I don't really know how to update Catagolue, but am glad to share my data if it would spare you some time.

Guns can be submitted to Catagolue by going to the syntheses page, scrolling to the bottom, pasting the gun into the text box, and clicking the "post" button.

I haven't tried to optimize any guns myself. I was just trying to see how effectively the known stator reducers could be used to optimize the gun collection.

Inspired by your program, I wrote a new OR-Tools-based stator optimizer that is available here. It currently only works in Life, only takes LifeHistory patterns as input, and has no features (not even the ability to change the bounding box), but it's quite a bit faster for what it does, because it leverages lifelib for quick pattern evolution and manipulation. I'll create a separate thread for it in a moment.

[I6_I6]

As far as I understand, this script finds the optimal stator that can support a specified rotor, right?
But when I compared jeremydover's recent glider gun reductions with their old versions on LifeWiki, I saw that some of them have a different rotor.
For example, this is the older p14 glider gun that was on LifeWiki:

Code: Select all

x = 72, y = 64, rule = B3/S23
39b2o$38bo2bob2o$37bo2b2obobo$37b2obo4bo$38bo2b2o2bob2o$36bo2bobo2b2o
2bo$35bob3obobo2bo$26bo9bo5bob2o$26b3o8b3o$4b2o23bo10b6o$4bobo4b2o3b2o
6b4o2bo4b3ob2o4bo$7bo3b2o2bobo6bo3b2o4bo3bobob2o$2o3b2obo6bobob2ob2o3b
o4bo2b4obobo$bo2bobob7obobobobo5b6obobo2bo3bo$o3bo2bo8bo3bo2bo4bo6bo2b
o2b4o$4obo2b6o2b2ob6o5b5o3b2o$5b3o4bo2b3obo4bo8bo5bob2o$2o3bobobo4bo5b
ob2o10b2obobobobo$o4bobobob10obo4bo6bo3bobo2bo$b3ob2o2bo12bo3bobo5bo3b
obobo$4bo4b4o2b2o2b2obob3obo4b5o3bo$b2obo7bo2bo4bo2bo4b2o2b5o$bobo7bo
4bo3bo3b4o2bo5bo$10bob4o2b2ob3o4b2o5bo$11bo4b2obobo3b2obobo3b2o3b2o$12b
3obo9bobo2b2obo3bo2bo$14bo2b4o4bo2bo4bo4b3o$15b2o4bo4b3ob3obo$17b5o7b
ob2o3b3o$17bob4o3b2obo4b2o3bo$4b2o8b2obo5bobobob2o4bo3bo$5bo8bo2bo2bo
2bobo3bo2b2o3bob2o$5bobo7b2o2bobobo2bo2bo6b2o3bo$6b3ob2o5b5ob3o2b2obo
6b3o3b2o$8b2obo5bo4bo7b2obo4bo5bo2b2o$8b3o7b3obob6o2b2o11bobo$4b2o3bo
10bobobo9b2o8b2obo2b2o10b2o$4bo2bobo17b2obo2bobo7bo3bobobo10bobob2o$6b
2obo2bo8b3o3bo4bo2bo6b3ob2obo14bobobob2o$10b2o16bo3bo2b2ob2o23b2o3bob
o$29b2ob2o6bo5b2o4b2ob2o7bo3bo2bo$22bo9b2o3bo2bo4b3o3b6o2b2o2bo5b2o$21b
3o13bo2bo3bo13bo5b5o$11b2o7b5o12b2obo3b2o4bobo2bobo3bo6bo$11b2o6b2o3b
2o12bobo3bo3bobob2obob11o$10bo8b2ob3o13bobobobobobobo14bo$9b3o8b4o15b
obob2ob2o2bobob9o$19bo2bo18bo3bo4bob2o5bo2bo$40b2o3bob3o5b2o$14b3o7bo
21b2o8bo$15bo7bobo28bo$13b2o9bo29b2o$13b2o4$14b2o$14bobo$15b2o2$12b2o
$13bo$10b3o$10bo!

Here's the guntrue_14 that's currently on catagolue (which I'm assuming is the reduced version by jeremydover):

Code: Select all

#C [[ GRID MAXGRIDSIZE 14 THEME Catagolue ]]
#CSYNTH guntrue_14 costs 4320 cells.
#C period 14 fullperiod 14 bbox 72 by 60
#CLL state-numbering golly
x = 72, y = 60, rule = LifeHistory
38.2A3.A2.A2.A$38.A2.3A2.6A4.2A$39.2A3.2A6.A3.A$26.2A5.A2.A3.2B2A
2.2A2B2A.A3.A2.2A$26.A6.7AB2.A2BA.AB.A.4A.A2.A$4.2A21.A12.3A3.B2A
2BAB3.A.2A$4.A.A4.2A3.2A6.4A2.A4.3AB2A2.4A2.B.A3B2A.A$7.A3.2A2.A.A
6.A3.3A3.A2.BA.ABA4.6AB.BA.A.A2.A$2A3.2A.A6.A.A.2A.2A2.BA5.A.4A.A.
A.2A7.BA.A3B4A$.A2.A.A.7A.A.A.A.A3.2B6A.A.A2BA2.A.A.6A.A.A.B$A3.A.
BA6.B.A.B.A.BAB.2BAB5.A2BA.B2A3.2A5.2A.6A$4A.A.B6A2B2A.6AB.3B5A2.B
2A10.2A3.A5.A$3.B.3A.B2.A.B3ABA.B2.AB4.2B.A.3B.A.2A7.A4.A.4A$2A3BA
.A.A2B2.A.B3.A.2AB6.3B2ABA.A.A.A7.A4.A.A$A2.B.A.A.A.10A.A4.A4.2BA
3BA.A2.A6.2A$.3A.2A2.A12.A3.A.A4.BA.B.A.A.A$4.A4.6A2.A.2A.A.3A.A3.
B5A3.A$.2A.A9.A2.2A.A2.A4.2A2B5A$.A.A7.A8.A4.3A2.AB.3BA$10.A.A3.A.
2A.4A3.2A5BAB$11.A4.2A.A.A3.A2.A.A3B2A4.2A$19.2B3.A.A.A.B2ABAB2.A
2.A$16.5A4.A2.A.2B.A2B2.3A$16.A2.2BA4.3A.3ABAB$17.5A7.A.2A3B3A$13.
A.A.A.4A3.2A.A.3B2A.B.A$9.2A.A.2A.A.4BA.A.A.2A.2B.A2B.A$8.A2.2A4.A
2BAB.A.A3.A.B2A2B.A.2A$7.A.A3.4A2.A.A.A2.A2.A.4B.2A3.A$8.A.2A5.5A.
3A2.2A.A2B4.3A3.2A$10.A.4A.A3.BA7.2ABAB3.A5.A2.2A$8.A.A.A2.A2.3A.A
.6A2B2A2B9.A.A$7.A.3AB3.2A2.ABABA5.4B2AB7.2A.A2.2A10.2A$7.A3.B5.A
3.3B3.2ABA2BABAB5.BA3.A.A.A10.A.A.2A$8.AB2A4.A4.3A3.A.3BAB.AB3.2B
3AB2A.AB13.A.A.A.2A$6.A.A.A2B3.2A4.B5.A3BA2B2A.2A.5B.4B12.2A.B.A.A
$6.2A2.3B8.B.B4.B2AB2A6BA5B2A4B2A.2AB.2B.B.A3BA2.A$11.3B7.BAB4.4B
2A2B.A2BAB2.B3A2B.6A2B2AB.A.2B2.2A$11.4B5.B3A2B.7B.2BA.BA3BA2B.2B.
3B.B.BA5B5A$10.B2A4B2.B5A5B5.2B2ABA3B2A4BABA2BABA3.AB5.A$8.3B2A4B
2.2A3B2A4BA7.A.A.B.A3BA.A.2ABA.11A$6.4BA6B2.2AB3A3BABAB6.A.A.A.A.A
.A.A.B.B10.A$5.4B3A7B.4A2B3.2A2B6.A.A.2A.2A2.A.A.5A2.2A$5.14BAB.AB
6.3BA7.A3.A4.A.2A5.A2.A$6.15B2.2B6.3BA5.2A3.A.3A5.2A2.2A$7.7B3A4B.
2BAB6.3AB10.2A8.A$9.6BA4B3.A.A7.4B17.A$9.4B2A3B6.A9.3BA16.2A$9.4B
2AB19.ABAB$11.4B21.2A2B$12.3B22.3BA$13.3B22.3BA$13.B2A23.3AB$13.BA
.A23.4B$14.B2A24.3BA$12.4B26.ABAB$12.2A29.2A2B$13.A30.3BA$10.3A32.
3BA$10.A35.3AB!

The top part has a different rotor.
Can this script also adjust the rotor, or was there an intermediate version that I missed?

[Sokwe]

Can this script also adjust the rotor, or was there an intermediate version that I missed?

No, this program, as well as my version and Keith Amling's rstatoropt only reduce the stator while leaving all parts of the rotor unchanged. It's difficult to search for rotor reductions, because that essentially amounts to finding whole new supporting components. It would probably be possible to optimize a p2 supporting rotor and maybe some smaller p3 supporting rotors, but beyond that you're generally lucky just to find any solution at all, and you're not likely going to be able to prove that it's optimal.

[HartmutHolzwart]

Could we have something similar to optimize the p2 part of c/2 puffer engines? Or is that not tractable with the same means. I was recently scanning through the c/2-extended section of jslife-moving, especially the 4n+2 period results. It would be nice to have that minimized.

[Sokwe]

Could we have something similar to optimize the p2 part of c/2 puffer engines? Or is that not tractable with the same means. I was recently scanning through the c/2-extended section of jslife-moving, especially the 4n+2 period results. It would be nice to have that minimized.

It could certainly be done, but it would take some rewrites to identify the p2 parts of a spaceship and set up an appropriate model, and I'm not sure if it would run fast enough to be useful. An easier problem to try first would be a model that minimizes the p2 part of an oscillator. If that works well, it might be reasonable to try this method with spaceships.