rstatoropt

For scripts to aid with computation or simulation in cellular automata.
Post Reply
amling
Posts: 704
Joined: April 2nd, 2020, 9:47 pm

rstatoropt

Post by amling » November 16th, 2021, 2:32 pm

Automated, best-effort stator optimization in strips:
https://github.com/amling/rstatoropt

EDIT 2023/12/06: moved to https://codeberg.org/amling/rstatoropt

For starters I ran it on a collection suggested to me [1] and it produced quite a few reductions, even when restricted to not increase bounding box.

Some of these might be "right", e.g. a few examined by hand but more or less randomly:

Code: Select all

x = 117, y = 131, rule = B3/S23
5bo2bo2bo66b2o$5b7o66b2o$75bo$5b7o63b7o$4bo7bo60b2o7bo$2obob2o3b2obob
2o53bobo2b2o3b2obo$bobobo5bobobo54b2obobo5bobo$bobo9bobo57bo9bob2o$2ob
o9bob2o56bo9bob2o$bobo9bobo54b2obo9bo$bobobo5bobobo54bo2bobo5bobo$2obo
b2o3b2obob2o55bo2b2o3b2ob2o$4bo7bo60b2o7bo$5b7o63b6obo$75bo5bo$5b7o66b
3o$5bo2bo2bo66bo24$10bo$8b5o$7bo5bo59b2o9bo$7bo2b2obo22bo37bo5b2obobo$
3bob3obobob2o19b5o34bo5bobob2o$3b2o4bo23bo5bo33b2o4bo22bo8b2o$6b2ob2o
22bob2o2bo36b2ob2o20bobob2o4bo$b5obobo2bo19b2obobob3obo27b5obobo2bo19b
2obobo5bo$o6bo3bobo23bo4b2o26bo6bo3bobo23bo4b2o$2o2b5ob2obo22b2ob2o29b
2o2b5ob2obo22b2ob2o$12b2o20bo2bobob5o36b2o20bo2bobob5o$5b2o4b3o12bo6bo
bo3bo6bo28b2o4b3o12bo6bobo3bo6bo$5b2o4b3o5b2o4bobo5bob2ob5o2b2o28b2o4b
3o5b2o4bobo5bob2ob5o2b2o$12b2o4bo2bo3bo2bo4b2o47b2o4bo2bo3bo2bo4b2o$2o
2b5ob2obo5bobo4b2o5b3o4b2o28b2o2b5ob2obo5bobo4b2o5b3o4b2o$o6bo3bobo6bo
12b3o4b2o28bo6bo3bobo6bo12b3o4b2o$b5obobo2bo20b2o36b5obobo2bo20b2o$6b
2ob2o22bob2ob5o2b2o29b2ob2o22bob2ob5o2b2o$3b2o4bo23bobo3bo6bo26b2o4bo
23bobo3bo6bo$3bob3obobob2o19bo2bobob5o27bo5bobob2o19bo2bobob5o$7bo2b2o
bo22b2ob2o33bo5b2obobo20b2ob2o$7bo5bo23bo4b2o29b2o9bo22bo4b2o$8b5o19b
2obobob3obo58b2obobo5bo$10bo22bob2o2bo61bobob2o4bo$33bo5bo62bo8b2o$34b
5o$36bo24$8b2o4b2o61b2o4b2o$7bobo4bobo59bobo4bobo$7bo8bo59bo8bo$4b2obo
bo4bobob2o51bob2obobo4bobob2obo$5bobobo4bobobo52b2obobobo4bobobob2o$4b
o2bobob2obobo2bo56bobob2obobo$4bobo2b2o2b2o2bobo55bo2b2o2b2o2bo$2b3ob
2obo4bob2ob3o53b2obo4bob2o$bo8bo2bo8bo56bo2bo$bo2b5o6b5o2bo50b5o6b5o$
2obo16bob2o48bo16bob2o$bob2o3b2o4b2o3b2obo49b2o3b2o4b2o3b2obo$bo7b6o7b
o55b6o7bo$2b3o2b2o6b2o2b3o48b4o2b2o6b2o2b3o$4bo14bo50bo2bo14bo2$24b2o
67b2o$2b2o2bo13b3o2bo45b2o2bo13b3o2bo$2bo2b2o6bo9b2o46bo2b2o6bo9b2o$3b
5o4bobo4bo52b5o4bobo4bo$12bobo4bo61bobo4bo$13bo9b2o57bo9b2o$3b5o12b3o
2bo46b5o12b3o2bo$2bo2b2o17b2o45bo2b2o17b2o$2b2o2bo8b2o54b2o2bo8b2o2$8b
o3bo6bo3bo53bo3bo6bo3bo2bo$6b3o2bo8bo2b3o49b3o2bo8bo2b4o$5bo3b3o3b2o3b
3o3bo47bo3b3o3b2o3b3o$5bob2ob5o2b5ob2obo47bob2ob5o2b5ob2o$4b2obo6b4o6b
ob2o45b2obo6b4o6bo$5bo2b5obo2bob5o2bo50b5obo2bob5o$5bo7b2o2b2o7bo55b2o
2b2o$6b3ob2obo4bob2ob3o53b2obo4bob2o$8bobo2bo4bo2bobo55bo2bo4bo2bo$8bo
2bobo4bobo2bo51b2o3bobo4bobo3b2o$9bobob6obobo52bo2bobob6obobo2bo$8b2ob
2o2b2o2b2ob2o53b2ob2o2b2o2b2ob2o$11bo8bo59bo8bo$11bobo4bobo59bobo4bobo
$12b2o4b2o61b2o4b2o!
Some maybe less, e.g.:

Code: Select all

x = 35, y = 7, rule = B3/S23
2b2ob2o$bobob2o27bo$o2bo30bo$2o3b2o27bo$3bo2bo$2obobo$2ob2o!
This is the unfortunate result of the optimizer only considering the rotor per se to be the identity of the oscillator and so deciding that entire complex oscillator just wants to be a blinker. It's technically correct per its intended programming although maybe not what a human would decide...

Attached is a tarball of the 119 reductions from running it with arguments 0 (don't increase bounding box) and 10 (width of optimization strips) on the 893 individual oscillators some light analysis had dumped out of that collection. The "manifest" has a list of oscillator IDs (assigned by original analyzer/splitter) and then the "before" and "after" files are dumped into folders sorted by period.

I'm guessing at a minimum P2 and P3 aren't going to be very interesting since many of them seem to be somewhat more artistic and/or have a different notion of oscillator identity than the optimizer. As for the rest, who can say?

[1] https://github.com/dvgrn/b3s23osc
Attachments
20211116-rstatoropt-results-01.tar.bz2
(26.79 KiB) Downloaded 98 times
Last edited by amling on December 6th, 2023, 5:26 pm, edited 1 time in total.

User avatar
LaundryPizza03
Posts: 2298
Joined: December 15th, 2017, 12:05 am
Location: Unidentified location "https://en.wikipedia.org/wiki/Texas"

Re: rstatoropt

Post by LaundryPizza03 » November 16th, 2021, 9:09 pm

Is this script specific to Conway's Life, or does it also work for OCA? Your fore and back test case, in particular, should be minimal in the non-totalistic rule B1e3/S23. It should be easy to verify manually.

Code: Select all

x = 7, y = 7, rule = B1e3/S23
2ob2o$2obobo$6bo$3ob3o$o$bobob2o$2b2ob2o!

Code: Select all

x = 4, y = 3, rule = B3-q4z5y/S234k5j
2b2o$b2o$2o!
LaundryPizza03 at Wikipedia

amling
Posts: 704
Joined: April 2nd, 2020, 9:47 pm

Re: rstatoropt

Post by amling » November 17th, 2021, 1:02 am

LaundryPizza03 wrote:
November 16th, 2021, 9:09 pm
Is this script specific to Conway's Life, or does it also work for OCA? Your fore and back test case, in particular, should be minimal in the non-totalistic rule B1e3/S23. It should be easy to verify manually.

Code: Select all

x = 7, y = 7, rule = B1e3/S23
2ob2o$2obobo$6bo$3ob3o$o$bobob2o$2b2ob2o!
Uh, not strictly specific to B3/S23, although the code as written is. Rule is encoded in "f_live":

Code: Select all

fn f_live(live: usize, nh: usize) -> bool {
    let magic_ct = 2 * nh + 1 - live;
    6 <= magic_ct && magic_ct <= 8
}
The optimizations are however specific to what the wiki informs me would be called "outer totalistic", namely that the immediate future of a cell is determined by its own liveness and the count of live neighbors.
Last edited by amling on November 17th, 2021, 2:48 am, edited 1 time in total.

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: rstatoropt

Post by Sokwe » November 17th, 2021, 1:34 am

amling wrote:
November 16th, 2021, 2:32 pm
This is the unfortunate result of the optimizer only considering the rotor per se to be the identity of the oscillator and so deciding that entire complex oscillator just wants to be a blinker. It's technically correct per its intended programming although maybe not what a human would decide...
One way you might be able to get around this is by allowing the user to set some stator cells as fixed, so that they can't be changed by the optimizer. So, for example, you could fix the center of the blinker rotor to be off.
-Matthias Merzenich

amling
Posts: 704
Joined: April 2nd, 2020, 9:47 pm

Re: rstatoropt

Post by amling » November 17th, 2021, 2:39 am

Sokwe wrote:
November 17th, 2021, 1:34 am
One way you might be able to get around this is by allowing the user to set some stator cells as fixed, so that they can't be changed by the optimizer. So, for example, you could fix the center of the blinker rotor to be off.
Any cell it considers "rotor" it will leave alone. Right now the rotor analysis happens to pick rotor strictly but I had considered modifying it to understand input "r" for "cell is off but please consider it rotor anyway" and "R" for "cell is on but please consider it rotor anyway". Either way not relevant for batch optimization of existing pattern collection.

EDIT: Done, but you can't win them all, now it optimizes

Code: Select all

**.**..
**.*.*.
......*
***r***
*......
.*.*.**
..**.**
to

Code: Select all

...**
....*
.*.*.
*....
**...

hkoenig
Posts: 258
Joined: June 20th, 2009, 11:40 am

Re: rstatoropt

Post by hkoenig » November 17th, 2021, 2:35 pm

There are a number of possible casings for that rotor. Which one of these were you expecting?

Code: Select all

x=103, y=9, rule = B3/S23
3o9b2o10b2o3b2o5b2o10b2ob2o7b2ob2obo5b2ob2obo5b2ob2o2b2o3b2ob2obo$12bobo9b
o4bo6bobo3b2o4b2obobo6b2obob2o5b2obob2o5b2obo2bobo4bobob2o$25b3obo8bo2bob
o7bo2bo8bo11bo11bo8bo2bo$14bobo10bob2o7b2o8b2o3b2o5b2o3b2o5b2o3b2o8b2obo5b
2o3b2o$15b2o10bobo2bo8bo6bo2bo8bo2bo2bo5bo2bo2bo12bo7bo2bo$31b2o5b2obo7bob
ob2o6bobobo7bobobo9b5o4b2obobo$25bobo10b2ob3o6b2ob2o5b2ob2o9b2ob2o8bo8bob
2ob2o$25b2o17bo44bo$43b2o43b2o!

amling
Posts: 704
Joined: April 2nd, 2020, 9:47 pm

Re: rstatoropt

Post by amling » November 17th, 2021, 3:18 pm

hkoenig wrote:
November 17th, 2021, 2:35 pm
There are a number of possible casings for that rotor. Which one of these were you expecting?

Code: Select all

x=103, y=9, rule = B3/S23
3o9b2o10b2o3b2o5b2o10b2ob2o7b2ob2obo5b2ob2obo5b2ob2o2b2o3b2ob2obo$12bobo9b
o4bo6bobo3b2o4b2obobo6b2obob2o5b2obob2o5b2obo2bobo4bobob2o$25b3obo8bo2bob
o7bo2bo8bo11bo11bo8bo2bo$14bobo10bob2o7b2o8b2o3b2o5b2o3b2o5b2o3b2o8b2obo5b
2o3b2o$15b2o10bobo2bo8bo6bo2bo8bo2bo2bo5bo2bo2bo12bo7bo2bo$31b2o5b2obo7bob
ob2o6bobobo7bobobo9b5o4b2obobo$25bobo10b2ob3o6b2ob2o5b2ob2o9b2ob2o8bo8bob
2ob2o$25b2o17bo44bo$43b2o43b2o!
I wasn't "expecting" anything, the program works as designed. It's less evidence against "the program does what I intended" and more evidence against "any optimizations per this definition of oscillators from that collection will be interesting because that collection 'is thought to be optimal'".

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: rstatoropt

Post by Sokwe » November 18th, 2021, 2:09 am

How feasible do you think your method would be for finding the intersection of all minimal stators for a particular oscillator. Here I mean that a cell is in the intersection of two patterns if it has the same state in both patterns. For example, consider the p5 you used as an example in your first post:

Code: Select all

x = 87, y = 17, rule = B3/S23
5bo2bo2bo66b2o$5b7o66b2o$75bo$5b7o63b7o$4bo7bo60b2o7bo$2obob2o3b2obob
2o53bobo2b2o3b2obo$bobobo5bobobo54b2obobo5bobo$bobo9bobo57bo9bob2o$2ob
o9bob2o56bo9bob2o$bobo9bobo54b2obo9bo$bobobo5bobobo54bo2bobo5bobo$2obo
b2o3b2obob2o55bo2b2o3b2ob2o$4bo7bo60b2o7bo$5b7o63b6obo$75bo5bo$5b7o66b
3o$5bo2bo2bo66bo!
I used JLS to find the intersection (or "combination", as JLS calls it) of all 68-cell variants fitting in a 17×17 bounding box, which looks like this:

Code: Select all

.....???????.....
......?????......
.....?.....?.....
....??*****??....
...?*...r...*?...
?.??.R*rrr*R.??.?
??.*.*rr.rr*.*.??
??.*.rr...rr.*.??
??.*rr.....rr*.??
??.*.rr...rr.*.??
??.*.*rr.rr*.*.??
?.??.R*rrr*R.??.?
...?*...r...*?...
....??*****??....
.....?.....?.....
......?????......
.....???????.....
where '?' is a stator cell not in the intersection. JLS is too slow to do this in most cases, so I was wondering if your method might yield a faster solution.
-Matthias Merzenich

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: rstatoropt

Post by Scorbie » November 18th, 2021, 5:51 am

For those who are lazy and just want to paste whatever the script outputs, postprocess the results with sed.

Code: Select all

cargo run --release m n < input-file 2>&1 | sed 's/r/./g'
Or using here documents,

Code: Select all

cargo run --release m n << EOF 2>&1 | sed 's/r/./g'
(Paste your dot star pattern here)
EOF
Sometimes I'm even lazy to do `sed 's/r/./g'` so I do `sed 's r . g'` instead.

hotdogPi
Posts: 1587
Joined: August 12th, 2020, 8:22 pm

Re: rstatoropt

Post by hotdogPi » November 18th, 2021, 10:59 am

7: 44P7 is a sparker and needs clearance; other three reduced.
8: Two reduced, one not reduced because RLE size, one deleted due to similarity with others.
9: Billiard table reduced; honey farm hassler previously had major p3 rotor reduction.
10: Wick reduced, sparker deleted because it's too large and obsoleted by 55P10 anyway, blinker hassler previously had a huge rotor reduction.
11: One partially changed (eater 2 is kept in standard form; they're identical in population), one deleted for being similar, and one not changed because RLE size.
12: All four changed.
13: Changed. 53P13 needs an update on the wiki page.
15: Bi-block hassler changed; the other is that way to preserve symmetry.
17: Changed.
18: One changed; also a two-row reduction. The other is that way to preserve symmetry.
20: One changed; the other two have had major reductions that aren't live yet.
21: Traffic light hassler changed despite lower clearance because the p7 keeps the original form. Also a 4-row reduction. The other one would have a larger RLE size if chnaged.
25: Loaf hassler changed. Wing and block hassler half changed; the higher-clearance p5 sparker should be shown at least somewhere in the collection.
27: Changed.
30: Both reduced. Both are also bounding box reductions. Wondering why one side has a snake and the other an aircraft carrier, though.
35: Changed. It's also a 2-row reduction.
45: Want to preserve symmetry.
50: One has been reduced but isn't live yet (it's actually in jslife), and the other has been deleted for being a simple phase change on an already existing p25.
55: There's a recently discovered more compact form that's not live yet.
56: Changed.
57: Changed. Reduced by 6 rows; the wiki article on 258P3 needs an update.
74: This has already been changed; it's just not live yet.
90: Changed. While it's actually one byte more, it still feels better in the reduced form.
110: Reduced. (It's still one of the largest, but I know this program only reduces stators, not rotors.)
188: One changed, the other not due to RLE size difference.
225: Want to preserve symmetry.
230: There's a smaller form that isn't live yet but uses smaller p5s the same way one of the p50s does.
246: I optimize RLE size over population.
532: I optimize RLE size over population.

I also checked p5, p6, and the larger p4s, despite no summary above.
User:HotdogPi/My discoveries

Periods discovered: 5-16,⑱,⑳G,㉑G,㉒㉔㉕,㉗-㉛,㉜SG,㉞㉟㊱㊳㊵㊷㊹㊺㊽㊿,54G,55G,56,57G,60,62-66,68,70,73,74S,75,76S,80,84,88,90,96
100,02S,06,08,10,12,14G,16,17G,20,26G,28,38,47,48,54,56,72,74,80,92,96S
217,486,576

S: SKOP
G: gun

amling
Posts: 704
Joined: April 2nd, 2020, 9:47 pm

Re: rstatoropt

Post by amling » November 18th, 2021, 1:47 pm

Sokwe wrote:
November 18th, 2021, 2:09 am
How feasible do you think your method would be for finding the intersection of all minimal stators for a particular oscillator. Here I mean that a cell is in the intersection of two patterns if it has the same state in both patterns.
The tricky bit is probably defining "all" and "minimal" in "all minimal stators". Right now rstatoropt breaks ties in a single strip of optimization by preferring existing contents and then by strip contents themselves making each strip optimization deterministic (we still do strips in random order so overall still random). This could be changed to pick among ties randomly and thereby randomly walk between a bunch of matched population variants. Something something decide how long you want to run for something something.

What is the goal/use for the intersection of minimal stators?

Sokwe
Moderator
Posts: 2645
Joined: July 9th, 2009, 2:44 pm

Re: rstatoropt

Post by Sokwe » November 18th, 2021, 9:10 pm

amling wrote:
November 18th, 2021, 1:47 pm
The tricky bit is probably defining "all" and "minimal" in "all minimal stators".
By "minimal", I meant having minimum population. By "all", I meant all within a given bounding box.
amling wrote:
November 18th, 2021, 1:47 pm
What is the goal/use for the intersection of minimal stators?
When minimizing an oscillator, I like to consider all possibilities, so I can make a final decision on a "canonical" form based on aesthetics. For example, the p5 in your first post can be minimized with 90-degree rotational symmetry:

Code: Select all

x = 17, y = 17, rule = B3/S23
8bo$8b3o$5bo5bo$5b6obo$3b2o7bo$2bo2b2o3b2ob2o$bobobo5bobo$bobo9bo$2obo
9bob2o$3bo9bobo$3bobo5bobobo$2b2ob2o3b2o2bo$4bo7b2o$4bob6o$5bo5bo$6b3o
$8bo!
This feature is ultimately unimportant, so you shouldn't feel the need to implement it.
-Matthias Merzenich

User avatar
DroneBetter
Posts: 94
Joined: December 1st, 2021, 5:16 am
Location: The UK (a delightful place)
Contact:

Re: rstatoropt

Post by DroneBetter » February 11th, 2024, 12:38 am

I have gotten much use out of this, for both reducing my own rudimentary oscillator search results (to find that their rotors are already parts of known oscillators) and perusing old forgotten billiard table oscillators on the wiki to see whether there is a reduction no-one thought to note (which worked for New five (29 -> 28) and 123P27.1 (123 -> 120)), thank you very much for it.

Could you allow inputted patterns to have four additional cell types labelled, representing each combination of 'stator that is [off/on] that I would like to be [off/on] in the output,' so modifications of slices containing them would constrain themselves to searching only the stator configurations that contain them in the desired state (or return it unmodified if impossible, in case another slice can solve it)? Then one would be able to increase oscillators' clearances with it as well as reduce population, or minimise the noninteracting portion of an eater/drifter-style still life.
That concludes my post (I hope you liked it)

amling
Posts: 704
Joined: April 2nd, 2020, 9:47 pm

Re: rstatoropt

Post by amling » February 11th, 2024, 12:54 am

DroneBetter wrote:
February 11th, 2024, 12:38 am
Could you allow inputted patterns to have four additional cell types labelled, representing each combination of 'stator that is [off/on] that I would like to be [off/on] in the output,' so modifications of slices containing them would constrain themselves to searching only the stator configurations that contain them in the desired state (or return it unmodified if impossible, in case another slice can solve it)? Then one would be able to increase oscillators' clearances with it as well as reduce population, or minimise the noninteracting portion of an eater/drifter-style still life.
"r" is already off/off and "R" is on/on (the internals think of it as a rotor cell that is always off/on then, but the effect is the same).

As for forcing a stator cell to be on or off instead of what it was in input, it does not sit well with the rest of the algorithm, at least in my recollection of it. It might work to do as you suggest: search each strip constrained as requested, but now a strip search can fail at worst instead of finding the existing solution at worst in which case you'd just refuse to replace. I'll go digging when I'm at a real computer to see if I can swing it.

rstatoropt is really designed to be a piecemeal optimizer, not a solver, and I think this type of problem might be better served by a program more oriented that way.

amling
Posts: 704
Joined: April 2nd, 2020, 9:47 pm

Re: rstatoropt

Post by amling » February 11th, 2024, 2:09 am

amling wrote:
February 11th, 2024, 12:54 am
DroneBetter wrote:
February 11th, 2024, 12:38 am
Could you allow inputted patterns to have four additional cell types labelled, representing each combination of 'stator that is [off/on] that I would like to be [off/on] in the output,' so modifications of slices containing them would constrain themselves to searching only the stator configurations that contain them in the desired state (or return it unmodified if impossible, in case another slice can solve it)? Then one would be able to increase oscillators' clearances with it as well as reduce population, or minimise the noninteracting portion of an eater/drifter-style still life.
I'll go digging when I'm at a real computer to see if I can swing it.
I have a criminally rough sketch of this pushed up to codeberg as 20240210-forces-01. "f" marks a cell which is off but which any alteration must turn on and "F" marks a cell which is on but any alteration must turn off. It's a huge mess for a variety of reasons and I'm not really sure how to clean it up.

The biggest problem is that it thrashes constantly. Normally it refuses alterations that do not strictly reduce population which thus prevents useless fiddling of equal-size solutions. But now we have to accept even strip solutions that make population worse (as they might fix such forced cells). Probably we want to do something like accept a change if there were forced cells it fixes or it reduced population. I guess I have to think on it, but I'm not too excited about this change in general.

In the meantime it generally works (at least in my testing), although it does not always succeed in completing the forced changes and it outputs a lot of useless thrashing on the way.

Post Reply