Self-destruct search program

For scripts to aid with computation or simulation in cellular automata.
simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Self-destruct search program

Post by simeks » July 2nd, 2016, 8:41 pm

I'm releasing a test version of the program described here
Its purpuse is to search for a way to add simple objects to a pattern in a way that causes it to self destruct.

Get the program here

Prepare a LifeHistory pattern in Golly and save as an .rle-file (an .mc-file will not work).

Use state 1 for still lifes to be destroyed and for the active pattern that initiates the destruction.
Use state 4 for the area where the program is allowed to place still lifes. All cells (in both phases for a blinker) must fit in the red area.
Use state 2 for the rest of the area that the active pattern is allowed to reach during the self destruct.

Run the program from the command line in Windows. It should compile with gcc for other platforms as well. There are two versions: Use destroy256.exe if you have a newer CPU (Inter Haswell or later), or use the somewhat slower destroy128.exe otherwise.

The command line format is:
destroy128 <pattern file> <objects> <max pool size> <max objects>

<objects> is a number of digits representing the type of objects the program may place:
1 = blocks, 2 = hives, 3 = blinkers, 4 = loaves, 5 = boats

<max pool size> describes how wide the search should be. The running time is proportional to this parameter.

<max objects> is the max number of objects the program will place. Currently the program will stop when the first solution is found, so this parameter can just be set to a high enough value.

For example:

> destroy128 demonoid.rle 124 5000 32

It happens sometimes that the program will fail to find one particular solution at one setting of <max pool size>, that it found at a lower setting of that parameter. This is a consequence of the search algorithm, and should not be considered a bug.

The cost function of the search is changed for this test release, to work better with larger patterns. It is now based on the size of the minimum spanning tree of the individual objects in the pattern after it has settled.

Here is an example file. Note that this is a rather difficult problem for the program to solve - depending on the search settings it will sometimes fail to make much progress when trying to get rid of the last few objects:

Code: Select all

x = 104, y = 132, rule = LifeHistory
24.36B$23.38B$22.14BA25B$21.15BABA24B$20.16B2A26B$19.46B$18.48B$17.
50B$16.52B$15.54B$14.56B$13.51B2D5B$12.51B4D5B$11.52B5D5B$10.54B5D5B$
9.37B2A17B5D5B$8.38BA18B6D5B$7.37BABA18B7D5B$6.38B2A13B2A9B3D5B$5.54B
2A10B3D5B$4.67B4D5B$3.30BA4BA32B5D5B$2.21B2A7B2A3B2A26B2A4B6D5B$.22B
2A6B2A3B2A27B2A4B7D5B$32B2A4BA22B2A8B8D5B$33B2A26B2A8B9D5B$72B9D5B$
18B2D52B10D5B$17B11D44B11D5B$16B12D38B2A4B12D5B$16B12D38B2A4B12D6B$
16B11D45B12D7B$16B11D11B8D26B12D8B$16B11D11B9D25B12D9B$16B12D11B9D23B
13D10B$16B13D10B10D18B17D11B$16B13D10B10D17B18D12B$16B13D4B2A4B10D17B
18D13B$16B13D4B2A4B10D16B19D14B$16B13D10B10D15B20D15B$16B13D10B9D16B
20D16B$16B13D9B5D22B19D17B$16B14D7B5D24B18D18B$16B25D26B17D19B$16B25D
27B16D20B$16B24D6B2A21B15D20B$16B24D5BABA22B14D20B$16B24D5BA13B2D10B
13D20B$16B24D4B2A13B3D10B12D20B$16B24D19B4D10B11D20B$16B24D20B4D10B
10D20B$16B24D20B4D11B9D20B$16B25D35B8D20B$16B31D30B7D20B$16B31D31B6D
20B$16B31D7B2A23B5D20B$16B25D13B2A7B2A39B$16B24D23BA5B2D33B$16B15D30B
ABA5B3D32B$16B14D31B2A6B4D31B$16B14D14B2A22B6D30B$16B14D14B2A22B7D29B
$16B14D4B2A31B9D28B$16B14D5BA30B11D27B$16B14D5BABA28B12D26B$16B14D6B
2A29B12D25B$16B14D38B12D24B$16B15D38B12D23B$16B16D38B12D22B$16B17D37B
13D21B$16B18D37B13D20B$16B19D36B13D20B$16B19D36B13D20B$16B19D36B13D
20B$16B18D6B2A29B13D20B$16B18D5BABA28B14D20B$16B18D5BA28B16D20B$16B
18D4B2A25B19D20B$16B18D31B19D20B$16B18D32B18D20B$16B18D32B18D20B$16B
19D31B18D20B$17B19D29B19D20B$18B18D19B2A7B20D20B$19B17D19B2A7B20D20B$
20B15D12B2A14B21D20B$21B13D14BA14B21D20B$22B12D11B3A15B21D20B$23B11D
11BA17B21D20B$24B10D29B21D20B$25B9D12BA16B21D20B$26B8D11BABA14B22D20B
$27B7D11BABA14B22D20B$28B6D9B3AB2A13B22D20B$29B5D8BA19B22D20B$30B4D9B
3AB2A20B15D20B$45BAB2A21B14D19B$70B14D18B$55B2A13B13D18B$55B2A7B2A4B
12D18B$64BA5B11D18B$62BABA5B10D18B$62B2A6B9D18B$69B9D18B$.68B8D18B$2.
66B8D18B$3.39B2A23B8D18B$4.38B2A23B7D18B$5.62B6D18B$6.62B4D18B$7.62B
2D18B$8.80B$9.49BA28B$10.47BABA26B$11.46BABA25B$12.46BA25B$13.46B3A
21B$14.47BA20B$15.66B$16.64B$17.62B$18.60B$19.58B$20.56B$21.54B$22.
52B$23.50B$24.48B$25.46B$26.44B$27.42B$28.40B!

chris_c
Posts: 966
Joined: June 28th, 2014, 7:15 am

Re: Self-destruct search program

Post by chris_c » July 3rd, 2016, 7:13 pm

simeks wrote:I'm releasing a test version of the program described here
Thanks! It seems to work well. I compiled on Linux with:

Code: Select all

gcc destroy.c -o destroy128 -O3 -Wall -Wextra -Wno-unused-function -fno-tree-loop-distribute-patterns -D __NO_AVX2 -std=c99 -lm
And did a quick run with blocks, blinkers, hives and max pool size 256. The following 14 object solution was obtained:

Code: Select all

x = 256, y = 256, rule = LifeHistory
6$40.A$40.A.A$40.2A11$50.2A$50.A$48.A.A$48.2A13.2A$63.2A2$37.A4.A$27.
2A7.2A3.2A26.2A$27.2A6.2A3.2A27.2A$36.2A4.A22.2A$37.2A26.2A4$70.2A$70.
2A4$24.C4.2C$24.C4.2C$24.C$37.2A9.3C$37.2A6.C$45.C$45.C5$50.2A$49.A.A
$49.A$36.3C9.2A3$42.C$42.C$42.C2$38.2C18.2A$38.2C18.2A7.2A$67.A$65.A.
A$65.2A$48.2A$48.2A$38.2A$39.A$39.A.A$40.2A7$37.C$37.C$37.C6.2A$27.C15.
A.A$26.C.C14.A$26.C.C13.2A$27.C2$77.2C$76.C2.C$77.2C$59.2A$59.2A10.C$
51.2A18.C$52.A18.C$49.3A$49.A$35.2C$34.C2.C12.A$35.2C12.A.A25.3C$49.A
.A16.3C$47.3A.2A$46.A$47.3A.2A$49.A.2A2$59.2A$59.2A7.2A$68.A$66.A.A$66.
2A4$46.2A$46.2A5$62.A$61.A.A$61.A.A$62.A$63.3A$65.A!
Also I noticed that gcc 4.8 is required for the call to __builtin_cpu_supports (possibly relevant if you are an old Ubuntu 12.04 user like me).

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Self-destruct search program

Post by simsim314 » July 4th, 2016, 8:19 am

Very nice!

I've some improvement suggestion:

Say we use the current mechanism. Starting from some point (say after depth = 4) all the variation include the same "first" SL. At the moment this happens we "commit" to this first SL, and make the search again from depth = 2, i.e. we move back in the tree search, to look for improvements after we've committed to some SL.

Think of it like chess - at the moment you make a "move" (i.e. commit to certain SL), you should make the calculation again, because after the move was done, the variation tree will be pretty different, and you could miss some important variation.

In slightly more "soft" variation we can "commit" to certain SL after it's popularity is above some threshold (i.e. 90% of the "good" variations include this SL as first one).
Last edited by simsim314 on July 4th, 2016, 9:40 am, edited 1 time in total.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Self-destruct search program

Post by dvgrn » July 4th, 2016, 9:09 am

I really like the results that this program can produce already. Here's a 10sL solution with blocks, beehives, and boats, with all kinds of improbable-looking cleanups buried in it:

Code: Select all

x = 123, y = 231, rule = LifeHistory
122.A$120.2A$121.2A119$23.2A$23.A$21.A.A$21.2A13.2A$36.2A3$2A40.2A$2A
40.2A$38.2A$38.2A4$43.2A$43.2A3$2.2C$.C2.C17.2C$2.2C18.2C2$10.2A6.2C$
10.2A6.2C7$23.2A$22.A.A$22.A$21.2A6$16.C$15.C.C13.2A$15.2C14.2A7.2A$
40.A$38.A.A$38.2A$21.2A$21.2A$11.2A$12.A$12.A.A$13.2A9$17.2A$16.A.A$
16.A$15.2A$3.2C$3.2C3.C$7.C.C$8.2C$51.2C$32.2A17.C.C$2.C29.2A18.C$.C.
C20.2A$.2C22.A$22.3A$22.A2$23.A$22.A.A32.2C$22.A.A31.C2.C$20.3A.2A31.
2C$19.A$20.3A.2A$22.A.2A$51.2C$32.2A16.C2.C$32.2A7.2A8.2C$41.A$39.A.A
$39.2A4$19.2A$19.2A5$35.A$34.A.A$34.A.A$35.A$36.3A$38.A5$52.3A$52.A$
53.A!
I also tried a couple of searches on the 19sL replicator unit. So far my best is the same 10sL still life count, but I'm sure that can be improved quite a bit:

Code: Select all

x = 83, y = 86, rule = LifeHistory
56.A.A$59.A$59.A$56.A2.A$57.3A6$45.C$44.C.C$45.2C$68.A$68.3A$71.A$70.
2A2$64.C$63.C.C$63.C.C$64.C5$58.2A$9.2A3.2A27.A15.A$9.2A3.2A25.3A15.A
.A$40.A19.2A$40.2A$2.2A$3.A$3.A.A75.2A$4.2A75.2A2$43.2A$43.2A4$7.2A$
8.A$5.3A28.2A$5.A31.A$34.3A$34.A$62.2C5.2A$2C53.2C5.2C6.A$C.C52.C.C9.
3A$.C54.C10.A$20.2A13.2C$20.2A12.C2.C$12.2A21.2C$13.A35.2C$10.3A36.2C
$10.A2$11.A$10.A.A16.2C$10.A.A15.C.C$8.3A.2A15.C$7.A$2.C5.3A.2A$.C.C
6.A.2A$.C2.C$2.2C16.2A8.2A$20.2A7.A.A$29.A$27.A.A$27.2A3$35.2C$7.2A
26.2C$7.2A5$23.A$22.A.A$22.A.A$23.A$24.3A$26.A!
Here are the two LWSS inputs that I've tried so far:

For the 10sL solution:

Code: Select all

x = 114, y = 108, rule = LifeHistory
34.45B$33.47B$32.49B$31.51B$30.53B$29.55B$28.57B$27.59B$26.61B$25.42B
ABA18B$24.46BA18B$23.47BA19B$22.45BA2BA20B$21.47B3A21B$20.73B$19.75B$
18.77B$17.79B$16.81B$15.6B44D9B3D7B9D5B$14.7B44D9B2D8B10D5B$13.9B43D
9B2D9B10D5B$12.11B42D9B2D3BA6B10D5B$11.13B41D9B2D3B3A5B10D5B$10.5B2D
8B40D9B2D6BA4B11D5B$9.5B4D8B39D9B3D4B2A4B12D5B$8.5B6D8B38D9B4D10B12D
5B$7.5B8D8B37D9B5D10B12D5B$6.5B10D8B36D9B5D13B10D5B$5.5B12D8B35D9B5D
13B11D5B$4.5B14D8B34D9B4D14B12D5B$3.5B15D9B33D9B3D15B13D5B$2.5B16D10B
32D9B3D15B14D5B$.5B11D17B17D7B7D9B3D16B14D5B$5B9D25B11D9B6D10B2D17B
14D5B$4B8D28B9D10B7D3B2A24B14D5B$3B8D9B2A3B2A14B7D6BA4B7D4BA23B16D4B$
3B7D10B2A3B2A15B5D5B3A4B7D4BABA20B18D3B$3B7D33B4D4BA7B7D5B2A19B18D4B$
3B7D41B2A6B8D24B18D5B$3B7D3B2A45B8D28B12D6B$3B7D4BA46B7D28B11D7B$3B7D
4BABA75B2A2B10D8B$3B7D5B2A75B2A2B9D9B$3B7D86B8D10B$3B7D44B2A40B7D11B$
3B8D43B2A34B12D12B$3B9D78B11D13B$3B10D77B10D14B$3B10D76B10D15B$3B10D
5B2A69B9D16B$3B10D6BA69B8D17B$3B10D3B3A28B2A23B7D10B7D18B$3B10D3BA31B
A21B9D11B5D19B$3B10D32B3A3B8D10B9D13B3D20B$3B10D32BA5B7D10B10D14BD21B
$3B10D38B6D10B9D4B2A32B$3B18D26B9D10B10D5BA32B$3B18D21B13D10B11D2B3A
33B$3B16D22B13D10B12D2BA35B$3B15D13B2A8B12D10B13D38B$3B15D13B2A8B11D
10B14D37B$3B15D5B2A16B10D10B15D36B$3B14D7BA15B10D10B15D36B$3B13D5B3A
16B9D10B15D36B$3B12D6BA18B8D10B15D36B$3B11D26B7D10B15D36B$3B11D8BA16B
7D10B15D36B$3B11D7BABA15B6D10B15D36B$3B11D7BABA15B5D10B15D36B$3B11D5B
3AB2A14B4D10B15D36B$3B11D4BA33B15D36B$3B11D5B3AB2A26B15D36B$3B12D6BAB
2A25B15D36B$3B13D33B15D36B$3B14D14B2A8B2A5B15D36B$3B15D13B2A7BABA4B
15D36B$3B15D22BA5B15D36B$3B14D21BABA5B14D36B$4B12D22B2A6B13D36B$.4B
10D30B13D36B$2.4B8D30B13D36B$3.4B7D29B13D36B$4.4B6D4B2A21B14D36B$5.4B
5D4B2A22B12D36B$6.4B4D29B10D36B$7.4B3D30B8D36B$8.4B3D30B6D36B$9.4B3D
7B6D17B4D36B$10.4B16D4BA12B2D36B$11.4B15D3BABA48B$12.4B14D3BABA47B$
13.4B13D4BA47B$14.4B12D5B3A43B$15.4B12D6BA42B$16.4B11D48B$17.4B11D10B
2D34B$18.4B12D7B4D32B$19.4B23D30B$20.4B23D28B$21.4B23D26B$22.4B23D24B
$23.4B23D22B$24.4B23D20B$25.4B23D14B.3B$26.43B$27.41B$28.39B!
For a search that got stuck in the middle and needed 20sL for a blocks-and-beehives-only run with a pool of 5000, if I remember correctly -- seems like that was probably just bad luck and it would do better with slightly different parameters:

Code: Select all

x = 114, y = 101, rule = LifeHistory
27.59B$26.61B$25.63B$24.13BABA49B$23.17BA49B$22.18BA50B$21.16BA2BA51B
$20.18B3A52B$19.75B$18.77B$17.79B$16.81B$15.6B14D8B34D7B9D5B$14.7B14D
8B33D8B10D5B$13.9B13D8B33D9B10D5B$12.11B12D8B33D3BA6B10D5B$11.13B11D
8B33D3B3A5B10D5B$10.5B2D8B10D8B33D6BA4B11D5B$9.5B4D8B9D8B34D4B2A4B12D
5B$8.5B6D8B8D8B35D10B12D5B$7.5B8D8B7D8B36D10B12D5B$6.5B10D8B6D8B36D
13B10D5B$5.5B12D8B5D8B36D13B11D5B$4.5B14D8B4D8B35D14B12D5B$3.5B15D9B
3D8B34D15B13D5B$2.5B16D10B2D8B23D8B3D15B14D5B$.5B11D17BD8B8D7B8D8B3D
16B14D5B$5B9D29B7D9B7D9B2D17B14D5B$4B8D31B6D10B7D3B2A24B14D5B$3B8D9B
2A3B2A16B5D6BA4B7D4BA23B16D4B$3B7D10B2A3B2A16B4D5B3A4B7D4BABA20B18D3B
$3B7D33B4D4BA7B7D5B2A19B18D4B$3B7D41B2A6B8D24B18D5B$3B7D3B2A45B8D28B
12D6B$3B7D4BA46B7D28B11D7B$3B7D4BABA75B2A2B10D8B$3B7D5B2A75B2A2B9D9B$
3B7D86B8D10B$3B7D44B2A40B7D11B$3B8D43B2A34B12D12B$3B9D78B11D13B$3B10D
77B10D14B$3B10D76B10D15B$3B10D5B2A69B9D16B$3B10D6BA69B8D17B$3B10D3B3A
28B2A23B7D10B7D18B$3B10D3BA31BA21B9D11B5D19B$3B10D32B3A3B8D10B9D13B3D
20B$3B10D32BA5B7D10B10D14BD21B$3B10D38B6D10B9D4B2A32B$3B18D26B9D10B
10D5BA32B$3B18D21B13D10B11D2B3A33B$3B16D22B13D10B12D2BA35B$3B15D13B2A
8B12D10B13D38B$3B15D13B2A8B11D10B14D37B$3B15D5B2A16B10D10B15D36B$3B
14D7BA15B10D10B15D36B$3B13D5B3A16B9D10B15D36B$3B12D6BA18B8D10B15D36B$
3B11D26B7D10B15D36B$3B11D8BA16B7D10B15D36B$3B11D7BABA15B6D10B15D36B$
3B11D7BABA15B5D10B15D36B$3B11D5B3AB2A14B4D10B15D36B$3B11D4BA33B15D36B
$3B11D5B3AB2A26B15D36B$3B12D6BAB2A25B15D36B$3B13D33B15D36B$3B14D14B2A
8B2A5B15D36B$3B15D13B2A7BABA4B15D36B$3B15D22BA5B15D36B$3B14D21BABA5B
14D36B$4B12D22B2A6B13D36B$.4B10D30B13D36B$2.4B8D30B13D36B$3.4B7D29B
13D36B$4.4B6D4B2A21B14D36B$5.4B5D4B2A22B12D36B$6.4B4D29B10D36B$7.4B3D
30B8D36B$8.4B3D30B6D36B$9.4B3D7B6D17B4D36B$10.4B16D4BA12B2D36B$11.4B
15D3BABA48B$12.4B14D3BABA47B$13.4B13D4BA47B$14.4B12D5B3A43B$15.4B12D
6BA42B$16.4B11D48B$17.4B11D10B2D34B$18.4B12D7B4D32B$19.4B23D30B$20.4B
23D28B$21.4B23D26B$22.4B23D24B$23.4B23D22B$24.4B23D20B$25.4B23D14B.3B
$26.43B$27.41B$28.39B!
Unless we can get the number of additional still lifes down into the low single digits, it's probably going to be more cost-effective to shoot down the 19sL pattern with multiple *WSSes. Which is a different kind of search.

It could get complicated if a combination of seeding and multiple shots is allowed. Probably two or three added objects would allow the whole thing to be shot down with two or three *WSSes, somehow.

EDIT: This search algorithm can sure come up with a wide variety of strange solutions for the same problem. This one was blocks-and-beehives, but it used almost all beehives:

Code: Select all

x = 89, y = 93, rule = LifeHistory
62.A.A$65.A$65.A$62.A2.A$63.3A9$58.C15.A$57.C.C14.3A$57.C.C17.A$58.C
17.2A9$56.2C$56.2C6.2A$15.2A3.2A27.A15.A$15.2A3.2A25.3A15.A.A$46.A19.
2A$46.2A$8.2A$9.A$9.A.A75.2A$10.2A75.2A2$49.2A$2.2C45.2A$.C2.C$2.2C2$
13.2A$14.A$11.3A28.2A$5.2C4.A31.A$4.C2.C32.3A22.C$5.2C33.A23.C.C$64.C
.C8.2A$65.C10.A$39.2C27.2C3.3A$38.C2.C19.2C4.C2.C2.A$26.2A11.2C19.C2.
C4.2C$26.2A33.2C$18.2A$19.A$16.3A$.C14.A$C.C$C.C3.C10.A$.C3.C.C8.A.A$
5.C.C8.A.A$6.C7.3A.2A$13.A$14.3A.2A$16.A.2A2$26.2A8.2A$26.2A7.A.A$35.
A$33.A.A$33.2A4$13.2A$13.2A5$29.A$23.C4.A.A$22.C.C3.A.A$22.C.C4.A$23.
C6.3A$32.A4$25.C9.C$24.C.C7.C.C$24.C.C7.C.C$25.C9.C!

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Self-destruct search program

Post by simsim314 » July 4th, 2016, 1:01 pm

Some small request (I hope it's small): how complex would it be to add OpenMP support?

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Self-destruct search program

Post by dvgrn » July 4th, 2016, 11:36 pm

It seems fairly likely that building two eaters will be easier than building the single integral in the 19sL replicator unit. Here's a sample start pattern for the conventional more-Spartan version:

Code: Select all

x = 121, y = 101, rule = LifeHistory
34.59B$33.61B$32.63B$31.65B$30.67B$29.69B$28.71B$27.73B$26.75B$25.77B
$24.79B$23.81B$22.9B53D7B9D5B$21.10B52D8B10D5B$20.12B51D9B10D5B$19.
14B50D3BA6B10D5B$18.16B49D3B3A5B10D5B$17.18B48D6BA4B11D5B$16.20B48D4B
2A4B12D5B$15.9B2D11B48D10B12D5B$14.2BABA5B3D11B48D10B12D5B$13.6BA4B4D
11B47D13B10D5B$12.7BA4B5D11B46D13B11D5B$11.5BA2BA4B6D11B44D14B12D5B$
10.7B3A4B6D12B42D15B13D5B$9.15B6D13B18DB11D8B3D15B14D5B$8.36B14D7B8D
8B3D16B14D5B$7.5B2D31B12D9B7D9B2D17B14D5B$6.5B3D32B10D10B7D3B2A24B14D
5B$5.5B4D13B2A3B2A13B8D6BA4B7D4BA23B16D4B$4.6B4D13B2A3B2A14B6D5B3A4B
7D4BABA20B17D4B$3.7B4D35B5D4BA7B7D5B2A19B18D4B$2.8B5D43B2A6B8D25B17D
5B$.9B6D4B2A45B8D28B12D6B$10B7D4BA46B7D28B11D7B$10B7D4BABA75B2A2B10D
8B$10B7D5B2A75B2A2B9D9B$10B7D86B8D10B$10B7D44B2A40B7D11B$10B8D43B2A
34B12D12B$10B9D78B11D13B$10B10D77B10D14B$10B10D76B10D15B$10B10D5B2A
69B9D16B$10B10D6BA69B8D17B$10B10D3B3A28B2A23B6D11B7D18B$10B10D3BA31BA
15B2A5B7D12B5D19B$10B10D32B3A3B7D7BA4B7D14B3D20B$10B10D32BA5B7D4B3A4B
7D38B$10B10D38B6D5BA5B7D5B2A32B$10B18D29B6D11B8D6BA32B$10B18D27B7D11B
9D3B3A33B$10B16D22B13D11B10D3BA35B$10B15D13B2A8B12D10B12D39B$10B15D
13B2A8B11D10B13D38B$10B15D5B2A16B10D10B14D37B$10B15D6BA15B10D10B15D
36B$10B14D4B3A16B9D10B15D36B$10B14D4BA18B8D10B15D36B$10B14D23B7D10B
15D36B$10B14D5BA16B7D10B15D36B$10B13D5BABA15B6D10B15D36B$10B12D6BABA
15B5D10B15D36B$10B11D5B3AB2A14B4D10B15D36B$10B11D4BA33B15D36B$10B11D
5B3AB2A26B15D36B$.9B12D6BAB2A25B15D36B$2.8B13D33B15D36B$3.7B14D14B2A
15B15D36B$4.6B15D13B2A7B2A5B15D36B$5.5B15D22BA5B15D36B$6.4B15D20BABA
5B14D36B$7.4B13D21B2A6B13D36B$8.4B11D29B13D36B$9.4B9D29B13D36B$10.4B
8D28B13D36B$11.4B6D4B2A21B14D36B$12.4B5D4B2A22B12D36B$13.4B5D28B10D
36B$14.4B4D29B8D36B$15.4B4D29B6D36B$16.4B5D2B9D17B4D36B$17.4B16D4BA
12B2D36B$18.4B15D3BABA48B$19.4B14D3BABA47B$20.4B13D4BA47B$21.4B12D5B
3A43B$22.4B12D6BA42B$23.4B11D48B$24.4B11D10B2D34B$25.4B12D7B4D32B$26.
4B23D30B$27.4B23D28B$28.4B23D26B$29.4B23D24B$30.4B23D22B$31.4B23D20B$
32.4B22D19B$33.43B$34.41B$35.39B!
As before, there are a lot of other good potential starting lanes for an LWSS. I haven't tried MWSS or HWSS, or any of these striking a self-destruct object first, as the initial reaction that then spreads to the rest of the circuitry. It might make sense to set up some kind of pre-search to find the most likely input lanes.

Here's a reasonable 9-stable-object solution for the above template:

Code: Select all

x = 91, y = 73, rule = LifeHistory
76.A$76.3A$79.A$78.2A2$6.A.A$9.A$9.A$6.A2.A62.C$7.3A61.C.C$71.C.C$59.
2C11.C$58.C2.C$58.C.C5.2A$17.2A3.2A27.A7.C7.A$17.2A3.2A25.3A15.A.A$
48.A19.2A$48.2A$10.2A$11.A$11.A.A75.2A$12.2A75.2A2$51.2A$.2C48.2A$C2.
C$.C.C$2.C$15.2A$16.A$13.3A28.2A$13.A31.A15.2A$42.3A17.A$42.A16.3A$
59.A5.C11.2A$47.2C15.C.C11.A$12.2C32.C2.C14.2C9.3A$12.C.C32.C.C25.A$
13.C14.2A18.C$28.2A$20.2A$21.A$18.3A$18.A2$19.A$18.A.A34.C$18.A.A33.C
.C$16.3A.2A33.2C$15.A$16.3A.2A$18.A.2A2$28.2A16.2C$11.C16.2A7.2A7.C.C
$10.C.C24.A9.C$10.C2.C21.A.A$11.2C22.2A4$15.2A$15.2A5$31.A$30.A.A$30.
A.A$31.A$32.3A$34.A!
Another interesting variable that it always seemed too complicated to worry about, is that the two eaters that catch unused glider outputs can be in a range of locations and two different orientations -- and if you count boat-bit catches with either the head or tail of the eater, that's a whole lot more options. It might knock the total cost down by a still life or two, if an optimal location could somehow be chosen for those movable eaters.

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Self-destruct search program

Post by simeks » July 5th, 2016, 3:04 pm

chris_c wrote:Thanks! It seems to work well. I compiled on Linux with:

Code: Select all

gcc destroy.c -o destroy128 -O3 -Wall -Wextra -Wno-unused-function -fno-tree-loop-distribute-patterns -D __NO_AVX2 -std=c99 -lm
Thanks for trying it out! I'm pretty surprised it worked just like that, given I've only ever tried to compile it on Windows... Without a "-march=..." compiler option I'm guessing you get no vectorization at all, which would slow down the search a bit.
chris_c wrote:Also I noticed that gcc 4.8 is required for the call to __builtin_cpu_supports (possibly relevant if you are an old Ubuntu 12.04 user like me).
Thanks, I'll add a check for this.
simsim314 wrote: Very nice!

I've some improvement suggestion:

Say we use the current mechanism. Starting from some point (say after depth = 4) all the variation include the same "first" SL. At the moment this happens we "commit" to this first SL, and make the search again from depth = 2, i.e. we move back in the tree search, to look for improvements after we've committed to some SL.
Thanks!

Using my standard example, searching only for blocks with a pool size of 4096, I took some statistics of the first block.
Turns out it isn't until 15 blocks have been added that all variations in the pool actually use the same first block (the (-99, -92) one). Even as late as after 10 added block a different first block is in the lead (2216 counts of (-97, -89), 1878 counts of (-99, -92) and 2 counts of (-102, -87)).
Given that, it seems it would take several times longer to run a search with a given pool size using your idea. It would still be interesting to try, but I'm inclined to think that that extra time is better spent using a larger pool size instead.
dvgrn wrote:I really like the results that this program can produce already.
Thanks! I'm pretty surprised myself how this pretty simple idea worked out like that to produce interesting results.
dvgrn wrote:I also tried a couple of searches on the 19sL replicator unit. So far my best is the same 10sL still life count, but I'm sure that can be improved quite a bit:
I think it might possibly help a bit to increase the area where objects may be added, and the area for the allowed reaction envelope, on the west and south-west side of your pattern.
simsim314 wrote:Some small request (I hope it's small): how complex would it be to add OpenMP support?
The algorithm should lend itself well to core-level parallelism. I have no experience with OpenMP, but it's something I'd really like to look into. Thanks for the idea!
dvgrn wrote:It seems fairly likely that building two eaters will be easier than building the single integral in the 19sL replicator unit.
Are you sure? According to Catagolue Eater 1 is only about 3 times more common than the integral (considering it has 8 symmetry cases versus 4 for the integral). Seems to me that building one integral should probably be cheaper than building two Eater 1s.

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Self-destruct search program

Post by simsim314 » July 5th, 2016, 3:46 pm

simeks wrote: I have no experience with OpenMP, but it's something I'd really like to look into. Thanks for the idea!
OpenMP is very simple (I learned it in half an hour and it took another few hours to master in real life situations). It's very simple parallelisation "addon", I personally really recommend it, as in 10-15 minutes of simple pragma directives you can accelerate your software by #cores, in pretty straight forward manner. If you have some question I can advise you in PM.
simeks wrote:Given that, it seems it would take several times longer to run a search with a given pool size using your idea. It would still be interesting to try, but I'm inclined to think that that extra time is better spent using a larger pool size instead.
Let me formulate it in other words. Think of it as a search tree - the tree branches exponentially, but your algorithm is linear no matter what is the "constant" you chose. Now the deeper you go, your error growths exponentially (in other words, you know exponentially less about this depth).

One way to tackle this problem is not increasing the memory "width", which will still be linear, but limiting the exponent by ignoring the "obvious" bad cases (in chess it's called alpha-beta pruning) i.e. limiting the branching factor. This will allow you to know much more about your "tree" with higher accuracy, than any "linear" approach.

We don't have to run everything from "beginning", only refining our knowledge "backwards" for cases that are clearly good. This "refining backwards" approach, allows us to know the situation in much better resolution much deeper, than the linear approach.

Yet once again - I think there is no other way than just write and see what works best. My intuition is that refining results is much more correct than wider search, and the deeper you go the more accurate the results would be, but I could be wrong on that.

EDIT BTW chris_c's compilation command worked for me, and what was posted in the repository didn't worked. So thx Chris, just letting you know. I'm not sure what failed, I think I had some compilation error.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Self-destruct search program

Post by dvgrn » July 5th, 2016, 6:23 pm

simeks wrote:
dvgrn wrote:It seems fairly likely that building two eaters will be easier than building the single integral in the 19sL replicator unit.
Are you sure?
Oh, not sure at all.
simeks wrote:According to Catagolue Eater 1 is only about 3 times more common than the integral (considering it has 8 symmetry cases versus 4 for the integral). Seems to me that building one integral should probably be cheaper than building two Eater 1s.
I'm tempted to try and weasel out: what I said was that the more Spartan version of the replicator unit would be "easier" to build, not necessarily cheaper...

My idea was that we're going to have to find slow edgy *WSS recipes for all orientations of eater, anyway. But we might appreciate not having to run the search program three times longer (or whatever) to dig up a decent edgy integral recipe -- or else build an integral-seed by hand that can be triggered by a *WSS, since that kind of manual work is likely to end up costing quite a bit more.

Technically using the integral would mean we'd only need three orientations of eater recipe -- assuming we're actually doing the construction with slow *WSSes from the west. If we were building the 19sL R.U. using gliders from the NW, we'd need four orientations anyway, with or without the ones replaced by the integral.

Do you happen to have any likely search code that can be adapted to build slow *WSS recipe libraries? It looks like BlinkerSpawn's investigations were done without automated assistance... I can throw something together, but the initial draft will be probably in Python or Lua, and therefore not very efficient. Usually I don't mind just letting the search run longer, but in this case it's probably better to do a better job the first time around.

EDIT: Just out of curiosity, I ran the same search, pool size 10,000, on the standard 19sL replicator unit using each of the five destruction seed objects on its own. The results were thoroughly not-surprising. Completing the self-destruct circuit needed either
  • 15 blocks,
  • 12 blinkers,
  • 11 beehives,
  • 10 loaves, or
  • 9 boats.
"Not-surprising" because the program gets to choose between four orientations of boats or loaves, but only two orientations of beehives or blinkers, and only one orientation of blocks. As the search tree gets bigger, the best solution gradually improves.

Code: Select all

x = 569, y = 331, rule = LifeHistory
4.A.A117.A.A117.A.A117.A.A117.A.A$7.A119.A119.A119.A119.A$7.A119.A
119.A119.A119.A$4.A2.A116.A2.A116.A2.A116.A2.A116.A2.A$5.3A117.3A117.
3A117.3A117.3A244$201.2C$189.C10.C2.C$188.C.C10.2C$74.A113.C.C3.A100.
3C16.A119.A119.A$74.3A112.C4.3A117.3A117.3A117.3A$77.A119.A119.A119.A
119.A$76.2A118.2A118.2A118.2A112.C5.2A$532.C16.C.C$286.C244.C.C16.2C$
181.2C103.C245.2C$180.C2.C102.C111.2C$55.2C124.2C214.C2.C$55.2C237.3C
101.C.C$399.C$417.2C$273.3C140.C2.C$55.2C7.2A118.2A118.2A110.C.C5.2A
118.2A$15.2A3.2A27.A5.2C8.A69.2A3.2A27.A15.A69.2A3.2A27.A15.A69.2A3.
2A27.A7.C7.A69.2A3.2A27.A15.A$15.2A3.2A25.3A15.A.A67.2A3.2A25.3A15.A.
A67.2A3.2A25.3A15.A.A67.2A3.2A25.3A15.A.A67.2A3.2A25.3A15.A.A$46.A19.
2A98.A19.2A98.A7.3C9.2A98.A12.2C5.2A98.A19.2A$46.2A118.2A118.2A118.2A
10.C2.C104.2A9.C$8.2A118.2A118.2A118.2A48.C.C67.2A46.C.C$9.A119.A119.
A119.A49.C69.A47.2C$9.A.A75.2A40.A.A75.2A31.C8.A.A75.2A40.A.A75.2A40.
A.A75.2A$10.2A75.2A41.2A75.2A31.C9.2A75.2A41.2A75.2A41.2A75.2A$240.C$
49.2A118.2A118.2A118.2A118.2A$49.2A118.2A118.2A118.2A118.2A$3.2C$3.2C
481.2C$485.C.C$13.2A118.2A118.2A118.2A111.C6.2A$14.A111.C7.A119.A119.
A119.A$11.3A28.2A81.C.C3.3A28.2A80.3C4.3A28.2A80.C6.3A28.2A87.3A28.2A
$11.A31.A15.2A64.C.C3.A31.A15.2A70.A31.A15.2A62.C.C5.A31.A15.2A70.A
31.A15.2A7.C$3.2C35.3A4.2C11.A65.C33.3A17.A99.3A17.A62.C2.C33.3A17.A
99.3A17.A6.C.C$3.2C35.A6.2C8.3A100.A16.3A5.C94.A16.3A64.2C34.A16.3A
100.A16.3A7.2C$57.A5.2C10.2A100.A6.C.C8.2A100.A17.2A100.A17.2A50.C49.
A17.2A$63.2C11.A107.C.C9.A119.A53.C65.A49.C.C67.A$45.2C20.2C4.3A53.2C
54.C7.3A50.C59.C6.3A53.C.C61.3A50.2C65.3A$45.2C20.2C4.A49.2C3.C2.C61.
A52.C59.C6.A55.C2.C60.A49.C69.A$3.2C21.2A94.C2.C3.2C15.2A98.C19.2A38.
C63.2C14.2A94.C.C21.2A$3.2C21.2A95.2C21.2A118.2A118.2A39.C55.2C21.2A$
18.2A118.2A118.2A118.2A46.C.C69.2A$19.A43.2C74.A39.C79.A119.A46.C2.C
69.A$16.3A44.2C71.3A39.C.C75.3A117.3A48.2C67.3A$16.A20.2C97.A41.C.C
64.C10.A119.A119.A$37.2C20.2C118.C65.C$17.A41.2C76.A107.C11.A119.A
119.A$16.A.A117.A.A117.A.A36.3C78.A.A117.A.A$16.A.A105.2C10.A.A117.A.
A117.A.A117.A.A$14.3A.2A103.C2.C7.3A.2A28.C85.3A.2A114.3A.2A114.3A.2A
$2C11.A110.2C7.A33.C.C83.A119.A119.A$2C12.3A.2A114.3A.2A27.C.C84.3A.
2A37.C76.3A.2A103.2C9.3A.2A$16.A.2A116.A.2A28.C87.A.2A37.C78.A.2A103.
C.C10.A.2A$297.C115.2C69.C$26.2A118.2A17.2C99.2A102.C15.2A24.C2.C90.
2A$9.2C15.2A7.2A109.2A7.2A7.C2.C98.2A7.2A92.C.C14.2A7.2A15.C.C91.2A7.
2A$9.2C24.A119.A9.2C108.A93.C2.C22.A17.C101.A$33.A.A117.A.A117.A.A94.
2C21.A.A117.A.A$33.2A118.2A118.2A118.2A118.2A2$407.C114.C$400.2C4.C.C
112.C.C$13.2A118.2A118.2A118.2A24.C2.C3.C2.C83.2A26.2C$13.2A23.2C93.
2A118.2A118.2A25.C.C4.2C84.2A$38.2C361.C4$29.A119.A119.A119.A119.A$
28.A.A117.A.A117.A.A117.A.A117.A.A$28.A.A117.A.A117.A.A117.A.A117.A.A
$29.A119.A119.A119.A119.A$30.3A117.3A117.3A117.3A117.3A$32.A119.A119.
A119.A119.A5$46.3A117.3A117.3A117.3A117.3A$46.A119.A119.A119.A119.A$
47.A119.A119.A119.A119.A!
A couple of runs allowing any stable object produced other 9-object solutions... which both included a lot of boats:

Code: Select all

x = 211, y = 73, rule = LifeHistory
76.A119.A$76.3A117.3A$79.A119.A$78.2A118.2A2$6.A.A117.A.A$9.A58.2C59.
A$9.A57.C.C59.A$6.A2.A58.C57.A2.A62.C$7.3A117.3A61.C.C$44.2C145.C.C$
44.2C133.2C11.C$178.C2.C$66.2A110.C.C5.2A$17.2A3.2A27.A15.A69.2A3.2A
27.A7.C7.A$17.2A3.2A25.3A15.A.A67.2A3.2A25.3A15.A.A$48.A19.2A98.A19.
2A$48.2A118.2A$10.2A118.2A$11.A119.A$11.A.A75.2A40.A.A75.2A$12.2A75.
2A41.2A75.2A2$51.2A118.2A$.2C48.2A68.2C48.2A$C2.C116.C2.C$.C.C117.C.C
$2.C119.C$15.2A118.2A$16.A119.A$13.3A28.2A87.3A28.2A$13.A31.A15.2A70.
A31.A15.2A$42.3A17.A99.3A17.A$42.A16.3A100.A16.3A$59.A17.2A100.A5.C
11.2A$78.A88.2C15.C.C11.A$12.2C61.3A54.2C32.C2.C14.2C9.3A$12.C.C60.A
56.C.C32.C.C25.A$13.C14.2A30.2C71.C14.2A18.C$28.2A29.C2.C85.2A$20.2A
38.2C6.C71.2A$21.A45.C.C71.A$18.3A47.2C68.3A$18.A119.A2$19.A119.A$18.
A.A117.A.A34.C$18.A.A30.C86.A.A33.C.C$16.3A.2A28.C.C83.3A.2A33.2C$15.
A34.2C83.A$16.3A.2A114.3A.2A$18.A.2A116.A.2A2$28.2A17.C100.2A16.2C$
11.C16.2A7.2A7.C.C82.C16.2A7.2A7.C.C$10.C.C24.A9.2C81.C.C24.A9.C$10.C
2.C21.A.A92.C2.C21.A.A$11.2C22.2A94.2C22.2A4$15.2A118.2A$15.2A118.2A
5$31.A119.A$30.A.A117.A.A$30.A.A117.A.A$31.A119.A$32.3A117.3A$34.A
119.A!
Based on this, I'm kind of expecting that there are 7sL or 8sL solutions out there to be found, but 5sL or 6sL may be a little over-optimistic. We'll see. I'll be interested to find out whether increasing the pool size even further has any effect on efficiency, or if it helps to give the reaction more "spark space".

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Self-destruct search program

Post by simsim314 » July 7th, 2016, 10:05 am

Just ran self destruct for p120:

Here is the best solution (without blinkers):

Code: Select all

x = 85, y = 96, rule = LifeHistory
9$67.2C$67.2C2$61.2C$60.C2.C$61.C.C$62.C$70.A$68.3A$67.A$67.2A$49.2C$
49.2C3$71.2A5.2A$71.2A5.2A$60.A$58.2A.2A11.2A$55.5A14.2A$55.A2.A$55.A
2.A$56.2A$51.2A$51.2A2$47.2A5.2A$47.2A5.2A11$52.A$50.2A$51.2A23$19.2C
$18.C2.C$19.C.C$20.C$26.2A$26.2A4$30.C$29.C.C$28.C2.C$23.2C4.2C$22.C
2.C$23.2C!
Here is my input:

Code: Select all

x = 124, y = 110, rule = LifeHistory
12.104B$12.104B$12.104B$12.104B$12.104B$11.105B$11.105B$11.105B$11.
105B$11.105B$2.114B$2.58B36D20B$2.58B36D20B$2.58B36D20B$2.58B36D20B$
2.57B37D20B$2.56B38D20B$2.55B39D20B$2.54B40D20B$2.53B23D38B$2.52B23D
39B$2.51B23D40B$2.50B23D6BA34B$2.49B23D5B3A32B$2.48B20D8BA35B$2.47B
19D10B2A34B$2.46B18D48B$2.45B18D49B$46B18D50B$45B18D51B$44B18D20B2A5B
2A23B$43B18D21B2A5B2A23B$42B18D11BA42B$41B18D10B2AB2A11B2A27B$40B18D
8B5A14B2A27B$39B18D9BA2BA44B$38B18D10BA2BA44B$37B18D12B2A47B$36B18D8B
2A52B$35B18D9B2A52B$34B18D64B$33B18D7B2A5B2A49B$32B18D8B2A5B2A49B$31B
18D67B$30B18D68B$29B18D69B$28B18D70B$27B18D71B$.25B18D72B$.24B18D73B$
.23B18D74B$.22B18D75B$.21B18D76B$.20B18D24BA52B$.19B18D23B2A53B$.18B
18D25B2A49B$.17B18D77B$.16B18D78B$.15B18D79B$.14B18D80B$.13B18D81B$.
12B18D82B$.11B19D82B$.10B20D82B$.10B20D82B$.10B20D82B$.10B20D82B$.10B
20D82B$.10B20D82B$.10B20D77B$.10B20D77B$.10B20D77B$.10B20D77B$.10B53D
44B$.10B53D44B$.10B53D44B$.10B53D44B$.10B53D44B$.10B53D44B$11B53D44B$
11B53D44B$11B53D44B$11B26D2A25D33B$11B26D2A25D33B$11B53D33B$11B53D33B
$11B53D33B$11B53D33B$11B53D33B$11B53D33B$11B53D33B$11B53D33B$11B53D
32B$11B53D32B$11B53D32B$11B53D32B$96B$96B$96B$96B$93B$95B$95B$95B$97B
$97B$97B$97B$97B!

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Self-destruct search program

Post by simeks » July 10th, 2016, 9:45 am

Probably because of too many levels of function inlining by GCC, the GoLGrid_evolve function in the innermost loop failed to vectorize as expected in the first release.

This is fixed in a new update. It should now run about 3 times faster on Intel Haswell.

I've also tried to improve compatibility for compiling on Linux, and it should now compile without changes.

Note that on Windows I compile with MinGW-w64, using this distribution, but it should now work without trouble in Cygwin too.
dvgrn wrote:Do you happen to have any likely search code that can be adapted to build slow *WSS recipe libraries?
I'm working towards that...
About finding slow-salvo recipes for integrals: I remember with the code I used to search for glider slow-salvo recipes for edgy eater 1s, that it had no trouble finding even hives-with-tails, and they are some 25 times rarer than integrals.

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: Self-destruct search program

Post by Rhombic » September 4th, 2016, 9:38 am

Very interesting and efficient. However, how can I save the resulting RLE directly? I have actually had to type the result by hand to check what it was (thankfully, it was short). Is there any way to save it directly as NAME_solution.rle?
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Self-destruct search program

Post by dvgrn » September 4th, 2016, 10:50 am

Rhombic wrote:Very interesting and efficient. However, how can I save the resulting RLE directly? I have actually had to type the result by hand to check what it was (thankfully, it was short). Is there any way to save it directly as NAME_solution.rle?
Almost. Are you running in Windows, and seeing the LifeHistory RLE in a command window? You can right-click on the window and choose "Mark", select the area of screen with the RLE you want (works for intermediate results while the program is running, too) and then hit [Enter]. All very weird and archaic, but the RLE gets copied to the clipboard:

Code: Select all

x = 62, y = 46, rule = LifeHistory
39.A2.2A9.2A$39.4A.A8.2A$44.A$36.2A3.3A$37.A2.A3.3A$30.2A5.A.A2.A3.A$
16.2A3.2A3.2A2.A5.2A.7A$16.2A2.A2.A2.A.A.A.A2.A12.2A$20.A.A.A.A.A.A.
4A5.2A.2A2.A$19.2A.A.2A3.A6.2A3.2A.A.A.A$18.A2.A8.3A.2A2.A7.A2.2A$19.
2A6.A4.A.A2.A3.5A.2A2.A$14.2A10.A.A6.2A3.A5.A2.2A$15.A6.2A.A.A13.2A.A
.A.A$15.A.2A4.A.A2.3A.2A8.A.2A2.A$16.A.A4.A2.2A2.A.A2.A.2A.A7.2A$10.
2A6.A.2A.A3.A2.A3.2A.A.3A11.A$10.A.A4.A.A.A.4A4.3A3.A5.2A.A5.A.A$12.A
2.A2.A2.A12.2A.A.3A.A.2A3.3A.A$11.2A.A.2A3.A.4A4.2A2.A2.A2.A.A5.A3.A$
11.A2.A2.A.A.A.A3.A2.A.2A.A3.2A3.3A2.A.2A7.2A$13.A.A.A.2A5.2A2.A3.A
11.A3.A9.2A$12.2A.A.A9.A.2A.2A10.2A5.2A$16.2A.4A4.A2.A.A3.2A.2A3.A7.A
$19.A2.A2.2A.A.A2.A3.A.A2.A.A4.3A$16.2A.A2.A.A.A.2A2.2A3.A.A.2A.3A2.A
$16.2A.4A.2A8.2A.A.A7.A.A$2.A31.A.A2.A6.A.A$A.A13.2A.2A18.A.A5.A$.2A
6.2A5.2A.2A9.2A.A6.2A11.2A$9.2A20.A.3A9.5A2.A.A$14.4A.4A.2A5.A4.A.4A
2.A5.A2.A$14.A2.A.A2.A.A.A.A3.3A.A.A2.A3.5A.2A$18.A5.A2.2A5.A.A2.2A5.
A4.A$23.2A10.2A7.A3.2A.A$16.5A2.A3.4A13.5A.A$15.A2.A2.A.A3.A2.A$15.2A
3.2A.2A6.2A.2A2.A7.A$32.A.A2.A.A5.A.A3.A$32.A3.2A.A6.A.A.A.A$31.2A5.A
.2A.3A2.A.A2.A$38.A2.A.A4.2A2.2A$39.2A$25.2A8.A20.2A$25.2A7.A.A19.2A$
35.2A!
Alternatively, you could run something like "destroy256 destroy43x45.rle 1 5000 5 >> output.txt", wait until it finishes running, and then copy RLE chunks out of the text file. That's kind of annoying, though, because you don't see the progress being reported any more unless you keep re-opening output.txt -- all the output gets piped (>>) to the file.

An optional fifth parameter for an output filename would be a fairly small addition to the search code. If you get something working, you can contribute the change to chris_c's project.

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Self-destruct search program

Post by simeks » September 4th, 2016, 11:44 am

Rhombic wrote:Very interesting and efficient. However, how can I save the resulting RLE directly? I have actually had to type the result by hand to check what it was (thankfully, it was short). Is there any way to save it directly as NAME_solution.rle?
Thanks!
dvgrn wrote:Alternatively, you could run something like "destroy256 destroy43x45.rle 1 5000 5 >> output.txt", wait until it finishes running, and then copy RLE chunks out of the text file. That's kind of annoying, though, because you don't see the progress being reported any more unless you keep re-opening output.txt -- all the output gets piped (>>) to the file.
In fact, the progress report is all written to stderr, and only the solutions are written to stdout. This means if you redirect the output to a file, you would still see the progress report in the console, but the solutions would end up in the file.
I would normally use ">" instead of ">>" unless I really wanted to append to the output file rather than just overwrite it.
dvgrn wrote:If you get something working, you can contribute the change to chris_c's project.
You could, but I think both I and chris_c would get rather confused by that... ;)

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: Self-destruct search program

Post by Rhombic » September 4th, 2016, 12:14 pm

A few notes. The program itself is pretty good and shows some destructions that I would have never even though about.
I have been trying to prepare some slightly forcing conditions to see what kind of imprecisions it might have and I came up with this. I prepared a somewhat chaotic starting point with limited access for still life placement, so that not correcting an earlier mistake could account for losing track of a trivial solution. This was my input, with all still lifes allowed to be used:

Code: Select all

x = 135, y = 109, rule = LifeHistory
135B$135B$135B$135B$135B$135B$135B$135B$135B$135B$135B$135B$135B$135B
$135B$135B$135B$135B$135B$135B$135B$135B$86B6D43B$86B6D43B$13B4D69B6D
43B$13B4D69B6D43B$13B4D69B6D43B$13B4D17B7D94B$13B4D17B7D94B$13B4D17B
7D94B$34B7D94B$34B7D94B$34B7D94B$135B$135B$70B9D56B$70B9D56B$70B9D56B
$70B9D56B$70B9D56B$70B9D56B$50B7D78B$50B7D78B$50B7D78B$50B7D78B$50B7D
78B$50B7D78B$50B7D78B$50B7D78B$18B6D26B7D78B$18B6D111B$18B6D88B4D19B$
18B6D88B4D19B$112B4D19B$112B4D19B$135B$135B$135B$81B13D41B$81B13D41B$
43B6D32B13D41B$43B6D32B13D41B$43B6D32B13D41B$43B6D32B13D41B$43B6D32B
13D41B$43B6D32B13D41B$43B6D86B$43B6D86B$70BA64B$70BABA62B$70B2A63B$
135B$135B$65B2A19BA48B$65B2A18BABA47B$63B2A19BA2BA47B$63B2A20B2A48B$
76B2A57B$75BA2BA56B$76B2A57B$135B$135B$135B$135B$51B8D76B$51B8D76B$
51B8D76B$51B8D76B$51B8D76B$51B8D76B$135B$135B$135B$135B$135B$135B$
135B$135B$135B$135B$135B$135B$135B$135B$135B$135B$135B$135B$135B!
Now, the intermediate that the program eventually gives is this one:

Code: Select all

x = 51, y = 28, rule = LifeHistory
46.2C$45.C2.C$39.2C5.2C$4.C33.C2.C$3.C.C33.2C$3.2C44.2C$44.3C2.2C$2C$
2C2$27.A$27.A.A$27.2A3$22.2A19.A$22.2A18.A.A$20.2A19.A2.A$20.2A20.2A$
33.2A$32.A2.A$33.2A5$8.2C$8.2C!
Which is quite good except that the block on the bottom left corner is totally unnecessary. I am assuming that it was one of the first still lifes calculated, but after the third or fourth, the behaviour/evolution of the pattern changed enough so that it was unnecessary.
The program should be able to check whether all script-placed still lifes interact after a new one is added, or if they are redundant or, like in this case, actually conceal a perfect solution.
Any thoughts?

Again, congratulations on such a nice script.
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Self-destruct search program

Post by dvgrn » September 4th, 2016, 1:12 pm

Rhombic wrote:The program should be able to check whether all script-placed still lifes interact after a new one is added, or if they are redundant or, like in this case, actually conceal a perfect solution.
Any thoughts?
Interesting! I hadn't run into that case before. Seems like a quick recheck of previous objects will definitely improve the algorithm for situations like this.
simeks wrote:
dvgrn wrote:If you get something working, you can contribute the change to chris_c's project.
You could, but I think both I and chris_c would get rather confused by that... ;)
Ha! Then we'd all be confused. Apologies for the confusion...

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Self-destruct search program

Post by simeks » September 4th, 2016, 1:28 pm

Rhombic wrote: Which is quite good except that the block on the bottom left corner is totally unnecessary. I am assuming that it was one of the first still lifes calculated, but after the third or fourth, the behaviour/evolution of the pattern changed enough so that it was unnecessary.
Thanks for reporting! I guess this is a "known limitation" of the program right now.

I think you got the reason pretty much figured out. The requirement that the pattern must settle after each added object, if that object should be considered further, could mean that object B can't be placed first, because the pattern doesn't settle. But if it object A is placed first, and then object B, that could mean the pattern settles. Then the program might place object C, which changes the use of object B completely. Now object A is not touched at all, but object B is still allowed, because in combination with object C the pattern settles again.

The requirement that the pattern must settle after each added object simplifies the program a lot, because it allows a cost (or value) to be assigned to each new object, based on the final census after the pattern has stabilized.

I don't want to make a quick fix to a program I haven't looked at in two month, because I wouldn't feel sure what I was doing. Can we even be sure the program wouldn't get stuck in an endless loop if it was allowed to alternetively remove and add objects? The next time I revisit this project for real, I will consider ways to improve this behaviour.

Gamedziner
Posts: 795
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: Self-destruct search program

Post by Gamedziner » September 4th, 2016, 2:22 pm

Why not just tell it to check and see if those extra bits have any effect when it comes up with a potential solution, and delete them if they have no effect? I think it could track which parts are added using LifeHistory.

Code: Select all

x = 81, y = 96, rule = LifeHistory
58.2A$58.2A3$59.2A17.2A$59.2A17.2A3$79.2A$79.2A2$57.A$56.A$56.3A4$27.
A$27.A.A$27.2A21$3.2A$3.2A2.2A$7.2A18$7.2A$7.2A2.2A$11.2A11$2A$2A2.2A
$4.2A18$4.2A$4.2A2.2A$8.2A!

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: Self-destruct search program

Post by Rhombic » September 5th, 2016, 11:53 am

simeks wrote: I don't want to make a quick fix to a program I haven't looked at in two month, because I wouldn't feel sure what I was doing. Can we even be sure the program wouldn't get stuck in an endless loop if it was allowed to alternatively remove and add objects? The next time I revisit this project for real, I will consider ways to improve this behaviour.
It shouldn't be too bad though, because it would just run the pattern and then check whether it stabilises (so what it already does). If it does, it then checks the SLs used and if one is redundant, it gets taken away as long as the final result is more efficient than the previous intermediate, which, to be fair, would be true almost definitely.


EDIT:
Setting a particular object to delete and placing a block far away allows for the calculation of how to generate gliders or *WSS from Bs, Pis, Hs, etc. as well as choosing the lane.

Code: Select all

x = 63, y = 25, rule = LifeHistory
54.2C$54.2C5$3C$5.2C$5.2C2$28.2C19.2C$28.2C19.2C$9.2C10.2C$8.C.C9.C2.
C$9.C11.2C3$60.2C$59.C2.C$60.C.C$61.C2$5.A20.A19.A$4.3A18.3A17.3A$3.
2A.A17.2A.A16.2A.A!
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Self-destruct search program

Post by calcyman » September 10th, 2016, 6:44 pm

I'm very impressed with this program, by the way -- nice work!

I was wondering why your cost is given by the sum of the 1.25th powers of the lengths of the edges in the spanning tree. In particular, why 1.25?

Your function has the curious property of not obeying the triangle inequality: f(x) + f(y) need not be greater than f(x + y), where f(x) := x ** 1.25 is the cost of an edge of length x. Consequently, adding a still-life can actually decrease the cost. For example, the following arrangement of 2 blocks has a cost of 32 (= 16 ** 1.25):

Code: Select all

x = 18, y = 2, rule = B3/S23
2o14b2o$2o14b2o!
Inserting a third block midway between them decreases the cost to 26.9087:

Code: Select all

x = 18, y = 2, rule = B3/S23
2o6b2o6b2o$2o6b2o6b2o!
Now, this might be intended behaviour; after all, I can imagine it being more difficult to destroy two clusters than one. Did you have this in mind when you developed your cost function? Or was it found through empirical investigation?
What do you do with ill crystallographers? Take them to the mono-clinic!

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Self-destruct search program

Post by simeks » September 11th, 2016, 8:55 am

calcyman wrote:I'm very impressed with this program, by the way -- nice work!
Thanks! I consider it very experimental, so it's nice to see it produces useful results.
calcyman wrote: I was wondering why your cost is given by the sum of the 1.25th powers of the lengths of the edges in the spanning tree. In particular, why 1.25?
Your function has the curious property of not obeying the triangle inequality: f(x) + f(y) need not be greater than f(x + y), where f(x) := x ** 1.25 is the cost of an edge of length x. Consequently, adding a still-life can actually decrease the cost. For example, the following arrangement of 2 blocks has a cost of 32 (= 16 ** 1.25):
[...]
Now, this might be intended behaviour; after all, I can imagine it being more difficult to destroy two clusters than one. Did you have this in mind when you developed your cost function? Or was it found through empirical investigation?
Yes, it is indeed intended. I tried at first to use just the geometric lenght of the minimum spanning tree, but I kept having problems with single still lifes or small clusters being left behind in one part of the pattern, far away from anything else that remained.

That's why I tried the current cost function, which discourages intermediate results with distant isolated islands. The theory is that it is easier for the active part of the pattern to return to a distant part of the pattern if there is a trace of still lifes not too far apart from each other, for the active patterns to "climb on".

As I remember it, this improved the behaviour of the program significantly.

I picked an exponent that looked like a resonable value, but I havn't done any real testing to find out the optimal value. The cost is supposed to decrease if the intermediate still life is in the general direction of the remote area, but if it's too much in the wrong direction it should still increase the cost, as I've tried to illustrate here:

Code: Select all

x = 211, y = 32, rule = LifeHistory
47.2A14.2A30.2A6.2A6.2A30.2A14.2A30.2A14.2A$47.2A14.2A30.2A6.2A6.2A
30.2A14.2A30.2A14.2A3$151.2A$151.2A$199.2A$199.2A17$.4D37.3D4.3D11.3D
24.3D5.3D10.3D24.3D4.3D11.3D24.3D4.4D11.3D$D3.D17.D18.D3.D2.D3.D9.D3.
D22.D3.D3.D12.D3.D22.D3.D2.D3.D9.D3.D22.D3.D3.D13.D$D7.3D4.4D2.4D20.D
6.D9.D3.D26.D2.D13.D3.D26.D2.D3.D9.D3.D26.D3.D12.D$D6.D3.D2.D7.D20.2D
6.D10.D3.D25.D3.4D10.D3.D24.2D3.D3.D9.D3.D24.2D4.3D10.4D$D6.D3.D3.3D
4.D22.D4.D11.D3.D24.D4.D3.D10.4D26.D2.D3.D10.4D26.D6.D9.D3.D$D6.D3.D
6.D3.D22.D3.D12.D3.D23.D5.D3.D13.D26.D2.D3.D13.D26.D6.D9.D3.D$D3.D2.D
3.D2.D3.D3.D2.D15.D3.D2.D7.2D4.D3.D22.D6.D3.D3.2D7.D23.D3.D2.D3.D3.2D
7.D23.D3.D2.D3.D3.2D4.D3.D$.3D4.3D4.3D5.2D17.3D3.5D3.2D5.3D23.5D3.3D
4.2D4.3D25.3D4.3D4.2D4.3D25.3D4.3D4.2D5.3D!

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Self-destruct search program

Post by calcyman » September 11th, 2016, 10:06 am

simeks wrote:Thanks! I consider it very experimental, so it's nice to see it produces useful results.
Indeed it does!

I'm thinking about how best to allow your algorithm to scale well to larger grids. I've written an O(n log n) spanning tree implementation (which can do a 100-node tree in 143 microseconds and a million-node tree in about 3 seconds), and am also midway through building a hybrid of HashLife and GolGrid.
What do you do with ill crystallographers? Take them to the mono-clinic!

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Self-destruct search program

Post by simeks » September 11th, 2016, 1:27 pm

calcyman wrote: I'm thinking about how best to allow your algorithm to scale well to larger grids. I've written an O(n log n) spanning tree implementation (which can do a 100-node tree in 143 microseconds and a million-node tree in about 3 seconds), and am also midway through building a hybrid of HashLife and GolGrid.
Sounds interesting! Makes me wonder what kind of patterns you're planning to destroy...

Anyway, I thought it might be time to create an official repository for GoLGrid, so the latest version is now available from here

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: Self-destruct search program

Post by Rhombic » September 13th, 2016, 10:55 am

Unless I am very wrong about how the script works, I think that it should be pretty easy to modify this to be able to run tLifeHistory and tDryLifeHistory too (or any non-totalistic Life-like History rule). Of course, blinkers would not be allowed.
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

simeks
Posts: 401
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Self-destruct search program

Post by simeks » September 13th, 2016, 5:45 pm

Rhombic wrote:Unless I am very wrong about how the script works, I think that it should be pretty easy to modify this to be able to run tLifeHistory and tDryLifeHistory too (or any non-totalistic Life-like History rule). Of course, blinkers would not be allowed.
Well, actually, the "History" part isn't really important. You could use standard LifeHistory to specify the problem. All that's really needed is a version of the GoLGrid_int_evolve_word function in golgrid.c that evolves a pattern for the rule in question.

That function is declared as:

Code: Select all

static __force_inline u64 GoLGrid_int_evolve_word (u64 upper_word, u64 mid_word, u64 lower_word)
Where upper_word/mid_word/lower_word represent a 64 cells wide by 3 cells high part of the pattern, where each bit in the 64-bit unsigned words represents a cell, and the result should be the evolved 64-by-1 cells in the middle (assuming off-cells on the left and right side of the 64-bit rectangle).

Post Reply