Guam's CollisionsSearch utility

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Guam's CollisionsSearch utility

Post by dvgrn » June 6th, 2016, 12:22 pm

This announcement has been a painfully long time in coming. I owe an apology or two to Guam, who some time ago kindly supplied me with the full source code and impressively complete operating instructions for his search utility. This is the program that found the semi-Snark in 2013, along with an unprecedented number (at the time!) of new Herschel conduits. It's a Windows-only utility at the moment -- a compiled Delphi program, same as the grand old pre-Golly CA simulator/editors Life32 and Mirek's Cellebration.

The documentation included versions in Russian and in English, and I volunteered to clean up the English documentation before posting the whole package publicly.

This was back toward the end of last year, just as I started a new job, and also decided to attempt a tenth-anniversary update of the Life Lexicon... which I can now finally get back to again. I've been expecting to find time to finish that promised documentation work, every week for some months now.

-- Well, the CollisionsSearch documentation may still not really be done, but at this point I should let someone else proofread my proofreading job, and get this search utility out into the hands of people who will actually try it out!
CollisionsSearch v.0.1a_with_updated_docs_6-6-2016.zip
Guam's CollisionsSearch utility with updated documentation -- 6 June 2016
(1.94 MiB) Downloaded 629 times
CollisionsSearch has an impressive GUI, and should be particularly useful for finding Spartan constructs. Or near-Spartan constructible circuitry, anyway. The basic algorithm seems to be along the lines of CatForce, but with a lot of useful options for adding limitations to allow a deeper exploration of the search space.

Disclaimer: I haven't actually attempted to run many searches with the program yet, myself. So I've included the original Word-document version of the English documentation, as well as Word and PDF versions of my re-translations, in case I've missed the mark with some of my re-wording attempts.

If anyone has trouble downloading or extracting the embedded .exe files in the attached ZIP, let me know and I'll see if I can work out an alternate delivery mechanism. Questions, comments, documentation bug reports, search results, and project files for successful or unsuccessful searches are all appreciated. If I make any new changes to the docs I'll update the date stamp in the ZIP filename.

Happy hunting!

User avatar
simsim314
Posts: 1823
Joined: February 10th, 2014, 1:27 pm

Re: Guam's CollisionsSearch utility

Post by simsim314 » June 6th, 2016, 3:22 pm

Hey Dave thx a lot for the effort! Guams search utility was long waited utility, missing from the collective knowledge that brought us some new conduits, so this is really great.

Looking at it at the first glance - I kinda miss some simple 3-4 steps tutorial, on how to use the examples, where to look in the GUI, and where the results are shown. Everything immediately looks very technical and overwhelmingly detailed. I guess I can figure it out, but some simple - step by step guide for basic usage of examples would be very helpful.

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Guam's CollisionsSearch utility

Post by dvgrn » June 6th, 2016, 5:42 pm

simsim314 wrote:Looking at it at the first glance - I kinda miss some simple 3-4 steps tutorial, on how to use the examples, where to look in the GUI, and where the results are shown. Everything immediately looks very technical and overwhelmingly detailed. I guess I can figure it out, but some simple - step by step guide for basic usage of examples would be very helpful.
That's certainly a good idea. A good place to start might be in Section 1.5 of Help_en_CollisionsSearch.pdf, which gives examples of different ways to fill out the two key tables, "Initial filling" and "final filling".

-- Just by the way, a better translation of those table names would probably be along the lines of "Initial conditions" and "Target conditions" -- but changing the GUI is not an option without recompiling the Delphi 7 source code, so I think we can live with "Initial filling" and "Final filling" for the time being.

Just did a first successful search using a pre-packaged example. Maybe there's at least some advantage to having gone through all the documentation. Here's a quick walkthrough:

1) Run CollisionsSearch, and in the Examples folder, open example_B_J.txt.
2) Interpret the Initial and Final tables according to the documentation. Here's my translation:

Initial: start with...
  • block @(4,7)
  • beehive orientation 0 @ (21,0)
  • B-heptomino orientation 0 2 (0,7)
  • any stable pattern that fits in a 5x3 box (no snakes allowed) anywhere in the rectangle (-15,-4)-(19,23).
Final: looking for...
  • block from first line of previous table must survive in same location
  • beehive from second line must survive in same location
  • stable pattern from fourth line must survive in same location
  • a new block must appear @(26,5)
  • the reaction must produce its result between T=79 and T=150
Click the Start button and the program will start to check 49,980 cases, looking for one that produces a block at that specific location.

When the search is done, the program will have found and reported two solutions -- at least if the "Immediately save solutions to a file" box is checked (but I think all the same files are created at the end if that checkbox is unchecked.) Look in the Temp folder to find the two .lif files.

The two files contain identical patterns. I don't know exactly why that is, or how to filter out one of the two, but it looks like one result is reported when the target block first appears, and one result is saying "the block is still here indefinitely". Don't know why the filename seems to be reporting T=144 rather than T=150.

If you load the example_B_J.txt project file in the CollisionsExporter utility, you can display the two solutions and run them in the lower right display pane, to confirm that a block really does appear in the right position.

The example_B_J2.txt project appears to run the exact same search, but the initial block and eater have been combined into a pattern file called example_B_J.lif.

The Rule line of that pattern file is a bit puzzling, by the way -- it looks like a file copied out of the old MCell program, with a three-state rule applied that's something along the lines of HistoricalLife (the predecessor to LifeHistory). But I don't think it's HistoricalLife, because Golly can recognize that specific rule string.

The example_stab1.txt project file seems relatively straightforward -- look at stab1.lif, and don't be confused by the fact that the 'o' cells are actually undefined cells, and the '*' cells are the live ones (!).

The search problem amounts to "find a combination of cells in a 2x4 rectangle that will be stable in the presence of a domino spark to the right." I don't understand why the CollisionsExporter sometimes shows the block-on-table solution with the block in the northeast, though. It seems like both of the actual solutions have the block in the southeast, where it seems to be long based on stab1.lif.

If someone else can post a walkthrough of example.txt (the project shown in the documentation screenshots) that might be good. There are 33,000+ possibilities to test, and CollisionsSearch finds 104 solutions. It doesn't seem like a very comprehensible search, though there are some things to learn about overlapping still lifes and the Sift the superposition setting.

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

My next attempt will involve a very simple new search, to make sure I understand how to set this kind of thing up. It will probably be something like a rediscovery of the semi-Snark, at first with a very small search space that specifies object types and rough locations, and then with progressively larger spaces. Then maybe I'll try to write a single search that finds both the R64 and the Bx60 conduit (and anything else that's out there with just four blocks in a small area).

This may or may not happen in the next week, since I have a lot of other things to catch up on -- that was a lot of documentation to update! If anyone else gets around to any of this first, please publish the project files and any details that seem to need better explanation.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Guam's CollisionsSearch utility

Post by wildmyron » November 19th, 2016, 10:15 am

dvgrn wrote:My next attempt will involve a very simple new search, to make sure I understand how to set this kind of thing up. It will probably be something like a rediscovery of the semi-Snark, at first with a very small search space that specifies object types and rough locations, and then with progressively larger spaces. Then maybe I'll try to write a single search that finds both the R64 and the Bx60 conduit (and anything else that's out there with just four blocks in a small area).
Attached is a project which finds the Bx60 and R64. I'm not sure that the approach of trying to place four blocks at once is viable in any realistic search, and this is evident in the constrained regions set up for individual blocks. There are many solutions found containing the B60 as the fourth block is readily placed in it's region without interacting in any way. No other three or four block solutions were found.

The steps required to set up the search from default parameters are:
  • Change steps range to 40 - 100 (the larger this range the longer each configuration tales to check)
  • Under 'Find the objects in final filling' select 'in each spep' (should be 'in each step')
  • Optionally adjust Renewal period and Saving period
  • Optionally select 'Immediately save solutions to a file' (though there are 86 so exporting them when the search is complete might be a better idea)
  • Add objects to Initial filling
    • Herschel at (0,0)
    • Block within (6,-12) -> (11,-6)
    • Block within (9,-11) -> (17,-5)
    • Block within (9,-11) -> (17,-5)
    • Block within (16,-5) -> (21,1) (Shifted down so that the R64 is found early-ish in the search)
  • Add objects to Final filling
    • A herschel or other interesting output anywhere on the grid
    • Object 2, unmoved (StartX and StartY should be set to 0, else the criteria won't be applied)
    • Object 3, unmoved
    • Object 4, unmoved
    • Object 5, unmoved
It's not clear to me how the 'Period of stabilized pattern' parameter affects this search (I left it at 6), nor how large the impact of 'Sift the superposition' is on the search time due to configurations with overlapping blocks being discarded.

As it is both conduits were found during the first hour of the search and the total search time was about 2.5 hours. I found that when adding other options to the objects to be placed particularly hives) there were more solutions given which had an H, B, or Pi output along with a largish ongoing reaction. These can be rejected by limiting the 'Number of cells' to < N for some suitable value of N. I'm sure that you more experienced conduit finders know other suitable tricks.

Reducing the number of simultaneous blocks to three is much more manageable and quite a large area can be specified for all three blocks before the run time becomes days long.

Out of curiosity I decided to try my hand at making something of this transparent hive

Code: Select all

x = 8, y = 15, rule = LifeHistory
6.A$5.A.A$5.A.A$6.A8$A$A.A$3A$2.A!
I didn't notice it in the 2015 Conduit Collection, nor did I find the outcome of other peoples attempts though I'm sure they're somewhere to be found. In any case, this is the farthest I got and while there's some potential to keep things going and plenty of alternatives to this partial conduit, I fear it's pretty hopeless.

Code: Select all

x = 27, y = 32, rule = LifeHistory
7.A$6.A.A$6.A.A$7.A4$26.A$24.3A$23.A$24.A$.A21.2A$.A.A$.3A$3.A3$19.2A
$19.2A4$17.2A$17.A.A$19.A$19.2A3$2.2A$3.A$3A$A!
Attachments
H-4_blocks.txt
4 block H conduit search
(411 Bytes) Downloaded 423 times
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

Post Reply