CatForce new catalyst search utility (LifeAPI based)

[mvr]

I thought that those benefits only kicked in when advancing a pattern by many generations, rather than just by 1.

[GUYTU6J]

(Edited to remove unnecessary expression of frustration)

For new starters unfamiliar with clang, don't follow the steps from the official website to install llvm! You will find yourself either dowloading a 213 MB llvm-project-main.zip from github which decompress to over 1 GB files, or spending three hours running build and make which consumes 6.37 GB of disk space when completed.

llvm.png (6.58 KiB) Viewed 2103 times

Moreover, doing so does nothing good to CatForce; the latter's make file will complain that it cannot find command clang++.

The right way to get the compiler is to enter this command:

Code: Select all

sudo apt-get install clang

See the post below for more details about executing CatForce, and (to cfc) thanks for pointing this out.

[confocaloid]

(As usual: everything is provided as is, no warranty of any kind whatsoever, etc.)

I had clang already installed on my system, IIRC with these commands:

Code: Select all

# sudo apt-get update
# sudo apt-get install build-essential
# sudo apt-get install clang

To test CatForce, I did this in a new directory (some output lines are omitted for clarity):

Code: Select all

# mkdir test
# cd test
# git clone https://github.com/luke-kiernan/CatForce.git
# cd CatForce
# ls
1.in  2.in  3.in  4.in  CatForce.cpp  LifeAPI.h  Makefile  README.md  sym.in
# make
# ls
1.in  2.in  3.in  4.in  CatForce  CatForce.cpp  LifeAPI.h  Makefile  README.md  sym.in

After compiling I did this (the output of CatForce omitted for clarity):

Code: Select all

# ./CatForce 1.in
# ls
1.in  1.rle  2.in  3.in  4.in  CatForce  CatForce.cpp  full.rle  LifeAPI.h  Makefile  README.md  sym.in

The output of CatForce was:

Code: Select all

Input: 1.in
Initializing please wait...
Approximated Total: 2038431744
Total elapsed CPU time (not wallclock if nthreads>1): 1.722665 seconds

Initialization finished, searching...

0.1%,1M/2038M, cats/total: 0/0, unfiltered: 0/0, now: 0:00:13, est: 7:04:35, 80K/sec
Saving 1.rle
Saving full.rle
0.1%,2M/2038M, cats/total: 0/0, unfiltered: 0/0, now: 0:00:23, est: 6:13:47, 91K/sec
Saving 1.rle
Saving full.rle
0.2%,4M/2038M, cats/total: 0/0, unfiltered: 0/0, now: 0:00:42, est: 5:40:28, 99K/sec
Saving 1.rle
Saving full.rle
0.3%,6M/2038M, cats/total: 1/1, unfiltered: 1/1, now: 0:01:02, est: 5:34:48, 101K/sec
Saving 1.rle
Saving full.rle
0.4%,7M/2038M, cats/total: 1/1, unfiltered: 3/3, now: 0:01:12, est: 5:33:11, 101K/sec
Saving 1.rle
Saving full.rle
0.4%,7M/2038M, cats/total: 1/1, unfiltered: 3/3, now: 0:01:18, est: 5:40:06, 99K/sec
Saving 1.rle
Saving full.rle


FINISH
Total elapsed CPU time (not wallclock if nthreads>1): 77.388723 seconds

1.rle created by CatForce:

Code: Select all

x = 0, y = 0, rule = B3/S23
23$22bo13bo$22b3o9b3o3b2o$25bo7bo5bobo$24b2o7b2o4bo$38b2o$31bo$30bobo$29bo3bo$29bo3bo$29bo3bo$30bobo$31bo66$

full.rle created by CatForce:

Code: Select all

x = 0, y = 0, rule = B3/S23
23$22bo13bo$22b3o9b3o3b2o$25bo7bo5bobo$24b2o7b2o4bo$38b2o$31bo$30bobo$29bo3bo$29bo3bo$29bo3bo$30bobo$31bo66$28$31bo$30bobo$29bo3bo$29bo3bo$29bo3bo$30bobo$31bo$38b2o$24b2o7b2o4bo$25bo7bo5bobo$22b3o9b3o3b2o$22bo13bo61$28$31bo$30bobo$29bo3bo$29bo3bo$29bo3bo$30bobo$31bo$38b2o$33b2o4bo$33bo5bobo$27b2o5b3o3b2o$27b2o7bo61$

All this to say that the program compiles successfully and seems to run correctly as far as I could test (I do not have experience with actually using CatForce, so I did not continue further). I think the whole process took about ten minutes; IIRC installation of clang took approximately the same time.

Writing this post down took some 40-50 minutes, I think.

Why on earth people develop a program and require anyone using it to install a special compiler from a gigantic project? You cannot expect everyone to have 6.37 GB of free space, and there is no warning about it

I think this software is intended for people able to install and use a well-known compiler.
(Of course, feel free to continue this discussion in Sandbox if you think that's something reasonable and does not break any forum rules. I think non-Sandbox threads are not the place for discussing matters that are totally unrelated to CA.)

[mvr]

I don't have a Windows machine, I can't test on Windows. There are only two source files, CatForce.cpp and LifeAPI.h, if you create a new MSVC project (or something, I don't know how it works) with just those files, that might already be enough to build it.

[GUYTU6J]

Another nooby question: how do I specify variable pattern offsets under some symmetry?

For example, with these commands

Code: Select all

pat o$obo$3o$2bo! 4 4
symmetry C4_1

the tested active pattern will only be

Code: Select all

x = 15, y = 15, rule = B3/S23
bo$b3o8b3o$bobo9bo$3bo7b3o8$b3o7bo$bo9bobo$3o8b3o$13bo!

But I want to try other offsets like 5 5 and 6 6 in the same search because I cannot tell which is/are more promising with naked eyes. So how?

[mvr]

There isn't currently a way, you have to run CatForce separately for each offset. yoleo is working on fixing this!

[yoleo]

Here's some scripts to convert between normal plaintext catalyst lists, csv catalyst lists, and rle. (I find CSV's a lot easier to modify than plaintext: it prevents against additional spaces or swapping entries.)

[yoleo]

How to use symmetric CatForce:

Technical setup:
Step 0: install clang. This is already on Macs. On Linux, something like

Code: Select all

sudo apt install clang-11 --install-suggests

should work. I don't know how Windows stuff works.
Step 1: clone master and depth-first-periodic branches of CatForce from mvr's GitHub repo.

Code: Select all

git clone https://github.com/mvr/CatForce.git

would work. Or just download zip's via your browser and click and drag the folder.
Step 2a: cd into each folder and run

Code: Select all

make

. You might need to change

Code: Select all

CC = clang++

to

Code: Select all

CC = clang++-11

.
Step 2b (optional): figure out where profiling data for the clang compiler is kept. In the Makefile, set PROFDATAEXE equal to that location, and run

Code: Select all

make instrument

. The location should be something like /usr/bin/llvm-profdata-11 (Linux) or /Library/Developer/CommandLineTools/usr/bin/llvm-profdata (Mac). Apparently this helps performance, but I can't tell you why or how much.
Step 3: inside each folder, create an empty folder named masks. CatForce will store masks here, which dramatically speeds up the initialization step when running a search with catalysts you've used before.
Step 4: run

Code: Select all

./CatForce examples/1.in

This should yield: results: 1/1, unfiltered: 3/3.

How to use it to find things:

If you're trying symmetric combinations of active regions, then use a driver bash script that I wrote. This just creates input files and feeds them into CatForce; I've attached the current version that I'm using for a p7 periodic CatForce search. The "main parameters to edit" are marked pretty clearly in the script. It also requires a few other .cpp and .py files: I've posted these previously. (Worth mentioning: the .cpp files use stuff in LifeAPI.h, so they need their own rules in the Makefile. Just copy-paste the rule for CatForce and change each instance of 'CatForce' to 'active_region_occurs:' that should work.) Look for a .zip attachment maybe 10 posts back, titled something like "CatForce_bash_osc_search_v3."

I typically copy-paste around catalysts and sparkers until I have a list I like. I run it in debug mode (debug="true") until I'm satisfied I didn't make any typos. (It's easy to accidentally forget a \n or put two spaces somewhere: always open the temp.txt input file and double-check things.) Then I switch debug to false, and make sure I didn't make a search that'll take forever: I typically aim for 2-5 minutes per offset. (The script prints the averages.) In my experience, this usually means either a 2-catalyst search with about 50 catalysts (eg tiny or small list in catlists folder), or a 3-catalyst search with about 15-20 catalysts, assuming things are non-transparent. (Here I count with symmetry: eg all 8 orientations of fishhook = 8 catalysts.) Once I'm satisfied with that, I'll let it run for a few days. Also, the stop-after-cats-destroyed parameter is very useful for minimizing false positives.

If you're doing a lone active region, then one option is to set a filter for the active region re-occuring in the same spot. However, that won't catch instances where the region flips or reappears in a different spot. CatForce doesn't have filters to catch these things, but mvr made a script that will filter the results, and report which objects resulted. Download the catfilter.py script from mvr's golchemy repo. (This requires setting up Lifelib.) Then run

Code: Select all

python3 catfilter.py results.rle

. This results in two things: a .rlefiltered text document, and a .rlegroups rle. The .rlegroups can be opened in Golly. If you want to look for shuttles, I'd think of using control+F to search the .rlefiltered report for the active region you started with. A few words of warning for using catfilter.py: first, make sure to use a standard form of the active region, not a predecessor. Second, it relies on the results falling between certain (x,y) coordinates: if you open the results file in golly and re-save it, that spacing may change. I also suspect the script only works with stable catalysts, not with sparkers.

Related: catfilter.py makes conduit hunting very feasible. Run CatForce searches (from 1 cat, big list to 4 catalysts, fishhook+block) on an active region (stairstep, century aren't too well-searched), filter the results with catfilter.py, run a second search on the most promising ones, etc.

What I do when I have a partial that might work
0. If there's sparkers involved, work out the period. Also take note of whether the sparkers interact once, or more than once. If things only interact once, you might be able to find other sparkers that divide the period and do the same job.
1. Copy and paste the partial into a new layer in golly. If there's symmetry involved, make sure it's centered: quick way to tell is to use control + A to select the region. If the left edge is at -n, you want the right edge should be at n or n+1. Same for top and bottom. Set the pat parameter in your search file: don't forget the dx dy, the upper right corner of the region.
2. Note the dimensions: if it's C2, even width, odd height, then you want

Code: Select all

symmetry C2horizontaleven

in your search file. Odd width, odd height is just C2. Even width, even height is C2even. (See the CatForce readme for other symmetries--C2 just has the most variants.)
3. Add a filter to make sure the active region re-occurs. (Might also add filters to make sure the existing catalysts recover ok, and that the sparkers aren't destroyed.)
4. Start by running a 1-catalyst search with the big list. If this doesn't yield anything, then I'll go do a 2 catalyst search with the tiny list.
Attached is a sample for a p90 R hassler. If I keep getting 0/0, I sometimes wonder if I just set things up wrong: a good way to check this is to add a full-results output (which saves solutions that don't meet the filters), or delete the filters one-by-one until you start getting results.

[yoleo]

Here's a Lifelib mock-up of the CatForce algorithm. I started writing this when I was wondering about implementing the overlapping subclasses in python, but I ended up switching back to C++. It's very rough around the edges (I think it's currently reporting each solution 4 times, for unknown reasons) and quite slow. But someone requested I post this, so here it is.

Here's also some scripts for generating periodic CatForce catalyst lists, with sample inputs. You can include stable catalysts as well. edit: The rle-to-csv one is a golly script. The csv-to-plaintext one is a plain python 3 script, just run it from command line.

I've also attached a more thorough compilation of high period (7+) sparkers. (Edit: forgot the symmetry character for one of them. Fixed now.)

[yoleo]

Seems like I can't add more than 3 attachments to a post, so I guess I have to double-post. Attached is a Lifelib script that will group results by the generation of match. Syntax:

Code: Select all

python3 categorize_by_match_multi.py [rleToMatch] [earliestGen]-[latestGen] results_1.rle ... results_n.rle > combined_results_grouped_by_match_gen.rle

It looks for all orientations and positions of the rleToMatch, within the specified range of generations. You can feed it one RLE file, or a list of RLE files--either way, it'll combine the categories such that the pattern appears in the same gen. The rleToMatch can be a path to a .rle file, or an rle string. (If you go the second route, don't forget that $'s have a special meaning in a shell! Enclose the rle with single quotes.) This should make going over results from my bash script a lot faster--just use regex to run this script on all the outputs with given symmetry.

edit: maybe not as useful as I thought. Issue #1 is the fact that sometimes the region re-appears, but in a different spot than where it was in gen zero (since I'm searching for oscillators). Issue #2 is wraparound problems: CatForce runs on a 64x64 torus, but Lifelib runs in on a plane. I'm working on a better version, with a location parameter (options: any, same as gen 0, or some specific coordinates) and wraparound fixed. Will update this post once it's done (a few days)