ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

CatForce new catalyst search utility (LifeAPI based)

For scripts to aid with computation or simulation in cellular automata.

CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 18th, 2015, 5:31 pm

I was working lately on new utility called CatForce.

It uses brute force placement of potential catalysts in some area, and validate the catalysts. It doesn't uses tree search so it doesn't care if some catalysts disappears for a while, or even all the catalysts disappear for a while. As long as they return in given number of generations (defined for each catalyst in the input), the search will continue.

It's made mainly as spartan alternative search to the existing search utilities. One major advantage in the brute force approach and not tree search, is that it can be accelerated using hardware parallel acceleration and each check is totally independent of the other checks (unlike in the current utilities that implement tree depth search, parallelization is very complex even if possible).

I made quite few optimizations to ensure no "absolutely useless" calculation effort is wasted. CatForce starts from the first generation it's relevant, and uses the order of catalysts correctly.

Please comment, report bugs and suggest improvements.

Link here.
Last edited by simsim314 on April 20th, 2015, 6:17 am, edited 1 time in total.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby codeholic » April 18th, 2015, 6:23 pm

Cool! Nice to see there is a new catalyst search program.

Things I can instantly say that I miss:

  • a way to read result patterns separately
  • a tool similar to 'survive' in the 'ptbsearch' suite
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1138
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 19th, 2015, 4:41 am

codeholic wrote:a way to read result patterns separately


It can be easily done - but I see no point. Writing python script with the current report should be straightforward.

codeholic wrote:a tool similar to 'survive' in the 'ptbsearch' suite


If I understand you right it's made to make sure some cells are live at the end. i.e. #F in bellman?

I can add target to the .in - it would be as same as #F in bellman. The report can report all the results, and the filtered as well. I can add flags what types of reports you get.

All these are very straightforward.

I can also allow filters for emitted gliders (i.e. report to separate place all catalysts solution with emitted glider).
----

Symmetry is another request which is not trivial to implement.

I've also few extra ideas I didn't implement yet:

- place limitation on a search area (all the catalysts should be in some small rectangle).
- try and combine few solutions to check out if they as well work as catalysts.

- Make depth recursion.
- Categorize the solutions and recurs on the most potential ones.

----

As a side note - it's the simplest implementation, and a straightforward code that allows transparency. Very easy to maintain and improve - at least at this stage.

Another branch of this utility is parallelization. This search utility can easily be moved to gpu and accelerated by factor of 30.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby codeholic » April 19th, 2015, 4:54 am

simsim314 wrote:If I understand you right it's made to make sure some cells are live at the end. i.e. #F in bellman?

Yes, that's what I meant. And it also does categorization, that you mentioned:
simsim314 wrote:- Categorize the solutions and recurs on the most potential ones.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1138
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 19th, 2015, 6:05 am

codeholic wrote:And it also does categorization


I must admit that categorization is not totally straightforward.

I think same category should be defined as: removing all the catalysts at the point where all interactions with catalysts ended, the remaining cells are the same. I think dvgrn could elaborate more on the topic of "similar" catalysts as he encountered this issue more than any of us (I guess).

EDIT As a side note, LifeAPI rle functionality is pretty limited. So probably CatForce should categorize the results, and place them into separated rle files. While python script for golly should be simple enough to combine the results into single report.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby dvgrn » April 19th, 2015, 9:41 am

simsim314 wrote:I think same category should be defined as: removing all the catalysts at the point where all interactions with catalysts ended, the remaining cells are the same. I think dvgrn could elaborate more on the topic of "similar" catalysts as he encountered this issue more than any of us (I guess).

Well, only if by "encountered" you mean "failed to finish writing the obvious code for longer than any of us". The exact method outlined above would speed up inspection of catalyst/catgl results by an order of magnitude or so, and very little would get missed.

In particular, this kind of categorization would mean that no one would ever have to look at all the catalysts that do something useless with a dying spark, or all the dozens of ways to stop each output glider, or all the cases where an eater2 does the same thing as a fishhook eater.
dvgrn
Moderator
 
Posts: 4036
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: CatForce new catalyst search utility (LifeAPI based)

Postby codeholic » April 19th, 2015, 11:04 am

It seems that there is an overflow somewhere

Checked: 5%, 2113M / 38654M, found: 0, elapsed: 1613
Checked: 5%, 2124M / 38654M, found: 0, elapsed: 1618
Checked: 5%, 2132M / 38654M, found: 0, elapsed: 1624
Checked: 5%, 2140M / 38654M, found: 0, elapsed: 1630
Checked: -5%, -2145M / 38654M, found: 0, elapsed: 1636
Checked: -5%, -2138M / 38654M, found: 0, elapsed: 1641
Checked: -5%, -2130M / 38654M, found: 0, elapsed: 1646
Checked: -5%, -2120M / 38654M, found: 0, elapsed: 1652
Checked: -5%, -2113M / 38654M, found: 0, elapsed: 1657
Checked: -5%, -2103M / 38654M, found: 0, elapsed: 1663
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1138
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 19th, 2015, 1:26 pm

codeholic wrote:Checked: -5%, -2145M / 38654M, found: 0, elapsed: 1636


Haha. Yes don't worry it doesn't influence the results - I didn't think that if the total count should be long long, the counter as well should be long long (this is stupid bug in the reporting level only).

By the way - the results.rle is updated constantly so if you get a solution you could see it.

Probably the system is not best if you have millions of solutions, as results.rle is updated every five seconds.

Thx for the feedback, will fix soon.

dvgrn wrote:The exact method outlined above would speed up inspection of catalyst/catgl results by an order of magnitude or so, and very little would get missed.


Thx for the feedback. I hope to add categories soon enough. Probably some basic rating system would also be nice.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 19th, 2015, 4:19 pm

Small update: codeholics' bug fixed.

options added:

filter <gen> <rle> <dx> <dy>

you can use several filters as well.

fit-in-width-height <width> <height>

Fit all catalysts centers into rectangle with size (width, height).

---

1.in file updated to contain all the options. ReadMe updated as well.

Will not report anything if the filter failed. I'll probably add an option to report everything that was found, even if the filter didn't passed, into separate rle.

EDIT I've added the full-report option, for those who want the full report ignoring the filters as well.
Last edited by simsim314 on April 20th, 2015, 4:29 am, edited 2 times in total.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 19th, 2015, 6:14 pm

I've a small issue with category: Lets assume some catalyst interaction ends iteration or two after another catalyst. The result is the same after two iterations, and in the same generation they get the same smoke.

How would I place those two into the same category?

Notice I'm pretty liberal here to let it loose for 3-5 ticks. This bothers me less than how to make them all be on the same "phase" while knowing some of them end a bit later/earlier than others? Notice if I let them loose too much some of the catalysts could be unstable again.

DEIT More annoying case mentioned by dvgrn: what if we have glider that was blocked by catalyst 5 times during 20 iterations. How would we know to place them all into the same category?

I think the correct way to go is a tree. Two catalysts variations can "converge" into the same leave after some number of iterations. So that different dying sparks will eventually converge into the empty universe (ignoring the catalysts), but on different generations. This is also true for gliders eaters - they will converge after few generations apart.

Another option to look at it is that some generations after the interaction - the pattern generates "cluster" of patterns. Two catalysts that have intersecting patterns in their clusters will be categorized into the same category. Those cluster can obviously grow, and discover new "intersections". Those clusters should be made of "large enough patterns" - say patterns with at least 10 cells.
Last edited by simsim314 on April 19th, 2015, 6:33 pm, edited 1 time in total.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby dvgrn » April 19th, 2015, 6:26 pm

simsim314 wrote:I've a small issue with category: Lets assume some catalyst interaction ends iteration or two after another catalyst. The result is the same after two iterations, and in the same generation they get the same smoke.

Can you post a pattern to illustrate the problem? I don't quite see the difficulty yet.

My theory would be that two sets of catalysts would end up in the same category if their output was bit-for-bit identical. If two catalysts take different amounts of time to recover -- the eater vs. eater2 would be the classic example -- then as long as the extra recovery time makes no difference to the final state of the pattern at T=???, an eater variant and an eater2 variant will end up in the same category.

In some cases the difference in recovery time is critical -- either the eater recovers fast enough to do a second catalysis successfully where the eater2 can't, or the eater2 stays out of the way of a dying spark for long enough and the eater doesn't. In those cases there will be only one successful catalysis out of the two cases, so no category is needed.

I have the feeling that I missed the point of the question, though...?
dvgrn
Moderator
 
Posts: 4036
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 19th, 2015, 6:36 pm

dvgrn wrote: then as long as the extra recovery time makes no difference to the final state of the pattern at T=???


My question was - how to calculate T. But see my update, I bring up another annoying case: eater after 4*N generations, and N could be pretty big. Getting empty universe after T=200 is actually a bad idea I think. As some die-hards can be good catalysts material.

EDIT In other words: how do you distinguish glider+eater that takes 50 generations to eat and very nice die-hard that takes 50 generations to die? They both end up in an empty universe after T=50.

EDIT2 As a side note LifeAPI has very nice support for glider recognition and elimination. So this particular case (glider + eater) can be solved with LifeAPI tools. But I guess we're looking to solve more general case.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 20th, 2015, 5:14 pm

CatForce went through major refactoring. The old long and ugly spaghetti is now replaced by class with logical names. Comments in main added for additional clarification.

People who know programming are now very welcome to contribute/comment/ask questions/make suggestion for improvement of the current code.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby dvgrn » April 20th, 2015, 10:30 pm

simsim314 wrote:EDIT In other words: how do you distinguish glider+eater that takes 50 generations to eat and very nice die-hard that takes 50 generations to die? They both end up in an empty universe after T=50.

Measuring die-hard sparks for "niceness" seems like kind of a separate issue, just by the way: a 50-tick diehard might be totally useless if it turns on no new reaction-envelope cells, or it might be really promising if it travels into a large new territory before it dies.

I'm actually quite happy with a glider+eater and a diehard ending up in the same category, I think. At least for catgl-type searches, the difference is that when you try searching the same reaction with an additional catalyst, a nice diehard will produce some new categories, whereas an absorbed glider won't.

There are always some possibilities that won't be explored fully, just because they're at the edge of the current search space. A careful inspection of the results could still find the interesting diehard -- it's just that it's much easier if a quick review of all the categories can be done first. You never know, one of the categories might occasionally be exactly what you're looking for, without any need to search further...!

-- Maybe there's some way of categorizing based on the shape of the reaction envelope instead. But I think then you get right back into every possible glider absorption ending up in its own category -- though you could probably get eater and eater2 absorptions into the same category, at least.

How about sorting the catalyses within each category, according to the number of cells in the reaction envelope, so that the bigger ones show up as the default examples for the category? I don't know -- that would probably turn out to be the interesting diehards in some cases, but it would be the maximally useless ways to catch a glider at the last possible moment in other cases.
dvgrn
Moderator
 
Posts: 4036
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 22nd, 2015, 2:57 pm

I've commited to CatForce categories analysis and report. You're welcome to check it out. I've also modified the prints to be more informative.

As for categories analysis: I just took 5 generations difference.

As for my question the only thing I needed to do is: evolve the "category key" or the added LifeState to the same generation. As they both after catalyst has done working should behave the same. This will obviously include fast dying spraks and eaters.

As for glider + eater vs diehard - CategoryKey will evolve 4 * N ticks to check out that the result is the same for eaters. But for diehard CategoryKey will evolve only 5 ticks. If the die hard died - great we will include it in the same category, if not - diehard has different information and will be in separate category.

One could stop comparing two LifeStates with small population as they don't have enough information for comparison. In this case all eaters will be included into different categories. That's all the difference. I think eaters should be in the same category.

EDIT I've added a 3.in example to show case the categories. I've also committed all the spartan catalysts (in 2.in as well).

EDIT2 Now new problem arose:

x = 22, y = 11, rule = B3/S23
2bo12bo$obo10bobo$b2o11b2o4$4b2o$5bo12b2o$5bobo11bo$6b2o11bobo$20b2o!


To solve it I'll add forbidden flag to the cat setup. If forbidden present in the result with the catalyst, CatForce will just remove it. I don't see any use to it. (Similar flag could just remove forbidden from the category).
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 22nd, 2015, 6:16 pm

Forbidden flag added to catalysts. Now everything regarding categories, similar catalysts, and eaters converting gliders to SL is solved. See 3.in for syntax on how to use forbidden flag.

Eaters are now simply removed from the report.

EDIT Small update: last-gen flag added. It's now possible to limit the first generation the catalysts start to work. Used for example to search for eaters - as the spaceship is repeating pattern there is no point to search an entire space, but on the other hand it doesn't limits the catalyst location in any way, just ensure the first encounter is before generation T.
Last edited by simsim314 on April 23rd, 2015, 11:47 am, edited 1 time in total.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 23rd, 2015, 6:20 am

As a side note, CatForce is great starting point for gencols alternative based on LifeAPI.

In more details: I was thinking of something between complex command line arguments and scripting language for basic Life searches. Something where you can define patterns, symmetries, search areas and filters. More advanced scenarios might include - remove k gliders from synthesis and try to find k - 1 glider combination.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 24th, 2015, 12:12 pm

I need some advice in the catalyst search approach:

I did something pretty interesting: I've combined all results from single search into pairs, triplets etc. and I got around 6K different categories of working catalysts combinations for Herschel.

Now the question is:

1. How to sort out the results? I remember Guam talked about removing all the common patterns like pies, r-pentaminos, herschels etc. and check out if after some of the removal we get everything empty? (gliders removal automated already). Anyway the question is how to get meaningful report of results for different purposes (filter is already included, but I guess we need more subtle prioritization algorithm). Looking by hand through 6K pattern is pretty tedious, and most of the results are simply irrelevant or at least need further deepening.

2. The next question is how to proceed recursively? Having 6K results in the first generation of search, requires some kind of prioritization, for the next level. One parameter I thought about is number of single catalysts that can be placed in the result. So lets say if the catalyst end with block in the center, there is no option to add any catalyst. On the other if something moved far away and the interaction continues - there is plenty of new options opened, so we need to investigate those first. On the other hand G->H or G->G will not benefit from this approach as the chances to get back the "sacrificed" SL are getting lower.

NOTE I'll post some of the results soon, and the code as well (CatForce is not fully accustomed to this introduction).

EDIT I've attached the results from search on combining all the single catalysts to hersch.
Attachments
Pairs8Herschel.rle.gz
(34.47 KiB) Downloaded 174 times
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 26th, 2015, 6:07 pm

I've published a new version with very cool feature called combine-results.

The main idea of this feature is that if we have some interaction, and catalysts A and B working for it, then there are many chances that also A + B will also work as catalyst. It starts from the regular search results, and then will try to add the catalysts to make pairs, triplets etc.

For usage and more information see README.md for CatForce (See combine-results yes section)

NOTE If you use this feature notice the results will ignore your filters and stability inputs. They will be only applied at the Final report. This is made to allow more potential catalysts to enter the search space, to increase the possible combinations. For example if A will die after 2 iteration from activation, and B will die after 5, A+B could be stable catalyst that will remain stable. Also A+B could comply to the filter while not A nor B would comply.

I intend to introduce more extreme version of a filter that will filter results as they come and will not wait for the final results, just to reduce the mess. Anyway this is just performance issue, and a bit cleaner result files, which I intend to improve anyway.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby Kazyan » April 27th, 2015, 12:02 am

Might be a false alarm, but...are you able to run CatForce for multiple-hour durations, Simkin? I think there's a memory leak in the run I'm doing right now. Is it supposed to be eating 87% or so of my machine's memory intermittently?

EDIT: Yep; Ubuntu eventually killed it due to an "out of memory" situation.
Tanner Jacobi
User avatar
Kazyan
 
Posts: 713
Joined: February 6th, 2014, 11:02 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 27th, 2015, 3:02 am

Kazyan wrote:..are you able to run CatForce for multiple-hour durations


Yes definitely, I've did 24 hour run without any memory issues.

1. Please take the latest version.

2.There was in the first versions real memory leak. This is fixed few weeks now.

3. There is a memory intensive operation during the reporting. This is not memory-leak but memory intensive operation, that sometimes gets out of memory during the reporting stage. This was fixed yesterday when I "officially" released the combine-results flag.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby Kazyan » April 27th, 2015, 3:22 am

Right, I got it now. It's working fine. Thank you for being patient and answering my inane questions all the time.

After getting the hang of how to use the input files, this program is incredible for finding transparent catalysts, which are the major unexplored area of Spartan search space. Props and thanks.
Tanner Jacobi
User avatar
Kazyan
 
Posts: 713
Joined: February 6th, 2014, 11:02 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 27th, 2015, 4:13 am

Kazyan wrote:After getting the hang of how to use the input files


I've included some very nice samples to make your life easier. I am also trying to keep updated the Readme with all the options and configurations covered.

Kazyan wrote: this program is incredible for finding transparent catalysts, which are the major unexplored area of Spartan search space


If you want to get into unexplored areas, I would start from searching with 3 catalysts and use fit-in-width-height. Another options is to increase the catalysts to 4 and use less catalysts (i.e. blocks only or blocks with eaters). CatForce finds in two minutes the 4 block catalyst for Herschel, in pretty large area -you just need to limit the search rectangle (i.e. fit-in-width-height). In this case I wouldn't use combine-results yes.

After getting new transparent stuff I would continue with 1-2 catalysts and combine-results yes

EDIT I'm planning to automate this sort of searches, i.e. stage deepening.

EDIT2 Please (continue to) comment, report bugs, suggest improvements and of course - post your findings :)
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Re: CatForce new catalyst search utility (LifeAPI based)

Postby Scorbie » April 28th, 2015, 3:16 am

I'm not sure if others would need this, but can there be a 'negative filter' for the pattern? e.g. eliminating the FNG of a Herschel or eliminating the block of the B-heptomino.
EDIT: How did you make 2.in work so fast? Does catalyzing moving objects take more time than static ones? My input file was like this: (catalyzing a b-heptomino)
max-gen 80
start-gen 1
num-catalyst 3
stable-interval 15
search-area -20 -20 40 20
pat 2bo$b3o$2obo!
filter 20 2o$2o! 1 4
cat 2o$2o! 60 0 0 . forbidden obo$b2o$bo2$2o$2o! 0 -4 forbidden 2o3bo$2ob2o$4b2o! 0 0 forbidden b2o$b2o2$bo$2o$obo! -1 0 forbidden 2o$b2ob2o$o3b2o! -4 -1 forbidden o3b2o$b2ob2o$2o! -4 0 forbidden obo$2o$bo2$b2o$b2o! -1 -4 forbidden 4b2o$2ob2o$2o3bo! 0 -1 forbidden 2o$2o2$bo$b2o$obo! 0 0
cat 2o$o$b3o$3bo! 12 -2 -2 * forbidden 2o$o$b3ob2o$3bobobo$6bo! -2 -2 forbidden bo$obo$2o2$2o$o$b3o$3bo! -2 -6 forbidden bo$2bo$3o2$3b2o$3bo$4b3o$6bo! -5 -6 forbidden 2bo$obo$b2o2$3b2o$3bo$4b3o$6bo! -5 -6
cat bo$obo$obo$bo! 40 1 2 /
cat b2o$o2bo$bobo$2bo! 35 2 2 +
cat bo$obo$bo! 15 1 1 .
cat 2o$obo$bo! 25 1 1 +
cat 2o$obo$b2o! 35 1 1 |
output bhept.rle
#full-report bhept-full.rle
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1329
Joined: December 7th, 2013, 1:05 am

Re: CatForce new catalyst search utility (LifeAPI based)

Postby simsim314 » April 28th, 2015, 5:27 am

Scorbie wrote:but can there be a 'negative filter' for the pattern


I can add it but I do have workaround currently. Just use last-gen flag. last-gen N means that the first interaction will start before generation N. This usually removes all the "junk" catalysts that leave FNG or block.

Scorbie wrote:How did you make 2.in work so fast?


2.in uses feature called fit-in-width-height. This feature makes sure all the catalysts are inside the same rectangular area with some width and height. This will work faster but obviously will not cover the whole 3 catalysts space.

--

I guess your input will run for few days at least. You've added 3 catalysts, and asked them to run in 40x20 rectangle. This is very strong request. If you're looking for transparent catalyst consider limiting the catalyst by rectangle using fit-in-width-height.

Another way to reduce the run-time is to use less catalysts. Like try to add blocks+eaters only.

EDIT Just saw last-gen wasn't in the ReadMe. Guys please tell me if I mention here something which isn't in the ReadMe. I try to keep it updated, but sometimes miss things, there are many small stuff which hard to keep track.
User avatar
simsim314
 
Posts: 1516
Joined: February 10th, 2014, 1:27 pm

Next

Return to Scripts

Who is online

Users browsing this forum: No registered users and 1 guest