genfind: Search for spaceships in multi-state rules

[Rocknlol]

I've been sitting on this for a while but the code isn't getting any more readable so I'm releasing this now with some minor clean-ups.

genfind is a gfind derivative able to search for (currently only orthogonal) ships in multi-state rules in range-1 Moore (it can do about up to six states). It's admittedly a fair bit slower than other gfind-likes, but makes up for it in the breadth of rules it can search for.

You can download the latest version of genfind here.

genfind has both compile-time and run-time parameters. Compile-time parameters include tree and table sizes, width, and the rule, all of which you can modify in rule.cpp. If you have a POSIX OS or a compatibility layer like WSL, you can then compile it with "make". Run-time parameters include period, displacement, and symmetry. Pass those in as follows:

Code: Select all

./genfind <displacement> <period> <symmetry>

For symmetry, "0" is asymmetric, "1" is odd-width bilaterally symmetric, and "2" is even-width bilaterally symmetric. For example, the following search with the rule set to Life and the width set to at least 6 would find the Turtle:

Code: Select all

./genfind 1 3 2

Do note that for asymmetric searches the width in rule.cpp will be one higher than the actual width of the search.

Here is a showcase of some of the rules genfind can find spaceships for:

Code: Select all

x = 94, y = 22, rule = Symbiosis
2.2A13.2A40.B.B.B.B.B$59.B.B.B.B.B$2.A5.2B.2B5.A40.B7.B$3.2A11.2A13.A
2.2A5.2A2.A16.B.B$4.A4.B.B4.A15.3A7.3A15.B.B.B.B$.A5.B.3B.B5.A13.A2.
2B.2B2.A15.B2.B.B2.B$.A3.A.B5.B.A3.A40.B.B.B.B$3.A.A.B5.B.A.A17.B5.B
15.B4.B.B4.B$2A.A.A2.B3.B2.A.A.2A15.B3.B15.B.B.B.B.B.B.B.B14.2A.2A$4.
2A3.3B3.2A20.3B17.3B.2B.2B.3B14.A5.A$A3.A11.A3.A40.B3.B20.A.A$A.A.A.A
7.A.A.A.A14.A5.A39.2A3.A.A3.2A$.2A.A.A.A.A.A.A.A.2A13.A2.A3.A2.A13.A.
2A.A.A.2A.A11.2A2.A3.A2.2A$.2A.A.A7.A.A.2A11.2A3.A3.A3.2A10.A5.A.A5.A
10.4A5.4A$4.A.A.2A.2A.A.A19.A3.A16.2A3.A.A3.2A$3.2A.A.A3.A.A.2A13.A4.
A3.A4.A12.A3.A.A3.A13.2A.A.A.A.2A$5.2A7.2A19.2A3.2A18.2A3.2A16.3A.A.
3A$6.A7.A18.A.A5.A.A$5.2A7.2A16.3A7.3A17.3A21.A.A$6.2A.A.A.2A18.A2.A
3.A2.A17.A3.A16.B.B5.B.B$7.3A.3A20.3A3.3A19.A.A18.B2.3A2.B$8.A3.A22.A
5.A21.A19.B7.B!

Code: Select all

x = 52, y = 17, rule = inbredLife
2.A7.A$2.A7.A$.A9.A$2.A7.A$3.A.A.A.A$4.2A.2A14.A.A3.A.A$3.A.A.A.A13.
2A.A.A.2A$2.2A.A.A.2A12.2A.A.A.2A$3.A.A.A.A17.A$4.AB.BA17.A.A$4.A3.A$
5.3A16.2A.A.2A$A.A7.A.A11.A5.A14.4A$3.A5.A$3.A5.A15.A3.A12.A.A4.A.A$A
2.A5.A2.A13.3A14.A6.A$.3A5.3A14.3A14.B6.B!

Code: Select all

x = 12, y = 18, rule = Brew
2.C6.C$C.C6.C.C$.C8.C$.C8.C$5.2B$.2B6C2B$.2A6C2A$.B8AB$2.CB4CBC$2.A6B
A$2.A6BA$2.CBA2CABC$2.2AB2AB2A$.C.2A2C2A.C$BACA4BACAB$.2A6B2A$.2A.A2B
A.2A$5.2A!

Code: Select all

x = 138, y = 16, rule = Custom-Rule-1
128.2B5.2B$128.2A5.2A$129.2A3.2A$72.B3.B52.2A3.2A$72.2A.2A$72.2A.2A
52.2B3.2B$18.2A17.2A32.A2B.2BA49.B3A3.3AB$19.B17.B33.3A.3A18.BA.ABA3.
ABA.AB16.2A2.B.B2.2A$19.AB15.BA31.2A2.A.A2.2A17.2A.A2B.2BA.2A18.B.2A.
2A.B$19.3AB.B7.B.B3A32.B2AB.B2AB18.2AB3A.3AB2A20.5A$24.A7.A18.B.B16.
3AB.B3A22.BA.AB25.ABA$22.3AB5.B3A15.2A44.B3.AB3.BA3.B21.A$23.B2A.A.A.
2AB15.3A43.A2.A2.BA.AB2.A2.A$.AB20.2AB.3B.B2A15.2ABAB18.2A.2A19.2A4BA
.A4B2A20.3A$AB22.A.2AB2A.A17.3A19.A3BA19.2A.ABA3.ABA.2A20.3A$3A25.A
22.A21.3A24.A5.A25.A!

These two patterns were found with versions of genfind that I'm hoping to later incorporate into the public branch: A 2c/25 ship in Rule 2166637080 and a 2c/5 ship in NaiveLife:

wargo.png (17.55 KiB) Viewed 4349 times

Code: Select all

x = 23, y = 73, rule = NaiveLifeEmulated
23E$E21.E$E.B19.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E
21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.
E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E21.E$E8.A.A.
2A7.E$E7.2A.A.A8.E$E10.A.A.A6.E$E9.2A.A.2A5.E$E8.A12.E$E7.A.A.4A6.E$E
6.2A.A.A.2A6.E$E9.A.A.A7.E$E6.2A.A3.A2.A4.E$E7.A.A2.5A4.E$E6.2A.3A9.E
$E5.A.A.A2.4A5.E$E5.A.A.A.A.A7.E$E4.2A.A3.A9.E$E7.2A.A.2A7.E$E4.2A.2A
.A2.A7.E$E4.A.2A2.A.2A7.E$E9.2A.A.2A5.E$E10.A.A8.E$E9.2A.A8.E$E10.A.
2A7.E$E10.A10.E$E9.2A.2A7.E$E21.E$E21.E$E10.2A.2A6.E$E14.2A5.E$E9.A4.
2A5.E$E8.3A10.E$E6.A5.5A4.E$E5.A.5A9.E$E5.A15.E$E21.E$E9.A.2A8.E$E8.A
3.2A7.E$E21.E$E21.E$E21.E$E21.E$23E!

Now, please do keep in mind that the code in its current state is a big mess, and that it might be healthier to think of it as a prototype or a proof-of-concept rather than as a full-fledged search program. That being said, I'm hoping everyone can find some cool stuff with this!

[Sylvani]

The program doesn't work on my computer. It says "segmentation fault" no matter if it's a fresh install or with tweaked parameters.

[vilc]

The program doesn't work on my computer. It says "segmentation fault" no matter if it's a fresh install or with tweaked parameters.

How did you compile it and on what system ?
It works well for me on mingw-w64, compiled with the default make command. When I set WIDTH to 11 in rule.hpp and run :

Code: Select all

> genfind 1 2 1

[displacement : 1, period : 2, symmetry : odd]
The output is the following (it finds 70P2H1V0.1) :

Code: Select all

Setting up L0 edge table... Done!
Setting up L1 edge table... Done!
Setting up L2 edge table... Done!
1K      7       881
2K      8       587
3K      9       1754
4K      10      1264
5K      10      757
6K      12      991
7K      13      619
8K      14      760
9K      16      261
10K     19      316
11K     21      296
12K     24      413
13K     27      354
14K     31      212
Ship found at depth 31:

x = 0, y = 0, rule =23/3/2
$.....................$
.....................$
AA...A..A...A..A...AA$
....A....A.A....A....$
A...A.AA.A.A.AA.A...A$
.AA.A....A.A....A.AA.$
..A.A.A..A.A..A.A.A..$
...AA.A.AA.AA.A.AA...$
....A.A.......A.A....$
.......A.....A.......$
.....A.........A.....$
.....A...A.A...A.....$
......A..A.A..A......$
.......AAA.AAA.......$
!
Search took 0 seconds

[Rocknlol]

After a (very!) long time I'm happy to find release v0.2 of genfind, which is in all but name a completely new program. You can download it here.

v0.2 takes on a somewhat different approach than v0.1—I've dropped the arbitrary multistate support with the intention to instead focus on better specific classes of rules. I'm not currently planning on adding that back, at least any time soon, but if that feature actually saw use I'll certainly reconsider.

To this end v0.2's a somewhat limited release—orthogonal/outer totalistic-only, with Generations and Naive support. This includes symmetry, including what passes for symmetry in Naive rules.

I have my own rough plans for what I want to support in the future, but please let me know if any rule classes in particular would be of interest!

EDIT (03/26): genfind 0.2.1 is out, with support for diagonal ships and alternating rules