Adapting Gencols

[Paul Tooke]

Paul Callahans 'Gencols' collision enumeration program is a useful utility, albeit tricky to master, but as with many utilities it has its limitations and these introduce a temptation to roll ones sleeves up and tweak the code. As a result I have made a number of modifications that make it more useful to me. I suspect others may have done so also. When I mentioned on the "Other rules" forum that I had adapted Gencols to handle CA rules other than Life, Ntsimp asked whether I would be willing to share the code. Well here it is in the attached file. [EDIT: anyone who downloaded gencols-pat-001.zip might want to download the latest file here. The original had a typo that affected periodicity detection]

I started this new topic in the hope that it would prompt other Gencols users to share the modifications they have made. Not necessarily the code: sometimes just a description of how to make the modification may be better, partlicularly if one already has a non-standard build.

For example, here is a recipe for adapting Gencols to handle rules other than Life. It assumes some C knowledge, because you are going to have to write some code yourself.

Step 1. Eliminate Life-specific fast generation code.
Edit the defs.h file and look for the line that says "#define USEBOXES 1" and comment it out.
Rebuild Gencols without boxes.c.
The result should run correctly, albeit slightly slower, and it will still only use the Life rule.

Step 2. Add the CA rule parser.
The file lists.c contains an array called rule and a function called gensparse() that uses it. Add a setrule(char *) function to populate this array from a rule string. If, as I did, you wish to handle more than just totalistic rules then you will need a larger array and will need to adapt gensparse() to handle this.

Step 3. Add the command line parameter
Open gencols.c and look for a long string of if .. else if constructs looking a bit like the line below. Somewhere in there insert

Code: Select all

		} else if (!strcmp(argv[argind],"-rule")) {
			setrule(argv[++argind]);

Rebuild gencols and now you can specify the rule on the command line by adding -rule myrulestring to the command line. I went a bit further than this and got Gencols to read rule strings from the pattern file and write them to output.

[David]

I need Python file, not C.

[calcyman]

Gencols is a C program, and translating it to Python would only reduce the speed (and significantly so).

[Nathaniel]

I haven't used gencols myself, so forgive my ignorance -- is it the type of thing that would benefit from a distributed search setup? That is, would it be a reasonable modification to make to have a downloadable executable file for people to run and have it automatically choose some particular search to perform and then upload the results of the search? Or is it the type of thing where search parameters have to be chosen fairly carefully by the user to produce anything interesting?

[dvgrn]

I haven't used gencols myself, so forgive my ignorance -- is it the type of thing that would benefit from a distributed search setup? That is, would it be a reasonable modification to make to have a downloadable executable file for people to run and have it automatically choose some particular search to perform and then upload the results of the search? Or is it the type of thing where search parameters have to be chosen fairly carefully by the user to produce anything interesting?

There are some basic problems related to making distributable versions of any of the commonly used Life search utilities -- gencols, lifesrc, catalyst/ptbsearch, dr, etc. The first is the potential asymmetry between the problem and the results: a problem description just a few hundred bytes long might produce megabytes of solutions. Or it might produce nothing at all, or anything in between. Second, it might take an arbitrarily large amount of time to return either a multi-megabyte or a nothing-at-all result.

The nothing result would be easy to relay back to the server, of course, and could sometimes be useful to know, especially in conjunction with an online database that records negative results of this type so that the same search never has to be tried again. However, a distributed search setup probably won't work too well if there are megabytes of results coming back from each client.

Unfortunately it's usually hard to tell what you're likely to get without running the search -- or, more likely, starting to run it and then cancelling and adjusting the parameters depending on the partial results.

Gencols is likely to be one of the worst offenders in the big-results department, actually, as the name suggests -- it generates all possible collisions between two (or more) objects. In many cases it would be faster to regenerate a collision list from scratch than to send a copy of it over the Internet. So the key is in the filtering -- the -filt parameter in gencols, or other analogous parameters to describe the target output in other search utilities. Generally the hard part is figuring out how to reliably separate interesting results from boring ones, algorithmically instead of by inspection... though in some cases maybe the manual inspection could be distributed as well, come to think of it!

Anyway, there are certainly some interesting possibilities for distributed versions all these utilities, but I don't think any of them would allow for a really quick and easy conversion. In some cases it might not be _too_ difficult -- lifesrc and ptbsearch might be good candidates to look at.

One idea might be to define a sequence of increasingly time-consuming search problems, where the first search in the sequence is narrow enough that it will fail quickly -- but the last search is guaranteed to succeed, except it would take too long to run it. Farming out these searches to client utilities in rough order of difficulty might help zero in on minimal solutions to various problems.

For example, suppose you're looking for a p8 or p9 pipsquirter, which would look similar to the p6 or p7 versions, but would take a few ticks longer to recover. You might start by defining, say, an 8x8 square of "unknown" cells in lifesrc, with the key domino-spark reaction at one edge. That's probably too small a space to sustain a p8 or p9 domino spark, so the first search will fail quickly and return "no solution" to the server. The server would then send out the next search in the sequence -- an 8x8 square plus one more unknown cell, perhaps. Then two extra unknown cells, and so on. The order in which to add new cells around the boundary of the "unknown" area is an important detail; you'd probably want to maintain a roughly circular or octagonal shape, all other things being equal, since corners are an invitation for lifesrc to find lots of trivially equivalent solutions...

Eventually either a solution would be found, or (probably more likely, in most cases) the searches would start taking an unreasonable amount of time to return a no-solution result. In that case, well, at least we'd know exactly where the limits were for that type of search, and can maybe pick up the search again after Moore's Law has had another few years to speed things up.

Anyone have better suggestions for coming up with an interesting distributable search sequence for any of these utilities?

[Paul Tooke]

Nathaniel wrote:

I haven't used gencols myself, so forgive my ignorance -- is it the type of thing that would benefit from a distributed search setup? That is, would it be a reasonable modification to make to have a downloadable executable file for people to run and have it automatically choose some particular search to perform and then upload the results of the search? Or is it the type of thing where search parameters have to be chosen fairly carefully by the user to produce anything interesting?

Dave Greene has answered this fairly comprehensively. I have just a couple of thoughts to add:

I'm not sure that Gencols is an ideal candidate for this. Dave has already listed some of the reasons. Yes, Gencols is a tricky program to work with and you do need to select search parameters carefully. Furthermore, its search space is a bit nebulous. It just collides things together and filters the results. Why would one want to do this? I think the principal difficulty with a distributed search would be establishing what searches to perform.

One candidate for distributed search that Dave didn't mention is gfind. This has a more clearly defined objective than gencols and is particularly suited to distributed search because it is based on searching a tree. Separate branches of the tree can be searched independently and many will be eliminated very quickly. In most searches there will be just a few branches that take up most of the search time. These can be further subdivided into separate searches. The drawbacks are that there is the potential for a runaway proliferation of searches and that writing the client/server portions of the search would mean a fair amount of work for someone.

[dvgrn]

I think the principal difficulty with a distributed search would be establishing what searches to perform... there is the potential for a runaway proliferation of searches...

Agreed. For any of these search utilities, if the server automatically generates new searches to try, it's eventually likely to wander off into search spaces larger than the visible universe, and no useful results will ever come back.

This isn't necessarily an insurmountable problem. There are several search spaces where an expert could manually generate in advance enough sets of "interesting" search parameters to stay ahead of a distributed search indefinitely (or until a solution was actually found.) If the list of untested parameter sets start to run short, it would be easy enough to add a new set of somewhat more difficult search problems.

One case I'm thinking of in particular is a 'catalyst' / 'ptbsearch' search for catalyzed signal reactions. Almost ten years ago now I cobbled together a version of Gabriel Nivasch's 'catalyst' with some additional output filters that might make it more amenable to distributed searching. I called it 'catgl' because it caught and counted output gliders, as well as printing an extra 'matched!" message when an output matched an optional target filter.

Here's a sample of the size of message that a distributed client/server system might send back and forth -- this is a reformatted version of the actual batch-file input to 'catgl':

Code: Select all

y,3,7,0,
75,250
49
3
78,85,86
./
../
///
.
.
.
........00000
........01100
........01010
........00100
........00000!

Explanation of the 'catgl' input data above:

- use the G+Boat = B-heptomino base reaction:
x = 12, y = 10, rule = B3/S23
bo$2bo$3o5$9b2o$9bobo$10bo!
- collide a glider ('/' = shouldn't exist in the output)
with a boat ('1' = must exist in the output, and
- '0' = must be OFF in the output.)
- Use only catalysts #3 and #7,
- search the space between 75 and 250 ticks,
- pattern must survive at least 49 ticks after catalyst placement,
- maximum number of catalysts to be placed is 3,
- resume search at the point where
1st catalyst reacts at T=78,
2nd catalyst reacts at T=85,
3rd catalyst reacts at T=85

Clients could be set to run a search for a relatively short amount of time -- ten or fifteen minutes, maybe? -- and then if no match is found, return a new partial search result to the server. For example, in ten minutes the search might have reached "79,90,91" instead of "78,85,86" -- that new string is all that would have to be sent back, since all the other parameters would remain the same.

------------------------

However, a distributed search utility that actually uses this 'catgl' code base is going to be fairly limited, because the catalyst definitions don't allow for transparent reactions -- you can work around this only to a very limited extent, as in the transparent-boat search shown above. Transparent reaction play a role in a fairly large fraction of the useful signal reactions that have been found so far. So it would probably be better to start with something along the lines of Paul Callahan's 'ptbsearch' instead. The messages between the client and server wouldn't have to change much from what's shown above.

A distributed system like this could be used to search for things like new Herschel conduits and converters -- glider outputs on different lanes, direct constructions of various still lifes or even *WSS spaceships. It would also give us a fresh shot at finding a small stable 90-degree reflector, for which the prize has been going begging for almost a decade now. If I were doing any of the programming on this project, I would definitely use $thimbles & care() ...

Keep the cheer,


Dave Greene

[calcyman]

If I may interject at this point, ptbsearch is another depth-first tree search. By using a pre- and post-processor, ptbsearch can be enginnered into a generic search program for finding stable reflectors. And since Dave Greene has offered $100 of prizes for compact stable reflectors, it may be worthwhile to distribute a search of this type.

My attempts at writing a ptbsearch/catalyst program from scratch have been unsuccessful, for some reason. Maybe I should try again, and then integrate FTP support to enable the program to download tasks and upload results. (Mainly to Dave: this is the technique I used for uploading highscores and customised levels in Atomtrap.)


By the way, Moore's Law is not the panacea for large computational problems. Generally, an improved algorithm (such as reducing O(n²) to O(n log n)) is preferable, as it reduces the computational complexity, rather than simply reducing the timescale by a constant factor.

For example, in multi-catalyst searches, such as ptbsearch, there are factorials caused by the various ways of permuting the catalysts. In a 5-catalyst search, for instance, permuting the catalysts would multiply the timescale by a factor of 120. Admittedly, you could use Moore's Law over a decade to compensate for that, but a superior algorithm is a better option.



Dave Greene has mentioned distributed searches before, on his web-blog (http://b3s23life.blogspot.com). He considered a hashing approach, to remove redundant computations. For example, browsing through a ptbsearch/catalyst output, there are lots of similar results where gliders are concerned, with eaters in slightly different positions and so forth. This is especially problematic when there are two radiated gliders: there is now an O(t²) overhead. And with three radiated gliders, this increases to O(t³).

Dave's hashing idea, if it can be made to work, would reduce these mutli-glider problems from O(t^N) to O(Nt), where t is the time in generations, and N is the number of gliders. Here, 'gliders' can refer to other spaceships (only *WSSes, and switch engines if you are especially fortunate, are likely to appear naturally) or travelling propagations.



As for implementing a distributed search, I have a few ideas. The search begins on the 'root computer' (could be a server), and begins progressing through the tree. When another computer (a client) connects to the root computer, a branch of the search is transferred from the root computer to the other computer (this could be split exactly in half, or weighted according to the relative processing power/RAM of the machines). These computers can also share their workload to other computers, so the structure resembles a tree, mirroring that of the search.

What is essential for such a search is a heuristic -- the search needs to know when it is spending a lot of time on a particular branch, and thus be able to estimate the size of the branch. In general, when a new client connects to the server, it should be allocated to the computer with the highest heuristic; this will have the effect of splitting the largest branches. This is a type of minimax problem -- you have to minimise the maximum branch size.

[Ntsimp]

The modified version has a bug in the "-filt" option, confusing one parameter for another. My knowledge of C is pretty rudimentary, but I'm trying to find the problem.

[Paul Tooke]

Ntsimp wrote:

The modified version has a bug in the "-filt" option

Can you describe the symptoms?

[dvgrn]

If I may interject at this point, ptbsearch is another depth-first tree search. By using a pre- and post-processor, ptbsearch can be engineered into a generic search program for finding stable reflectors. And since Dave Greene has offered $100 of prizes for compact stable reflectors, it may be worthwhile to distribute a search of this type.

That depends on how you define "worthwhile"; it probably wouldn't end up paying too well in dollars per hour, especially if you have to distribute the prize as well as the computation...

However, there would be the great satisfaction of solving a problem that's on the same list as the Riemann Hypothesis -- at least if you're looking on the mathpuzzle.com Prizes Page! http://mathpuzzle.com/prizes.html . The Snark (small 90-degree stable reflector) is higher on the list than the Riemann Hypothesis, in fact... and the prize amount is exactly the same, give or take four orders of magnitude.

My attempts at writing a ptbsearch/catalyst program from scratch have been unsuccessful, for some reason. Maybe I should try again, and then integrate FTP support to enable the program to download tasks and upload results. (Mainly to Dave: this is the technique I used for uploading highscores and customised levels in Atomtrap.)

Actually I'm kind of hoping some of the infrastructure for the Online Soup Search on conwaylife.com can be reused for other projects. Nathaniel, what could you use in the way of a client program -- would a C++ command-line utility be workable? Say it used stdin or a text file as input, and wrote its partial results to stdout; maybe a small Python wrapper script could take care of the rest -- the authentication and communication and so forth. Not sure about running searches on multiple platforms, but it won't be a problem for a good while; the early stages of vaporware are extraordinarily portable.

On the server side, it might be good to have a visible list of searches currently in process or waiting to be started -- maybe eventually people could add new searches to the back of this queue, using a separate Golly script.

[Ntsimp]

Ntsimp wrote:

The modified version has a bug in the "-filt" option

Can you describe the symptoms?

For example, I'm looking at 3-glider collisions in B36/S235, some of which produce a pair of blinkers. Without -filt the program finds these. With -filt 2 or -filt p it doesn't, but with -filt a it does. In fact, I haven't been able to get -filt 234 or -filt p to give any results with any pattern or rule at all, and -filt 1 finds only patterns that annihilate completely.

[Paul Tooke]

Ntsimp:
Has anyone mentioned that Gencols is a bit tricky?
You had me worried that I may have broken something in the filtering code. I don't recall ever touching this code so I went back to check.
The pattern filtering code appears in the outputpattern() function in output.c. Here is the appropriate section taken directly from a copy of the original shell archive that Jason Summers has on his web site:

Code: Select all

            if (removefailed && !strchr(filterstring,'f') ) return; 
            if (per== -1 && !strchr(filterstring,'n') ) return; 
            if (per>MAXOSCTEST && !strchr(filterstring,'a') ) return;
            if (per>=1 && per <=4 && !strchr(filterstring,'p') && 
                !strchr(filterstring,'0'+per)
                && (maxmove!=1 || !strchr(filterstring,'g'))
                && (maxmove!=2 || !strchr(filterstring,'s'))) return;

.. and here it is from my source file:

Code: Select all

	if (removefailed && !strchr(filterstring,'f') ) return; 
	if (per== -1 && !strchr(filterstring,'n') ) return; 
	if (per>MAXOSCTEST && !strchr(filterstring,'a') ) return;
	if (per>=1 && per <=4 && !strchr(filterstring,'p') && 
		!strchr(filterstring,'0'+per)
		&& (maxmove!=1 || !strchr(filterstring,'g'))
		&& (maxmove!=2 || !strchr(filterstring,'s'))) return;

Spot any differences other than the tab spacing? I can't. That last 'if' is a bit tricky. My decoding of it is this:

Code: Select all

	if ( the entire result is periodic and of period 1 to 4)
	and (p wasn't in the filter string)
	and (the specified period wasn't in the filter string)
	and (the pattern doesn't move by one cell or 'g' wasn't in the filter string)
	and (the pattern doesn't move by two cells or 's' wasn't in the filter string)
	then
		reject the collision

Note that including 'p' in the filter string should cause the second part of the test to fail, leading to the pattern being output.
Likewise including the period in the filter string should cause the third part of the test to fail.

Were those two blinkers the only things that resulted from the collision? Filtering is applied to the entire result of the collision, not individual components. If the result consists only of blinkers, then filt -p or filt -2 ought to work. Try running one of these collisions to check how many generations elapse before the pattern becomes p2. How does that compare to the argument you specified for the '-gen' parameter? If the collision takes longer to settle down than you specified, the filtering won't work properly.

[Ntsimp]

Like I say, my C knowledge isn't what it should be. I haven't found the bug in the source code yet, but it's definitely a bug.

Using the same options in both yours and the original should give the same results, right? Here's one from the Examples script included with the original:
gencols -pat obj/glider_ne.life obj/glider_nw.life -nph 4 -tc 10 13 -gen 51 -leq 24 -geq 1 -filt 12
The original version outputs 35 results, and the modified one none.

By the way, I haven't properly thanked you yet, Paul. Thanks so much for this code! I've been doing some collisions like this manually in other rules for a while, and this program saves much much effort.

[Paul Tooke]

Ntsimp wrote:

it's definitely a bug

Yes
and:

Using the same options in both yours and the original should give the same results, right? Here's one from the Examples script included with the original:
gencols -pat obj/glider_ne.life obj/glider_nw.life -nph 4 -tc 10 13 -gen 51 -leq 24 -geq 1 -filt 12
The original version outputs 35 results, and the modified one none.

Thanks. A specific test case is a great help in debugging. Yes, you are right, the two should behave identically in the Life rule. Using this test case helped to narrow things down to the offending function quite quickly. In reformatting lists.c I must have inadvertantly deleted a "!" character in the function that compares patterns. This was causing the periodicity matching to fail. I never spotted this because I've never used gencols to look for periodic patterns. I have now uploaded a revised version with the "!" restored to its rightful place. This version now gives the same results as the original, but in both cases I get 36 results (is there a chance that you miscounted?):

Code: Select all

x = 479, y = 82, rule = S23/B3
b2o40b2o7b2o40b2o32b2o6b2o41b2o32b2o50b2o32b2o50b2o31b2o48b2o
41b2o$obo39bobo7bobo39bobo30bobo6bobo40bobo30bobo50bobo30bobo
41b2o6b2o31bobo7b2o38b2o41b2o$2bo41bo7bo41bo34bo6bo42bo34bo50b
o34bo40bobo8bo32bo6b2o41bo31b2o9bo$9b2o75b2o82b2o50b2o119bo50b
o71bobo$9bobo73bobo81bobo50bobo31b2o50b2o116b2o40bo$9bo77bo83b
o50bo32bobo50bobo114bobo$257bo50bo118bo31$b2o41b2o49b3o39b3o31b
2o6b3o31b2o40b2o40b2o47b3o31b2o47b3o31b2o7b3o$obo40bobo49bo33b
2o6bo32bobo6bo32bobo6b3o30bobo39bobo47bo32bobo47bo32bobo7bo$2b
o8b2o32bo41b2o7bo31bobo7bo33bo7bo33bo6bo34bo41bo48bo33bo38b2o
8bo33bo8bo$10b2o42b2o30bobo41bo91bo40b3o72b2o79bobo$12bo40b2o
33bo174bo73bobo81bo$55bo208bo39b3o32bo46b3o$304bo81bo$305bo81b
o31$b2o41b2o41b2o49b3o31b2o48b3o40bo41bo32b2o50bo32b2o41b2o$o
bo7b3o30bobo40bobo49bo32bobo48bo41b2o40b2o31bobo40b2o7b2o31bo
bo8bo31bobo$2bo7bo34bo7b3o32bo50bo33bo49bo40bobo31b2o6bobo32b
o7bo31bobo7bobo32bo7b2o33bo$11bo41bo42b3o157b2o39bobo48b2o33b
o50bobo$54bo41bo33b2o49b3o31b2o38bobo41bo48bobo126bo$97bo31bo
bo49bo32bobo40bo218b2o$131bo50bo33bo259bobo$!

Thanks so much for this code! I've been doing some collisions like this manually in other rules for a while, and this program saves much much effort.

Glad to help. I would say that is worthwhile spending some time to learn C/C++ or a similar programming language. Life hacking is a bit of a programmers sport because the time spent on putting together a program to do a task is repaid back many times over in terms of the amount of manual labour it saves. Some tasks, finding "unnatural" spaceships for example, are pretty much impossible to do manually. In these cases writing a program or script is the only way to get the job done. It doesn't have to be C or C++, I only mention these because they are fast and consequently much of the code that has been published on the web was written in them. If someone has published a program that does 99% of what you want to do, then it is handy being able to add the last 1%. This of course, is the whole point behind this topic.

[Nathaniel]

Nathaniel, what could you use in the way of a client program -- would a C++ command-line utility be workable? Say it used stdin or a text file as input, and wrote its partial results to stdout; maybe a small Python wrapper script could take care of the rest -- the authentication and communication and so forth. Not sure about running searches on multiple platforms, but it won't be a problem for a good while; the early stages of vaporware are extraordinarily portable.

Sorry for the late reply to this. Pretty much anything can be used as the front-end. All that matters is that it is capable of hashing data and uploading that data to the internet (and I can't think of a language that can't do that). The upload/authentication stuff that the client does for the soup search is pretty basic:

1. Compute a (salted) hash of data to be uploaded.

2. Send the data and the hash to the server via a POST request.

The hash is then re-computed on the server, and if it matches then the data is processed and added to the database.

[David]

Gencols is a C program, and translating it to Python would only reduce the speed (and significantly so).

But I REALLY need python script! I don't have C/C++ compiller and I can't use it!

[codeholic]

There are some modifications I made to the original gencols code, while working on the glider synthesis for the Snark.

https://github.com/codeholic/gencols

The most important is an ability to filter resulting patterns not only by alive cells (using "-test1" and "-test2" command line options), but also by dead cells (with "-mask1" and "-mask2" accordingly).

Other minor additions are sequence numbers of initial patterns and their phases in the outcome, which makes it much easier to identify which patterns were collided, and printing sequence numbers of initial patterns on stderr, which gives some understanding of the progress, if it takes some time.