CatForce new catalyst search utility (LifeAPI based)

For scripts to aid with computation or simulation in cellular automata.
User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: CatForce new catalyst search utility (LifeAPI based)

Post by Scorbie » January 6th, 2018, 5:56 pm

danny wrote:I'm really sorry to necrobump this thread, but I'm running the example 1.in and it returns with no 1.rle and no console output. What's going on? I'm not very skilled in C. If you need it, here is the example 1.in:
Hmm, could you paste the messages on your terminal (with basic information such as your OS, 32/64bit, C compiler etc. would certainly help)? Mine goes like this: (in the examples directory)

Code: Select all

$ ../catforce 1.in
Input: 1.in
Initializing please wait...
Approximated Total: 2038431744

Initialization finished, searching...

13.8%,281M/2038M, cats/find: 1/1, now: 0:0:11, est: 0:1:19, 25547K/sec
Saving 1.rle
30.0%,611M/2038M, cats/find: 1/1, now: 0:0:21, est: 0:1:10, 29110K/sec
Saving 1.rle
47.4%,966M/2038M, cats/find: 1/1, now: 0:0:31, est: 0:1:5, 31186K/sec
Saving 1.rle
64.6%,1317M/2038M, cats/find: 1/1, now: 0:0:41, est: 0:1:3, 32122K/sec
Saving 1.rle
79.3%,1616M/2038M, cats/find: 1/1, now: 0:0:51, est: 0:1:4, 31704K/sec
Saving 1.rle
88.4%,1802M/2038M, cats/find: 1/1, now: 0:1:1, est: 0:1:8, 29549K/sec
Saving 1.rle
98.5%,2008M/2038M, cats/find: 1/1, now: 0:1:11, est: 0:1:12, 28282K/sec
Saving 1.rle
99.9%,2035M/2038M, cats/find: 1/1, now: 0:1:14, est: 0:1:14, 27510K/sec
Saving 1.rle


FINISH
Total elapsed time: 73.066585 seconds

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Post by dani » January 6th, 2018, 6:10 pm

Scorbie wrote:Hmm, could you paste the messages on your terminal (with basic information such as your OS, 32/64bit, C compiler etc. would certainly help)? Mine goes like this: (in the examples directory)

Code: Select all

CatForce output
First of all, thanks dearly for your help. Second of all, it's not outputting anything to the console. It just returns after less than a second with no output.

Code: Select all

Dan@[i]Computer Name[/i] ~/catforce
$ ./catforce 1.in

Dan@[i]Computer Name[/i] ~/catforce
$
Also I don't have an example directory, it's all in the same directory for me, it looks like this:
My directory for CatForce.
My directory for CatForce.
Untitled.png (113.94 KiB) Viewed 9455 times
EDIT: Oops, I forgot. My computer is Windows 7, 64-bit, I don't know anything about compilation so I wouldn't know how to check that, the .exe came with the file

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

Re: CatForce new catalyst search utility (LifeAPI based)

Post by Scorbie » January 6th, 2018, 6:13 pm

Whoop, I get it... Clicking catforce.exe won't work.
You should launch the terminal (type cmd + Enter on the file explorer's search bar) and type

Code: Select all

catforce.exe  examples/1.in
or something alike.

Edit: Actually, that might not work. I see you have Cygwin, so your best bet would be to launch mintty (this is cygwin's terminal as far as I remember), navigate to the catforce directory, and call something like

Code: Select all

./catforce examples/1.in
there.

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Post by dani » January 6th, 2018, 6:25 pm

Scorbie wrote:I see you have Cygwin, so your best bet would be to launch mintty (this is cygwin's terminal as far as I remember), navigate to the catforce directory, and call something like

Code: Select all

./catforce examples/1.in
there.
I get that, I typed

Code: Select all

./catforce 1.in
While in the catforce directory and it did the same thing. The examples are in the same directly. Running it does the same thing every time regardless of any input. Running it from mintty directly doesn't do anything different either.
EDIT: Should I try recompiling? How do I recompile the catforce.c? Am I missing any files in the screenshot?

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Post by dani » January 14th, 2018, 2:43 pm

Alright, so dvgrn sent me a helpful PM that got my CatForce working. Here's the PM in question:
dvgrn wrote:Okay, so today I downloaded CatForce and tried to get it running on a Windows 10 system.

I didn't get the behavior you saw -- immediate return to command line with no response -- but it was pretty close:
The code execution cannot proceed because libgcc_s_seh-1.dll was not found / libstdc++-6.dll was not found. Reinstalling the program may fix this problem.
To get CatForce to work, I had to throw away the downloaded executable and compile the program locally.

Luckily that's not as difficult as it might sound -- especially if you already have apgluxe running successfully. CatForce just needs one of the same tools, g++.

Here's everything I had to do:

Code: Select all

{open Cygwin64 Terminal}
cd c:
cd Users/Dave/Desktop/Catforce
{your path may vary -- just get to wherever you extracted the CatForce ZIP from GitHub}
g++ -O3 CatForce.c
{compiles the program, producing a.exe}
rm CatForce.exe
{old executable deleted}
mv a.exe CatForce.exe
./CatForce.exe 1.in
{starts doing a long search, displaying stuff in the Cygwin window}
Let me know if you try this and have questions. The key is that if you compile with Cygwin, you'll have to run the program in a Cygwin window -- a regular DOS command prompt will throw ugly errors (see above).
Extreme thanks to Dave for this.

EDIT: Added simeks' suggestion, an -O3 in the compilation.
Last edited by dani on January 14th, 2018, 3:31 pm, edited 2 times in total.

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

Re: CatForce new catalyst search utility (LifeAPI based)

Post by simeks » January 14th, 2018, 3:26 pm

danny wrote:...
dvgrn wrote:...

Code: Select all

...
g++ CatForce.c
...
...
...
But always compile with optimization, the executable will be at least 3 times faster:

Code: Select all

g++ -O3 CatForce.c

User avatar
Entity Valkyrie 2
Posts: 1756
Joined: February 26th, 2019, 7:13 pm
Contact:

Re: CatForce new catalyst search utility (LifeAPI based)

Post by Entity Valkyrie 2 » May 19th, 2020, 8:10 am

How to use CatForce? I tried running the application, but it came up with this error message:

Code: Select all

The application was unable to start correctly (0xc000007b).
Click OK to close the application.
Bx222 IS MY WORST ENEMY.

Please click here for my own pages.

My recent rules:
StateInvestigator 3.0
B3-kq4ej5i6ckn7e/S2-i34q6a7
B3-kq4ej5y6c/S2-i34q5e
Move the Box

yoleo
Posts: 124
Joined: October 26th, 2021, 11:48 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Post by yoleo » December 7th, 2021, 10:13 pm

My experiments with CatForce make me think there's a bug or compatibility issue lurking somewhere. Compiling CatForce with -O3 on a Linux based cloud machine then running 1.in yields a segfault message; if I do the same locally on a MacBook Air, it runs but fails to find any results. If I compile without -O3, in contrast, 1.in does find results: this is consistent across the two platforms. I tried running 2.in on the Linux cloud-based machine, compiling without -O3, and that failed to find results. (That took 150+ hours, though, so hard to test for consistency.)

I tried replacing the version of LifeAPI.h that comes with CatForce with the more recent version--that eliminated the segfault issue on the Linux machine, but 1.in still failed to find anything (independent of compiling with or without -O3).

UPDATE: removing all filters from the search typically eliminates the segfault. Fixing this bug is likely beyond my skill set, but I'll at least see if I can pinpoint the source of the problem.

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: CatForce new catalyst search utility (LifeAPI based)

Post by GUYTU6J » May 10th, 2022, 9:58 pm

Where is the code for the symmetric version that people have been using recently?

Unrelated, is there any non-totalistic version of CatForce?

mvr
Posts: 53
Joined: November 8th, 2009, 4:58 am

Re: CatForce new catalyst search utility (LifeAPI based)

Post by mvr » May 10th, 2022, 10:04 pm

The code is here: https://github.com/mvr/CatForce

As well as adding a symmetric search option, there are various changes that make it quite a lot faster than the original.

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: CatForce new catalyst search utility (LifeAPI based)

Post by GUYTU6J » May 10th, 2022, 10:54 pm

Did I make mistakes in the following steps? In WSL2 (Ubuntu 20.04 with the usual prerequisities for apgsearch), I git cloned the repository and then got these when compiling CatForce:

Code: Select all

azulena@LAPTOP-GG46SGQR:~/CatForce$ ./Makefile
-bash: ./Makefile: Permission denied
azulena@LAPTOP-GG46SGQR:~/CatForce$ g++ -o CatForce CatForce.cpp -O3 -Ofast -flto -march=native
In file included from CatForce.cpp:3:
LifeAPI.h: In function ‘Locator* Realloc(Locator*)’:
LifeAPI.h:788:1: warning: no return statement in function returning non-void [-Wreturn-type]
  788 | }
      | ^
azulena@LAPTOP-GG46SGQR:~/CatForce$ ./CatForce 1.in
Segmentation fault
The program after compiling has no .exe suffix.

EDIT: this seems to be part of the issue already mentioned by yoleo above.

mvr
Posts: 53
Joined: November 8th, 2009, 4:58 am

Re: CatForce new catalyst search utility (LifeAPI based)

Post by mvr » May 11th, 2022, 12:54 am

Give it another try now. If you just run 'make' then it should call the compiler for you. Also, for whatever reason, it runs much faster for me when compiled with clang rather than GCC.

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: CatForce new catalyst search utility (LifeAPI based)

Post by GUYTU6J » May 11th, 2022, 2:02 am

No, the same error is still shown for the program compiled in WSL.

In another attempt in Visual Studio Code (directly in Windows 10, no WSL involved), there are a bunch of unrelated errors:

Code: Select all

CatForceorig.cpp:61:33: error: '>>' should be '> >' within a nested template argument list
   std::vector<std::pair<int, int>> filterGenRange;
                                 ^
CatForceorig.cpp:96:33: error: '>>' should be '> >' within a nested template argument list
   std::vector<std::pair<int, int>> forbiddenXY;
                                 ^
CatForceorig.cpp:385:57: error: '>>' should be '> >' within a nested template argument list
                     std::vector<std::vector<LifeTarget *>> &forbidden,
                                                         ^
CatForceorig.cpp:420:56: error: '>>' should be '> >' within a nested template argument list
                    std::vector<std::vector<LifeTarget *>> &forbidden,
                                                        ^
CatForceorig.cpp:430:44: error: '>>' should be '> >' within a nested template argument list
     std::vector<std::vector<std::vector<int>>> &statexyGen) {
                                            ^
CatForceorig.cpp: In function 'void XYStartGenPerState(const std::vector<LifeTarget*>&, LifeState*, const SearchParams&, const std::vector<LifeState*>&, std::vector<std::vector<std::vector<int> > >&)':
CatForceorig.cpp:433:32: error: '>>' should be '> >' within a nested template argument list
     std::vector<std::vector<int>> xyVec;
                                ^
CatForceorig.cpp: At global scope:
CatForceorig.cpp:477:53: error: '>>' should be '> >' within a nested template argument list
 std::string GetRLE(const std::vector<std::vector<int>> &life2d) {
                                                     ^
CatForceorig.cpp: In member function 'std::string Category::RLE()':
CatForceorig.cpp:696:32: error: '>>' should be '> >' within a nested template argument list
     std::vector<std::vector<int>> vec;
                                ^
CatForceorig.cpp: At global scope:
CatForceorig.cpp:807:39: error: '>>' should be '> >' within a nested template argument list
   std::vector<std::vector<LifeTarget *>> forbiddenTargets;
                                       ^
CatForceorig.cpp:808:42: error: '>>' should be '> >' within a nested template argument list
   std::vector<std::vector<std::vector<int>>> statexyGen;
                                          ^
After fixing them (twice on line 430 and 808) manually, the g++ compilation without O3 flag succeeds in giving a CatForce.exe. But there is still something wrong with the pre-packaged 1.in as input:

Code: Select all

Input: 1.in
Initializing please wait...
Did not read any pattern!
What exactly is the difference between clang and gcc-g++, and does that make the compilation different on several platforms including Win10 and WSL2-Ubuntu?

mvr
Posts: 53
Joined: November 8th, 2009, 4:58 am

Re: CatForce new catalyst search utility (LifeAPI based)

Post by mvr » May 11th, 2022, 2:39 am

I think it will also give that error if the file is not found, is everything in the same directory? I don't have a Windows machine so I won't be able to diagnose the segfault, I'm afraid. clang and gcc are entirely separate compilers, there could be small differences in the way they are compiling this.

mvr
Posts: 53
Joined: November 8th, 2009, 4:58 am

Re: CatForce new catalyst search utility (LifeAPI based)

Post by mvr » May 12th, 2022, 11:16 am

Give it one more try now, Goldtiger997 spotted a missing 'return' that fixed the problem for him. Also, if you add the flag '-std=c++11' when you compile, it will hopefully stop complaining about the >>.

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: CatForce new catalyst search utility (LifeAPI based)

Post by GUYTU6J » May 12th, 2022, 11:57 am

A new kind of bug here, with the message printed in Win10's Command Prompt and WSL2-Ubuntu respectively:

Code: Select all

D:\cellular_automata\CatForce-master>g++ -o CatForce CatForce.cpp -O3 -Ofast -flto -march=native -std=c++11
In file included from CatForce.cpp:3:0:
LifeAPI.h: In function 'int Next(Enumerator&, int)':
LifeAPI.h:1795:17: error: invalid conversion from 'LifeState*' to 'int' [-fpermissive]
     Run(&temp, 1);
                 ^
LifeAPI.h:1795:17: error: too many arguments to function 'void Run(int)'
LifeAPI.h:1232:6: note: declared here
 void Run(int numIter) { Evolve(GlobalState, numIter); }
      ^

Code: Select all

azulena@LAPTOP-GG46SGQR:~/CatForce-master$ make
g++ -std=c++11 -O3 -march=native -mtune=native -fno-stack-protector -fomit-frame-pointer -o CatForce CatForce.cpp
In file included from CatForce.cpp:3:
LifeAPI.h: In function ‘int Next(Enumerator&, int)’:
LifeAPI.h:1795:9: error: invalid conversion from ‘LifeState*’ to ‘int’ [-fpermissive]
 1795 |     Run(&temp, 1);
      |         ^~~~~
      |         |
      |         LifeState*
LifeAPI.h:1795:17: error: too many arguments to function ‘void Run(int)’
 1795 |     Run(&temp, 1);
      |                 ^
LifeAPI.h:1232:6: note: declared here
 1232 | void Run(int numIter) { Evolve(GlobalState, numIter); }
      |      ^~~
LifeAPI.h: In function ‘char* ReadFile(const char*)’:
LifeAPI.h:1638:12: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
 1638 |       fread(buffer, 1, length, f);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
make: *** [Makefile:5: CatForce] Error 1

mvr
Posts: 53
Joined: November 8th, 2009, 4:58 am

Re: CatForce new catalyst search utility (LifeAPI based)

Post by mvr » May 12th, 2022, 12:11 pm

Oops, forgot to add a line, try again.

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: CatForce new catalyst search utility (LifeAPI based)

Post by GUYTU6J » May 12th, 2022, 9:38 pm

Now the segfault is back in WSL2-Ubuntu.

Code: Select all

azulena@LAPTOP-GG46SGQR:~/CatForce-master$ make
g++ -std=c++11 -O3 -march=native -mtune=native -fno-stack-protector -fomit-frame-pointer -o CatForce CatForce.cpp
In file included from CatForce.cpp:3:
LifeAPI.h: In function ‘char* ReadFile(const char*)’:
LifeAPI.h:1639:12: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
 1639 |       fread(buffer, 1, length, f);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
azulena@LAPTOP-GG46SGQR:~/CatForce-master$ ./CatForce 1.in
Input: 1.in
Initializing please wait...
Approximated Total: 2038431744

Initialization finished, searching...

Segmentation fault
Attempts in the Command Prompt just halts after initialization and gives no message.

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

Re: CatForce new catalyst search utility (LifeAPI based)

Post by calcyman » May 13th, 2022, 9:59 am

mvr wrote:
May 11th, 2022, 2:39 am
I think it will also give that error if the file is not found, is everything in the same directory? I don't have a Windows machine so I won't be able to diagnose the segfault, I'm afraid. clang and gcc are entirely separate compilers, there could be small differences in the way they are compiling this.
LLVM's automatic vectoriser is better than GCC's, so it can make huge differences to the speed of the internal GoL calculation routines.

That's the main reason for lifelib containing so much inline assembly -- it means that the code is correctly vectorised irrespective of which compiler you use.
What do you do with ill crystallographers? Take them to the mono-clinic!

yoleo
Posts: 124
Joined: October 26th, 2021, 11:48 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Post by yoleo » June 17th, 2022, 10:41 pm

I made a few modifications to symmetric CatForce to make searching for oscillators easier.

First, there's a "stop after catalysts destroyed" parameter:

Code: Select all

stop-after-cats-destroyed [N] 
If provided, this requires that all filters are met within N generations of when the catalysts are destroyed. ("Destroyed" meaning activated, recovered, then failed to be present for 10 consecutive generations.) This cuts down on false positives.

Second, filters now accept a symmetry parameter

Code: Select all

filter [gen/genRange] [targetRLE] [dx] [dy] [group]
This translates to: there is some g in the group such that g applied to the target appears in the pattern. This means one search covers all flipper-type oscillators. Just use the filter group that's the largest group containing the symmetry of the search pattern.

I also made a driver bash script to automate searching. It iterates through a list of active regions, a list of static symmetries, and a list of positions of the center of the active region. There's a lot of unexplored space here: I've run 1 catalyst with the big list, the half-dozen most common active regions, and various C2 and C4 symmetries so far, out to placements with x, y <= 8 and 100 generations. That took a day or two, at 10 seconds per search. That's how I found the p30 R hassler. [I found a bug in the script through bad positives today: I may have missed some flippers in the C2even and C4even symmetries.] I wouldn't use this for anything more than a few minutes per search, though. At that point, you should probably fine-tune the parameters more or pre-screen for promising active region placements.

Goals for future improvements: somehow tell CatForce "don't put non-transparent catalysts between the active regions" or "the active regions must interact within the first N generations." That would open up more territory, longer catalyst lists and further apart active regions.

EDIT: now on version 2. I found a few bugs with how I was determining which group to use for flippers. Also I made a helper script that'll determine if the active region is present, so that it can simply skip over those where the active region overlaps with its reflection.

EDIT^2 (July 6): now on version 3. Major improvement: RLE file names now include the generation(s) where the object reoccurs, eliminating the occasionally tedious "can you spot where the active region reoccurs?" part. Also added an option to disable flippers, plus some miscellaneous fixes. The version of CatForce included is just the depth-first branch of https://github.com/luke-kiernan/CatForce.
Attachments
CatForce_bash_osc_search_v3.zip
(36.9 KiB) Downloaded 26 times
Last edited by yoleo on July 23rd, 2022, 3:14 pm, edited 2 times in total.

carsoncheng
Posts: 471
Joined: June 11th, 2022, 11:24 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Post by carsoncheng » June 26th, 2022, 5:12 am

Is it a good option to rewrite CatForce with lifelib, or is LifeAPI faster for this purpose? Also, there doesn't seem to be D4 or D8 symmetry support in CatForce, and a lack of documentation on C2 symmetry support (I had to take a look at the source code to obtain the C2 symmetry option of "rotate180").

User avatar
ClippyCosmologist
Posts: 22
Joined: May 7th, 2022, 5:24 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Post by ClippyCosmologist » June 26th, 2022, 6:08 am

carsoncheng wrote:
June 26th, 2022, 5:12 am
Is it a good option to rewrite CatForce with lifelib, or is LifeAPI faster for this purpose? Also, there doesn't seem to be D4 or D8 symmetry support in CatForce, and a lack of documentation on C2 symmetry support (I had to take a look at the source code to obtain the C2 symmetry option of "rotate180").
I don't know about speed, but lifelib would have the advantage of making it easy to support ruletables, which I think would be nice.
"Human beings, five hundred years after the Scientific Revolution, are only just starting to match their wits against the billion-year heritage of biology." -- E. Yudkowsky

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: CatForce new catalyst search utility (LifeAPI based)

Post by pzq_alex » June 26th, 2022, 6:20 am

carsoncheng wrote:
June 26th, 2022, 5:12 am
Is it a good option to rewrite CatForce with lifelib, or is LifeAPI faster for this purpose? Also, there doesn't seem to be D4 or D8 symmetry support in CatForce, and a lack of documentation on C2 symmetry support (I had to take a look at the source code to obtain the C2 symmetry option of "rotate180").
Lifelib woukd be better for the purpose in that it supports arbitrarily large patterns, where LifeAPI will not fit large searches.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

mvr
Posts: 53
Joined: November 8th, 2009, 4:58 am

Re: CatForce new catalyst search utility (LifeAPI based)

Post by mvr » June 30th, 2022, 1:43 pm

A lifelib version would be cool, if anybody wanted to try putting that together! The most important thing for this application is being able to run a single life step as fast as possible. I did a quick test, and it seems that (this updated version of) LifeAPI is about 30% faster than apg::upattern<apg::VTile28, 28>, probably because it does not deal with the overhead of possibly many tiles. I hope that is the correct comparison.

Do the experts have any sense for whether CatForce could benefit from some more sophisticated approach, rather than the uint64_t[64] structure used currently?

carsoncheng
Posts: 471
Joined: June 11th, 2022, 11:24 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Post by carsoncheng » June 30th, 2022, 8:07 pm

Is apg::pattern (not apg::upattern) suitable for the purposes of CatForce? It could be faster than LifeAPI because of the property of storing the evolutionary sequences of similar patterns, but I don't know the realistic distribution of similar patterns that CatForce is facing when running patterns.

Post Reply